author | peter1138 |
Sun, 01 Oct 2006 12:00:32 +0000 | |
changeset 4694 | c917a3ad0dd2 |
parent 4549 | 106ed18a7675 |
child 5081 | fe3a6da19d9f |
permissions | -rw-r--r-- |
3900
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
1 |
/* $Id$ */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
2 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
3 |
#ifndef HASHTABLE_HPP |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
4 |
#define HASHTABLE_HPP |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
5 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
6 |
template <class Titem_> |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
7 |
struct CHashTableSlotT |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
8 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
9 |
typedef typename Titem_::Key Key; // make Titem_::Key a property of HashTable |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
10 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
11 |
Titem_* m_pFirst; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
12 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
13 |
CHashTableSlotT() : m_pFirst(NULL) {} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
14 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
15 |
/** hash table slot helper - linear search for item with given key through the given blob - const version */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
16 |
FORCEINLINE const Titem_& Find(const Key& key) const |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
17 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
18 |
for (const Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
19 |
if (pItem->GetKey() == key) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
20 |
// we have found the item, return it |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
21 |
return *pItem; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
22 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
23 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
24 |
return *(Titem_*)NULL; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
25 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
26 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
27 |
/** hash table slot helper - linear search for item with given key through the given blob - non-const version */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
28 |
FORCEINLINE Titem_& Find(const Key& key) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
29 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
30 |
for (Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
31 |
if (pItem->GetKey() == key) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
32 |
// we have found the item, return it |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
33 |
return *pItem; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
34 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
35 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
36 |
return *(Titem_*)NULL; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
37 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
38 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
39 |
/** hash table slot helper - add new item to the slot */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
40 |
FORCEINLINE void Attach(Titem_& new_item) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
41 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
42 |
assert(new_item.GetHashNext() == NULL); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
43 |
new_item.SetHashNext(m_pFirst); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
44 |
m_pFirst = &new_item; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
45 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
46 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
47 |
/** hash table slot helper - remove item from a slot */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
48 |
FORCEINLINE bool Detach(Titem_& item_to_remove) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
49 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
50 |
if (m_pFirst == &item_to_remove) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
51 |
m_pFirst = item_to_remove.GetHashNext(); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
52 |
item_to_remove.SetHashNext(NULL); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
53 |
return true; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
54 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
55 |
Titem_* pItem = m_pFirst; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
56 |
while (true) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
57 |
if (pItem == NULL) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
58 |
return false; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
59 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
60 |
Titem_* pNextItem = pItem->GetHashNext(); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
61 |
if (pNextItem == &item_to_remove) break; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
62 |
pItem = pNextItem; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
63 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
64 |
pItem->SetHashNext(item_to_remove.GetHashNext()); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
65 |
item_to_remove.SetHashNext(NULL); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
66 |
return true; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
67 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
68 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
69 |
/** hash table slot helper - remove and return item from a slot */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
70 |
FORCEINLINE Titem_& Detach(const Key& key) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
71 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
72 |
// do we have any items? |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
73 |
if (m_pFirst == NULL) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
74 |
return *(Titem_*)NULL; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
75 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
76 |
// is it our first item? |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
77 |
if (m_pFirst->GetKey() == key) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
78 |
Titem_& ret_item = *m_pFirst; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
79 |
m_pFirst = m_pFirst->GetHashNext(); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
80 |
ret_item.SetHashNext(NULL); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
81 |
return ret_item; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
82 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
83 |
// find it in the following items |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
84 |
Titem_* pPrev = m_pFirst; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
85 |
for (Titem_* pItem = m_pFirst->GetHashNext(); pItem != NULL; pPrev = pItem, pItem = pItem->GetHashNext()) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
86 |
if (pItem->GetKey() == key) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
87 |
// we have found the item, unlink and return it |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
88 |
pPrev->SetHashNext(pItem->GetHashNext()); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
89 |
pItem->SetHashNext(NULL); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
90 |
return *pItem; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
91 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
92 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
93 |
return *(Titem_*)NULL; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
94 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
95 |
}; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
96 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
97 |
/** @class CHashTableT<Titem, Thash_bits> - simple hash table |
4549
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
98 |
* of pointers allocated elsewhere. |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
99 |
* |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
100 |
* Supports: Add/Find/Remove of Titems. |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
101 |
* |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
102 |
* Your Titem must meet some extra requirements to be CHashTableT |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
103 |
* compliant: |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
104 |
* - its constructor/destructor (if any) must be public |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
105 |
* - if the copying of item requires an extra resource management, |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
106 |
* you must define also copy constructor |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
107 |
* - must support nested type (struct, class or typedef) Titem::Key |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
108 |
* that defines the type of key class for that item |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
109 |
* - must support public method: |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
110 |
* const Key& GetKey() const; // return the item's key object |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
111 |
* |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
112 |
* In addition, the Titem::Key class must support: |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
113 |
* - public method that calculates key's hash: |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
114 |
* int CalcHash() const; |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
115 |
* - public 'equality' operator to compare the key with another one |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
116 |
* bool operator == (const Key& other) const; |
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
117 |
*/ |
3900
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
118 |
template <class Titem_, int Thash_bits_> |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
119 |
class CHashTableT { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
120 |
public: |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
121 |
typedef Titem_ Titem; // make Titem_ visible from outside of class |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
122 |
typedef typename Titem_::Key Tkey; // make Titem_::Key a property of HashTable |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
123 |
ST_CONST(int, Thash_bits = Thash_bits_); // publish num of hash bits |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
124 |
ST_CONST(int, Tcapacity = 1 << Thash_bits); // and num of slots 2^bits |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
125 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
126 |
protected: |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
127 |
/** each slot contains pointer to the first item in the list, |
4549
106ed18a7675
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
3900
diff
changeset
|
128 |
* Titem contains pointer to the next item - GetHashNext(), SetHashNext() */ |
3900
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
129 |
typedef CHashTableSlotT<Titem_> Slot; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
130 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
131 |
Slot* m_slots; // here we store our data (array of blobs) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
132 |
int m_num_items; // item counter |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
133 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
134 |
public: |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
135 |
// default constructor |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
136 |
FORCEINLINE CHashTableT() |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
137 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
138 |
// construct all slots |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
139 |
m_slots = new Slot[Tcapacity]; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
140 |
m_num_items = 0; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
141 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
142 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
143 |
~CHashTableT() {delete [] m_slots; m_num_items = 0; m_slots = NULL;} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
144 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
145 |
protected: |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
146 |
/** static helper - return hash for the given key modulo number of slots */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
147 |
FORCEINLINE static int CalcHash(const Tkey& key) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
148 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
149 |
int32 hash = key.CalcHash(); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
150 |
if ((8 * Thash_bits) < 32) hash ^= hash >> (min(8 * Thash_bits, 31)); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
151 |
if ((4 * Thash_bits) < 32) hash ^= hash >> (min(4 * Thash_bits, 31)); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
152 |
if ((2 * Thash_bits) < 32) hash ^= hash >> (min(2 * Thash_bits, 31)); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
153 |
if ((1 * Thash_bits) < 32) hash ^= hash >> (min(1 * Thash_bits, 31)); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
154 |
hash &= (1 << Thash_bits) - 1; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
155 |
return hash; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
156 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
157 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
158 |
/** static helper - return hash for the given item modulo number of slots */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
159 |
FORCEINLINE static int CalcHash(const Titem_& item) {return CalcHash(item.GetKey());} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
160 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
161 |
public: |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
162 |
/** item count */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
163 |
FORCEINLINE int Count() const {return m_num_items;} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
164 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
165 |
/** const item search */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
166 |
const Titem_& Find(const Tkey& key) const |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
167 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
168 |
int hash = CalcHash(key); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
169 |
const Slot& slot = m_slots[hash]; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
170 |
const Titem_& item = slot.Find(key); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
171 |
return item; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
172 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
173 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
174 |
/** non-const item search */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
175 |
Titem_& Find(const Tkey& key) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
176 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
177 |
int hash = CalcHash(key); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
178 |
Slot& slot = m_slots[hash]; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
179 |
Titem_& item = slot.Find(key); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
180 |
return item; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
181 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
182 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
183 |
/** non-const item search & optional removal (if found) */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
184 |
Titem_& TryPop(const Tkey& key) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
185 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
186 |
int hash = CalcHash(key); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
187 |
Slot& slot = m_slots[hash]; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
188 |
Titem_& item = slot.Detach(key); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
189 |
if (&item != NULL) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
190 |
m_num_items--; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
191 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
192 |
return item; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
193 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
194 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
195 |
/** non-const item search & removal */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
196 |
Titem_& Pop(const Tkey& key) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
197 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
198 |
Titem_& item = TryPop(key); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
199 |
assert(&item != NULL); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
200 |
return item; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
201 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
202 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
203 |
/** non-const item search & optional removal (if found) */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
204 |
bool TryPop(Titem_& item) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
205 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
206 |
const Tkey& key = item.GetKey(); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
207 |
int hash = CalcHash(key); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
208 |
Slot& slot = m_slots[hash]; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
209 |
bool ret = slot.Detach(item); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
210 |
if (ret) { |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
211 |
m_num_items--; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
212 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
213 |
return ret; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
214 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
215 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
216 |
/** non-const item search & removal */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
217 |
void Pop(Titem_& item) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
218 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
219 |
bool ret = TryPop(item); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
220 |
assert(ret); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
221 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
222 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
223 |
/** add one item - copy it from the given item */ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
224 |
void Push(Titem_& new_item) |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
225 |
{ |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
226 |
int hash = CalcHash(new_item); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
227 |
Slot& slot = m_slots[hash]; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
228 |
assert(&slot.Find(new_item.GetKey()) == NULL); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
229 |
slot.Attach(new_item); |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
230 |
m_num_items++; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
231 |
} |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
232 |
}; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
233 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
234 |
#endif /* HASHTABLE_HPP */ |