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