Annotation of embedaddon/ntp/ntpd/ntp_data_structures.c, revision 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