src/misc/hashtable.hpp

   1 /* $Id: hashtable.hpp 23640 2011-12-20 17:57:56Z truebrain $ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * 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.
   6  * 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.
   7  * 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/>.
   8  */
   9
  10 /** @file hashtable.hpp Hash table support. */
  11
  12 #ifndef HASHTABLE_HPP
  13 #define HASHTABLE_HPP
  14
  15 #include "../core/math_func.hpp"
  16
  17 template <class Titem_>
  18 struct CHashTableSlotT
  19 {
  20         typedef typename Titem_::Key Key;          // make Titem_::Key a property of HashTable
  21
  22         Titem_ *m_pFirst;
  23
  24         inline CHashTableSlotT() : m_pFirst(NULL) {}
  25
  26         /** hash table slot helper - clears the slot by simple forgetting its items */
  27         inline void Clear()
  28         {
  29                 m_pFirst = NULL;
  30         }
  31
  32         /** hash table slot helper - linear search for item with given key through the given blob - const version */
  33         inline const Titem_ *Find(const Key &key) const
  34         {
  35                 for (const Titem_ *pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
  36                         if (pItem->GetKey() == key) {
  37                                 /* we have found the item, return it */
  38                                 return pItem;
  39                         }
  40                 }
  41                 return NULL;
  42         }
  43
  44         /** hash table slot helper - linear search for item with given key through the given blob - non-const version */
  45         inline Titem_ *Find(const Key &key)
  46         {
  47                 for (Titem_ *pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
  48                         if (pItem->GetKey() == key) {
  49                                 /* we have found the item, return it */
  50                                 return pItem;
  51                         }
  52                 }
  53                 return NULL;
  54         }
  55
  56         /** hash table slot helper - add new item to the slot */
  57         inline void Attach(Titem_ &new_item)
  58         {
  59                 assert(new_item.GetHashNext() == NULL);
  60                 new_item.SetHashNext(m_pFirst);
  61                 m_pFirst = &new_item;
  62         }
  63
  64         /** hash table slot helper - remove item from a slot */
  65         inline bool Detach(Titem_ &item_to_remove)
  66         {
  67                 if (m_pFirst == &item_to_remove) {
  68                         m_pFirst = item_to_remove.GetHashNext();
  69                         item_to_remove.SetHashNext(NULL);
  70                         return true;
  71                 }
  72                 Titem_ *pItem = m_pFirst;
  73                 for (;;) {
  74                         if (pItem == NULL) {
  75                                 return false;
  76                         }
  77                         Titem_ *pNextItem = pItem->GetHashNext();
  78                         if (pNextItem == &item_to_remove) break;
  79                         pItem = pNextItem;
  80                 }
  81                 pItem->SetHashNext(item_to_remove.GetHashNext());
  82                 item_to_remove.SetHashNext(NULL);
  83                 return true;
  84         }
  85
  86         /** hash table slot helper - remove and return item from a slot */
  87         inline Titem_ *Detach(const Key &key)
  88         {
  89                 /* do we have any items? */
  90                 if (m_pFirst == NULL) {
  91                         return NULL;
  92                 }
  93                 /* is it our first item? */
  94                 if (m_pFirst->GetKey() == key) {
  95                         Titem_ &ret_item = *m_pFirst;
  96                         m_pFirst = m_pFirst->GetHashNext();
  97                         ret_item.SetHashNext(NULL);
  98                         return &ret_item;
  99                 }
 100                 /* find it in the following items */
 101                 Titem_ *pPrev = m_pFirst;
 102                 for (Titem_ *pItem = m_pFirst->GetHashNext(); pItem != NULL; pPrev = pItem, pItem = pItem->GetHashNext()) {
 103                         if (pItem->GetKey() == key) {
 104                                 /* we have found the item, unlink and return it */
 105                                 pPrev->SetHashNext(pItem->GetHashNext());
 106                                 pItem->SetHashNext(NULL);
 107                                 return pItem;
 108                         }
 109                 }
 110                 return NULL;
 111         }
 112 };
 113
 114 /**
 115  * class CHashTableT<Titem, Thash_bits> - simple hash table
 116  *  of pointers allocated elsewhere.
 117  *
 118  *  Supports: Add/Find/Remove of Titems.
 119  *
 120  *  Your Titem must meet some extra requirements to be CHashTableT
 121  *  compliant:
 122  *    - its constructor/destructor (if any) must be public
 123  *    - if the copying of item requires an extra resource management,
 124  *        you must define also copy constructor
 125  *    - must support nested type (struct, class or typedef) Titem::Key
 126  *        that defines the type of key class for that item
 127  *    - must support public method:
 128  *        const Key& GetKey() const; // return the item's key object
 129  *
 130  *  In addition, the Titem::Key class must support:
 131  *    - public method that calculates key's hash:
 132  *        int CalcHash() const;
 133  *    - public 'equality' operator to compare the key with another one
 134  *        bool operator==(const Key &other) const;
 135  */
 136 template <class Titem_, int Thash_bits_>
 137 class CHashTableT {
 138 public:
 139         typedef Titem_ Titem;                         // make Titem_ visible from outside of class
 140         typedef typename Titem_::Key Tkey;            // make Titem_::Key a property of HashTable
 141         static const int Thash_bits = Thash_bits_;    // publish num of hash bits
 142         static const int Tcapacity = 1 << Thash_bits; // and num of slots 2^bits
 143
 144 protected:
 145         /**
 146          * each slot contains pointer to the first item in the list,
 147          *  Titem contains pointer to the next item - GetHashNext(), SetHashNext()
 148          */
 149         typedef CHashTableSlotT<Titem_> Slot;
 150
 151         Slot  m_slots[Tcapacity]; // here we store our data (array of blobs)
 152         int   m_num_items;        // item counter
 153
 154 public:
 155         /* default constructor */
 156         inline CHashTableT() : m_num_items(0)
 157         {
 158         }
 159
 160 protected:
 161         /** static helper - return hash for the given key modulo number of slots */
 162         inline static int CalcHash(const Tkey &key)
 163         {
 164                 int32 hash = key.CalcHash();
 165                 if ((8 * Thash_bits) < 32) hash ^= hash >> (min(8 * Thash_bits, 31));
 166                 if ((4 * Thash_bits) < 32) hash ^= hash >> (min(4 * Thash_bits, 31));
 167                 if ((2 * Thash_bits) < 32) hash ^= hash >> (min(2 * Thash_bits, 31));
 168                 if ((1 * Thash_bits) < 32) hash ^= hash >> (min(1 * Thash_bits, 31));
 169                 hash &= (1 << Thash_bits) - 1;
 170                 return hash;
 171         }
 172
 173         /** static helper - return hash for the given item modulo number of slots */
 174         inline static int CalcHash(const Titem_ &item)
 175         {
 176                 return CalcHash(item.GetKey());
 177         }
 178
 179 public:
 180         /** item count */
 181         inline int Count() const
 182         {
 183                 return m_num_items;
 184         }
 185
 186         /** simple clear - forget all items - used by CSegmentCostCacheT.Flush() */
 187         inline void Clear()
 188         {
 189                 for (int i = 0; i < Tcapacity; i++) m_slots[i].Clear();
 190         }
 191
 192         /** const item search */
 193         const Titem_ *Find(const Tkey &key) const
 194         {
 195                 int hash = CalcHash(key);
 196                 const Slot &slot = m_slots[hash];
 197                 const Titem_ *item = slot.Find(key);
 198                 return item;
 199         }
 200
 201         /** non-const item search */
 202         Titem_ *Find(const Tkey &key)
 203         {
 204                 int hash = CalcHash(key);
 205                 Slot &slot = m_slots[hash];
 206                 Titem_ *item = slot.Find(key);
 207                 return item;
 208         }
 209
 210         /** non-const item search & optional removal (if found) */
 211         Titem_ *TryPop(const Tkey &key)
 212         {
 213                 int hash = CalcHash(key);
 214                 Slot &slot = m_slots[hash];
 215                 Titem_ *item = slot.Detach(key);
 216                 if (item != NULL) {
 217                         m_num_items--;
 218                 }
 219                 return item;
 220         }
 221
 222         /** non-const item search & removal */
 223         Titem_& Pop(const Tkey &key)
 224         {
 225                 Titem_ *item = TryPop(key);
 226                 assert(item != NULL);
 227                 return *item;
 228         }
 229
 230         /** non-const item search & optional removal (if found) */
 231         bool TryPop(Titem_ &item)
 232         {
 233                 const Tkey &key = item.GetKey();
 234                 int hash = CalcHash(key);
 235                 Slot &slot = m_slots[hash];
 236                 bool ret = slot.Detach(item);
 237                 if (ret) {
 238                         m_num_items--;
 239                 }
 240                 return ret;
 241         }
 242
 243         /** non-const item search & removal */
 244         void Pop(Titem_ &item)
 245         {
 246                 bool ret = TryPop(item);
 247                 assert(ret);
 248         }
 249
 250         /** add one item - copy it from the given item */
 251         void Push(Titem_ &new_item)
 252         {
 253                 int hash = CalcHash(new_item);
 254                 Slot &slot = m_slots[hash];
 255                 assert(slot.Find(new_item.GetKey()) == NULL);
 256                 slot.Attach(new_item);
 257                 m_num_items++;
 258         }
 259 };
 260
 261 #endif /* HASHTABLE_HPP */