Files
@ r7596:afd285ff90bb
Branch filter:
Location: cpp/openttd-patchpack/source/src/misc/hashtable.hpp
r7596:afd285ff90bb
6.7 KiB
text/x-c++hdr
(svn r11123) -Update: WebTranslator2 update to 2007-09-17 12:45:29
afrikaans - 47 fixed, 52 changed by TrueTenacity (99)
brazilian_portuguese - 23 changed by fukumori (23)
bulgarian - 14 fixed by thetitan (14)
catalan - 3 changed by arnaullv (3)
croatian - 6 fixed, 12 changed by knovak (15), tperic (3)
danish - 20 fixed by ThomasA (20)
finnish - 20 fixed by habazi (20)
german - 10 fixed by Timwi (10)
hungarian - 1 fixed by miham (1)
italian - 1 fixed by lorenzodv (1)
japanese - 6 fixed by ickoonite (6)
norwegian_nynorsk - 6 fixed by pollux (6)
piglatin - 20 fixed by adammw (20)
russian - 20 fixed by Smoky555 (20)
slovak - 1 fixed by lengyel (1)
slovenian - 7 fixed by Necrolyte (7)
spanish - 1 changed by Cabu (1)
traditional_chinese - 21 fixed by xbddc (21)
afrikaans - 47 fixed, 52 changed by TrueTenacity (99)
brazilian_portuguese - 23 changed by fukumori (23)
bulgarian - 14 fixed by thetitan (14)
catalan - 3 changed by arnaullv (3)
croatian - 6 fixed, 12 changed by knovak (15), tperic (3)
danish - 20 fixed by ThomasA (20)
finnish - 20 fixed by habazi (20)
german - 10 fixed by Timwi (10)
hungarian - 1 fixed by miham (1)
italian - 1 fixed by lorenzodv (1)
japanese - 6 fixed by ickoonite (6)
norwegian_nynorsk - 6 fixed by pollux (6)
piglatin - 20 fixed by adammw (20)
russian - 20 fixed by Smoky555 (20)
slovak - 1 fixed by lengyel (1)
slovenian - 7 fixed by Necrolyte (7)
spanish - 1 changed by Cabu (1)
traditional_chinese - 21 fixed by xbddc (21)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 | /* $Id$ */
/** @file hashtable.hpp */
#ifndef HASHTABLE_HPP
#define HASHTABLE_HPP
template <class Titem_>
struct CHashTableSlotT
{
typedef typename Titem_::Key Key; // make Titem_::Key a property of HashTable
Titem_* m_pFirst;
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;
while (true) {
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; // here we store our data (array of blobs)
int m_num_items; // item counter
public:
// default constructor
FORCEINLINE CHashTableT()
{
// construct all slots
m_slots = new Slot[Tcapacity];
m_num_items = 0;
}
~CHashTableT() {delete [] m_slots; m_num_items = 0; m_slots = NULL;}
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() const {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 */
|