src/pathfinder/npf/queue.h

   1 /*
   2  * This file is part of OpenTTD.
   3  * 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.
   4  * 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.
   5  * 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/>.
   6  */
   7
   8 /** @file queue.h Binary heap implementation, hash implementation. */
   9
  10 #ifndef QUEUE_H
  11 #define QUEUE_H
  12
  13 //#define HASH_STATS
  14
  15
  16 struct BinaryHeapNode {
  17         void *item;
  18         int priority;
  19 };
  20
  21
  22 /**
  23  * Binary Heap.
  24  * For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm
  25  */
  26 struct BinaryHeap {
  27         static const int BINARY_HEAP_BLOCKSIZE;
  28         static const int BINARY_HEAP_BLOCKSIZE_BITS;
  29         static const int BINARY_HEAP_BLOCKSIZE_MASK;
  30
  31         void Init(uint max_size);
  32
  33         bool Push(void *item, int priority);
  34         void *Pop();
  35         bool Delete(void *item, int priority);
  36         void Clear(bool free_values);
  37         void Free(bool free_values);
  38
  39         /**
  40          * Get an element from the #elements.
  41          * @param i Element to access (starts at offset \c 1).
  42          * @return Value of the element.
  43          */
  44         inline BinaryHeapNode &GetElement(uint i)
  45         {
  46                 assert(i > 0);
  47                 return this->elements[(i - 1) >> BINARY_HEAP_BLOCKSIZE_BITS][(i - 1) & BINARY_HEAP_BLOCKSIZE_MASK];
  48         }
  49
  50         uint max_size;
  51         uint size;
  52         uint blocks; ///< The amount of blocks for which space is reserved in elements
  53         BinaryHeapNode **elements;
  54 };
  55
  56
  57 /*
  58  * Hash
  59  */
  60 struct HashNode {
  61         uint key1;
  62         uint key2;
  63         void *value;
  64         HashNode *next;
  65 };
  66 /**
  67  * Generates a hash code from the given key pair. You should make sure that
  68  * the resulting range is clearly defined.
  69  */
  70 typedef uint Hash_HashProc(uint key1, uint key2);
  71 struct Hash {
  72         /* The hash function used */
  73         Hash_HashProc *hash;
  74         /* The amount of items in the hash */
  75         uint size;
  76         /* The number of buckets allocated */
  77         uint num_buckets;
  78         /* A pointer to an array of num_buckets buckets. */
  79         HashNode *buckets;
  80         /* A pointer to an array of numbuckets booleans, which will be true if
  81          * there are any Nodes in the bucket */
  82         bool *buckets_in_use;
  83
  84         void Init(Hash_HashProc *hash, uint num_buckets);
  85
  86         void *Get(uint key1, uint key2) const;
  87         void *Set(uint key1, uint key2, void *value);
  88
  89         void *DeleteValue(uint key1, uint key2);
  90
  91         void Clear(bool free_values);
  92         void Delete(bool free_values);
  93
  94         /**
  95          * Gets the current size of the hash.
  96          */
  97         inline uint GetSize() const
  98         {
  99                 return this->size;
 100         }
 101
 102 protected:
 103 #ifdef HASH_STATS
 104         void PrintStatistics() const;
 105 #endif
 106         HashNode *FindNode(uint key1, uint key2, HashNode** prev_out) const;
 107 };
 108
 109 #endif /* QUEUE_H */