libStatGen Software  1
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 
31 template <class ObjectT> class LongHash
32 {
33 protected:
34  ObjectT * objects;
35  long long * keys;
36  bool * occupancy;
37  unsigned int count, size;
38  unsigned int mask;
39  bool allowDuplicates;
40 
41 public:
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 
269 private:
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