1*2b15cb3dSCy Schubert /* ntp_prio_q.h 2*2b15cb3dSCy Schubert * 3*2b15cb3dSCy Schubert * This file contains the structures and function prototypes for the 4*2b15cb3dSCy Schubert * priority queue implementation used by the discrete event simulator. 5*2b15cb3dSCy Schubert * 6*2b15cb3dSCy Schubert * Written By: Sachin Kamboj 7*2b15cb3dSCy Schubert * University of Delaware 8*2b15cb3dSCy Schubert * Newark, DE 19711 9*2b15cb3dSCy Schubert * Copyright (c) 2006 10*2b15cb3dSCy Schubert */ 11*2b15cb3dSCy Schubert 12*2b15cb3dSCy Schubert #ifndef NTP_PRIO_Q_H 13*2b15cb3dSCy Schubert #define NTP_PRIO_Q_H 14*2b15cb3dSCy Schubert 15*2b15cb3dSCy Schubert #include <stddef.h> /* size_t */ 16*2b15cb3dSCy Schubert 17*2b15cb3dSCy Schubert /* Structures for storing a priority queue 18*2b15cb3dSCy Schubert * --------------------------------------- 19*2b15cb3dSCy Schubert */ 20*2b15cb3dSCy Schubert 21*2b15cb3dSCy Schubert typedef struct node { 22*2b15cb3dSCy Schubert union { 23*2b15cb3dSCy Schubert struct node *next; 24*2b15cb3dSCy Schubert double d; 25*2b15cb3dSCy Schubert } nodeu; 26*2b15cb3dSCy Schubert } node; 27*2b15cb3dSCy Schubert #define node_next nodeu.next 28*2b15cb3dSCy Schubert 29*2b15cb3dSCy Schubert typedef int (*q_order_func)(const void *, const void *); 30*2b15cb3dSCy Schubert 31*2b15cb3dSCy Schubert typedef struct Queue { 32*2b15cb3dSCy Schubert q_order_func get_order; 33*2b15cb3dSCy Schubert node * front; 34*2b15cb3dSCy Schubert int no_of_elements; 35*2b15cb3dSCy Schubert } queue; 36*2b15cb3dSCy Schubert 37*2b15cb3dSCy Schubert 38*2b15cb3dSCy Schubert /* FUNCTION PROTOTYPES 39*2b15cb3dSCy Schubert * ------------------- 40*2b15cb3dSCy Schubert */ 41*2b15cb3dSCy Schubert /* Define a function to create a FIFO queue */ 42*2b15cb3dSCy Schubert #define create_queue() create_priority_queue(&get_fifo_order) 43*2b15cb3dSCy Schubert 44*2b15cb3dSCy Schubert void destroy_queue(queue *my_queue); 45*2b15cb3dSCy Schubert void free_node(void *my_node); 46*2b15cb3dSCy Schubert void *next_node(void *my_node); 47*2b15cb3dSCy Schubert int empty(queue *my_queue); 48*2b15cb3dSCy Schubert void *queue_head(queue *my_queue); 49*2b15cb3dSCy Schubert queue *enqueue(queue *my_queue, void *my_node); 50*2b15cb3dSCy Schubert void append_queue(queue *q1, queue *q2); 51*2b15cb3dSCy Schubert void *dequeue(queue *my_queue); 52*2b15cb3dSCy Schubert int get_no_of_elements(queue *my_queue); 53*2b15cb3dSCy Schubert int get_fifo_order(const void *el1, const void *el2); 54*2b15cb3dSCy Schubert 55*2b15cb3dSCy Schubert /* 56*2b15cb3dSCy Schubert * Preserve original callsite __FILE__ and __LINE__ for these 57*2b15cb3dSCy Schubert * malloc-like funcs when using MS C runtime debug heap. 58*2b15cb3dSCy Schubert */ 59*2b15cb3dSCy Schubert #ifdef _CRTDBG_MAP_ALLOC 60*2b15cb3dSCy Schubert # define create_priority_queue(order) debug_create_priority_queue(order, __FILE__, __LINE__) 61*2b15cb3dSCy Schubert # define get_node(size) debug_get_node(size, __FILE__, __LINE__) 62*2b15cb3dSCy Schubert #else 63*2b15cb3dSCy Schubert # define create_priority_queue(order) debug_create_priority_queue(order) 64*2b15cb3dSCy Schubert # define get_node(size) debug_get_node(size) 65*2b15cb3dSCy Schubert #endif 66*2b15cb3dSCy Schubert 67*2b15cb3dSCy Schubert queue *debug_create_priority_queue( 68*2b15cb3dSCy Schubert q_order_func get_order 69*2b15cb3dSCy Schubert #ifdef _CRTDBG_MAP_ALLOC 70*2b15cb3dSCy Schubert , const char * sourcefile 71*2b15cb3dSCy Schubert , int line_num 72*2b15cb3dSCy Schubert #endif 73*2b15cb3dSCy Schubert ); 74*2b15cb3dSCy Schubert 75*2b15cb3dSCy Schubert void *debug_get_node( 76*2b15cb3dSCy Schubert size_t size 77*2b15cb3dSCy Schubert #ifdef _CRTDBG_MAP_ALLOC 78*2b15cb3dSCy Schubert , const char * sourcefile 79*2b15cb3dSCy Schubert , int line_num 80*2b15cb3dSCy Schubert #endif 81*2b15cb3dSCy Schubert ); 82*2b15cb3dSCy Schubert 83*2b15cb3dSCy Schubert #endif /* NTP_PRIO_Q_H */ 84