18#include "StringHash.h"
22StringHash::StringHash(
int startsize)
31 error(
"StringHash: Hash table size must be a power of two.\n");
33 strings =
new String * [size];
34 objects =
new void * [size];
35 keys =
new unsigned int [size];
37 for (
unsigned int i = 0; i < size; i++)
44StringHash::~StringHash()
46 for (
unsigned int i = 0; i < size; i++)
47 if (strings[i] != NULL)
50 if(strings)
delete [] strings;
51 if(objects)
delete [] objects;
52 if(keys)
delete [] keys;
55void StringHash::Clear()
57 for (
unsigned int i = 0; i < size; i++)
58 if (strings[i] != NULL)
70void StringHash::SetSize(
int newsize)
72 int newmask = newsize - 1;
75 void ** newobjects =
new void * [newsize];
76 unsigned int * newkeys =
new unsigned int [newsize];
78 for (
int i = 0; i < newsize; i++)
85 for (
unsigned int i = 0; i < size; i++)
86 if (strings[i] != NULL)
88 unsigned int key = keys[i];
89 unsigned int h = key & newmask;
91 while (newstrings[h] != NULL &&
93 (!stringsEqual(*(newstrings[h]), *(strings[i])))))
94 h = (h + 1) & newmask;
97 newstrings[h] = strings[i];
98 newobjects[h] = objects[i];
101 if(strings)
delete [] strings;
102 if(objects)
delete [] objects;
103 if(keys)
delete [] keys;
105 strings = newstrings;
106 objects = newobjects;
112int StringHash::Add(
const String &
string,
void *
object)
114 unsigned int key = getKey(
string);
115 unsigned int h = Iterate(key,
string);
117 if (strings[h] == NULL)
118 Insert(h, key,
string);
122 if (count * 2 > size)
125 return Iterate(key,
string);
131int StringHash::Find(
const String &
string,
void *(*create_object)())
133 unsigned int key = getKey(
string);
134 unsigned int h = Iterate(key,
string);
136 if (strings[h] == NULL && create_object == NULL)
139 if (strings[h] == NULL && create_object != NULL)
141 Insert(h, key,
string);
142 objects[h] = create_object();
144 if (count * 2 > size)
147 return Iterate(key,
string);
154int StringHash::Find(
const String &
string)
const
156 unsigned int key = getKey(
string);
157 unsigned int h = Iterate(key,
string);
159 if (strings[h] == NULL)
164void * StringHash::CreateHash()
169void StringHash::Delete(
unsigned int index)
171 if (index >= size || strings[index] == NULL)
174 delete strings[index];
175 strings[index] = NULL;
178 if (count * 8 < size && size > 32)
183 index = (index + 1) & mask;
185 while (strings[index] != NULL)
187 if ((keys[index] & mask) != index)
189 unsigned int h = Iterate(keys[index], *strings[index]);
191 if (h != (
unsigned int) index)
193 keys[h] = keys[index];
194 strings[h] = strings[index];
195 objects[h] = objects[index];
197 strings[index] = NULL;
198 objects[index] = NULL;
202 index = (index + 1) & mask;
207void StringHash::ReadLinesFromFile(
const char * filename)
210 if (f == NULL)
return;
211 ReadLinesFromFile(f);
215void StringHash::ReadLinesFromFile(FILE * f)
226void StringHash::ReadLinesFromFile(
IFILE & f)
239StringIntHash::StringIntHash(
int startsize)
244 mask = startsize - 1;
247 if (startsize & mask)
248 error(
"StringIntHash: Hash table size must be a power of two.\n");
250 strings =
new String * [size];
251 integers =
new int [size];
252 keys =
new unsigned int [size];
254 for (
unsigned int i = 0; i < size; i++)
258StringIntHash::~StringIntHash()
260 for (
unsigned int i = 0; i < size; i++)
261 if (strings[i] != NULL)
264 if(strings)
delete [] strings;
265 if(integers)
delete [] integers;
266 if(keys)
delete [] keys;
269void StringIntHash::SetSize(
int newsize)
271 int newmask = newsize - 1;
274 int * newintegers =
new int [newsize];
275 unsigned int * newkeys =
new unsigned int [newsize];
277 for (
int i = 0; i < newsize; i++)
278 newstrings[i] = NULL;
280 for (
unsigned int i = 0; i < size; i++)
281 if (strings[i] != NULL)
283 unsigned int key = keys[i];
284 unsigned int h = key & newmask;
286 while (newstrings[h] != NULL &&
287 (newkeys[h] != key || (!stringsEqual(*(newstrings[h]), *(strings[i])))))
288 h = (h + 1) & newmask;
291 newstrings[h] = strings[i];
292 newintegers[h] = integers[i];
295 if(strings)
delete [] strings;
296 if(integers)
delete [] integers;
297 if(keys)
delete [] keys;
299 strings = newstrings;
300 integers = newintegers;
306void StringIntHash::Clear()
308 for (
unsigned int i = 0; i < size; i++)
309 if (strings[i] != NULL)
321int StringIntHash::Add(
const String &
string,
int value)
323 unsigned int key = getKey(
string);
324 unsigned int h = Iterate(key,
string);
326 if (strings[h] == NULL)
327 Insert(h, key,
string);
331 if (count * 2 > size)
334 return Iterate(key,
string);
340int StringIntHash::Find(
const String &
string,
int defaultValue)
342 unsigned int key = getKey(
string);
343 unsigned int h = Iterate(key,
string);
345 if (strings[h] == NULL)
347 Insert(h, key,
string);
348 integers[h] = defaultValue;
350 if (count * 2 > size)
353 return Iterate(key,
string);
360int StringIntHash::Find(
const String &
string)
const
362 unsigned int key = getKey(
string);
363 unsigned int h = Iterate(key,
string);
365 if (strings[h] == NULL)
371void StringIntHash::Delete(
unsigned int index)
373 if (index >= size || strings[index] == NULL)
376 delete strings[index];
377 strings[index] = NULL;
380 if (count * 8 < size && size > 32)
385 index = (index + 1) & mask;
387 while (strings[index] != NULL)
389 if ((keys[index] & mask) != index)
391 unsigned int h = Iterate(keys[index], *strings[index]);
393 if (h != (
unsigned int) index)
395 keys[h] = keys[index];
396 strings[h] = strings[index];
397 integers[h] = integers[index];
399 strings[index] = NULL;
403 index = (index + 1) & mask;
410StringDoubleHash::StringDoubleHash(
int startsize)
415 mask = startsize - 1;
418 if (startsize & mask)
419 error(
"StringDoubleHash: Hash table size must be a power of two.\n");
421 strings =
new String * [size];
422 doubles =
new double [size];
423 keys =
new unsigned int [size];
425 for (
unsigned int i = 0; i < size; i++)
429StringDoubleHash::~StringDoubleHash()
431 for (
unsigned int i = 0; i < size; i++)
432 if (strings[i] != NULL)
435 if(strings)
delete [] strings;
436 if(doubles)
delete [] doubles;
437 if(keys)
delete [] keys;
440void StringDoubleHash::SetSize(
int newsize)
442 int newmask = newsize - 1;
445 double * newdoubles =
new double [newsize];
446 unsigned int * newkeys =
new unsigned int [newsize];
448 for (
int i = 0; i < newsize; i++)
449 newstrings[i] = NULL;
451 for (
unsigned int i = 0; i < size; i++)
452 if (strings[i] != NULL)
454 unsigned int key = keys[i];
455 unsigned int h = key & newmask;
457 while (newstrings[h] != NULL &&
458 (newkeys[h] != key || (!stringsEqual(*(newstrings[h]), *(strings[i])))))
459 h = (h + 1) & newmask;
462 newstrings[h] = strings[i];
463 newdoubles[h] = doubles[i];
466 if(strings)
delete [] strings;
467 if(doubles)
delete [] doubles;
468 if(keys)
delete [] keys;
470 strings = newstrings;
471 doubles = newdoubles;
477int StringDoubleHash::Add(
const String &
string,
double value)
479 unsigned int key = getKey(
string);
480 unsigned int h = Iterate(key,
string);
482 if (strings[h] == NULL)
483 Insert(h, key,
string);
487 if (count * 2 > size)
490 return Iterate(key,
string);
496int StringDoubleHash::Find(
const String &
string,
double defaultValue)
498 unsigned int key = getKey(
string);
499 unsigned int h = Iterate(key,
string);
501 if (strings[h] == NULL)
503 Insert(h, key,
string);
504 doubles[h] = defaultValue;
506 if (count * 2 > size)
509 return Iterate(key,
string);
516int StringDoubleHash::Find(
const String &
string)
const
518 unsigned int key = getKey(
string);
519 unsigned int h = Iterate(key,
string);
521 if (strings[h] == NULL)
527void StringDoubleHash::Delete(
unsigned int index)
529 if (index >= size || strings[index] == NULL)
532 delete strings[index];
533 strings[index] = NULL;
536 if (count * 8 < size && size > 32)
541 index = (index + 1) & mask;
543 while (strings[index] != NULL)
545 if ((keys[index] & mask) != index)
547 unsigned int h = Iterate(keys[index], *strings[index]);
549 if (h != (
unsigned int) index)
551 keys[h] = keys[index];
552 strings[h] = strings[index];
553 doubles[h] = doubles[index];
555 strings[index] = NULL;
559 index = (index + 1) & mask;
564void StringHash::Print()
569void StringHash::Print(
const char * filename)
571 FILE * output = fopen(filename,
"wt");
578void StringHash::Print(FILE * output)
580 for (
unsigned int i = 0; i < size; i++)
582 strings[i]->WriteLine(output);
585String StringHash::StringList(
char separator)
589 for (
unsigned int i = 0; i < size; i++)
591 list += *strings[i] + separator;
593 list.SetLength(list.Length() - 1);
598int StringIntHash::GetCount(
const String & key)
const
600 int index = Find(key);
601 return index == -1 ? 0 : integers[index];
604int StringIntHash::IncrementCount(
const String & key)
606 int index = Find(key);
609 return ++(integers[index]);
615int StringIntHash::IncrementCount(
const String & key,
int amount)
617 int index = Find(key);
620 return (integers[index] += amount);
622 SetInteger(key, amount);
626int StringIntHash::DecrementCount(
const String & key)
628 int index = Find(key);
631 return --(integers[index]);
637void StringDoubleHash::Clear()
639 for (
unsigned int i = 0; i < size; i++)
640 if (strings[i] != NULL)
656 for (
int i = 0; i < rhs.Capacity(); i++)
657 if (rhs.SlotInUse(i))
658 Add(*(rhs.strings[i]), rhs.objects[i]);
667 for (
int i = 0; i < rhs.Capacity(); i++)
668 if (rhs.SlotInUse(i))
669 Add(*(rhs.strings[i]), rhs.integers[i]);
674bool StringIntHash::operator == (
const StringIntHash & rhs)
const
676 if (Capacity() != rhs.Capacity())
return false;
677 if (Entries() != rhs.Entries())
return false;
678 for (
int i = 0; i < rhs.Capacity(); i++)
680 if(rhs.SlotInUse(i) != SlotInUse(i))
684 if (rhs.SlotInUse(i))
686 if(*(strings[i]) != *(rhs.strings[i]))
690 if(rhs.integers[i] != integers[i])
703 for (
int i = 0; i < rhs.Capacity(); i++)
704 if (rhs.SlotInUse(i))
705 Add(*(rhs.strings[i]), rhs.doubles[i]);
712 String ** tstrings = s.strings;
716 void ** tobjects = s.objects;
720 unsigned int * tkeys = s.keys;
724 unsigned int temp = s.count;