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 - clears the slot by simple forgetting its items */

    16

	FORCEINLINE void Clear() {m_pFirst = NULL;}

    17

    18

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

    19

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

    20

	{

    21

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

    22

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

    23

				// we have found the item, return it

    24

				return pItem;

    25

			}

    26

		}

    27

		return NULL;

    28

	}

    29

    30

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

    31

	FORCEINLINE Titem_* Find(const Key& key)

    32

	{

    33

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

    34

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

    35

				// we have found the item, return it

    36

				return pItem;

    37

			}

    38

		}

    39

		return NULL;

    40

	}

    41

    42

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

    43

	FORCEINLINE void Attach(Titem_& new_item)

    44

	{

    45

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

    46

		new_item.SetHashNext(m_pFirst);

    47

		m_pFirst = &new_item;

    48

	}

    49

    50

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

    51

	FORCEINLINE bool Detach(Titem_& item_to_remove)

    52

	{

    53

		if (m_pFirst == &item_to_remove) {

    54

			m_pFirst = item_to_remove.GetHashNext();

    55

			item_to_remove.SetHashNext(NULL);

    56

			return true;

    57

		}

    58

		Titem_* pItem = m_pFirst;

    59

		while (true) {

    60

			if (pItem == NULL) {

    61

				return false;

    62

			}

    63

			Titem_* pNextItem = pItem->GetHashNext();

    64

			if (pNextItem == &item_to_remove) break;

    65

			pItem = pNextItem;

    66

		}

    67

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

    68

		item_to_remove.SetHashNext(NULL);

    69

		return true;

    70

	}

    71

    72

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

    73

	FORCEINLINE Titem_* Detach(const Key& key)

    74

	{

    75

		// do we have any items?

    76

		if (m_pFirst == NULL) {

    77

			return NULL;

    78

		}

    79

		// is it our first item?

    80

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

    81

			Titem_& ret_item = *m_pFirst;

    82

			m_pFirst = m_pFirst->GetHashNext();

    83

			ret_item.SetHashNext(NULL);

    84

			return &ret_item;

    85

		}

    86

		// find it in the following items

    87

		Titem_* pPrev = m_pFirst;

    88

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

    89

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

    90

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

    91

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

    92

				pItem->SetHashNext(NULL);

    93

				return pItem;

    94

			}

    95

		}

    96

		return NULL;

    97

	}

    98

};

    99

   100

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

   101

 *  of pointers allocated elsewhere.

   102

 *

   103

 *  Supports: Add/Find/Remove of Titems.

   104

 *

   105

 *  Your Titem must meet some extra requirements to be CHashTableT

   106

 *  compliant:

   107

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

   108

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

   109

 *        you must define also copy constructor

   110

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

   111

 *        that defines the type of key class for that item

   112

 *    - must support public method:

   113

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

   114

 *

   115

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

   116

 *    - public method that calculates key's hash:

   117

 *        int CalcHash() const;

   118

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

   119

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

   120

 */

   121

template <class Titem_, int Thash_bits_>

   122

class CHashTableT {

   123

public:

   124

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

   125

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

   126

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

   127

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

   128

   129

protected:

   130

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

   131

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

   132

	typedef CHashTableSlotT<Titem_> Slot;

   133

   134

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

   135

	int    m_num_items; // item counter

   136

   137

public:

   138

	// default constructor

   139

	FORCEINLINE CHashTableT()

   140

	{

   141

		// construct all slots

   142

		m_slots = new Slot[Tcapacity];

   143

		m_num_items = 0;

   144

	}

   145

   146

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

   147

   148

protected:

   149

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

   150

	FORCEINLINE static int CalcHash(const Tkey& key)

   151

	{

   152

		int32 hash = key.CalcHash();

   153

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

   154

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

   155

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

   156

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

   157

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

   158

		return hash;

   159

	}

   160

   161

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

   162

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

   163

   164

public:

   165

	/** item count */

   166

	FORCEINLINE int Count() const {return m_num_items;}

   167

   168

	/** simple clear - forget all items - used by CSegmentCostCacheT.Flush() */

   169

	FORCEINLINE void Clear() const {for (int i = 0; i < Tcapacity; i++) m_slots[i].Clear();}

   170

   171

	/** const item search */

   172

	const Titem_* Find(const Tkey& key) const

   173

	{

   174

		int hash = CalcHash(key);

   175

		const Slot& slot = m_slots[hash];

   176

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

   177

		return item;

   178

	}

   179

   180

	/** non-const item search */

   181

	Titem_* Find(const Tkey& key)

   182

	{

   183

		int hash = CalcHash(key);

   184

		Slot& slot = m_slots[hash];

   185

		Titem_* item = slot.Find(key);

   186

		return item;

   187

	}

   188

   189

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

   190

	Titem_* TryPop(const Tkey& key)

   191

	{

   192

		int hash = CalcHash(key);

   193

		Slot& slot = m_slots[hash];

   194

		Titem_* item = slot.Detach(key);

   195

		if (item != NULL) {

   196

			m_num_items--;

   197

		}

   198

		return item;

   199

	}

   200

   201

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

   202

	Titem_& Pop(const Tkey& key)

   203

	{

   204

		Titem_* item = TryPop(key);

   205

		assert(item != NULL);

   206

		return *item;

   207

	}

   208

   209

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

   210

	bool TryPop(Titem_& item)

   211

	{

   212

		const Tkey& key = item.GetKey();

   213

		int hash = CalcHash(key);

   214

		Slot& slot = m_slots[hash];

   215

		bool ret = slot.Detach(item);

   216

		if (ret) {

   217

			m_num_items--;

   218

		}

   219

		return ret;

   220

	}

   221

   222

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

   223

	void Pop(Titem_& item)

   224

	{

   225

		bool ret = TryPop(item);

   226

		assert(ret);

   227

	}

   228

   229

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

   230

	void Push(Titem_& new_item)

   231

	{

   232

		int hash = CalcHash(new_item);

   233

		Slot& slot = m_slots[hash];

   234

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

   235

		slot.Attach(new_item);

   236

		m_num_items++;

   237

	}

   238

};

   239

   240

#endif /* HASHTABLE_HPP */