WvStreams
wvscatterhash.cc
1/*
2 * Worldvisions Weaver Software:
3 * Copyright (C) 1997-2003 Net Integration Technologies, Inc.
4 *
5 * A hash table container.
6 */
7
8#include "wvscatterhash.h"
9#include <assert.h>
10
11// Prime numbers close to powers of 2
12const unsigned WvScatterHashBase::prime_numbers[]
13 = {2u, 5u, 11u, 17u,
14 31u, 67u, 127u, 251u,
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};
21
22// we do not accept the _numslots value directly. Instead, we find the
23// next number of xslots which is >= _numslots and take the closest prime
24// number
25WvScatterHashBase::WvScatterHashBase(unsigned _numslots)
26{
27 num = 0;
28 used = 0;
29
30 if (_numslots == 0)
31 prime_index = 0;
32 else
33 {
34 prime_index = 1;
35 while ((_numslots >>= 1) != 0)
36 prime_index++;
37 }
38
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]));
44}
45
46size_t WvScatterHashBase::slowcount() const
47{
48 unsigned count = 0;
49 for (unsigned index = 0; index < numslots; index++)
50 {
51 if (IS_OCCUPIED(xstatus[index]))
52 count++;
53 }
54
55 return count;
56}
57
58void WvScatterHashBase::rebuild()
59{
60 if (!(numslots * REBUILD_LOAD_FACTOR <= used + 1))
61 return;
62
63 unsigned oldnumslots = numslots;
64
65 if (numslots * RESIZE_LOAD_FACTOR <= num + 1)
66 numslots = prime_numbers[++prime_index];
67
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]));
74 used = num = 0;
75
76 for (unsigned i = 0; i < oldnumslots; i++)
77 {
78 if (IS_OCCUPIED(tmpstatus[i]))
79 _add(tmpslots[i], IS_AUTO_FREE(tmpstatus[i]));
80 }
81
82 deletev tmpslots;
83 deletev tmpstatus;
84}
85
86void WvScatterHashBase::_add(void *data, bool auto_free)
87{
88 _add(data, do_hash(data), auto_free);
89}
90
91void WvScatterHashBase::_add(void *data, unsigned hash, bool auto_free)
92{
93 rebuild();
94 unsigned slot = hash % numslots;
95
96 if (IS_OCCUPIED(xstatus[slot]))
97 {
98 unsigned attempt = 0;
99 unsigned hash2 = second_hash(hash);
100
101 while (IS_OCCUPIED(xstatus[slot]))
102 slot = curhash(hash, hash2, ++attempt);
103 }
104
105 num++;
106 if (!IS_DELETED(xstatus[slot]))
107 used++;
108
109 xslots[slot] = data;
110 xstatus[slot] = auto_free ? 3 : 2;
111}
112
113void WvScatterHashBase::_remove(const void *data, unsigned hash)
114{
115 unsigned res = genfind(data, hash);
116
117 if (res != null_idx)
118 {
119 if (IS_AUTO_FREE(xstatus[res]))
120 do_delete(xslots[res]);
121 xstatus[res] = 1;
122 num--;
123 }
124}
125
126void WvScatterHashBase::_zap()
127{
128 for (unsigned i = 0; i < numslots; i++)
129 {
130 if (IS_AUTO_FREE(xstatus[i]))
131 do_delete(xslots[i]);
132
133 xstatus[i] = 0;
134 }
135
136 used = num = 0;
137}
138
139void WvScatterHashBase::_set_autofree(const void *data,
140 unsigned hash, bool auto_free)
141{
142 unsigned res = genfind(data, hash);
143
144 if (res != null_idx)
145 xstatus[res] = auto_free ? 3 : 2;
146}
147
148bool WvScatterHashBase::_get_autofree(const void *data, unsigned hash)
149{
150 unsigned res = genfind(data, hash);
151
152 if (res != null_idx)
153 return IS_AUTO_FREE(xstatus[res]);
154
155 assert(0 && "You checked auto_free of a nonexistant thing.");
156 return false;
157}
158
159unsigned WvScatterHashBase::genfind(const void *data, unsigned hash) const
160{
161 unsigned slot = hash % numslots;
162
163 if (IS_OCCUPIED(xstatus[slot]) && compare(data, xslots[slot]))
164 return slot;
165
166 unsigned attempt = 0;
167 unsigned hash2 = second_hash(hash);
168
169 while (xstatus[slot])
170 {
171 slot = curhash(hash, hash2, ++attempt);
172
173 if (IS_OCCUPIED(xstatus[slot]) && compare(data, xslots[slot]))
174 return slot;
175 }
176
177 return null_idx;
178}
179
180
181void *WvScatterHashBase::genfind_or_null(const void *data, unsigned hash) const
182{
183 unsigned slot = genfind(data, hash);
184 if (slot == null_idx)
185 return NULL;
186 else
187 return xslots[slot];
188}
#define deletev
Remplacement for delete[].
Definition: delete.h:129