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 */
debug_create_priority_queue(q_order_func get_order,const char * sourcefile,int line_num)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
destroy_queue(queue * my_queue)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
debug_get_node(size_t size,const char * sourcefile,int line_num)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 */
free_node(void * my_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 *
next_node(void * pv)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. */
empty(queue * my_queue)125 int empty(
126 queue *my_queue
127 )
128 {
129 return (!my_queue || !my_queue->front);
130 }
131
132
133 void *
queue_head(queue * q)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 */
enqueue(queue * my_queue,void * my_node)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 */
dequeue(queue * my_queue)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 */
get_no_of_elements(queue * my_queue)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 */
append_queue(queue * q1,queue * q2)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 */
get_fifo_order(const void * el1,const void * el2)235 int get_fifo_order(const void *el1, const void *el2)
236 {
237 return 1;
238 }
239