xref: /netbsd-src/external/bsd/ntp/dist/ntpd/ntp_prio_q.c (revision cdfa2a7ef92791ba9db70a584a1d904730e6fb46)
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