xref: /freebsd/contrib/ntp/ntpd/ntp_prio_q.c (revision bdd1243df58e60e85101c09001d9812a789b6bc4)
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