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
12 const 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
25 WvScatterHashBase::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 
46 size_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 
58 void 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 
86 void WvScatterHashBase::_add(void *data, bool auto_free)
87 {
88  _add(data, do_hash(data), auto_free);
89 }
90 
91 void 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 
113 void 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 
126 void 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 
139 void 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 
148 bool 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 
159 unsigned 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 
181 void *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 }
deletev
#define deletev
Remplacement for delete[].
Definition: delete.h:129