Files
@ r18989:156eeb86b09e
Branch filter:
Location: cpp/openttd-patchpack/source/src/misc/hashtable.hpp
r18989:156eeb86b09e
7.1 KiB
text/x-c++hdr
(svn r23855) -Fix [FS#5007]: out of bounds read for slowdown parameter caused desync when railtype >= 4, vehicles were fast, and the original acceleration model was used
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 243 244 245 246 247 248 249 | /* $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;
inline CHashTableSlotT() : m_pFirst(NULL) {}
/** hash table slot helper - clears the slot by simple forgetting its items */
inline void Clear() {m_pFirst = NULL;}
/** hash table slot helper - linear search for item with given key through the given blob - const version */
inline 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 */
inline 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 */
inline 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 */
inline 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 */
inline 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 */
inline CHashTableT() : m_num_items(0)
{
}
protected:
/** static helper - return hash for the given key modulo number of slots */
inline 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 */
inline static int CalcHash(const Titem_& item) {return CalcHash(item.GetKey());}
public:
/** item count */
inline int Count() const {return m_num_items;}
/** simple clear - forget all items - used by CSegmentCostCacheT.Flush() */
inline 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 */
|