libStatGen Software 1
Loading...
Searching...
No Matches
StringHash Class Reference
Inheritance diagram for StringHash:
Collaboration diagram for StringHash:

Public Member Functions

 StringHash (int startsize=32)
 
void Grow ()
 
void Shrink ()
 
void SetSize (int newsize)
 
void Clear ()
 
int Capacity () const
 
int Entries () const
 
void * Object (int i) const
 
void * Object (const String &key) const
 
void * Object (const String &key, void *(*create_object)())
 
void SetObject (int i, void *object)
 
void SetObject (const String &key, void *object)
 
int Add (const String &s, void *object=NULL)
 
int Find (const String &s, void *(*create_object)()=NULL)
 
int Find (const String &s) const
 
StringHashoperator= (const StringHash &rhs)
 
const Stringoperator[] (int i) const
 
Stringoperator[] (int i)
 
void Delete (unsigned int index)
 
void Delete (const String &key)
 
bool SlotInUse (int index) const
 
void Print ()
 
void Print (FILE *file)
 
void Print (const char *filename)
 
String StringList (char separator=',')
 
void ReadLinesFromFile (FILE *file)
 
void ReadLinesFromFile (const char *filename)
 
void ReadLinesFromFile (IFILE &file)
 
void Swap (StringHash &s)
 
- Public Member Functions inherited from StringHashBase
void setCaseSensitive (bool caseSensitive)
 

Static Public Member Functions

static void * CreateHash ()
 

Protected Attributes

String ** strings
 
void ** objects
 
unsigned int * keys
 
unsigned int count
 
unsigned int size
 
unsigned int mask
 
- Protected Attributes inherited from StringHashBase
bool myCaseSensitive
 

Additional Inherited Members

- Protected Member Functions inherited from StringHashBase
bool stringsEqual (const String &string1, const String &string2) const
 
unsigned int getKey (const String &string) const
 

Detailed Description

Definition at line 65 of file StringHash.h.

Constructor & Destructor Documentation

◆ StringHash()

StringHash::StringHash ( int  startsize = 32)

Definition at line 22 of file StringHash.cpp.

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("StringHash: Hash table size must be a power of two.\n");
32
33 strings = new String * [size];
34 objects = new void * [size];
35 keys = new unsigned int [size];
36
37 for (unsigned int i = 0; i < size; i++)
38 {
39 strings[i] = NULL;
40 objects[i] = NULL;
41 }
42};

◆ ~StringHash()

StringHash::~StringHash ( )
virtual

Definition at line 44 of file StringHash.cpp.

45{
46 for (unsigned int i = 0; i < size; i++)
47 if (strings[i] != NULL)
48 delete strings[i];
49
50 if(strings) delete [] strings;
51 if(objects) delete [] objects;
52 if(keys) delete [] keys;
53}

Member Function Documentation

◆ Add()

int StringHash::Add ( const String s,
void *  object = NULL 
)

Definition at line 112 of file StringHash.cpp.

113{
114 unsigned int key = getKey(string);
115 unsigned int h = Iterate(key, string);
116
117 if (strings[h] == NULL)
118 Insert(h, key, string);
119
120 objects[h] = object;
121
122 if (count * 2 > size)
123 {
124 Grow();
125 return Iterate(key, string);
126 }
127
128 return h;
129}

◆ Capacity()

int StringHash::Capacity ( ) const
inline

Definition at line 91 of file StringHash.h.

92 {
93 return size;
94 }

◆ Clear()

void StringHash::Clear ( )

Definition at line 55 of file StringHash.cpp.

56{
57 for (unsigned int i = 0; i < size; i++)
58 if (strings[i] != NULL)
59 {
60 delete strings[i];
61 strings[i] = NULL;
62 }
63
64 count = 0;
65
66 if (size > 256)
67 SetSize(256);
68}

◆ CreateHash()

void * StringHash::CreateHash ( )
static

Definition at line 164 of file StringHash.cpp.

165{
166 return (void *) new StringHash();
167}

◆ Delete() [1/2]

void StringHash::Delete ( const String key)
inline

Definition at line 145 of file StringHash.h.

146 {
147 Delete(Find(key));
148 }

◆ Delete() [2/2]

void StringHash::Delete ( unsigned int  index)

Definition at line 169 of file StringHash.cpp.

