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