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