1 /********************************************************************************
2 * Hash table class template (char* based) *
3 *********************************************************************************/
4
5 #ifndef GHash_HH
6 #define GHash_HH
7 #include "GBase.h"
8
9 /**
10 * This class maintains a fast-access hash table of entities
11 * indexed by a character string (essentially, maps strings to pointers)
12 */
13
14 //#define HASH_DBG_PRINT 1
15
16 #define GSTR_HASH(s) strhash(s)
17 //#define GSTR_HASH(s) djb_hash(s)
18 //#define GSTR_HASH(s) fnv1a_hash(s)
19 //#define GSTR_HASH(s) murmur3(s)
20
21 template <class OBJ> class GHash {
22 protected:
23 struct GHashEntry {
24 char* key; // Key string
25 bool keyalloc; // shared key flag (to free/not the key)
26 int hash; // Hash value of key
27 pointer data; // Data
28 };
29 GHashEntry* hash; // Hash
30 int fCapacity; // table size
31 int fCount; // number of valid entries
32 int fCurrentEntry;
33 char* lastkeyptr; //pointer to last key string added
34 //---------- Raw data retrieval (including empty entries)
35 // Return key at position pos.
Key(uint pos) const36 const char* Key(uint pos) const { return hash[pos].key; }
37 // return data OBJ* at given position
Data(uint pos) const38 OBJ* Data(uint pos) const { return (OBJ*) hash[pos].data; }
39 // Return position of first filled slot, or >= fCapacity
40 int First() const;
41 // Return position of last filled slot or -1
42 int Last() const;
43 // Return position of next filled slot in hash table
44 // or a value greater than or equal to fCapacity if no filled
45 // slot was found
46 int Next(int pos) const;
47 //Return position of previous filled slot in hash table
48 //or a -1 if no filled slot was found
49 int Prev(int pos) const;
50
51 private:
52 GHash(const GHash&);
53 GHash &operator=(const GHash&);
54 GFreeProc* fFreeProc; //procedure to free item data
55 protected:
56 public:
DefaultFreeProc(pointer item)57 static void DefaultFreeProc(pointer item) {
58 delete (OBJ*)item;
59 }
60 public:
61 GHash(GFreeProc* freeProc); // constructs of an empty hash
62 GHash(bool doFree=true); // constructs of an empty hash (free the item objects)
setFreeItem(GFreeProc * freeProc)63 void setFreeItem(GFreeProc *freeProc) { fFreeProc=freeProc; }
setFreeItem(bool doFree)64 void setFreeItem(bool doFree) { fFreeProc=(doFree)? &DefaultFreeProc : NULL; }
Capacity() const65 int Capacity() const { return fCapacity; } // table's size, including the empty slots.
66 void Resize(int m); // Resize the table to the given size.
Count() const67 int Count() const { return fCount; }// the total number of entries in the table.
68
69 // Insert a new entry into the table given key.
70 // If there is already an entry with that key, leave it unchanged
71 OBJ* Add(const char* ky, OBJ* ptr=NULL);
72
73 //same with Add, but frees the old element if it's a replacement
74 OBJ* fAdd(const char* ky, OBJ* ptr=NULL);
75
76 //same as Add, but the key pointer is stored directly, no string copy needed
77 //(shared-key-Add)
78 OBJ* shkAdd(const char* ky, OBJ* ptr);
79
80 // Replace data at key. If there was no existing entry,
81 // a new entry is inserted.
82 OBJ* Replace(const char* ky, OBJ* ptr);
83 // Remove a given key and its data
84 OBJ* Remove(const char* ky);
85 // Find data OBJ* given key.
86 OBJ* Find(const char* ky, char** keyptr=NULL);
87 bool hasKey(const char* ky);
getLastKey()88 char* getLastKey() { return lastkeyptr; }
operator [](const char * ky)89 OBJ* operator[](const char* ky) { return Find(ky); }
90 void startIterate(); //iterator-like initialization
91 char* NextKey(); //returns next valid key in the table (NULL if no more)
92 OBJ* NextData(); //returns next valid hash[].data
93 OBJ* NextData(char*& nextkey); //returns next valid hash[].data
94 //or NULL if no more
95 //nextkey is SET to the corresponding key
NextEntry()96 GHashEntry* NextEntry() { //returns a pointer to a GHashEntry
97 int pos=fCurrentEntry;
98 while (pos<fCapacity && hash[pos].hash<0) pos++;
99 if (pos==fCapacity) {
100 fCurrentEntry=fCapacity;
101 return NULL;
102 }
103 else {
104 fCurrentEntry=pos+1;
105 return &hash[pos];
106 }
107 }
108 /// Clear all entries
109 void Clear();
110
111 /// Destructor
112 virtual ~GHash();
113 };
114 //
115 //======================== method definitions ========================
116 //
117 /*
118 Notes:
119 - Since the algorithm doubles the table size when exceeding MAX_LOAD,
120 it would be prudent to keep MIN_LOAD less than 1/2 MAX_LOAD;
121 otherwise, the algorithm might flip between halving and doubling!
122 - We store the key hash value so that 99.999% of the time we can compare hash numbers;
123 only when hash numbers match we need to compare keys.
124 - Thus with a good hash function the fCount of calls to strcmp() should be
125 roughly the same as the fCount of successful lookups.
126 */
127
128 // Initial table size (MUST be power of 2)
129 #define DEF_HASH_SIZE 32
130 // Maximum hash table load factor (%)
131 #define MAX_LOAD 80
132 // Minimum hash table load factor (%)
133 #define MIN_LOAD 10
134
135 // Probe Position [0..n-1]
136 #define HASH1(x,n) (((unsigned int)(x)*13)%(n))
137 // Probe Distance [1..n-1]
138 #define HASH2(x,n) (1|(((unsigned int)(x)*17)%((n)-1)))
139
140 #define FREEDATA (fFreeProc!=NULL)
141
142 /*******************************************************************************/
143 // Construct empty hash
GHash(GFreeProc * freeProc)144 template <class OBJ> GHash<OBJ>::GHash(GFreeProc* freeProc) {
145 GMALLOC(hash, sizeof(GHashEntry)*DEF_HASH_SIZE);
146 fCurrentEntry=-1;
147 fFreeProc=freeProc;
148 lastkeyptr=NULL;
149 for (uint i=0; i<DEF_HASH_SIZE; i++)
150 hash[i].hash=-1; //this will be an indicator for 'empty' entries
151 fCapacity=DEF_HASH_SIZE;
152 fCount=0;
153 }
154
GHash(bool doFree)155 template <class OBJ> GHash<OBJ>::GHash(bool doFree) {
156 GMALLOC(hash, sizeof(GHashEntry)*DEF_HASH_SIZE);
157 fCurrentEntry=-1;
158 lastkeyptr=NULL;
159 fFreeProc = (doFree)?&DefaultFreeProc : NULL;
160 for (uint i=0; i<DEF_HASH_SIZE; i++)
161 hash[i].hash=-1; //this will be an indicator for 'empty' entries
162 fCapacity=DEF_HASH_SIZE;
163 fCount=0;
164 }
165
166
167 // Resize table
Resize(int m)168 template <class OBJ> void GHash<OBJ>::Resize(int m) {
169 int i,n,p,x,h;
170 GHashEntry *k;
171 GASSERT(fCount<=fCapacity);
172 if(m<DEF_HASH_SIZE) m=DEF_HASH_SIZE;
173 n=fCapacity;
174 while((n>>2)>m) n>>=1; // Shrink until n/4 <= m
175 while((n>>1)<m) n<<=1; // Grow until m <= n/2
176 GASSERT(m<=(n>>1));
177 GASSERT(DEF_HASH_SIZE<=n);
178 if(n!=fCapacity){
179 GASSERT(m<=n);
180 GMALLOC(k, sizeof(GHashEntry)*n);
181 for(i=0; i<n; i++) k[i].hash=-1;
182 for(i=0; i<fCapacity; i++){
183 h=hash[i].hash;
184 if(h>=0){
185 p=HASH1(h,n);
186 GASSERT(0<=p && p<n);
187 x=HASH2(h,n);
188 GASSERT(1<=x && x<n);
189 while(k[p].hash!=-1) p=(p+x)%n;
190 GASSERT(k[p].hash<0);
191 k[p]=hash[i];
192 }
193 }
194 GFREE(hash);
195 hash=k;
196 fCapacity=n;
197 }
198 }
199
200 // add a new entry, or update it if it already exists
201
202
Add(const char * ky,OBJ * pdata)203 template <class OBJ> OBJ* GHash<OBJ>::Add(const char* ky, OBJ* pdata) {
204 int p,i,x,h,n;
205 if(!ky) GError("GHash::insert: NULL key argument.\n");
206 GASSERT(fCount<fCapacity);
207 h=GSTR_HASH(ky);
208 GASSERT(0<=h);
209 p=HASH1(h,fCapacity);
210 GASSERT(0<=p && p<fCapacity);
211 x=HASH2(h,fCapacity);
212 GASSERT(1<=x && x<fCapacity);
213 i=-1;
214 n=fCapacity;
215 #ifdef HASH_DBG_PRINT
216 int iterations=0;
217 int init_p=p;
218 int init_x=x;
219 #endif
220 while(n && hash[p].hash!=-1) {
221 if ((i==-1)&&(hash[p].hash==-2)) i=p;
222 if (hash[p].hash==h && strcmp(hash[p].key,ky)==0) {
223 //replace hash data for this key!
224 lastkeyptr=hash[p].key;
225 OBJ* r = (OBJ*) hash[p].data;
226 hash[p].data = (void*) pdata;
227 #ifdef HASH_DBG_PRINT
228 GMessage("Add.R\t%s\t%d,%d,%d\t%d\t%d\t%d\n",
229 ky, h,init_p,init_x, iterations, fCount, fCapacity);
230 #endif
231 return r;
232 }
233 p=(p+x)%fCapacity;
234 n--;
235 }
236 if(i==-1) i=p;
237 #ifdef HASH_DBG_PRINT
238 GMessage("Add.N\t%s\t%d,%d,%d\t%d\t%d\t%d\n",
239 ky, h,init_p,init_x, iterations, fCount, fCapacity);
240 #endif
241 GTRACE(("GHash::insert: key=\"%s\"\n",ky));
242 //GMessage("GHash::insert: key=\"%s\"\n",ky);
243 GASSERT(0<=i && i<fCapacity);
244 GASSERT(hash[i].hash<0);
245 hash[i].hash=h;
246 hash[i].key=Gstrdup(ky);
247 hash[i].keyalloc=true;
248 lastkeyptr=hash[i].key;
249 hash[i].data= (void*) pdata;
250 fCount++;
251 if((100*fCount)>=(MAX_LOAD*fCapacity)) Resize(fCount);
252 GASSERT(fCount<fCapacity);
253 return pdata;
254 }
255
fAdd(const char * ky,OBJ * pdata)256 template <class OBJ> OBJ* GHash<OBJ>::fAdd(const char* ky, OBJ* pdata) {
257 int p,i,x,h,n;
258 if(!ky) GError("GHash::insert: NULL key argument.\n");
259 GASSERT(fCount<fCapacity);
260 h=GSTR_HASH(ky);
261 GASSERT(0<=h);
262 p=HASH1(h,fCapacity);
263 GASSERT(0<=p && p<fCapacity);
264 x=HASH2(h,fCapacity);
265 GASSERT(1<=x && x<fCapacity);
266 i=-1;
267 n=fCapacity;
268 #ifdef HASH_DBG_PRINT
269 int iterations=0;
270 int init_p=p;
271 int init_x=x;
272 #endif
273 while(n && hash[p].hash!=-1) {
274 if ((i==-1)&&(hash[p].hash==-2)) i=p;
275 if (hash[p].hash==h && strcmp(hash[p].key,ky)==0) {
276 //replace hash data for this key!
277 lastkeyptr=hash[p].key;
278 if (FREEDATA) (*fFreeProc)(hash[p].data);
279 hash[p].data = (void*) pdata;
280 #ifdef HASH_DBG_PRINT
281 GMessage("Add.R\t%s\t%d,%d,%d\t%d\t%d\t%d\n",
282 ky, h,init_p,init_x, iterations, fCount, fCapacity);
283 #endif
284 return pdata;
285 }
286 p=(p+x)%fCapacity;
287 #ifdef HASH_DBG_PRINT
288 ++iterations;
289 #endif
290 n--;
291 }
292 if(i==-1) i=p;
293 #ifdef HASH_DBG_PRINT
294 GMessage("Add.N\t%s\t%d,%d,%d\t%d\t%d\t%d\n",
295 ky, h,init_p,init_x, iterations, fCount, fCapacity);
296 #endif
297 GTRACE(("GHash::insert: key=\"%s\"\n",ky));
298 //GMessage("GHash::insert: key=\"%s\"\n",ky);
299 GASSERT(0<=i && i<fCapacity);
300 GASSERT(hash[i].hash<0);
301 hash[i].hash=h;
302 hash[i].key=Gstrdup(ky);
303 hash[i].keyalloc=true;
304 lastkeyptr=hash[i].key;
305 hash[i].data= (void*) pdata;
306 fCount++;
307 if((100*fCount)>=(MAX_LOAD*fCapacity)) Resize(fCount);
308 GASSERT(fCount<fCapacity);
309 return pdata;
310 }
311
shkAdd(const char * ky,OBJ * pdata)312 template <class OBJ> OBJ* GHash<OBJ>::shkAdd(const char* ky, OBJ* pdata) {
313 int p,i,x,h,n;
314 if(!ky) GError("GHash::insert: NULL key argument.\n");
315 GASSERT(fCount<fCapacity);
316 h=GSTR_HASH(ky);
317 GASSERT(0<=h);
318 p=HASH1(h,fCapacity);
319 GASSERT(0<=p && p<fCapacity);
320 x=HASH2(h,fCapacity);
321 GASSERT(1<=x && x<fCapacity);
322 i=-1;
323 n=fCapacity;
324 while(n && hash[p].hash!=-1){
325 if((i==-1)&&(hash[p].hash==-2)) i=p;
326 if(hash[p].hash==h && strcmp(hash[p].key,ky)==0){
327 //replace hash data for this key!
328 lastkeyptr=hash[p].key;
329 hash[p].data = (void*) pdata;
330 return (OBJ*)hash[p].data;
331 }
332 p=(p+x)%fCapacity;
333 n--;
334 }
335 if(i==-1) i=p;
336 GTRACE(("GHash::insert: key=\"%s\"\n",ky));
337 //GMessage("GHash::insert: key=\"%s\"\n",ky);
338 GASSERT(0<=i && i<fCapacity);
339 GASSERT(hash[i].hash<0);
340 hash[i].hash=h;
341 hash[i].key=(char *)ky;
342 lastkeyptr=hash[i].key;
343 hash[i].keyalloc=false;
344 hash[i].data= (void*) pdata;
345 fCount++;
346 if((100*fCount)>=(MAX_LOAD*fCapacity)) Resize(fCount);
347 GASSERT(fCount<fCapacity);
348 return pdata;
349 }
350
351 // Add or replace entry
Replace(const char * ky,OBJ * pdata)352 template <class OBJ> OBJ* GHash<OBJ>::Replace(const char* ky, OBJ* pdata){
353 int p,i,x,h,n;
354 if(!ky){ GError("GHash::replace: NULL key argument.\n"); }
355 GASSERT(fCount<fCapacity);
356 h=GSTR_HASH(ky);
357 GASSERT(0<=h);
358 p=HASH1(h,fCapacity);
359 GASSERT(0<=p && p<fCapacity);
360 x=HASH2(h,fCapacity);
361 GASSERT(1<=x && x<fCapacity);
362 i=-1;
363 n=fCapacity;
364 while(n && hash[p].hash!=-1){
365 if((i==-1)&&(hash[p].hash==-2)) i=p;
366 if(hash[p].hash==h && strcmp(hash[p].key,ky)==0){
367 GTRACE(("GHash::replace: %08x: replacing: \"%s\"\n",this,ky));
368 if (FREEDATA) (*fFreeProc)(hash[p].data);
369 hash[p].data=pdata;
370 return hash[p].data;
371 }
372 p=(p+x)%fCapacity;
373 n--;
374 }
375 if(i==-1) i=p;
376 GTRACE(("GHash::replace: %08x: inserting: \"%s\"\n",this,ky));
377 GASSERT(0<=i && i<fCapacity);
378 GASSERT(hash[i].hash<0);
379 hash[i].hash=h;
380 hash[i].key=Gstrdup(ky);
381 hash[i].data=pdata;
382 fCount++;
383 if((100*fCount)>=(MAX_LOAD*fCapacity)) Resize(fCount);
384 GASSERT(fCount<fCapacity);
385 return pdata;
386 }
387
388
389 // Remove entry
Remove(const char * ky)390 template <class OBJ> OBJ* GHash<OBJ>::Remove(const char* ky){
391 int p,x,h,n;
392 if(!ky){ GError("GHash::remove: NULL key argument.\n"); }
393 OBJ* removed=NULL;
394 if(0<fCount){
395 h=GSTR_HASH(ky);
396 GASSERT(0<=h);
397 p=HASH1(h,fCapacity);
398 GASSERT(0<=p && p<fCapacity);
399 x=HASH2(h,fCapacity);
400 GASSERT(1<=x && x<fCapacity);
401 GASSERT(fCount<fCapacity);
402 n=fCapacity;
403 while(n && hash[p].hash!=-1){
404 if(hash[p].hash==h && strcmp(hash[p].key,ky)==0){
405 GTRACE(("GHash::remove: %08x removing: \"%s\"\n",this,ky));
406 hash[p].hash=-2;
407 if (hash[p].keyalloc) GFREE((hash[p].key));
408 if (FREEDATA) (*fFreeProc)(hash[p].data);
409 else removed=(OBJ*)hash[p].data;
410 hash[p].key=NULL;
411 hash[p].data=NULL;
412 fCount--;
413 if((100*fCount)<=(MIN_LOAD*fCapacity)) Resize(fCount);
414 GASSERT(fCount<fCapacity);
415 return removed;
416 }
417 p=(p+x)%fCapacity;
418 n--;
419 }
420 }
421 return removed;
422 }
423
424
425 // Find entry
hasKey(const char * ky)426 template <class OBJ> bool GHash<OBJ>::hasKey(const char* ky) {
427 int p,x,h,n;
428 if(!ky){ GError("GHash::find: NULL key argument.\n"); }
429 if(0<fCount){
430 h=GSTR_HASH(ky);
431 GASSERT(0<=h);
432 p=HASH1(h,fCapacity);
433 GASSERT(0<=p && p<fCapacity);
434 x=HASH2(h,fCapacity);
435 GASSERT(1<=x && x<fCapacity);
436 GASSERT(fCount<fCapacity);
437 n=fCapacity;
438 while(n && hash[p].hash!=-1){
439 if(hash[p].hash==h && strcmp(hash[p].key,ky)==0){
440 return true;
441 }
442 p=(p+x)%fCapacity;
443 n--;
444 }
445 }
446 return false;
447 }
448
449
Find(const char * ky,char ** keyptr)450 template <class OBJ> OBJ* GHash<OBJ>::Find(const char* ky, char** keyptr){
451 int p,x,h,n;
452 if(!ky){ GError("GHash::find: NULL key argument.\n"); }
453 if (fCount==0) return NULL;
454 h=GSTR_HASH(ky);
455 GASSERT(0<=h);
456 p=HASH1(h,fCapacity);
457 GASSERT(0<=p && p<fCapacity);
458 x=HASH2(h,fCapacity);
459 GASSERT(1<=x && x<fCapacity);
460 GASSERT(fCount<fCapacity);
461 n=fCapacity;
462 #ifdef HASH_DBG_PRINT
463 int iterations=0;
464 int init_p=p;
465 int init_x=x;
466 #endif
467 while(n && hash[p].hash!=-1){
468 if(hash[p].hash==h && strcmp(hash[p].key,ky)==0){
469 if (keyptr!=NULL) *keyptr = hash[p].key;
470 #ifdef HASH_DBG_PRINT
471 GMessage("Found \t%s\t%d,%d,%d\t%d\t%d\t%d\n",
472 ky, h,init_p,init_x, iterations, fCount, fCapacity);
473 #endif
474 return (OBJ*)hash[p].data;
475 }
476 p=(p+x)%fCapacity;
477 n--;
478 #ifdef HASH_DBG_PRINT
479 ++iterations;
480 #endif
481 }
482 #ifdef HASH_DBG_PRINT
483 GMessage("Nfound\t%s\t%d,%d,%d\t%d\t%d\t%d\n",
484 ky, h,init_p,init_x, iterations, fCount, fCapacity);
485 #endif
486 return NULL;
487 }
488
startIterate()489 template <class OBJ> void GHash<OBJ>::startIterate() {// initialize a key iterator; call
490 fCurrentEntry=0;
491 }
492
NextKey()493 template <class OBJ> char* GHash<OBJ>::NextKey() {
494 int pos=fCurrentEntry;
495 while (pos<fCapacity && hash[pos].hash<0) pos++;
496 if (pos==fCapacity) {
497 fCurrentEntry=fCapacity;
498 return NULL;
499 }
500 else {
501 fCurrentEntry=pos+1;
502 return hash[pos].key;
503 }
504 }
505
NextData()506 template <class OBJ> OBJ* GHash<OBJ>::NextData() {
507 int pos=fCurrentEntry;
508 while (pos<fCapacity && hash[pos].hash<0) pos++;
509 if (pos==fCapacity) {
510 fCurrentEntry=fCapacity;
511 return NULL;
512 }
513 else {
514 fCurrentEntry=pos+1;
515 return (OBJ*)hash[pos].data;
516 }
517
518 }
519
NextData(char * & nextkey)520 template <class OBJ> OBJ* GHash<OBJ>::NextData(char* &nextkey) {
521 int pos=fCurrentEntry;
522 while (pos<fCapacity && hash[pos].hash<0) pos++;
523 if (pos==fCapacity) {
524 fCurrentEntry=fCapacity;
525 nextkey=NULL;
526 return NULL;
527 }
528 else {
529 fCurrentEntry=pos+1;
530 nextkey=hash[pos].key;
531 return (OBJ*)hash[pos].data;
532 }
533
534 }
535
536
537 // Get first non-empty entry
First() const538 template <class OBJ> int GHash<OBJ>::First() const {
539 int pos=0;
540 while(pos<fCapacity){ if(0<=hash[pos].hash) break; pos++; }
541 GASSERT(fCapacity<=pos || 0<=hash[pos].hash);
542 return pos;
543 }
544
545 // Get last non-empty entry
Last() const546 template <class OBJ> int GHash<OBJ>::Last() const {
547 int pos=fCapacity-1;
548 while(0<=pos){ if(0<=hash[pos].hash) break; pos--; }
549 GASSERT(pos<0 || 0<=hash[pos].hash);
550 return pos;
551 }
552
553
554 // Find next valid entry
Next(int pos) const555 template <class OBJ> int GHash<OBJ>::Next(int pos) const {
556 GASSERT(0<=pos && pos<fCapacity);
557 while(++pos <= fCapacity-1){ if(0<=hash[pos].hash) break; }
558 GASSERT(fCapacity<=pos || 0<=hash[pos].hash);
559 return pos;
560 }
561
562
563 // Find previous valid entry
Prev(int pos) const564 template <class OBJ> int GHash<OBJ>::Prev(int pos) const {
565 GASSERT(0<=pos && pos<fCapacity);
566 while(--pos >= 0){ if(0<=hash[pos].hash) break; }
567 GASSERT(pos<0 || 0<=hash[pos].hash);
568 return pos;
569 }
570
571
572 // Remove all
Clear()573 template <class OBJ> void GHash<OBJ>::Clear(){
574 int i;
575 for(i=0; i<fCapacity; i++){
576 if(hash[i].hash>=0){
577 if (hash[i].keyalloc) GFREE((hash[i].key));
578 if (FREEDATA)
579 (*fFreeProc)(hash[i].data);
580 }
581 }
582 GFREE(hash);
583 GMALLOC(hash, sizeof(GHashEntry)*DEF_HASH_SIZE);
584 //reinitialize it
585 for (i=0; i<DEF_HASH_SIZE; i++)
586 hash[i].hash=-1; //this will be an indicator for 'empty' entries
587 fCapacity=DEF_HASH_SIZE;
588 fCount=0;
589 }
590
591 // Destroy table
~GHash()592 template <class OBJ> GHash<OBJ>::~GHash(){
593 for(int i=0; i<fCapacity; i++){
594 if(hash[i].hash>=0){
595 if (hash[i].keyalloc) GFREE((hash[i].key));
596 if (FREEDATA) (*fFreeProc)(hash[i].data);
597 }
598 }
599 GFREE(hash);
600 }
601
602 class GStrSet:public GHash<int> {
603 protected:
604 bool free_keys;
605 public:
GStrSet(bool shared_keys=false)606 GStrSet(bool shared_keys=false):GHash<int>(false), free_keys(!shared_keys) {
607 }
Add(const char * str)608 void Add(const char* str) {
609 if (free_keys) {
610 //allocates a copy of str
611 GHash<int>::Add(str, NULL);
612 }
613 else this->shkAdd(str, NULL);
614 }
add(const char * str)615 void add(const char* str) { this->Add(str); }
push(const char * str)616 void push(const char* str) { this->Add(str); }
has(const char * str)617 bool has(const char* str) {
618 return hasKey(str);
619 }
620
621 };
622
623 #endif
624