| 1805 |
yogev_ezra |
1 |
#if !defined(HASH_TABLE_H) |
|
|
2 |
#define HASH_TABLE_H |
|
|
3 |
|
|
|
4 |
template |
|
|
5 |
class THashTable |
|
|
6 |
{ |
|
|
7 |
public: |
|
|
8 |
THashTable(int _m = -1) {MemInit(_m);} |
|
|
9 |
~THashTable() {null();} |
|
|
10 |
|
|
|
11 |
int hash1(const TypeString &x) const {return func1(x);} |
|
|
12 |
int hash2(const TypeString &x) const {return 2*func2(x) + 1;} |
|
|
13 |
|
|
|
14 |
void null(); |
|
|
15 |
int IsNull() const {return M >= 0;} |
|
|
16 |
int NumElem() const {return n;} |
|
|
17 |
int MaxNumElem() const {return stack_size;} |
|
|
18 |
int GetM() const {return M;} |
|
|
19 |
int TableSize() const {return 1 << M;} |
|
|
20 |
|
|
|
21 |
void resize(int _m); |
|
|
22 |
void push(const T &x); |
|
|
23 |
T *find(const TypeString &x); |
|
|
24 |
void pop(); |
|
|
25 |
|
|
|
26 |
T &last() {return stack[n-1];} |
|
|
27 |
const T &last() const {return stack[n-1];} |
|
|
28 |
T &first() {return stack[0];} |
|
|
29 |
const T &first() const {return stack[0];} |
|
|
30 |
T &operator[](int i) {return stack[i];} |
|
|
31 |
const T &operator[](int i) const {return stack[i];} |
|
|
32 |
T *operator()() {return stack;} |
|
|
33 |
const T *operator()() const {return stack;} |
|
|
34 |
protected: |
|
|
35 |
void _push(const T &x); |
|
|
36 |
int _find_pointer(const T *p) const; |
|
|
37 |
int _find(const TypeString &x) const; |
|
|
38 |
void MemInit(int _m); |
|
|
39 |
protected: |
|
|
40 |
int M; |
|
|
41 |
int stack_size; |
|
|
42 |
int n; |
|
|
43 |
T **table; |
|
|
44 |
T *stack; |
|
|
45 |
protected: |
|
|
46 |
HashFunction func1, func2; |
|
|
47 |
}; |
|
|
48 |
|
|
|
49 |
template |
|
|
50 |
void THashTable::null() |
|
|
51 |
{ |
|
|
52 |
if (table) delete[] table; |
|
|
53 |
if (stack) delete[] stack; |
|
|
54 |
M = -1; |
|
|
55 |
table = 0; |
|
|
56 |
stack = 0; |
|
|
57 |
stack_size = 0; |
|
|
58 |
n = 0; |
|
|
59 |
func1.init(-1); |
|
|
60 |
func2.init(-1); |
|
|
61 |
} |
|
|
62 |
|
|
|
63 |
template |
|
|
64 |
void THashTable::resize(int _m) |
|
|
65 |
{ |
|
|
66 |
delete[] table; |
|
|
67 |
T *stp = stack; |
|
|
68 |
int np = n; |
|
|
69 |
MemInit(_m); |
|
|
70 |
for (int i = 0; i < np && n < stack_size; i++) _push(stp[i]); |
|
|
71 |
if (stp) delete[] stp; |
|
|
72 |
} |
|
|
73 |
|
|
|
74 |
template |
|
|
75 |
inline void THashTable::push(const T &x) |
|
|
76 |
{ |
|
|
77 |
if (n == stack_size) resize(M + 1); |
|
|
78 |
_push(x); |
|
|
79 |
} |
|
|
80 |
|
|
|
81 |
template |
|
|
82 |
inline T *THashTable::find(const TypeString &x) |
|
|
83 |
{ |
|
|
84 |
int i = _find(x); |
|
|
85 |
if (i >= 0) return table[i]; |
|
|
86 |
else return 0; |
|
|
87 |
} |
|
|
88 |
|
|
|
89 |
template |
|
|
90 |
inline void THashTable::pop() |
|
|
91 |
{ |
|
|
92 |
if (n > 0) |
|
|
93 |
{ |
|
|
94 |
n--; |
|
|
95 |
int i = _find_pointer(stack + n); |
|
|
96 |
if (i >= 0) table[i] = NULL; |
|
|
97 |
} |
|
|
98 |
} |
|
|
99 |
|
|
|
100 |
template |
|
|
101 |
void THashTable::_push(const T &x) |
|
|
102 |
{ |
|
|
103 |
int h1 = hash1(x); |
|
|
104 |
int h2 = hash2(x); |
|
|
105 |
int i = h1; |
|
|
106 |
stack[n] = x; |
|
|
107 |
do |
|
|
108 |
{ |
|
|
109 |
if (table[i] == NULL) |
|
|
110 |
{ |
|
|
111 |
table[i] = stack + n; |
|
|
112 |
break; |
|
|
113 |
} |
|
|
114 |
i = (i + h2) & ((1 << M) - 1); |
|
|
115 |
} |
|
|
116 |
while (i != h1); |
|
|
117 |
n++; |
|
|
118 |
} |
|
|
119 |
|
|
|
120 |
template |
|
|
121 |
int THashTable::_find_pointer(const T *p) const |
|
|
122 |
{ |
|
|
123 |
if (n > 0) |
|
|
124 |
{ |
|
|
125 |
int h1 = hash1(*p); |
|
|
126 |
int h2 = hash2(*p); |
|
|
127 |
int i = h1; |
|
|
128 |
do |
|
|
129 |
{ |
|
|
130 |
if (table[i] == NULL) break; |
|
|
131 |
if (table[i] == p) return i; |
|
|
132 |
i = (i + h2) & ((1 << M) - 1); |
|
|
133 |
} |
|
|
134 |
while (i != h1); |
|
|
135 |
} |
|
|
136 |
return -1; |
|
|
137 |
} |
|
|
138 |
|
|
|
139 |
template |
|
|
140 |
int THashTable::_find(const TypeString &x) const |
|
|
141 |
{ |
|
|
142 |
if (n > 0) |
|
|
143 |
{ |
|
|
144 |
int h1 = hash1(x); |
|
|
145 |
int h2 = hash2(x); |
|
|
146 |
int i = h1; |
|
|
147 |
do |
|
|
148 |
{ |
|
|
149 |
if (table[i] == NULL) break; |
|
|
150 |
if ((*table[i]) == x) return i; |
|
|
151 |
i = (i + h2) & ((1 << M) - 1); |
|
|
152 |
} |
|
|
153 |
while (i != h1); |
|
|
154 |
} |
|
|
155 |
return -1; |
|
|
156 |
} |
|
|
157 |
|
|
|
158 |
template |
|
|
159 |
void THashTable::MemInit(int _m) |
|
|
160 |
{ |
|
|
161 |
M = _m; |
|
|
162 |
if (M < 0) |
|
|
163 |
{ |
|
|
164 |
M = -1; |
|
|
165 |
stack_size = 0; |
|
|
166 |
table = 0; |
|
|
167 |
stack = 0; |
|
|
168 |
n = 0; |
|
|
169 |
func1.init(-1); |
|
|
170 |
func2.init(-1); |
|
|
171 |
} |
|
|
172 |
else |
|
|
173 |
{ |
|
|
174 |
if (M < 3) M = 3; |
|
|
175 |
stack_size = (1 << M) / 3; |
|
|
176 |
table = new T*[1 << M]; |
|
|
177 |
for (int i = 0; i < (1 << M); i++) table[i] = NULL; |
|
|
178 |
stack = new T[stack_size]; |
|
|
179 |
n = 0; |
|
|
180 |
func1.init(M); |
|
|
181 |
func2.init(M-1); |
|
|
182 |
} |
|
|
183 |
} |
|
|
184 |
|
|
|
185 |
#endif // HASH_TABLE_H |