tron@2186: /* $Id$ */
tron@2186: 
truelight@110: #ifndef QUEUE_H
truelight@110: #define QUEUE_H
truelight@110: 
truelight@110: //#define NOFREE
truelight@110: //#define QUEUE_DEBUG
truelight@110: //#define HASH_DEBUG
matthijs@1661: //#define HASH_STATS
truelight@110: 
truelight@110: 
truelight@110: typedef struct Queue Queue;
truelight@110: typedef bool Queue_PushProc(Queue* q, void* item, int priority);
truelight@110: typedef void* Queue_PopProc(Queue* q);
truelight@110: typedef bool Queue_DeleteProc(Queue* q, void* item, int priority);
truelight@110: typedef void Queue_ClearProc(Queue* q, bool free_values);
truelight@110: typedef void Queue_FreeProc(Queue* q, bool free_values);
truelight@110: 
truelight@110: typedef struct InsSortNode InsSortNode;
truelight@110: struct InsSortNode {
truelight@110: 	void* item;
truelight@110: 	int priority;
truelight@110: 	InsSortNode* next;
truelight@110: };
tron@3012: 
truelight@110: typedef struct BinaryHeapNode BinaryHeapNode;
tron@3012: struct BinaryHeapNode {
truelight@110: 	void* item;
truelight@110: 	int priority;
truelight@110: };
truelight@110: 
truelight@110: 
truelight@110: struct Queue{
truelight@110: 	/*
truelight@110: 	 * Pushes an element into the queue, at the appropriate place for the queue.
truelight@110: 	 * Requires the queue pointer to be of an appropriate type, of course.
truelight@110: 	 */
truelight@110: 	Queue_PushProc* push;
truelight@110: 	/*
truelight@110: 	 * Pops the first element from the queue. What exactly is the first element,
truelight@110: 	 * is defined by the exact type of queue.
truelight@110: 	 */
truelight@110: 	Queue_PopProc* pop;
truelight@110: 	/*
truelight@110: 	 * Deletes the item from the queue. priority should be specified if
truelight@110: 	 * known, which speeds up the deleting for some queue's. Should be -1
truelight@110: 	 * if not known.
truelight@110: 	 */
truelight@110: 	Queue_DeleteProc* del;
truelight@110: 
truelight@110: 	/* Clears the queue, by removing all values from it. It's state is
truelight@110: 	 * effectively reset. If free_items is true, each of the items cleared
truelight@110: 	 * in this way are free()'d.
truelight@110: 	 */
truelight@110: 	Queue_ClearProc* clear;
truelight@110: 	/* Frees the queue, by reclaiming all memory allocated by it. After
truelight@110: 	 * this it is no longer usable. If free_items is true, any remaining
truelight@201: 	 * items are free()'d too.
truelight@110: 	 */
truelight@110: 	Queue_FreeProc* free;
truelight@110: 
truelight@110: 	union {
truelight@110: 		struct {
truelight@110: 			uint max_size;
truelight@110: 			uint size;
truelight@110: 			void** elements;
truelight@110: 		} stack;
truelight@110: 		struct {
truelight@110: 			uint max_size;
truelight@110: 			uint head; /* The index where the last element should be inserted */
truelight@110: 			uint tail; /* The index where the next element should be read */
truelight@110: 			void** elements;
truelight@110: 		} fifo;
truelight@110: 		struct {
truelight@110: 			InsSortNode* first;
truelight@110: 		} inssort;
truelight@110: 		struct {
truelight@110: 			uint max_size;
truelight@110: 			uint size;
truelight@110: 			uint blocks; /* The amount of blocks for which space is reserved in elements */
truelight@110: 			BinaryHeapNode** elements;
truelight@110: 		} binaryheap;
truelight@110: 	} data;
truelight@110: 
truelight@110: 	/* If true, this struct will be free'd when the
truelight@110: 	 * Queue is deleted. */
truelight@110: 	bool freeq;
truelight@110: };
truelight@110: 
truelight@110: /* Initializes a stack and allocates internal memory. */
truelight@110: void init_Stack(Queue* q, uint max_size);
truelight@110: 
truelight@110: /* Allocate a new stack with a maximum of max_size elements. */
truelight@110: Queue* new_Stack(uint max_size);
truelight@110: 
truelight@110: /*
truelight@110:  * Fifo
truelight@110:  */
truelight@110: 
truelight@110: /* Initializes a fifo and allocates internal memory for maximum of max_size
truelight@110:  * elements */
truelight@110: void init_Fifo(Queue* q, uint max_size);
truelight@110: 
truelight@110: /* Allocate a new fifo and initializes it with a maximum of max_size elements. */
truelight@110: Queue* new_Fifo(uint max_size);
truelight@110: 
truelight@110: Queue* new_Fifo_in_buffer(uint max_size, void* buffer);
truelight@110: 
truelight@110: int build_Fifo(void* buffer, uint size);
truelight@110: 
truelight@110: /*
truelight@110:  * Insertion Sorter
truelight@110:  */
truelight@110: 
truelight@110: /* Initializes a inssort and allocates internal memory. There is no maximum
truelight@110:  * size */
truelight@110: void init_InsSort(Queue* q);
truelight@110: 
truelight@110: /* Allocate a new fifo and initializes it. There is no maximum size */
tron@1093: Queue* new_InsSort(void);
truelight@110: 
truelight@110: /*
truelight@110:  *  Binary Heap
truelight@110:  *  For information, see:
truelight@110:  *   http://www.policyalmanac.org/games/binaryHeaps.htm
truelight@110:  */
truelight@110: 
truelight@110: /* The amount of elements that will be malloc'd at a time */
truelight@110: #define BINARY_HEAP_BLOCKSIZE_BITS 10
truelight@110: 
truelight@110: /* Initializes a binary heap and allocates internal memory for maximum of
truelight@110:  * max_size elements */
truelight@110: void init_BinaryHeap(Queue* q, uint max_size);
truelight@110: 
truelight@110: /* Allocate a new binary heap and initializes it with a maximum of max_size
truelight@110:  * elements. */
truelight@110: Queue* new_BinaryHeap(uint max_size);
truelight@110: 
truelight@110: /*
truelight@110:  * Hash
truelight@110:  */
truelight@110: typedef struct HashNode HashNode;
truelight@110: struct HashNode {
truelight@110: 	uint key1;
truelight@110: 	uint key2;
truelight@110: 	void* value;
truelight@110: 	HashNode* next;
truelight@110: };
matthijs@1661: /**
matthijs@1661:  * Generates a hash code from the given key pair. You should make sure that
truelight@110:  * the resulting range is clearly defined.
truelight@110:  */
truelight@110: typedef uint Hash_HashProc(uint key1, uint key2);
truelight@110: typedef struct Hash {
truelight@110: 	/* The hash function used */
truelight@110: 	Hash_HashProc* hash;
truelight@110: 	/* The amount of items in the hash */
truelight@110: 	uint size;
truelight@110: 	/* The number of buckets allocated */
truelight@110: 	uint num_buckets;
truelight@110: 	/* A pointer to an array of num_buckets buckets. */
truelight@110: 	HashNode* buckets;
truelight@110: 	/* A pointer to an array of numbuckets booleans, which will be true if
truelight@110: 	 * there are any Nodes in the bucket */
truelight@110: 	bool* buckets_in_use;
truelight@110: 	/* If true, buckets will be freed in delete_hash */
truelight@110: 	bool freeb;
truelight@110: 	/* If true, the pointer to this struct will be freed in delete_hash */
truelight@110: 	bool freeh;
truelight@110: } Hash;
truelight@110: 
truelight@110: /* Call these function to manipulate a hash */
truelight@110: 
truelight@110: /* Deletes the value with the specified key pair from the hash and returns
truelight@110:  * that value. Returns NULL when the value was not present. The value returned
truelight@110:  * is _not_ free()'d! */
truelight@110: void* Hash_Delete(Hash* h, uint key1, uint key2);
truelight@110: /* Sets the value associated with the given key pair to the given value.
truelight@110:  * Returns the old value if the value was replaced, NULL when it was not yet present. */
truelight@110: void* Hash_Set(Hash* h, uint key1, uint key2, void* value);
truelight@110: /* Gets the value associated with the given key pair, or NULL when it is not
truelight@110:  * present. */
tron@3012: void* Hash_Get(const Hash* h, uint key1, uint key2);
truelight@110: 
truelight@110: /* Call these function to create/destroy a hash */
truelight@110: 
truelight@110: /* Builds a new hash, with num_buckets buckets. Make sure that hash() always
truelight@110:  * returns a hash less than num_buckets! Call delete_hash after use */
truelight@110: Hash* new_Hash(Hash_HashProc* hash, int num_buckets);
truelight@110: /* Builds a new hash in an existing struct. Make sure that hash() always
truelight@110:  * returns a hash less than num_buckets! Call delete_hash after use */
matthijs@1661: void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets);
truelight@110: /*
truelight@110:  * Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash
truelight@110:  * & friends. If free is true, it will call free() on all the values that
truelight@110:  * are left in the hash.
truelight@110:  */
truelight@110: void delete_Hash(Hash* h, bool free_values);
truelight@110: /*
truelight@110:  * Cleans the hash, but keeps the memory allocated
truelight@110:  */
truelight@110: void clear_Hash(Hash* h, bool free_values);
truelight@110: /*
truelight@110:  * Gets the current size of the Hash
truelight@110:  */
tron@3012: uint Hash_Size(const Hash* h);
truelight@110: 
truelight@110: #endif /* QUEUE_H */