1/* $NetBSD: ntp_prio_q.c,v 1.5 2020/05/25 20:47:25 christos Exp $ */ 2 3/* ntp_prio_q.c 4 * 5 * This file contains the priority queue implementation used by the 6 * discrete event simulator. 7 * 8 * Written By: Sachin Kamboj 9 * University of Delaware 10 * Newark, DE 19711 11 * Copyright (c) 2006 12 */ 13#ifdef HAVE_CONFIG_H 14# include <config.h> 15#endif 16 17#include <ntp_stdlib.h> 18#include <ntp_prio_q.h> 19 20/* Priority Queue 21 * -------------- 22 * Define a priority queue in which the relative priority of the elements 23 * is determined by a function 'get_order' which is supplied to the 24 * priority_queue 25 */ 26queue *debug_create_priority_queue( 27 q_order_func get_order 28#ifdef _CRTDBG_MAP_ALLOC 29 , const char * sourcefile 30 , int line_num 31#endif 32 ) 33{ 34 queue *my_queue; 35 36#ifndef _CRTDBG_MAP_ALLOC 37 my_queue = emalloc(sizeof(queue)); 38#else 39 /* preserve original callsite __FILE__ and __LINE__ for leak report */ 40 my_queue = debug_erealloc(NULL, sizeof(queue), sourcefile, line_num); 41#endif 42 my_queue->get_order = get_order; 43 my_queue->front = NULL; 44 my_queue->no_of_elements = 0; 45 46 return my_queue; 47} 48 49 50/* Define a function to "destroy" a priority queue, freeing-up 51 * all the allocated resources in the process 52 */ 53 54void destroy_queue( 55 queue *my_queue 56 ) 57{ 58 node *temp = NULL; 59 60 /* Empty out the queue elements if they are not already empty */ 61 while (my_queue->front != NULL) { 62 temp = my_queue->front; 63 my_queue->front = my_queue->front->node_next; 64 free(temp); 65 } 66 67 /* Now free the queue */ 68 free(my_queue); 69} 70 71 72/* Define a function to allocate memory for one element 73 * of the queue. The allocated memory consists of size 74 * bytes plus the number of bytes needed for bookkeeping 75 */ 76 77void *debug_get_node( 78 size_t size 79#ifdef _CRTDBG_MAP_ALLOC 80 , const char * sourcefile 81 , int line_num 82#endif 83 ) 84{ 85 node *new_node; 86 87#ifndef _CRTDBG_MAP_ALLOC 88 new_node = emalloc(sizeof(*new_node) + size); 89#else 90 new_node = debug_erealloc(NULL, sizeof(*new_node) + size, 91 sourcefile, line_num); 92#endif 93 new_node->node_next = NULL; 94 95 return new_node + 1; 96} 97 98/* Define a function to free the allocated memory for a queue node */ 99void free_node( 100 void *my_node 101 ) 102{ 103 node *old_node = my_node; 104 105 free(old_node - 1); 106} 107 108 109void * 110next_node( 111 void *pv 112 ) 113{ 114 node *pn; 115 116 pn = pv; 117 pn--; 118 119 if (pn->node_next == NULL) 120 return NULL; 121 122 return pn->node_next + 1; 123} 124 125 126/* Define a function to check if the queue is empty. */ 127int empty( 128 queue *my_queue 129 ) 130{ 131 return (!my_queue || !my_queue->front); 132} 133 134 135void * 136queue_head( 137 queue *q 138 ) 139{ 140 if (NULL == q || NULL == q->front) 141 return NULL; 142 143 return q->front + 1; 144} 145 146 147/* Define a function to add an element to the priority queue. 148 * The element is added according to its priority - 149 * relative priority is given by the get_order function 150 */ 151queue *enqueue( 152 queue * my_queue, 153 void * my_node 154 ) 155{ 156 node *new_node = (node *)my_node - 1; 157 node *i = NULL; 158 node *j = my_queue->front; 159 160 while (j != NULL && 161 (*my_queue->get_order)(new_node + 1, j + 1) > 0) { 162 i = j; 163 j = j->node_next; 164 } 165 166 if (i == NULL) { /* Insert at beginning of the queue */ 167 new_node->node_next = my_queue->front; 168 my_queue->front = new_node; 169 } else { /* Insert Elsewhere, including the end */ 170 new_node->node_next = i->node_next; 171 i->node_next = new_node; 172 } 173 174 ++my_queue->no_of_elements; 175 return my_queue; 176} 177 178 179/* Define a function to dequeue the first element from the priority 180 * queue and return it 181 */ 182void *dequeue( 183 queue *my_queue 184 ) 185{ 186 node *my_node = my_queue->front; 187 188 if (my_node != NULL) { 189 my_queue->front = my_node->node_next; 190 --my_queue->no_of_elements; 191 return my_node + 1; 192 } else 193 return NULL; 194} 195 196 197/* Define a function that returns the number of elements in the 198 * priority queue 199 */ 200int get_no_of_elements( 201 queue *my_queue 202 ) 203{ 204 return my_queue->no_of_elements; 205} 206 207 208/* Define a function to append a queue onto another. 209 * Note: there is a faster way (O(1) as opposed to O(n)) 210 * to do this for simple (FIFO) queues, but we can't rely on 211 * that for priority queues. (Given the current representation) 212 * 213 * I don't anticipate this to be a problem. If it does turn 214 * out to be a bottleneck, I will consider replacing the 215 * current implementation with a binomial or fibonacci heap. 216 */ 217void append_queue( 218 queue *q1, 219 queue *q2 220 ) 221{ 222 while (!empty(q2)) 223 enqueue(q1, dequeue(q2)); 224 destroy_queue(q2); 225} 226 227 228/* FIFO Queue 229 * ---------- 230 * Use the priority queue to create a traditional FIFO queue. 231 * The only extra function needed is the create_queue 232 */ 233 234/* C is not Lisp and does not allow anonymous lambda functions :-(. 235 * So define a get_fifo_order function here 236 */ 237int get_fifo_order(const void *el1, const void *el2) 238{ 239 return 1; 240} 241