/************************************************************************** * # # # ## # # ### ## ## ### http://www.lyonesse.it * * # # # # # ## # # # # # * * # # # # # ## ## # # ## ## ## # # ## * * # # # # # ## # # # # # # # # # # # * * ### # ## # # ### ## ## ### # # #### ## Ver. 1.0 * * * * -Based on CircleMud & Smaug- Copyright (c) 2001-2002 by Mithrandir * * * * ********************************************************************** */ /* ************************************************************************ * File: queue.c * * * * Usage: generic queue functions for building and using a priority queue * * * * Written by Eric Green (ejg3@cornell.edu) * * * * Changes: * * 3/6/98 ejg: Moved defines and structs from queue.h. * ************************************************************************ */ #include "conf.h" #include "sysdep.h" #include "structs.h" #include "utils.h" /* external variables */ extern unsigned long pulse; /* returns a new, initialized queue */ QUEUE_DATA *queue_init( void ) { QUEUE_DATA *q; CREATE( q, QUEUE_DATA, 1 ); return ( q ); } /* add data into the priority queue q with key */ Q_ELEM_DATA *queue_enq( QUEUE_DATA *q, void *data, long key ) { Q_ELEM_DATA *qe, *i; int bucket; CREATE( qe, Q_ELEM_DATA, 1 ); qe->data = data; qe->key = key; bucket = key % NUM_EVENT_QUEUES; /* which queue does this go in */ if ( !q->head[bucket] ) /* queue is empty */ { q->head[bucket] = qe; q->tail[bucket] = qe; } else { for ( i = q->tail[bucket]; i; i = i->prev ) { if ( i->key < key ) /* found insertion point */ { if ( i == q->tail[bucket] ) q->tail[bucket] = qe; else { qe->next = i->next; i->next->prev = qe; } qe->prev = i; i->next = qe; break; } } if ( i == NULL ) /* insertion point is front of list */ { qe->next = q->head[bucket]; q->head[bucket] = qe; qe->next->prev = qe; } } return ( qe ); } /* remove queue element qe from the priority queue q */ void queue_deq( QUEUE_DATA *q, Q_ELEM_DATA *qe ) { int i; assert( qe ); i = qe->key % NUM_EVENT_QUEUES; if ( qe->prev == NULL ) q->head[i] = qe->next; else qe->prev->next = qe->next; if ( qe->next == NULL ) q->tail[i] = qe->prev; else qe->next->prev = qe->prev; free( qe ); } /* * removes and returns the data of the * first element of the priority queue q */ void *queue_head( QUEUE_DATA *q ) { void *data; int i; i = pulse % NUM_EVENT_QUEUES; if ( !q->head[i] ) return ( NULL ); data = q->head[i]->data; queue_deq( q, q->head[i] ); return ( data ); } /* * returns the key of the head element of the priority queue * if q is NULL, then return the largest unsigned number */ long queue_key( QUEUE_DATA *q ) { int i; i = pulse % NUM_EVENT_QUEUES; if ( q->head[i] ) return ( q->head[i]->key ); else return ( LONG_MAX ); } /* returns the key of queue element qe */ long queue_elmt_key( Q_ELEM_DATA *qe ) { return ( qe->key ); } /* free q and contents */ void queue_free( QUEUE_DATA *q ) { Q_ELEM_DATA *qe, *next_qe; int i; for ( i = 0; i < NUM_EVENT_QUEUES; i++ ) for ( qe = q->head[i]; qe; qe = next_qe ) { next_qe = qe->next; free( qe ); } free( q ); }