170{
171 if (index >= size || strings[index] == NULL)
172 return;
173
174 delete strings[index];
175 strings[index] = NULL;
176 count--;
177
178 if (count * 8 < size && size > 32)
179 Shrink();
180 else
181 {
182 // rehash the next strings until we find empty slot
183 index = (index + 1) & mask;
184
185 while (strings[index] != NULL)
186 {
187 if ((keys[index] & mask) != index)
188 {
189 unsigned int h = Iterate(keys[index], *strings[index]);
190
191 if (h != (unsigned int) index)
192 {
193 keys[h] = keys[index];
194 strings[h] = strings[index];
195 objects[h] = objects[index];
196
197 strings[index] = NULL;
198 objects[index] = NULL;
199 }
200 }
201
202 index = (index + 1) & mask;
203 }
204 }
205}

◆ Entries()

int StringHash::Entries ( ) const
inline

Definition at line 95 of file StringHash.h.

96 {
97 return count;
98 }

◆ Find() [1/2]

int StringHash::Find ( const String s) const

Definition at line 154 of file StringHash.cpp.

155{
156 unsigned int key = getKey(string);
157 unsigned int h = Iterate(key, string);
158
159 if (strings[h] == NULL)
160 return -1;
161
162 return h;
163}

◆ Find() [2/2]

int StringHash::Find ( const String s,
void *(*)()  create_object = NULL 
)

Definition at line 131 of file StringHash.cpp.

132{
133 unsigned int key = getKey(string);
134 unsigned int h = Iterate(key, string);
135
136 if (strings[h] == NULL && create_object == NULL)
137 return -1;
138
139 if (strings[h] == NULL && create_object != NULL)
140 {
141 Insert(h, key, string);
142 objects[h] = create_object();
143
144 if (count * 2 > size)
145 {
146 Grow();
147 return Iterate(key, string);
148 }
149 }
150
151 return h;
152}

◆ Grow()

void StringHash::Grow ( )
inline

Definition at line 78 of file StringHash.h.

79 {
80 SetSize(size * 2);
81 }

◆ Object() [1/3]

void * StringHash::Object ( const String key) const
inline

Definition at line 104 of file StringHash.h.

105 {
106 int index = Find(key);
107
108 return index >= 0 ? objects[index] : NULL;
109 }

◆ Object() [2/3]

void * StringHash::Object ( const String key,
void *(*)()  create_object 
)
inline

Definition at line 110 of file StringHash.h.

111 {
112 int index = Find(key, create_object);
113
114 return objects[index];
115 }

◆ Object() [3/3]

void * StringHash::Object ( int  i) const
inline

Definition at line 100 of file StringHash.h.

101 {
102 return objects[i];
103 }

◆ operator=()

StringHash & StringHash::operator= ( const StringHash rhs)

Definition at line 652 of file StringHash.cpp.

653{
654 Clear();
655
656 for (int i = 0; i < rhs.Capacity(); i++)
657 if (rhs.SlotInUse(i))
658 Add(*(rhs.strings[i]), rhs.objects[i]);
659
660 return *this;
661}

◆ operator[]() [1/2]

String & StringHash::operator[] ( int  i)
inline

Definition at line 136 of file StringHash.h.

137 {
138 return *(strings[i]);
139 }

◆ operator[]() [2/2]

const String & StringHash::operator[] ( int  i) const
inline

Definition at line 132 of file StringHash.h.

133 {
134 return *(strings[i]);
135 }

◆ Print() [1/3]

void StringHash::Print ( )

Definition at line 564 of file StringHash.cpp.

565{
566 Print(stdout);
567}

◆ Print() [2/3]

void StringHash::Print ( const char *  filename)

Definition at line 569 of file StringHash.cpp.

570{
571 FILE * output = fopen(filename, "wt");
572 if (output == NULL)
573 return;
574 Print(output);
575 fclose(output);
576}

◆ Print() [3/3]

void StringHash::Print ( FILE *  file)

Definition at line 578 of file StringHash.cpp.

579{
580 for (unsigned int i = 0; i < size; i++)
581 if (SlotInUse(i))
582 strings[i]->WriteLine(output);
583}

◆ ReadLinesFromFile() [1/3]

void StringHash::ReadLinesFromFile ( const char *  filename)

Definition at line 207 of file StringHash.cpp.

