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