ntp/ntpd/ntp_prio_q.c

3  * This file contains the priority queue implementation used by the
6  * Written By:	Sachin Kamboj
7  *		University of Delaware
8  *		Newark, DE 19711
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
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 */
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
96 /* Define a function to free the allocated memory for a queue node */
109 	void *pv
112 	node *pn;
114 	pn = pv;
115 	pn--;
117 	if (pn->node_next == NULL)
120 	return pn->node_next + 1;
124 /* Define a function to check if the queue is empty. */
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
164 	if (i == NULL) {	/* Insert at beginning of the queue */
177 /* Define a function to dequeue the first element from the priority
178  * queue and return it
186 	if (my_node != NULL) {
195 /* Define a function that returns the number of elements in the
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
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.
216 	queue *q1,
217 	queue *q2
220 	while (!empty(q2))
221 		enqueue(q1, dequeue(q2));
222 	destroy_queue(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