8 #include "wvscatterhash.h"
12 const unsigned WvScatterHashBase::prime_numbers[]
15 509u, 1021u, 2039u, 4093u,
16 8191u, 16381u, 32749u, 65521u,
17 131071u, 262139u, 524287u, 1048573u,
18 2097143u, 4194301u, 8388593u, 16777213u,
19 33554393u, 67108859u, 134217689u, 268435399u,
20 536870909u, 1073741789u, 2147483647u, 4294967281u};
25 WvScatterHashBase::WvScatterHashBase(
unsigned _numslots)
35 while ((_numslots >>= 1) != 0)
39 numslots = prime_numbers[prime_index];
40 xslots =
new Slot[numslots];
41 xstatus =
new Status[numslots];
42 memset(xslots, 0, numslots *
sizeof(xslots[0]));
43 memset(xstatus, 0, numslots *
sizeof(xstatus[0]));
46 size_t WvScatterHashBase::slowcount()
const
49 for (
unsigned index = 0; index < numslots; index++)
51 if (IS_OCCUPIED(xstatus[index]))
58 void WvScatterHashBase::rebuild()
60 if (!(numslots * REBUILD_LOAD_FACTOR <= used + 1))
63 unsigned oldnumslots = numslots;
65 if (numslots * RESIZE_LOAD_FACTOR <= num + 1)
66 numslots = prime_numbers[++prime_index];
68 Slot *tmpslots = xslots;
69 Status *tmpstatus = xstatus;
70 xslots =
new Slot[numslots];
71 xstatus =
new Status[numslots];
72 memset(xslots, 0, numslots *
sizeof(xslots[0]));
73 memset(xstatus, 0, numslots *
sizeof(xstatus[0]));
76 for (
unsigned i = 0; i < oldnumslots; i++)
78 if (IS_OCCUPIED(tmpstatus[i]))
79 _add(tmpslots[i], IS_AUTO_FREE(tmpstatus[i]));
86 void WvScatterHashBase::_add(
void *data,
bool auto_free)
88 _add(data, do_hash(data), auto_free);
91 void WvScatterHashBase::_add(
void *data,
unsigned hash,
bool auto_free)
94 unsigned slot = hash % numslots;
96 if (IS_OCCUPIED(xstatus[slot]))
99 unsigned hash2 = second_hash(hash);
101 while (IS_OCCUPIED(xstatus[slot]))
102 slot = curhash(hash, hash2, ++attempt);
106 if (!IS_DELETED(xstatus[slot]))
110 xstatus[slot] = auto_free ? 3 : 2;
113 void WvScatterHashBase::_remove(
const void *data,
unsigned hash)
115 unsigned res = genfind(data, hash);
119 if (IS_AUTO_FREE(xstatus[res]))
120 do_delete(xslots[res]);
126 void WvScatterHashBase::_zap()
128 for (
unsigned i = 0; i < numslots; i++)
130 if (IS_AUTO_FREE(xstatus[i]))
131 do_delete(xslots[i]);
139 void WvScatterHashBase::_set_autofree(
const void *data,
140 unsigned hash,
bool auto_free)
142 unsigned res = genfind(data, hash);
145 xstatus[res] = auto_free ? 3 : 2;
148 bool WvScatterHashBase::_get_autofree(
const void *data,
unsigned hash)
150 unsigned res = genfind(data, hash);
153 return IS_AUTO_FREE(xstatus[res]);
155 assert(0 &&
"You checked auto_free of a nonexistant thing.");
159 unsigned WvScatterHashBase::genfind(
const void *data,
unsigned hash)
const
161 unsigned slot = hash % numslots;
163 if (IS_OCCUPIED(xstatus[slot]) && compare(data, xslots[slot]))
166 unsigned attempt = 0;
167 unsigned hash2 = second_hash(hash);
169 while (xstatus[slot])
171 slot = curhash(hash, hash2, ++attempt);
173 if (IS_OCCUPIED(xstatus[slot]) && compare(data, xslots[slot]))
181 void *WvScatterHashBase::genfind_or_null(
const void *data,
unsigned hash)
const
183 unsigned slot = genfind(data, hash);
184 if (slot == null_idx)