diff options
Diffstat (limited to 'src/pathfinder/npf/queue.h')
| -rw-r--r-- | src/pathfinder/npf/queue.h | 167 |
1 files changed, 167 insertions, 0 deletions
diff --git a/src/pathfinder/npf/queue.h b/src/pathfinder/npf/queue.h new file mode 100644 index 000000000..76421e9ac --- /dev/null +++ b/src/pathfinder/npf/queue.h @@ -0,0 +1,167 @@ +/* $Id$ */ + +/* + * This file is part of OpenTTD. + * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2. + * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>. + */ + +/** @file queue.h Simple Queue/Hash implementations. */ + +#ifndef QUEUE_H +#define QUEUE_H + +//#define NOFREE +//#define QUEUE_DEBUG +//#define HASH_DEBUG +//#define HASH_STATS + + +struct Queue; +typedef bool Queue_PushProc(Queue *q, void *item, int priority); +typedef void *Queue_PopProc(Queue *q); +typedef bool Queue_DeleteProc(Queue *q, void *item, int priority); +typedef void Queue_ClearProc(Queue *q, bool free_values); +typedef void Queue_FreeProc(Queue *q, bool free_values); + +struct InsSortNode { + void *item; + int priority; + InsSortNode *next; +}; + +struct BinaryHeapNode { + void *item; + int priority; +}; + + +struct Queue{ + /* + * Pushes an element into the queue, at the appropriate place for the queue. + * Requires the queue pointer to be of an appropriate type, of course. + */ + Queue_PushProc *push; + /* + * Pops the first element from the queue. What exactly is the first element, + * is defined by the exact type of queue. + */ + Queue_PopProc *pop; + /* + * Deletes the item from the queue. priority should be specified if + * known, which speeds up the deleting for some queue's. Should be -1 + * if not known. + */ + Queue_DeleteProc *del; + + /* Clears the queue, by removing all values from it. It's state is + * effectively reset. If free_items is true, each of the items cleared + * in this way are free()'d. + */ + Queue_ClearProc *clear; + /* Frees the queue, by reclaiming all memory allocated by it. After + * this it is no longer usable. If free_items is true, any remaining + * items are free()'d too. + */ + Queue_FreeProc *free; + + union { + struct { + InsSortNode *first; + } inssort; + struct { + uint max_size; + uint size; + uint blocks; ///< The amount of blocks for which space is reserved in elements + BinaryHeapNode **elements; + } binaryheap; + } data; +}; + + +/** + * Insertion Sorter + */ + +/* Initializes a inssort and allocates internal memory. There is no maximum + * size */ +void init_InsSort(Queue *q); + + +/* + * Binary Heap + * For information, see: + * http://www.policyalmanac.org/games/binaryHeaps.htm + */ + +/* The amount of elements that will be malloc'd at a time */ +#define BINARY_HEAP_BLOCKSIZE_BITS 10 + +/** Initializes a binary heap and allocates internal memory for maximum of + * max_size elements */ +void init_BinaryHeap(Queue *q, uint max_size); + + +/* + * Hash + */ +struct HashNode { + uint key1; + uint key2; + void *value; + HashNode *next; +}; +/** + * Generates a hash code from the given key pair. You should make sure that + * the resulting range is clearly defined. + */ +typedef uint Hash_HashProc(uint key1, uint key2); +struct Hash { + /* The hash function used */ + Hash_HashProc *hash; + /* The amount of items in the hash */ + uint size; + /* The number of buckets allocated */ + uint num_buckets; + /* A pointer to an array of num_buckets buckets. */ + HashNode *buckets; + /* A pointer to an array of numbuckets booleans, which will be true if + * there are any Nodes in the bucket */ + bool *buckets_in_use; +}; + +/* Call these function to manipulate a hash */ + +/** Deletes the value with the specified key pair from the hash and returns + * that value. Returns NULL when the value was not present. The value returned + * is _not_ free()'d! */ +void *Hash_Delete(Hash *h, uint key1, uint key2); +/** Sets the value associated with the given key pair to the given value. + * Returns the old value if the value was replaced, NULL when it was not yet present. */ +void *Hash_Set(Hash *h, uint key1, uint key2, void *value); +/** Gets the value associated with the given key pair, or NULL when it is not + * present. */ +void *Hash_Get(const Hash *h, uint key1, uint key2); + +/* Call these function to create/destroy a hash */ + +/** Builds a new hash in an existing struct. Make sure that hash() always + * returns a hash less than num_buckets! Call delete_hash after use */ +void init_Hash(Hash *h, Hash_HashProc *hash, uint num_buckets); +/** + * Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash + * & friends. If free is true, it will call free() on all the values that + * are left in the hash. + */ +void delete_Hash(Hash *h, bool free_values); +/** + * Cleans the hash, but keeps the memory allocated + */ +void clear_Hash(Hash *h, bool free_values); +/** + * Gets the current size of the Hash + */ +uint Hash_Size(const Hash *h); + +#endif /* QUEUE_H */ |