/* $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 hashtable.hpp Hash table support. */ #ifndef HASHTABLE_HPP #define HASHTABLE_HPP #include "../core/math_func.hpp" template <class Titem_> struct CHashTableSlotT { typedef typename Titem_::Key Key; // make Titem_::Key a property of HashTable Titem_ *m_pFirst; FORCEINLINE CHashTableSlotT() : m_pFirst(NULL) {} /** hash table slot helper - clears the slot by simple forgetting its items */ FORCEINLINE void Clear() {m_pFirst = NULL;} /** hash table slot helper - linear search for item with given key through the given blob - const version */ FORCEINLINE const Titem_ *Find(const Key& key) const { for (const Titem_ *pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) { if (pItem->GetKey() == key) { /* we have found the item, return it */ return pItem; } } return NULL; } /** hash table slot helper - linear search for item with given key through the given blob - non-const version */ FORCEINLINE Titem_ *Find(const Key& key) { for (Titem_ *pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) { if (pItem->GetKey() == key) { /* we have found the item, return it */ return pItem; } } return NULL; } /** hash table slot helper - add new item to the slot */ FORCEINLINE void Attach(Titem_& new_item) { assert(new_item.GetHashNext() == NULL); new_item.SetHashNext(m_pFirst); m_pFirst = &new_item; } /** hash table slot helper - remove item from a slot */ FORCEINLINE bool Detach(Titem_& item_to_remove) { if (m_pFirst == &item_to_remove) { m_pFirst = item_to_remove.GetHashNext(); item_to_remove.SetHashNext(NULL); return true; } Titem_ *pItem = m_pFirst; for (;;) { if (pItem == NULL) { return false; } Titem_ *pNextItem = pItem->GetHashNext(); if (pNextItem == &item_to_remove) break; pItem = pNextItem; } pItem->SetHashNext(item_to_remove.GetHashNext()); item_to_remove.SetHashNext(NULL); return true; } /** hash table slot helper - remove and return item from a slot */ FORCEINLINE Titem_ *Detach(const Key& key) { /* do we have any items? */ if (m_pFirst == NULL) { return NULL; } /* is it our first item? */ if (m_pFirst->GetKey() == key) { Titem_& ret_item = *m_pFirst; m_pFirst = m_pFirst->GetHashNext(); ret_item.SetHashNext(NULL); return &ret_item; } /* find it in the following items */ Titem_ *pPrev = m_pFirst; for (Titem_ *pItem = m_pFirst->GetHashNext(); pItem != NULL; pPrev = pItem, pItem = pItem->GetHashNext()) { if (pItem->GetKey() == key) { /* we have found the item, unlink and return it */ pPrev->SetHashNext(pItem->GetHashNext()); pItem->SetHashNext(NULL); return pItem; } } return NULL; } }; /** * class CHashTableT<Titem, Thash_bits> - simple hash table * of pointers allocated elsewhere. * * Supports: Add/Find/Remove of Titems. * * Your Titem must meet some extra requirements to be CHashTableT * compliant: * - its constructor/destructor (if any) must be public * - if the copying of item requires an extra resource management, * you must define also copy constructor * - must support nested type (struct, class or typedef) Titem::Key * that defines the type of key class for that item * - must support public method: * const Key& GetKey() const; // return the item's key object * * In addition, the Titem::Key class must support: * - public method that calculates key's hash: * int CalcHash() const; * - public 'equality' operator to compare the key with another one * bool operator == (const Key& other) const; */ template <class Titem_, int Thash_bits_> class CHashTableT { public: typedef Titem_ Titem; // make Titem_ visible from outside of class typedef typename Titem_::Key Tkey; // make Titem_::Key a property of HashTable static const int Thash_bits = Thash_bits_; // publish num of hash bits static const int Tcapacity = 1 << Thash_bits; // and num of slots 2^bits protected: /** * each slot contains pointer to the first item in the list, * Titem contains pointer to the next item - GetHashNext(), SetHashNext() */ typedef CHashTableSlotT<Titem_> Slot; Slot m_slots[Tcapacity]; // here we store our data (array of blobs) int m_num_items; // item counter public: /* default constructor */ FORCEINLINE CHashTableT() : m_num_items(0) { } protected: /** static helper - return hash for the given key modulo number of slots */ FORCEINLINE static int CalcHash(const Tkey& key) { int32 hash = key.CalcHash(); if ((8 * Thash_bits) < 32) hash ^= hash >> (min(8 * Thash_bits, 31)); if ((4 * Thash_bits) < 32) hash ^= hash >> (min(4 * Thash_bits, 31)); if ((2 * Thash_bits) < 32) hash ^= hash >> (min(2 * Thash_bits, 31)); if ((1 * Thash_bits) < 32) hash ^= hash >> (min(1 * Thash_bits, 31)); hash &= (1 << Thash_bits) - 1; return hash; } /** static helper - return hash for the given item modulo number of slots */ FORCEINLINE static int CalcHash(const Titem_& item) {return CalcHash(item.GetKey());} public: /** item count */ FORCEINLINE int Count() const {return m_num_items;} /** simple clear - forget all items - used by CSegmentCostCacheT.Flush() */ FORCEINLINE void Clear() {for (int i = 0; i < Tcapacity; i++) m_slots[i].Clear();} /** const item search */ const Titem_ *Find(const Tkey& key) const { int hash = CalcHash(key); const Slot& slot = m_slots[hash]; const Titem_ *item = slot.Find(key); return item; } /** non-const item search */ Titem_ *Find(const Tkey& key) { int hash = CalcHash(key); Slot& slot = m_slots[hash]; Titem_ *item = slot.Find(key); return item; } /** non-const item search & optional removal (if found) */ Titem_ *TryPop(const Tkey& key) { int hash = CalcHash(key); Slot& slot = m_slots[hash]; Titem_ *item = slot.Detach(key); if (item != NULL) { m_num_items--; } return item; } /** non-const item search & removal */ Titem_& Pop(const Tkey& key) { Titem_ *item = TryPop(key); assert(item != NULL); return *item; } /** non-const item search & optional removal (if found) */ bool TryPop(Titem_& item) { const Tkey& key = item.GetKey(); int hash = CalcHash(key); Slot& slot = m_slots[hash]; bool ret = slot.Detach(item); if (ret) { m_num_items--; } return ret; } /** non-const item search & removal */ void Pop(Titem_& item) { bool ret = TryPop(item); assert(ret); } /** add one item - copy it from the given item */ void Push(Titem_& new_item) { int hash = CalcHash(new_item); Slot& slot = m_slots[hash]; assert(slot.Find(new_item.GetKey()) == NULL); slot.Attach(new_item); m_num_items++; } }; #endif /* HASHTABLE_HPP */