Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

wvhashtable.h

Go to the documentation of this file.
00001 /* -*- Mode: C++ -*- 00002 * Worldvisions Weaver Software: 00003 * Copyright (C) 1997-2002 Net Integration Technologies, Inc. 00004 * 00005 * A hash table container. 00006 */ 00007 #ifndef __WVHASHTABLE_H 00008 #define __WVHASHTABLE_H 00009 00010 #include "wvlinklist.h" 00011 #include "wvstring.h" 00012 00013 // predefined hashing functions (note: string hashes are case-insensitive) 00014 unsigned WvHash(WvStringParm s); 00015 unsigned WvHash(const char *s); 00016 unsigned WvHash(const int &i); 00017 00018 /** 00019 * A small, efficient, type-safe hash table (also known as dictionary) 00020 * container class. 00021 * 00022 * These are typically used to store a reasonably large number 00023 * of objects in no particular order and find them quickly when needed. 00024 * 00025 * Two semi-distinct types of hash tables are supported: tables and 00026 * dictionaries. 00027 * 00028 * TABLE EXAMPLE: 00029 * 00030 * DeclareWvTable(WvString); 00031 * int main() 00032 * { 00033 * WvString s("foo"), s2("blue"), s3("foo"); 00034 * WvStringTable t(10); // suggested size: 10 elements 00035 * t.add(&s); t.add(&s2); 00036 * printf("%s %s\n", t[s]->str, t[s3]->str); // prints "foo" "foo" 00037 * } 00038 * 00039 * 00040 * Here, the WvStrings "foo" and "blue" are stored in the table, and then 00041 * "foo" is looked up twice. Both table searches return &amp;s. 00042 * The suggested table size of 10 elements places no upper bound on 00043 * the maximum number of elements, but optimizes the hash table for 00044 * holding roughly 10 elements. 00045 * 00046 * To match an element, the WvString operator== function is used. That 00047 * means this particular example is rather contrived since if you already 00048 * have the search string, you do not need to find it in the table. 00049 * Objects with more specific operator== might have more luck. 00050 * 00051 * DICTIONARY EXAMPLE: 00052 * 00053 * class IntStr 00054 * { 00055 * int *key; 00056 * WvString data; 00057 * } 00058 * DeclareWvDict(IntStr, int, key[0]); 00059 * IntStrDict d(100); 00060 * 00061 * 00062 * Here, we are creating a dictionary that stores strings indexed by 00063 * integers. d[5] might return the address of IntStr number 5, which 00064 * in turn contains WvString number 5. When matching elements in this case, 00065 * a comparison is only done on key[0] of the two elements; thus, it is 00066 * not the operator== of IntStr that is important, but rather the operator== 00067 * for int. (In this case, the operator== of int is predefined.) 00068 * 00069 * The only reason *key is declared as a pointer in this example is to 00070 * demonstrate how to use pointer-based keys with our syntax. In this case 00071 * it would certainly make more sense to use int key; and 00072 * DeclareWvDict(IntStr, key). Note though, that int *key; and 00073 * DeclareWvDict(IntStr, key) is almost certainly not what you want, since 00074 * it would compare the POINTERS, not their values. 00075 * 00076 * The interface of this class resembles that of WvList by design. 00077 * In particular, we support iterators in a similar way. 00078 * 00079 * @see WvList<T> 00080 */ 00081 00082 /** 00083 * The untyped base class of WvHashTable<T>. 00084 * 00085 * Putting common code in here allows us to prevent it from being 00086 * replicated by each template instantiation of WvHashTable<T>. 00087 * 00088 */ 00089 00090 class WvHashTableBase 00091 { 00092 // Copy constructor - not defined anywhere! 00093 WvHashTableBase(const WvHashTableBase &t); 00094 protected: 00095 WvHashTableBase(unsigned _numslots); 00096 virtual ~WvHashTableBase() {}; 00097 WvHashTableBase& operator= (const WvHashTableBase &t); 00098 void setup() 00099 { /* default: do nothing */ } 00100 void shutdown() 00101 { /* default: do nothing */ } 00102 WvLink *prevlink(WvListBase *slots, const void *data, unsigned hash) const; 00103 void *genfind(WvListBase *slots, const void *data, unsigned hash) const; 00104 00105 virtual bool compare(const void *key, const void *elem) const = 0; 00106 public: 00107 unsigned numslots; 00108 WvListBase *wvslots; 00109 00110 /** 00111 * Returns the number of elements in the hash table. 00112 * Returns: the number of elements 00113 */ 00114 size_t count() const; 00115 00116 /** 00117 * Returns true if the hash table is empty. 00118 * Returns: true if empty 00119 */ 00120 bool isempty() const; 00121 00122 // base class for the auto-declared hash table iterators 00123 class IterBase 00124 { 00125 public: 00126 WvHashTableBase *tbl; 00127 unsigned tblindex; 00128 WvLink *link; 00129 00130 IterBase(WvHashTableBase &_tbl) : tbl(& _tbl) 00131 { } 00132 IterBase(const IterBase &other) : tbl(other.tbl), 00133 tblindex(other.tblindex), link(other.link) 00134 { } 00135 void rewind() 00136 { tblindex = 0; link = &tbl->wvslots[0].head; } 00137 WvLink *next(); 00138 WvLink *cur() const 00139 { return link; } 00140 void *vptr() const 00141 { return link->data; } 00142 }; 00143 }; 00144 00145 00146 // Default comparison function used by WvHashTable 00147 template <class K> 00148 struct OpEqComp 00149 { 00150 static bool compare(const K *key1, const K *key2) 00151 { return *key1 == *key2; } 00152 }; 00153 00154 00155 // Case-insensitive comparison function for WvHastTable 00156 template <class K> 00157 struct StrCaseComp 00158 { 00159 static bool compare(const K *key1, const K *key2) 00160 { return strcasecmp(*key1, *key2) == 0; } 00161 }; 00162 00163 00164 template < 00165 class T, // element type 00166 class K, // key type 00167 class Accessor, // element to key 00168 template <class> class Comparator = OpEqComp // comparison func 00169 > 00170 class WvHashTable : public WvHashTableBase 00171 { 00172 // copy constructor: not defined anywhere! 00173 WvHashTable(const WvHashTable &h); 00174 protected: 00175 typedef Comparator<K> MyComparator; 00176 00177 unsigned hash(const T *data) 00178 { return WvHash(*Accessor::get_key(data)); } 00179 00180 virtual bool compare(const void *key, const void *elem) const 00181 { return MyComparator::compare((const K *)key, 00182 Accessor::get_key((const T *)elem)); } 00183 00184 public: 00185 /** 00186 * Creates a hash table. 00187 * 00188 * "numslots" is the suggested number of slots 00189 */ 00190 WvHashTable(unsigned _numslots) : WvHashTableBase(_numslots) 00191 { wvslots = new WvList<T>[numslots]; setup(); } 00192 00193 WvList<T> *sl() 00194 { return (WvList<T> *)wvslots; } 00195 00196 virtual ~WvHashTable() 00197 { shutdown(); delete[] sl(); } 00198 00199 void add(T *data, bool auto_free) 00200 { sl()[hash(data) % numslots].append(data, auto_free); } 00201 00202 WvLink *getlink(const K &key) 00203 { return prevlink(wvslots, &key, WvHash(key))->next; } 00204 00205 T *operator[] (const K &key) const 00206 { return (T *)genfind(wvslots, &key, WvHash(key)); } 00207 00208 void remove(const T *data) 00209 { 00210 unsigned h = hash(data); 00211 WvLink *l = prevlink(wvslots, Accessor::get_key(data), h); 00212 if (l && l->next) sl()[h % numslots].unlink_after(l); 00213 } 00214 00215 void zap() 00216 { 00217 delete[] sl(); 00218 wvslots = new WvList<T>[numslots]; 00219 } 00220 00221 class Iter : public WvHashTableBase::IterBase 00222 { 00223 public: 00224 Iter(WvHashTable &_tbl) : IterBase(_tbl) 00225 { } 00226 Iter(const Iter &other) : IterBase(other) 00227 { } 00228 T *ptr() const 00229 { return (T *)link->data; } 00230 WvIterStuff(T); 00231 }; 00232 00233 typedef class WvSorter<T, WvHashTableBase, WvHashTableBase::IterBase> 00234 Sorter; 00235 }; 00236 00237 00238 // ****************************************** 00239 // WvDict and WvTable 00240 00241 00242 #define DeclareWvDict2(_classname_, _type_, _ftype_, _field_) \ 00243 __WvDict_base(_classname_, _type_, _ftype_, &obj->_field_) 00244 00245 #define DeclareWvDict(_type_, _ftype_, _field_) \ 00246 DeclareWvDict2(_type_##Dict, _type_, _ftype_, _field_) 00247 00248 #define DeclareWvTable2(_classname_, _type_) \ 00249 __WvDict_base(_classname_, _type_, _type_, obj) 00250 00251 #define DeclareWvTable(_type_) \ 00252 DeclareWvTable2(_type_##Table, _type_) 00253 00254 00255 #define __WvDict_base(_classname_, _type_, _ftype_, _field_) \ 00256 template <class T, class K> \ 00257 struct _classname_##Accessor \ 00258 { \ 00259 static const K *get_key(const T *obj) \ 00260 { return _field_; } \ 00261 }; \ 00262 \ 00263 typedef WvHashTable<_type_, _ftype_, \ 00264 _classname_##Accessor<_type_, _ftype_> > _classname_ 00265 00266 00267 00268 // ****************************************** 00269 // WvMap 00270 00271 // ***************************** 00272 // WvPair 00273 00274 // Type specification to facilitate auto_free 00275 // Object type - ignores auto_free 00276 template<typename TKey, typename _TData> 00277 class WvMapPair 00278 { 00279 typedef _TData TData; 00280 public: 00281 TKey key; 00282 TData data; 00283 WvMapPair(const TKey &_key, const TData &_data, bool _auto_free) 00284 : key(_key), data(_data) { }; 00285 }; 00286 00287 00288 // Pointer type 00289 template<typename TKey, typename _TData> 00290 class WvMapPair<TKey, _TData*> 00291 { 00292 typedef _TData* TData; 00293 public: 00294 TKey key; 00295 TData data; 00296 WvMapPair(const TKey &_key, const TData &_data, bool _auto_free) 00297 : key(_key), data(_data), auto_free(_auto_free) { }; 00298 virtual ~WvMapPair() 00299 { if (auto_free) delete data; }; 00300 protected: 00301 bool auto_free; 00302 }; 00303 00304 00305 // ***************************** 00306 // Main map template 00307 // 00308 // Since operator[] returns a reference you should always check 00309 // if the element exists() before using it. 00310 // Alternatively, use find(), to get a pointer to the data type, 00311 // which will be null if the element does not exist. 00312 00313 template 00314 < 00315 typename TKey, 00316 typename TData, 00317 template <class> class Comparator = OpEqComp, 00318 // Warning: Funny looking syntax follows! 00319 // If we decide that WvScatterHash is the One True Hash, 00320 // just get rid of this part 00321 template 00322 < 00323 class, 00324 class, 00325 class, 00326 template <class> class 00327 > class BackendHash = WvHashTable 00328 > 00329 class WvMap : public BackendHash<WvMapPair<TKey, TData>, TKey, 00330 WvMap<TKey, TData, Comparator, BackendHash>, Comparator> 00331 { 00332 protected: 00333 typedef WvMapPair<TKey, TData> MyPair; 00334 typedef WvMap<TKey, TData, Comparator, BackendHash> MyMap; 00335 typedef BackendHash<MyPair, TKey, MyMap, Comparator> MyHashTable; 00336 00337 // We need this last_accessed thing to make sure exists()/operator[] 00338 // does not cost us two hash lookups 00339 mutable MyPair* last_accessed; 00340 MyPair* find_helper(const TKey &key) const 00341 { 00342 if (last_accessed && 00343 Comparator<TKey>::compare(&last_accessed->key, &key)) 00344 return last_accessed; 00345 return last_accessed = MyHashTable::operator[](key); 00346 } 00347 00348 // copy constructor: not defined anywhere! 00349 WvMap(const WvMap &m); 00350 00351 public: 00352 // accessor method for WvHashTable to use 00353 static const TKey *get_key(const MyPair *obj) 00354 { return &obj->key; } 00355 00356 WvMap(int s) : MyHashTable(s), last_accessed(NULL) { }; 00357 TData *find(const TKey &key) const 00358 { 00359 MyPair* p = find_helper(key); 00360 return p ? &p->data : (TData*)NULL; 00361 } 00362 TData &operator[](const TKey &key) const 00363 { 00364 MyPair* p = find_helper(key); 00365 assert(p && "WvMap: operator[] called with a non-existent key"); 00366 return p->data; 00367 } 00368 bool exists(const TKey &key) const 00369 { return find_helper(key); } 00370 void set(const TKey &key, const TData &data, bool auto_free = false) 00371 { 00372 if (find_helper(key)) 00373 remove(key); 00374 add(key, data, auto_free); 00375 } 00376 void add(const TKey &key, const TData &data, bool auto_free = false) 00377 { MyHashTable::add(new MyPair(key, data, auto_free), true); } 00378 void remove(const TKey &key) 00379 { 00380 last_accessed = NULL; 00381 MyHashTable::remove(MyHashTable::operator[](key)); 00382 } 00383 typedef typename MyHashTable::Iter Iter; 00384 }; 00385 00386 00387 #endif // __WVHASHTABLE_H

Generated on Tue Oct 5 01:09:20 2004 for WvStreams by doxygen 1.3.7