18 #ifndef __LONGHASH_H__
19 #define __LONGHASH_H__
26 #define LH_NOTFOUND (UINT_MAX)
28 #define LH_NOTFOUND 0xFFFFFFFF
37 unsigned int count, size;
50 error(
"LongHash: Hash table size must be a power of two.\n");
52 occupancy =
new bool [size];
53 objects =
new ObjectT [size];
54 keys =
new long long [size];
56 allowDuplicates =
false;
58 for (
unsigned int i = 0; i < size; i++)
80 void SetSize(
int newsize)
82 int newmask = newsize - 1;
84 bool * newoccupancy =
new bool [newsize];
85 ObjectT * newobjects =
new ObjectT [newsize];
86 long long * newkeys =
new long long [newsize];
88 for (
int i = 0; i < newsize; i++)
89 newoccupancy[i] =
false;
92 for (
unsigned int i = 0; i < size; i++)
93 if (occupancy[i] !=
false)
95 long long key = keys[i];
96 unsigned int h = newmask & (
unsigned int) key;
98 while (newoccupancy[h] ==
true && (newkeys[h] != key || allowDuplicates))
99 h = (h + 1) & newmask;
105 newobjects[h] = objects[i];
106 newoccupancy[h] =
true;
113 occupancy = newoccupancy;
114 objects = newobjects;
127 for (
unsigned int i = 0; i < size; i++)
128 occupancy[i] =
false;
140 ObjectT Object(
int i)
const
144 ObjectT & Object(
int i)
149 void SetObject(
int i, ObjectT
object)
154 unsigned int Add(
long long key, ObjectT
object)
156 if (count * 2 > size)
159 unsigned int h = Iterate(key);
161 while (allowDuplicates && occupancy[h] && objects[h] !=
object)
162 h = ReIterate(key, h);
176 unsigned int Find(
long long key)
178 unsigned int h = Iterate(key);
180 return occupancy[h] ? h : LH_NOTFOUND;
183 unsigned int Rehash(
long long key,
unsigned int h)
185 h = ReIterate(key, h);
187 return occupancy[h] ? h : LH_NOTFOUND;
192 ObjectT operator [](
int i)
const
196 ObjectT operator [](
unsigned int i)
const
201 void Delete(
unsigned int index)
203 if (index >= size || !occupancy[index])
206 occupancy[index] =
false;
209 if (count * 8 < size && size > 32)
214 index = (index + 1) & mask;
216 while (occupancy[index])
218 if ((keys[index] & mask) != index)
220 unsigned int h = Iterate(keys[index]);
222 while (occupancy[h] && objects[h] != objects[index])
223 h = ReIterate(keys[index], h);
225 if (h != (
unsigned int) index)
227 keys[h] = keys[index];
229 objects[h] = objects[index];
231 occupancy[index] =
false;
235 index = (index + 1) & mask;
241 bool SlotInUse(
int index)
const
243 return occupancy[index] ==
true;
245 bool SlotInUse(
unsigned int index)
const
247 return occupancy[index] ==
true;
251 long long GetKey(
int index)
const
256 long long GetKey(
const unsigned int index)
const
261 void SetAllowDuplicateKeys(
bool toggle)
263 allowDuplicates = toggle;
265 if (count && !allowDuplicates)
270 unsigned int Iterate(
long long key)
const
272 unsigned int h = mask & (
unsigned int) key;
274 while (occupancy[h] ==
true && keys[h] != key)
280 unsigned int ReIterate(
long long key,
unsigned int h)
const
284 while (occupancy[h] ==
true && keys[h] != key)