Annotation of embedaddon/ntp/ntpd/ntp_data_structures.c, revision 1.1.1.1
1.1 misho 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:
25: queue *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:
39: void 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:
60: void *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 */
68: void free_node(void *my_node)
69: {
70: node *old_node = my_node;
71: free(old_node - 1);
72: }
73:
74:
75: void *
76: next_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. */
93: int empty(queue *my_queue)
94: {
95: return (!my_queue || !my_queue->front);
96: }
97:
98:
99: void *
100: queue_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: */
115: queue *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:
144: void *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: */
159: int 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:
174: void 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:
191: int get_fifo_order(void *el1, void *el2)
192: { return 1;
193: }
194:
195: /* Define a function to create a FIFO queue */
196:
197: queue *create_queue()
198: { return create_priority_queue(get_fifo_order);
199: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ntp_data_structures.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / ntp / ntpd