ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GHash.hh
Revision: 2
Committed: Mon Mar 22 22:03:27 2010 UTC (9 years, 6 months ago) by gpertea
File size: 16896 byte(s)
Log Message:
added my gclib source files

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