libStatGen Software  1
IntHash.cpp
1 /*
2  * Copyright (C) 2000-2007 Goncalo Abecasis
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 #include "IntHash.h"
19 #include "Error.h"
20 
21 #include <stdio.h>
22 
23 IntHash::IntHash(int startsize)
24 {
25  count = 0;
26  size = startsize;
27  mask = startsize - 1;
28 
29  // In this implementation, the size of hash tables must be a power of two
30  if (startsize & mask)
31  error("IntHash: Hash table size must be a power of two.\n");
32 
33  objects = new bool [size];
34  keys = new unsigned int [size];
35 
36  for (unsigned int i = 0; i < size; i++)
37  {
38  objects[i] = false;
39  }
40 };
41 
42 IntHash::~IntHash()
43 {
44  delete [] objects;
45  delete [] keys;
46 }
47 
48 void IntHash::Clear()
49 {
50 // printf("Clearing...\n");
51 
52  count = 0;
53 
54  if (size > 16)
55  SetSize(16);
56 
57  for (unsigned int i = 0; i < size; i++)
58  objects[i] = false;
59 }
60 
61 void IntHash::SetSize(int newsize)
62 {
63  int newmask = newsize - 1;
64 
65  bool * newobjects = new bool [newsize];
66  unsigned int * newkeys = new unsigned int [newsize];
67 
68  for (int i = 0; i < newsize; i++)
69  {
70  newobjects[i] = false;
71  }
72 
73  if (count)
74  for (unsigned int i = 0; i < size; i++)
75  if (objects[i] != false)
76  {
77  unsigned int key = keys[i];
78  unsigned int h = key & newmask;
79 
80  while (newobjects[h] != false && newkeys[h] != h)
81  h = (h + 1) & newmask;
82 
83  newkeys[h] = key;
84  newobjects[h] = objects[i];
85  }
86 
87  delete [] objects;
88  delete [] keys;
89 
90  objects = newobjects;
91  keys = newkeys;
92  size = newsize;
93  mask = newmask;
94 }
95 
96 int IntHash::Add(int key, bool object)
97 {
98  if (count * 2 > size)
99  Grow();
100 
101  unsigned int h = Iterate(key);
102 
103  while ((objects[h] != false) && (objects[h] != object))
104  h = ReIterate(key, h);
105 
106  if (objects[h] == false)
107  {
108 // printf("At position %d, inserted %x\n", h, key);
109  keys[h] = key;
110  count++;
111  }
112 
113  objects[h] = object;
114 
115  return h;
116 }
117 
118 int IntHash::Find(int key)
119 {
120  int h = Iterate(key);
121 
122  return objects[h] == false ? -1 : h;
123 }
124 
125 int IntHash::Rehash(int key, int h)
126 {
127  h = ReIterate(key, h);
128 
129  return objects[h] == false ? -1 : h;
130 }
131 
132 void IntHash::Delete(unsigned int index)
133 {
134  if (index >= size || objects[index] == false)
135  return;
136 
137  objects[index] = false;
138  count--;
139 
140  if (count * 8 < size && size > 32)
141  Shrink();
142  else
143  {
144  // rehash the next entries until we find empty slot
145  index = (index + 1) & mask;
146 
147  while (objects[index] != false)
148  {
149  if ((keys[index] & mask) != index)
150  {
151  unsigned int h = Iterate(keys[index]);
152 
153  while ((objects[h] != false) && (objects[h] != objects[index]))
154  h = ReIterate(keys[index], h);
155 
156  if (h != (unsigned int) index)
157  {
158  keys[h] = keys[index];
159  objects[h] = objects[index];
160  objects[index] = false;
161  }
162  }
163 
164  index = (index + 1) & mask;
165  }
166  }
167 }
168