208{
209 IFILE f = ifopen(filename, "rb");
210 if (f == NULL) return;
211 ReadLinesFromFile(f);
212 ifclose(f);
213}
IFILE ifopen(const char *filename, const char *mode, InputFile::ifileCompression compressionMode=InputFile::DEFAULT)
Open a file with the specified name and mode, using a filename of "-" to indicate stdin/stdout.
Definition InputFile.h:562
int ifclose(IFILE &file)
Close the file.
Definition InputFile.h:580
Class for easily reading/writing files without having to worry about file type (uncompressed,...
Definition InputFile.h:37

◆ ReadLinesFromFile() [2/3]

void StringHash::ReadLinesFromFile ( FILE *  file)

Definition at line 215 of file StringHash.cpp.

216{
217 String buffer;
218
219 while (!feof(f))
220 {
221 buffer.ReadLine(f);
222 Add(buffer.Trim());
223 }
224}

◆ ReadLinesFromFile() [3/3]

void StringHash::ReadLinesFromFile ( IFILE file)

Definition at line 226 of file StringHash.cpp.

227{
228 String buffer;
229
230 while (!ifeof(f))
231 {
232 buffer.ReadLine(f);
233 Add(buffer.Trim());
234 }
235}
int ifeof(IFILE file)
Check to see if we have reached the EOF (returns 0 if not EOF).
Definition InputFile.h:654

◆ SetObject() [1/2]

void StringHash::SetObject ( const String key,
void *  object 
)
inline

Definition at line 121 of file StringHash.h.

122 {
123 Add(key, object);
124 }

◆ SetObject() [2/2]

void StringHash::SetObject ( int  i,
void *  object 
)
inline

Definition at line 117 of file StringHash.h.

118 {
119 objects[i] = object;
120 }

◆ SetSize()

void StringHash::SetSize ( int  newsize)
virtual

Implements StringHashBase.

Definition at line 70 of file StringHash.cpp.

71{
72 int newmask = newsize - 1;
73
74 String ** newstrings = new String * [newsize];
75 void ** newobjects = new void * [newsize];
76 unsigned int * newkeys = new unsigned int [newsize];
77
78 for (int i = 0; i < newsize; i++)
79 {
80 newstrings[i] = NULL;
81 newobjects[i] = NULL;
82 }
83
84 if (count)
85 for (unsigned int i = 0; i < size; i++)
86 if (strings[i] != NULL)
87 {
88 unsigned int key = keys[i];
89 unsigned int h = key & newmask;
90
91 while (newstrings[h] != NULL &&
92 (newkeys[h] != key ||
93 (!stringsEqual(*(newstrings[h]), *(strings[i])))))
94 h = (h + 1) & newmask;
95
96 newkeys[h] = key;
97 newstrings[h] = strings[i];
98 newobjects[h] = objects[i];
99 }
100
101 if(strings) delete [] strings;
102 if(objects) delete [] objects;
103 if(keys) delete [] keys;
104
105 strings = newstrings;
106 objects = newobjects;
107 keys = newkeys;
108 size = newsize;
109 mask = newmask;
110}

◆ Shrink()

void StringHash::Shrink ( )
inline

Definition at line 82 of file StringHash.h.

83 {
84 SetSize(size / 2);
85 }

◆ SlotInUse()

bool StringHash::SlotInUse ( int  index) const
inline

Definition at line 150 of file StringHash.h.

151 {
152 return strings[index] != NULL;
153 }

◆ StringList()

String StringHash::StringList ( char  separator = ',')

Definition at line 585 of file StringHash.cpp.

586{
587 String list;
588
589 for (unsigned int i = 0; i < size; i++)
590 if (SlotInUse(i))
591 list += *strings[i] + separator;
592
593 list.SetLength(list.Length() - 1);
594
595 return list;
596}

◆ Swap()

void StringHash::Swap ( StringHash s)

Definition at line 710 of file StringHash.cpp.

711{
712 String ** tstrings = s.strings;
713 s.strings = strings;
714 strings = tstrings;
715
716 void ** tobjects = s.objects;
717 s.objects = objects;
718 objects = tobjects;
719
720 unsigned int * tkeys = s.keys;
721 s.keys = keys;
722 keys = tkeys;
723
724 unsigned int temp = s.count;
725 s.count = count;
726 count = temp;
727
728 temp = s.size;
729 s.size = size;
730 size = temp;
731
732 temp = s.mask;
733 s.mask = mask;
734 mask = temp;
735}

Member Data Documentation

◆ count

unsigned int StringHash::count
protected

Definition at line 71 of file StringHash.h.

◆ keys

unsigned int* StringHash::keys
protected

Definition at line 70 of file StringHash.h.

◆ mask

unsigned int StringHash::mask
protected

Definition at line 72 of file StringHash.h.

◆ objects

void** StringHash::objects
protected

Definition at line 69 of file StringHash.h.

◆ size

unsigned int StringHash::size
protected

Definition at line 71 of file StringHash.h.

◆ strings

String** StringHash::strings
protected

Definition at line 68 of file StringHash.h.


The documentation for this class was generated from the following files: