Return to ntp_data_structures.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / ntp / ntpd

ntp 4.2.6p5

    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: }