[68] | 1 | // This file is a part of the Framsticks GDK library.
|
---|
| 2 | // Copyright (C) 2002-2011 Szymon Ulatowski. See LICENSE.txt for details.
|
---|
| 3 | // Refer to http://www.framsticks.com/ for further information.
|
---|
| 4 |
|
---|
| 5 | #ifndef _HASHTABLE_H_
|
---|
| 6 | #define _HASHTABLE_H_
|
---|
| 7 |
|
---|
| 8 | #include "sstring.h"
|
---|
| 9 |
|
---|
| 10 | class HashEntry
|
---|
| 11 | {
|
---|
| 12 | public:
|
---|
| 13 | int hash;
|
---|
| 14 | SString key;
|
---|
| 15 | void *value;
|
---|
| 16 | HashEntry *next;
|
---|
| 17 |
|
---|
| 18 | HashEntry(int h,const SString& k,void *v):hash(h),key(k),value(v),next(0){}
|
---|
| 19 | };
|
---|
| 20 |
|
---|
| 21 | class HashEntryIterator;
|
---|
| 22 |
|
---|
| 23 | class HashTable
|
---|
| 24 | {
|
---|
| 25 | friend class HashEntryIterator;
|
---|
| 26 | HashEntry **tab;
|
---|
| 27 | int size;
|
---|
| 28 | int count;
|
---|
| 29 | int threshold;
|
---|
| 30 | float load;
|
---|
| 31 | long sync;
|
---|
| 32 |
|
---|
| 33 | int hash(const char *s);
|
---|
| 34 | void rehash(int newsize);
|
---|
| 35 | public:
|
---|
| 36 |
|
---|
| 37 | HashTable(int initsize,float lo) {init(initsize,lo);}
|
---|
| 38 | HashTable(int initsize) {init(initsize,0.75);}
|
---|
| 39 | HashTable() {init();}
|
---|
| 40 | ~HashTable();
|
---|
| 41 |
|
---|
| 42 | /** always use init() after clear() ! */
|
---|
| 43 | void clear();
|
---|
| 44 | void init(int initsize=11,float lo=0.75);
|
---|
| 45 |
|
---|
| 46 | int getSize() {return count;}
|
---|
| 47 | void* put(const SString& key,void *value);
|
---|
| 48 | void* get(const SString& key, int *reallygot=0);
|
---|
| 49 | void* remove(const SString& key);
|
---|
| 50 | /** can be used inside iteration loop:
|
---|
| 51 | for(HashEntryIterator it(hashtable);it;) hashtable.remove(it);
|
---|
| 52 | \note iterator is "iterated" to the next entry when the current one is removed (no "it++"!)
|
---|
| 53 | */
|
---|
| 54 | void* remove(HashEntryIterator& it);
|
---|
| 55 |
|
---|
| 56 | void debugprint();
|
---|
| 57 | void getstats(float *);
|
---|
| 58 | };
|
---|
| 59 |
|
---|
| 60 | /** for(HashEntryIterator it(hashtable);it;it++)
|
---|
| 61 | {
|
---|
| 62 | ... it->value
|
---|
| 63 | ... it->key
|
---|
| 64 | }
|
---|
| 65 | */
|
---|
| 66 | class HashEntryIterator
|
---|
| 67 | {
|
---|
| 68 | void findNext();
|
---|
| 69 | public:
|
---|
| 70 | HashTable *ht;
|
---|
| 71 | int hashindex;
|
---|
| 72 | HashEntry *entry;
|
---|
| 73 | int sync;
|
---|
| 74 | HashEntryIterator(HashTable&t):ht(&t),hashindex(0),entry(t.tab[0]),sync(ht->sync)
|
---|
| 75 | {if (!entry) findNext();}
|
---|
| 76 | HashEntryIterator() {}
|
---|
| 77 | void operator++();
|
---|
| 78 | void operator++(int) {operator++();}
|
---|
| 79 | HashEntry* operator->() {return entry;}
|
---|
| 80 | bool isValid() {return (entry&&(sync==ht->sync))?1:0;}
|
---|
| 81 | };
|
---|
| 82 |
|
---|
| 83 |
|
---|
| 84 | #endif
|
---|