1 /* $NetBSD: ntp_prio_q.c,v 1.1.1.1 2013/12/27 23:30:58 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 */ 26 queue *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 54 void 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 77 void *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 */ 99 void free_node( 100 void *my_node 101 ) 102 { 103 node *old_node = my_node; 104 105 free(old_node - 1); 106 } 107 108 109 void * 110 next_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. */ 127 int empty( 128 queue *my_queue 129 ) 130 { 131 return (!my_queue || !my_queue->front); 132 } 133 134 135 void * 136 queue_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 */ 151 queue *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 */ 182 void *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 */ 200 int 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 */ 217 void 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 */ 237 int get_fifo_order(const void *el1, const void *el2) 238 { 239 return 1; 240 } 241