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 */
26queue *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
54void 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
77void *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 */
99void free_node(
100	void *my_node
101	)
102{
103	node *old_node = my_node;
104
105	free(old_node - 1);
106}
107
108
109void *
110next_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. */
127int empty(
128	queue *my_queue
129	)
130{
131	return (!my_queue || !my_queue->front);
132}
133
134
135void *
136queue_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 */
151queue *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 */
182void *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 */
200int 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 */
217void 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 */
237int get_fifo_order(const void *el1, const void *el2)
238{
239	return 1;
240}
241