(svn r6601) - Codechange: Support cargo subtypes in the refit window. The refit window has been altered to support resizing and scrolling. Note that the cargo subtype isn't yet passed for actual refitting yet. (Based on mart3p's patch)
/* $Id$ */
#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 - 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 *(Titem_*)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 *(Titem_*)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 *(Titem_*)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 *(Titem_*)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
ST_CONST(int, Thash_bits = Thash_bits_); // publish num of hash bits
ST_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;}
/** 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 */