3 * This file contains the priority queue implementation used by the
4 * discrete event simulator.
6 * Written By: Sachin Kamboj
7 * University of Delaware
15 #include <ntp_stdlib.h>
16 #include <ntp_prio_q.h>
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
24 queue *debug_create_priority_queue(
25 q_order_func get_order
26 #ifdef _CRTDBG_MAP_ALLOC
27 , const char * sourcefile
34 #ifndef _CRTDBG_MAP_ALLOC
35 my_queue = emalloc(sizeof(queue));
37 /* preserve original callsite __FILE__ and __LINE__ for leak report */
38 my_queue = debug_erealloc(NULL, sizeof(queue), sourcefile, line_num);
40 my_queue->get_order = get_order;
41 my_queue->front = NULL;
42 my_queue->no_of_elements = 0;
48 /* Define a function to "destroy" a priority queue, freeing-up
49 * all the allocated resources in the process
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;
65 /* Now free the queue */
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
77 #ifdef _CRTDBG_MAP_ALLOC
78 , const char * sourcefile
85 #ifndef _CRTDBG_MAP_ALLOC
86 new_node = emalloc(sizeof(*new_node) + size);
88 new_node = debug_erealloc(NULL, sizeof(*new_node) + size,
89 sourcefile, line_num);
91 new_node->node_next = NULL;
96 /* Define a function to free the allocated memory for a queue node */
101 node *old_node = my_node;
117 if (pn->node_next == NULL)
120 return pn->node_next + 1;
124 /* Define a function to check if the queue is empty. */
129 return (!my_queue || !my_queue->front);
138 if (NULL == q || NULL == q->front)
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
154 node *new_node = (node *)my_node - 1;
156 node *j = my_queue->front;
159 (*my_queue->get_order)(new_node + 1, j + 1) > 0) {
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;
172 ++my_queue->no_of_elements;
177 /* Define a function to dequeue the first element from the priority
178 * queue and return it
184 node *my_node = my_queue->front;
186 if (my_node != NULL) {
187 my_queue->front = my_node->node_next;
188 --my_queue->no_of_elements;
195 /* Define a function that returns the number of elements in the
198 int get_no_of_elements(
202 return my_queue->no_of_elements;
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)
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.
221 enqueue(q1, dequeue(q2));
228 * Use the priority queue to create a traditional FIFO queue.
229 * The only extra function needed is the create_queue
232 /* C is not Lisp and does not allow anonymous lambda functions :-(.
233 * So define a get_fifo_order function here
235 int get_fifo_order(const void *el1, const void *el2)