# queue.h

Go to the documentation of this file.

    00001 /* $Id: queue.h 10673 2007-07-24 17:01:23Z rubidium $ */
    00002
    00005 #ifndef QUEUE_H
    00006 #define QUEUE_H
    00007
    00008 //#define NOFREE
    00009 //#define QUEUE_DEBUG
    00010 //#define HASH_DEBUG
    00011 //#define HASH_STATS
    00012
    00013
    00014 struct Queue;
    00015 typedef bool Queue_PushProc(Queue *q, void *item, int priority);
    00016 typedef void* Queue_PopProc(Queue *q);
    00017 typedef bool Queue_DeleteProc(Queue *q, void* item, int priority);
    00018 typedef void Queue_ClearProc(Queue *q, bool free_values);
    00019 typedef void Queue_FreeProc(Queue *q, bool free_values);
    00020
    00021 struct InsSortNode {
    00022   void *item;
    00023   int priority;
    00024   InsSortNode* next;
    00025 };
    00026
    00027 struct BinaryHeapNode {
    00028   void *item;
    00029   int priority;
    00030 };
    00031
    00032
    00033 struct Queue{
    00034   /*
    00035    * Pushes an element into the queue, at the appropriate place for the queue.
    00036    * Requires the queue pointer to be of an appropriate type, of course.
    00037    */
    00038   Queue_PushProc *push;
    00039   /*
    00040    * Pops the first element from the queue. What exactly is the first element,
    00041    * is defined by the exact type of queue.
    00042    */
    00043   Queue_PopProc *pop;
    00044   /*
    00045    * Deletes the item from the queue. priority should be specified if
    00046    * known, which speeds up the deleting for some queue's. Should be -1
    00047    * if not known.
    00048    */
    00049   Queue_DeleteProc *del;
    00050
    00051   /* Clears the queue, by removing all values from it. It's state is
    00052    * effectively reset. If free_items is true, each of the items cleared
    00053    * in this way are free()'d.
    00054    */
    00055   Queue_ClearProc *clear;
    00056   /* Frees the queue, by reclaiming all memory allocated by it. After
    00057    * this it is no longer usable. If free_items is true, any remaining
    00058    * items are free()'d too.
    00059    */
    00060   Queue_FreeProc *free;
    00061
    00062   union {
    00063     struct {
    00064       InsSortNode *first;
    00065     } inssort;
    00066     struct {
    00067       uint max_size;
    00068       uint size;
    00069       uint blocks;
    00070       BinaryHeapNode **elements;
    00071     } binaryheap;
    00072   } data;
    00073 };
    00074
    00075
    00080 /* Initializes a inssort and allocates internal memory. There is no maximum
    00081  * size */
    00082 void init_InsSort(Queue *q);
    00083
    00084
    00085 /*
    00086  *  Binary Heap
    00087  *  For information, see:
    00088  *   http://www.policyalmanac.org/games/binaryHeaps.htm
    00089  */
    00090
    00091 /* The amount of elements that will be malloc'd at a time */
    00092 #define BINARY_HEAP_BLOCKSIZE_BITS 10
    00093
    00096 void init_BinaryHeap(Queue *q, uint max_size);
    00097
    00098
    00099 /*
    00100  * Hash
    00101  */
    00102 struct HashNode {
    00103   uint key1;
    00104   uint key2;
    00105   void *value;
    00106   HashNode *next;
    00107 };
    00112 typedef uint Hash_HashProc(uint key1, uint key2);
    00113 struct Hash {
    00114   /* The hash function used */
    00115   Hash_HashProc *hash;
    00116   /* The amount of items in the hash */
    00117   uint size;
    00118   /* The number of buckets allocated */
    00119   uint num_buckets;
    00120   /* A pointer to an array of num_buckets buckets. */
    00121   HashNode *buckets;
    00122   /* A pointer to an array of numbuckets booleans, which will be true if
    00123    * there are any Nodes in the bucket */
    00124   bool *buckets_in_use;
    00125 };
    00126
    00127 /* Call these function to manipulate a hash */
    00128
    00132 void *Hash_Delete(Hash *h, uint key1, uint key2);
    00135 void *Hash_Set(Hash *h, uint key1, uint key2, void *value);
    00138 void *Hash_Get(const Hash *h, uint key1, uint key2);
    00139
    00140 /* Call these function to create/destroy a hash */
    00141
    00144 void init_Hash(Hash *h, Hash_HashProc *hash, uint num_buckets);
    00150 void delete_Hash(Hash *h, bool free_values);
    00154 void clear_Hash(Hash *h, bool free_values);
    00158 uint Hash_Size(const Hash *h);
    00159
    00160 #endif /* QUEUE_H */