libStatGen Software 1
Loading...
Searching...
No Matches
LongHash.h
1/*
2 * Copyright (C) 2010 Regents of the University of Michigan
3 *
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18#ifndef __LONGHASH_H__
19#define __LONGHASH_H__
20
21#include "Error.h"
22
23#include <limits.h>
24
25#ifdef UINT_MAX
26#define LH_NOTFOUND (UINT_MAX)
27#else
28#define LH_NOTFOUND 0xFFFFFFFF
29#endif
30
31template <class ObjectT> class LongHash
32{
33protected:
34 ObjectT * objects;
35 long long * keys;
36 bool * occupancy;
37 unsigned int count, size;
38 unsigned int mask;
39 bool allowDuplicates;
40
41public:
42 LongHash(int startsize = 32)
43 {
44 count = 0;
45 size = startsize;
46 mask = startsize - 1;
47
48 // In this implementation, the size of hash tables must be a power of two
49 if (startsize & mask)
50 error("LongHash: Hash table size must be a power of two.\n");
51
52 occupancy = new bool [size];
53 objects = new ObjectT [size];
54 keys = new long long [size];
55
56 allowDuplicates = false;
57
58 for (unsigned int i = 0; i < size; i++)
59 {
60 occupancy[i] = false;
61 }
62 };
63
64 ~LongHash()
65 {
66 delete [] occupancy;
67 delete [] objects;
68 delete [] keys;
69 }
70
71 void Grow()
72 {
73 SetSize(size * 2);
74 }
75 void Shrink()
76 {
77 SetSize(size / 2);
78 }
79
80 void SetSize(int newsize)
81 {
82 int newmask = newsize - 1;
83
84 bool * newoccupancy = new bool [newsize];
85 ObjectT * newobjects = new ObjectT [newsize];
86 long long * newkeys = new long long [newsize];
87
88 for (int i = 0; i < newsize; i++)
89 newoccupancy[i] = false;
90
91 if (count)
92 for (unsigned int i = 0; i < size; i++)
93 if (occupancy[i] != false)
94 {
95 long long key = keys[i];
96 unsigned int h = newmask & (unsigned int) key;
97
98 while (newoccupancy[h] == true && (newkeys[h] != key || allowDuplicates))
99 h = (h + 1) & newmask;
100
101 if (newoccupancy[h])
102 count--;
103
104 newkeys[h] = key;
105 newobjects[h] = objects[i];
106 newoccupancy[h] = true;
107 }
108
109 delete [] occupancy;
110 delete [] objects;
111 delete [] keys;
112
113 occupancy = newoccupancy;
114 objects = newobjects;
115 keys = newkeys;
116 size = newsize;
117 mask = newmask;
118 }
119
120 void Clear()
121 {
122 count = 0;
123
124 if (size > 32)
125 SetSize(32);
126
127 for (unsigned int i = 0; i < size; i++)
128 occupancy[i] = false;
129 }
130
131 int Capacity() const
132 {
133 return size;
134 }
135 int Entries() const
136 {
137 return count;
138 }
139
140 ObjectT Object(int i) const
141 {
142 return objects[i];
143 }
144 ObjectT & Object(int i)
145 {
146 return objects[i];
147 }
148
149 void SetObject(int i, ObjectT object)
150 {
151 objects[i] = object;
152 }
153
154 unsigned int Add(long long key, ObjectT object)
155 {
156 if (count * 2 > size)
157 Grow();
158
159 unsigned int h = Iterate(key);
160
161 while (allowDuplicates && occupancy[h] && objects[h] != object)
162 h = ReIterate(key, h);
163
164 if (!occupancy[h])
165 {
166 occupancy[h] = true;
167 keys[h] = key;
168 count++;
169 }
170
171 objects[h] = object;
172
173 return h;
174 }
175
176 unsigned int Find(long long key)
177 {
178 unsigned int h = Iterate(key);
179
180 return occupancy[h] ? h : LH_NOTFOUND;
181 }
182
183 unsigned int Rehash(long long key, unsigned int h)
184 {
185 h = ReIterate(key, h);
186
187 return occupancy[h] ? h : LH_NOTFOUND;
188 }
189
190 LongHash & operator = (const LongHash & rhs);
191
192 ObjectT operator [](int i) const
193 {
194 return objects[i];
195 }
196 ObjectT operator [](unsigned int i) const
197 {
198 return objects[i];
199 }
200
201 void Delete(unsigned int index)
202 {
203 if (index >= size || !occupancy[index])
204 return;
205
206 occupancy[index] = false;
207 count--;
208
209 if (count * 8 < size && size > 32)
210 Shrink();
211 else
212 {
213 // rehash the next entries until we find empty slot
214 index = (index + 1) & mask;
215
216 while (occupancy[index])
217 {
218 if ((keys[index] & mask) != index)
219 {
220 unsigned int h = Iterate(keys[index]);
221
222 while (occupancy[h] && objects[h] != objects[index])
223 h = ReIterate(keys[index], h);
224
225 if (h != (unsigned int) index)
226 {
227 keys[h] = keys[index];
228 occupancy[h] = true;
229 objects[h] = objects[index];
230
231 occupancy[index] = false;
232 }
233 }
234
235 index = (index + 1) & mask;
236 }
237 }
238 }
239
240
241 bool SlotInUse(int index) const
242 {
243 return occupancy[index] == true;
244 }
245 bool SlotInUse(unsigned int index) const
246 {
247 return occupancy[index] == true;
248 }
249
250 // Accessor to get a key.
251 long long GetKey(int index) const
252 {
253 return keys[index];
254 }
255
256 long long GetKey(const unsigned int index) const
257 {
258 return keys[index];
259 }
260
261 void SetAllowDuplicateKeys(bool toggle)
262 {
263 allowDuplicates = toggle;
264
265 if (count && !allowDuplicates)
266 SetSize(size);
267 }
268
269private:
270 unsigned int Iterate(long long key) const
271 {
272 unsigned int h = mask & (unsigned int) key;
273
274 while (occupancy[h] == true && keys[h] != key)
275 h = (h + 1) & mask;
276
277 return h;
278 }
279
280 unsigned int ReIterate(long long key, unsigned int h) const
281 {
282 h = (h + 1) & mask;
283
284 while (occupancy[h] == true && keys[h] != key)
285 h = (h + 1) & mask;
286
287 return h;
288 }
289};
290
291#endif