1

/* $Id$ */

     2

     3

#ifndef  HASHTABLE_HPP

     4

#define  HASHTABLE_HPP

     5

     6

template <class Titem_>

     7

struct CHashTableSlotT

     8

{

     9

	typedef typename Titem_::Key Key;          // make Titem_::Key a property of HashTable

    10

    11

	Titem_*    m_pFirst;

    12

    13

	CHashTableSlotT() : m_pFirst(NULL) {}

    14

    15

	/** hash table slot helper - linear search for item with given key through the given blob - const version */

    16

	FORCEINLINE const Titem_* Find(const Key& key) const

    17

	{

    18

		for (const Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {

    19

			if (pItem->GetKey() == key) {

    20

				// we have found the item, return it

    21

				return pItem;

    22

			}

    23

		}

    24

		return NULL;

    25

	}

    26

    27

	/** hash table slot helper - linear search for item with given key through the given blob - non-const version */

    28

	FORCEINLINE Titem_* Find(const Key& key)

    29

	{

    30

		for (Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {

    31

			if (pItem->GetKey() == key) {

    32

				// we have found the item, return it

    33

				return pItem;

    34

			}

    35

		}

    36

		return NULL;

    37

	}

    38

    39

	/** hash table slot helper - add new item to the slot */

    40

	FORCEINLINE void Attach(Titem_& new_item)

    41

	{

    42

		assert(new_item.GetHashNext() == NULL);

    43

		new_item.SetHashNext(m_pFirst);

    44

		m_pFirst = &new_item;

    45

	}

    46

    47

	/** hash table slot helper - remove item from a slot */

    48

	FORCEINLINE bool Detach(Titem_& item_to_remove)

    49

	{

    50

		if (m_pFirst == &item_to_remove) {

    51

			m_pFirst = item_to_remove.GetHashNext();

    52

			item_to_remove.SetHashNext(NULL);

    53

			return true;

    54

		}

    55

		Titem_* pItem = m_pFirst;

    56

		while (true) {

    57

			if (pItem == NULL) {

    58

				return false;

    59

			}

    60

			Titem_* pNextItem = pItem->GetHashNext();

    61

			if (pNextItem == &item_to_remove) break;

    62

			pItem = pNextItem;

    63

		}

    64

		pItem->SetHashNext(item_to_remove.GetHashNext());

    65

		item_to_remove.SetHashNext(NULL);

    66

		return true;

    67

	}

    68

    69

	/** hash table slot helper - remove and return item from a slot */

    70

	FORCEINLINE Titem_* Detach(const Key& key)

    71

	{

    72

		// do we have any items?

    73

		if (m_pFirst == NULL) {

    74

			return NULL;

    75

		}

    76

		// is it our first item?

    77

		if (m_pFirst->GetKey() == key) {

    78

			Titem_& ret_item = *m_pFirst;

    79

			m_pFirst = m_pFirst->GetHashNext();

    80

			ret_item.SetHashNext(NULL);

    81

			return &ret_item;

    82

		}

    83

		// find it in the following items

    84

		Titem_* pPrev = m_pFirst;

    85

		for (Titem_* pItem = m_pFirst->GetHashNext(); pItem != NULL; pPrev = pItem, pItem = pItem->GetHashNext()) {

    86

			if (pItem->GetKey() == key) {

    87

				// we have found the item, unlink and return it

    88

				pPrev->SetHashNext(pItem->GetHashNext());

    89

				pItem->SetHashNext(NULL);

    90

				return pItem;

    91

			}

    92

		}

    93

		return NULL;

    94

	}

    95

};

    96

    97

/** @class CHashTableT<Titem, Thash_bits> - simple hash table

    98

 *  of pointers allocated elsewhere.

    99

 *

   100

 *  Supports: Add/Find/Remove of Titems.

   101

 *

   102

 *  Your Titem must meet some extra requirements to be CHashTableT

   103

 *  compliant:

   104

 *    - its constructor/destructor (if any) must be public

   105

 *    - if the copying of item requires an extra resource management,

   106

 *        you must define also copy constructor

   107

 *    - must support nested type (struct, class or typedef) Titem::Key

   108

 *        that defines the type of key class for that item

   109

 *    - must support public method:

   110

 *        const Key& GetKey() const; // return the item's key object

   111

 *

   112

 *  In addition, the Titem::Key class must support:

   113

 *    - public method that calculates key's hash:

   114

 *        int CalcHash() const;

   115

 *    - public 'equality' operator to compare the key with another one

   116

 *        bool operator == (const Key& other) const;

   117

 */

   118

template <class Titem_, int Thash_bits_>

   119

class CHashTableT {

   120

public:

   121

	typedef Titem_ Titem;                         // make Titem_ visible from outside of class

   122

	typedef typename Titem_::Key Tkey;            // make Titem_::Key a property of HashTable

   123

	static const int Thash_bits = Thash_bits_;    // publish num of hash bits

   124

	static const int Tcapacity = 1 << Thash_bits; // and num of slots 2^bits

   125

   126

protected:

   127

	/** each slot contains pointer to the first item in the list,

   128

	 *  Titem contains pointer to the next item - GetHashNext(), SetHashNext() */

   129

	typedef CHashTableSlotT<Titem_> Slot;

   130

   131

	Slot*  m_slots;     // here we store our data (array of blobs)

   132

	int    m_num_items; // item counter

   133

   134

public:

   135

	// default constructor

   136

	FORCEINLINE CHashTableT()

   137

	{

   138

		// construct all slots

   139

		m_slots = new Slot[Tcapacity];

   140

		m_num_items = 0;

   141

	}

   142

   143

	~CHashTableT() {delete [] m_slots; m_num_items = 0; m_slots = NULL;}

   144

   145

protected:

   146

	/** static helper - return hash for the given key modulo number of slots */

   147

	FORCEINLINE static int CalcHash(const Tkey& key)

   148

	{

   149

		int32 hash = key.CalcHash();

   150

		if ((8 * Thash_bits) < 32) hash ^= hash >> (min(8 * Thash_bits, 31));

   151

		if ((4 * Thash_bits) < 32) hash ^= hash >> (min(4 * Thash_bits, 31));

   152

		if ((2 * Thash_bits) < 32) hash ^= hash >> (min(2 * Thash_bits, 31));

   153

		if ((1 * Thash_bits) < 32) hash ^= hash >> (min(1 * Thash_bits, 31));

   154

		hash &= (1 << Thash_bits) - 1;

   155

		return hash;

   156

	}

   157

   158

	/** static helper - return hash for the given item modulo number of slots */

   159

	FORCEINLINE static int CalcHash(const Titem_& item) {return CalcHash(item.GetKey());}

   160

   161

public:

   162

	/** item count */

   163

	FORCEINLINE int Count() const {return m_num_items;}

   164

   165

	/** const item search */

   166

	const Titem_* Find(const Tkey& key) const

   167

	{

   168

		int hash = CalcHash(key);

   169

		const Slot& slot = m_slots[hash];

   170

		const Titem_* item = slot.Find(key);

   171

		return item;

   172

	}

   173

   174

	/** non-const item search */

   175

	Titem_* Find(const Tkey& key)

   176

	{

   177

		int hash = CalcHash(key);

   178

		Slot& slot = m_slots[hash];

   179

		Titem_* item = slot.Find(key);

   180

		return item;

   181

	}

   182

   183

	/** non-const item search & optional removal (if found) */

   184

	Titem_* TryPop(const Tkey& key)

   185

	{

   186

		int hash = CalcHash(key);

   187

		Slot& slot = m_slots[hash];

   188

		Titem_* item = slot.Detach(key);

   189

		if (item != NULL) {

   190

			m_num_items--;

   191

		}

   192

		return item;

   193

	}

   194

   195

	/** non-const item search & removal */

   196

	Titem_& Pop(const Tkey& key)

   197

	{

   198

		Titem_* item = TryPop(key);

   199

		assert(item != NULL);

   200

		return *item;

   201

	}

   202

   203

	/** non-const item search & optional removal (if found) */

   204

	bool TryPop(Titem_& item)

   205

	{

   206

		const Tkey& key = item.GetKey();

   207

		int hash = CalcHash(key);

   208

		Slot& slot = m_slots[hash];

   209

		bool ret = slot.Detach(item);

   210

		if (ret) {

   211

			m_num_items--;

   212

		}

   213

		return ret;

   214

	}

   215

   216

	/** non-const item search & removal */

   217

	void Pop(Titem_& item)

   218

	{

   219

		bool ret = TryPop(item);

   220

		assert(ret);

   221

	}

   222

   223

	/** add one item - copy it from the given item */

   224

	void Push(Titem_& new_item)

   225

	{

   226

		int hash = CalcHash(new_item);

   227

		Slot& slot = m_slots[hash];

   228

		assert(slot.Find(new_item.GetKey()) == NULL);

   229

		slot.Attach(new_item);

   230

		m_num_items++;

   231

	}

   232

};

   233

   234

#endif /* HASHTABLE_HPP */