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 25queue *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 39void 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 60void *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 */ 68void free_node(void *my_node) 69{ 70 node *old_node = my_node; 71 free(old_node - 1); 72} 73 74 75void * 76next_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. */ 93int empty(queue *my_queue) 94{ 95 return (!my_queue || !my_queue->front); 96} 97 98 99void * 100queue_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 */ 115queue *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 144void *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 */ 159int 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 174void 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 191int get_fifo_order(void *el1, void *el2) 192{ return 1; 193} 194 195/* Define a function to create a FIFO queue */ 196 197queue *create_queue() 198{ return create_priority_queue(get_fifo_order); 199} 200