libStatGen Software 1
Loading...
Searching...
No Matches
BasicHash.cpp
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#include "BasicHash.h"
19#include "Error.h"
20
21#include <stdio.h>
22
23BasicHash::BasicHash(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("BasicHash: Hash table size must be a power of two.\n");
32
33 objects = new void * [size];
34 keys = new unsigned int [size];
35
36 for (unsigned int i = 0; i < size; i++)
37 {
38 objects[i] = NULL;
39 }
40};
41
42BasicHash::~BasicHash()
43{
44 delete [] objects;
45 delete [] keys;
46}
47
48void BasicHash::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] = NULL;
59}
60
61void BasicHash::SetSize(int newsize)
62{
63 int newmask = newsize - 1;
64
65 void ** newobjects = new void * [newsize];
66 unsigned int * newkeys = new unsigned int [newsize];
67
68 for (int i = 0; i < newsize; i++)
69 {
70 newobjects[i] = NULL;
71 }
72
73 if (count)
74 for (unsigned int i = 0; i < size; i++)
75 if (objects[i] != NULL)
76 {
77 unsigned int key = keys[i];
78 unsigned int h = key & newmask;
79
80 while (newobjects[h] != NULL && 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
96int BasicHash::Add(int key, void * object)
97{
98 if (count * 2 > size)
99 Grow();
100
101 unsigned int h = Iterate(key);
102
103 while ((objects[h] != NULL) && (objects[h] != object))
104 h = ReIterate(key, h);
105
106 if (objects[h] == NULL)
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
118int BasicHash::Find(int key)
119{
120 int h = Iterate(key);
121
122 return objects[h] == NULL ? -1 : h;
123}
124
125int BasicHash::Rehash(int key, int h)
126{
127 h = ReIterate(key, h);
128
129 return objects[h] == NULL ? -1 : h;
130}
131
132void BasicHash::Delete(unsigned int index)
133{
134 if (index >= size || objects[index] == NULL)
135 return;
136
137 objects[index] = NULL;
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] != NULL)
148 {
149 if ((keys[index] & mask) != index)
150 {
151 unsigned int h = Iterate(keys[index]);
152
153 while ((objects[h] != NULL) && (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] = NULL;
161 }
162 }
163
164 index = (index + 1) & mask;
165 }
166 }
167}