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
IntHash(int startsize)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
~IntHash()42 IntHash::~IntHash()
43 {
44 delete [] objects;
45 delete [] keys;
46 }
47
Clear()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
SetSize(int newsize)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
Add(int key,bool object)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
Find(int key)118 int IntHash::Find(int key)
119 {
120 int h = Iterate(key);
121
122 return objects[h] == false ? -1 : h;
123 }
124
Rehash(int key,int h)125 int IntHash::Rehash(int key, int h)
126 {
127 h = ReIterate(key, h);
128
129 return objects[h] == false ? -1 : h;
130 }
131
Delete(unsigned int index)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
169