contrib/ntp/ntpd/ntp_prio_q.c

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