1/*	$NetBSD: ntp_data_structures.c,v 1.1.1.1 2009/12/13 16:56:17 kardel Exp $	*/
2
3/* ntp_data_structures.c
4 *
5 * This file contains the data structures used by the ntp configuration
6 * code and the discrete event simulator.
7 *
8 * Written By: Sachin Kamboj
9 *             University of Delaware
10 *             Newark, DE 19711
11 * Copyright (c) 2006
12 */
13
14
15#include <stdlib.h>    /* Needed for malloc */
16#include "ntp_data_structures.h"
17#include "ntp_stdlib.h"
18
19/* Priority Queue
20 * --------------
21 * Define a priority queue in which the relative priority of the elements
22 * is determined by a function 'get_order' which is supplied to the
23 * priority_queue
24 */
25
26
27queue *create_priority_queue(int (*get_order)(void *, void *))
28{
29    queue *my_queue = (queue *) emalloc(sizeof(queue));
30    my_queue->get_order = get_order;
31    my_queue->front = NULL;
32    my_queue->no_of_elements = 0;
33    return my_queue;
34}
35
36
37/* Define a function to "destroy" a priority queue, freeing-up
38 * all the allocated resources in the process
39 */
40
41void destroy_queue(queue *my_queue)
42{
43    node *temp = NULL;
44
45    /* Empty out the queue elements if they are not already empty */
46    while (my_queue->front != NULL) {
47        temp = my_queue->front;
48        my_queue->front = my_queue->front->node_next;
49        free(temp);
50    }
51
52    /* Now free the queue */
53    free(my_queue);
54}
55
56
57/* Define a function to allocate memory for one element
58 * of the queue. The allocated memory consists of size
59 * bytes plus the number of bytes needed for bookkeeping
60 */
61
62void *get_node(size_t size)
63{
64    node *new_node = emalloc(sizeof(*new_node) + size);
65    new_node->node_next = NULL;
66    return new_node + 1;
67}
68
69/* Define a function to free the allocated memory for a queue node */
70void free_node(void *my_node)
71{
72    node *old_node = my_node;
73    free(old_node - 1);
74}
75
76
77void *
78next_node(
79	void *pv
80	)
81{
82	node *pn;
83
84	pn = pv;
85	pn--;
86
87	if (pn->node_next == NULL)
88		return NULL;
89
90	return pn->node_next + 1;
91}
92
93
94/* Define a function to check if the queue is empty. */
95int empty(queue *my_queue)
96{
97    return (!my_queue || !my_queue->front);
98}
99
100
101void *
102queue_head(
103	queue *q
104	)
105{
106	if (NULL == q || NULL == q->front)
107		return NULL;
108
109	return q->front + 1;
110}
111
112
113/* Define a function to add an element to the priority queue.
114 * The element is added according to its priority -
115 * relative priority is given by the get_order function
116 */
117queue *enqueue(queue *my_queue, void *my_node)
118{
119    node *new_node = ((node *) my_node) - 1;
120    node *i = NULL;
121    node *j = my_queue->front;
122
123    while (j != NULL && ((*my_queue->get_order)(new_node + 1, j + 1) > 0)) {
124        i = j;
125        j = j->node_next;
126    }
127
128    if (i == NULL) {       /* Insert at beginning of the queue */
129        new_node->node_next = my_queue->front;
130        my_queue->front = new_node;
131    }
132    else {                /* Insert Elsewhere, including the end */
133        new_node->node_next = i->node_next;
134        i->node_next = new_node;
135    }
136
137    ++my_queue->no_of_elements;
138    return my_queue;
139}
140
141
142/* Define a function to dequeue the first element from the priority
143 * queue and return it
144 */
145
146void *dequeue(queue *my_queue)
147{
148    node *my_node = my_queue->front;
149    if (my_node != NULL) {
150        my_queue->front = my_node->node_next;
151        --my_queue->no_of_elements;
152        return (void *)(my_node + 1);
153    }
154    else
155        return NULL;
156}
157
158/* Define a function that returns the number of elements in the
159 * priority queue
160 */
161int get_no_of_elements(queue *my_queue)
162{
163    return my_queue->no_of_elements;
164}
165
166/* Define a function to append a queue onto another.
167 * Note: there is a faster way (O(1) as opposed to O(n))
168 * to do this for simple (FIFO) queues, but we can't rely on
169 * that for priority queues. (Given the current representation)
170 *
171 * I don't anticipate this to be a problem. If it does turn
172 * out to be a bottleneck, I will consider replacing the
173 * current implementation with a binomial or fibonacci heap.
174 */
175
176void append_queue(queue *q1, queue *q2)
177{
178    while (!empty(q2))
179        enqueue(q1, dequeue(q2));
180    destroy_queue(q2);
181}
182
183/* FIFO Queue
184 * ----------
185 * Use the priority queue to create a traditional FIFO queue.
186 * The only extra function needed is the create_queue
187 */
188
189/* C is not Lisp and does not allow anonymous lambda functions :-(.
190 * So define a get_fifo_order function here
191 */
192
193int get_fifo_order(void *el1, void *el2)
194{   return 1;
195}
196
197/* Define a function to create a FIFO queue */
198
199queue *create_queue()
200{    return create_priority_queue(get_fifo_order);
201}
202