1

/* $Id$ */

     2

     3

/** @file hashtable.hpp Hash table support. */

     4

     5

#ifndef  HASHTABLE_HPP

     6

#define  HASHTABLE_HPP

     7

     8

template <class Titem_>

     9

struct CHashTableSlotT

    10

{

    11

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

    12

    13

	Titem_*    m_pFirst;

    14

    15

	CHashTableSlotT() : m_pFirst(NULL) {}

    16

    17

	/** hash table slot helper - clears the slot by simple forgetting its items */

    18

	FORCEINLINE void Clear() {m_pFirst = NULL;}

    19

    20

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

    21

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

    22

	{

    23

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

    24

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

    25

				// we have found the item, return it

    26

				return pItem;

    27

			}

    28

		}

    29

		return NULL;

    30

	}

    31

    32

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

    33

	FORCEINLINE Titem_* Find(const Key& key)

    34

	{

    35

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

    36

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

    37

				// we have found the item, return it

    38

				return pItem;

    39

			}

    40

		}

    41

		return NULL;

    42

	}

    43

    44

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

    45

	FORCEINLINE void Attach(Titem_& new_item)

    46

	{

    47

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

    48

		new_item.SetHashNext(m_pFirst);

    49

		m_pFirst = &new_item;

    50

	}

    51

    52

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

    53

	FORCEINLINE bool Detach(Titem_& item_to_remove)

    54

	{

    55

		if (m_pFirst == &item_to_remove) {

    56

			m_pFirst = item_to_remove.GetHashNext();

    57

			item_to_remove.SetHashNext(NULL);

    58

			return true;

    59

		}

    60

		Titem_* pItem = m_pFirst;

    61

		while (true) {

    62

			if (pItem == NULL) {

    63

				return false;

    64

			}

    65

			Titem_* pNextItem = pItem->GetHashNext();

    66

			if (pNextItem == &item_to_remove) break;

    67

			pItem = pNextItem;

    68

		}

    69

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

    70

		item_to_remove.SetHashNext(NULL);

    71

		return true;

    72

	}

    73

    74

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

    75

	FORCEINLINE Titem_* Detach(const Key& key)

    76

	{

    77

		// do we have any items?

    78

		if (m_pFirst == NULL) {

    79

			return NULL;

    80

		}

    81

		// is it our first item?

    82

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

    83

			Titem_& ret_item = *m_pFirst;

    84

			m_pFirst = m_pFirst->GetHashNext();

    85

			ret_item.SetHashNext(NULL);

    86

			return &ret_item;

    87

		}

    88

		// find it in the following items

    89

		Titem_* pPrev = m_pFirst;

    90

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

    91

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

    92

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

    93

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

    94

				pItem->SetHashNext(NULL);

    95

				return pItem;

    96

			}

    97

		}

    98

		return NULL;

    99

	}

   100

};

   101

   102

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

   103

 *  of pointers allocated elsewhere.

   104

 *

   105

 *  Supports: Add/Find/Remove of Titems.

   106

 *

   107

 *  Your Titem must meet some extra requirements to be CHashTableT

   108

 *  compliant:

   109

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

   110

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

   111

 *        you must define also copy constructor

   112

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

   113

 *        that defines the type of key class for that item

   114

 *    - must support public method:

   115

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

   116

 *

   117

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

   118

 *    - public method that calculates key's hash:

   119

 *        int CalcHash() const;

   120

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

   121

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

   122

 */

   123

template <class Titem_, int Thash_bits_>

   124

class CHashTableT {

   125

public:

   126

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

   127

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

   128

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

   129

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

   130

   131

protected:

   132

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

   133

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

   134

	typedef CHashTableSlotT<Titem_> Slot;

   135

   136

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

   137

	int    m_num_items; // item counter

   138

   139

public:

   140

	// default constructor

   141

	FORCEINLINE CHashTableT()

   142

	{

   143

		// construct all slots

   144

		m_slots = new Slot[Tcapacity];

   145

		m_num_items = 0;

   146

	}

   147

   148

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

   149

   150

protected:

   151

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

   152

	FORCEINLINE static int CalcHash(const Tkey& key)

   153

	{

   154

		int32 hash = key.CalcHash();

   155

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

   156

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

   157

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

   158

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

   159

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

   160

		return hash;

   161

	}

   162

   163

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

   164

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

   165

   166

public:

   167

	/** item count */

   168

	FORCEINLINE int Count() const {return m_num_items;}

   169

   170

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

   171

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

   172

   173

	/** const item search */

   174

	const Titem_* Find(const Tkey& key) const

   175

	{

   176

		int hash = CalcHash(key);

   177

		const Slot& slot = m_slots[hash];

   178

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

   179

		return item;

   180

	}

   181

   182

	/** non-const item search */

   183

	Titem_* Find(const Tkey& key)

   184

	{

   185

		int hash = CalcHash(key);

   186

		Slot& slot = m_slots[hash];

   187

		Titem_* item = slot.Find(key);

   188

		return item;

   189

	}

   190

   191

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

   192

	Titem_* TryPop(const Tkey& key)

   193

	{

   194

		int hash = CalcHash(key);

   195

		Slot& slot = m_slots[hash];

   196

		Titem_* item = slot.Detach(key);

   197

		if (item != NULL) {

   198

			m_num_items--;

   199

		}

   200

		return item;

   201

	}

   202

   203

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

   204

	Titem_& Pop(const Tkey& key)

   205

	{

   206

		Titem_* item = TryPop(key);

   207

		assert(item != NULL);

   208

		return *item;

   209

	}

   210

   211

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

   212

	bool TryPop(Titem_& item)

   213

	{

   214

		const Tkey& key = item.GetKey();

   215

		int hash = CalcHash(key);

   216

		Slot& slot = m_slots[hash];

   217

		bool ret = slot.Detach(item);

   218

		if (ret) {

   219

			m_num_items--;

   220

		}

   221

		return ret;

   222

	}

   223

   224

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

   225

	void Pop(Titem_& item)

   226

	{

   227

		bool ret = TryPop(item);

   228

		assert(ret);

   229

	}

   230

   231

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

   232

	void Push(Titem_& new_item)

   233

	{

   234

		int hash = CalcHash(new_item);

   235

		Slot& slot = m_slots[hash];

   236

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

   237

		slot.Attach(new_item);

   238

		m_num_items++;

   239

	}

   240

};

   241

   242

#endif /* HASHTABLE_HPP */