external/bsd/ntp/dist/ntpd/ntp_data_structures.c

   1 /*      $NetBSD$        */
   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
  27 queue *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
  41 void 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
  62 void *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 */
  70 void free_node(void *my_node)
  71 {
  72     node *old_node = my_node;
  73     free(old_node - 1);
  74 }
  75
  76
  77 void *
  78 next_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. */
  95 int empty(queue *my_queue)
  96 {
  97     return (!my_queue || !my_queue->front);
  98 }
  99
 100
 101 void *
 102 queue_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  */
 117 queue *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
 146 void *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  */
 161 int 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
 176 void 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
 193 int get_fifo_order(void *el1, void *el2)
 194 {   return 1;
 195 }
 196
 197 /* Define a function to create a FIFO queue */
 198
 199 queue *create_queue()
 200 {    return create_priority_queue(get_fifo_order);
 201 }