18 #include "BasicHash.h" 23 BasicHash::BasicHash(
int startsize)
31 error(
"BasicHash: Hash table size must be a power of two.\n");
33 objects =
new void * [size];
34 keys =
new unsigned int [size];
36 for (
unsigned int i = 0; i < size; i++)
42 BasicHash::~BasicHash()
48 void BasicHash::Clear()
57 for (
unsigned int i = 0; i < size; i++)
61 void BasicHash::SetSize(
int newsize)
63 int newmask = newsize - 1;
65 void ** newobjects =
new void * [newsize];
66 unsigned int * newkeys =
new unsigned int [newsize];
68 for (
int i = 0; i < newsize; i++)
74 for (
unsigned int i = 0; i < size; i++)
75 if (objects[i] != NULL)
77 unsigned int key = keys[i];
78 unsigned int h = key & newmask;
80 while (newobjects[h] != NULL && newkeys[h] != h)
81 h = (h + 1) & newmask;
84 newobjects[h] = objects[i];
96 int BasicHash::Add(
int key,
void *
object)
101 unsigned int h = Iterate(key);
103 while ((objects[h] != NULL) && (objects[h] !=
object))
104 h = ReIterate(key, h);
106 if (objects[h] == NULL)
118 int BasicHash::Find(
int key)
120 int h = Iterate(key);
122 return objects[h] == NULL ? -1 : h;
125 int BasicHash::Rehash(
int key,
int h)
127 h = ReIterate(key, h);
129 return objects[h] == NULL ? -1 : h;
132 void BasicHash::Delete(
unsigned int index)
134 if (index >= size || objects[index] == NULL)
137 objects[index] = NULL;
140 if (count * 8 < size && size > 32)
145 index = (index + 1) & mask;
147 while (objects[index] != NULL)
149 if ((keys[index] & mask) != index)
151 unsigned int h = Iterate(keys[index]);
153 while ((objects[h] != NULL) && (objects[h] != objects[index]))
154 h = ReIterate(keys[index], h);
156 if (h != (
unsigned int) index)
158 keys[h] = keys[index];
159 objects[h] = objects[index];
160 objects[index] = NULL;
164 index = (index + 1) & mask;