WvStreams
|
00001 /* -*- Mode: C++ -*- 00002 * Worldvisions Weaver Software: 00003 * Copyright (C) 1997-2002 Net Integration Technologies, Inc. 00004 * 00005 * A hash table container. See also wvscatterhash.h, which is newer, faster, 00006 * and better. 00007 */ 00008 #ifndef __WVHASHTABLE_H 00009 #define __WVHASHTABLE_H 00010 00011 #include "wvhash.h" 00012 #include "wvlinklist.h" 00013 #include "wvtypetraits.h" 00014 #include <assert.h> 00015 00088 class WvHashTableBase 00089 { 00090 // Copy constructor - not defined anywhere! 00091 WvHashTableBase(const WvHashTableBase &t); 00092 protected: 00093 WvHashTableBase(unsigned _numslots); 00094 virtual ~WvHashTableBase() {}; 00095 WvHashTableBase& operator= (const WvHashTableBase &t); 00096 void setup() 00097 { /* default: do nothing */ } 00098 void shutdown() 00099 { /* default: do nothing */ } 00100 WvLink *prevlink(WvListBase *slots, const void *data, unsigned hash) const; 00101 void *genfind(WvListBase *slots, const void *data, unsigned hash) const; 00102 00103 00104 00105 virtual bool compare(const void *key, const void *elem) const = 0; 00106 public: 00107 unsigned numslots; 00108 WvListBase *wvslots; 00109 00114 size_t count() const; 00115 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 00146 bool get_autofree() const 00147 { 00148 return link->get_autofree(); 00149 } 00150 00154 void set_autofree(bool autofree) 00155 { 00156 link->set_autofree(autofree); 00157 } 00158 }; 00159 }; 00160 00161 00162 template < 00163 class T, // element type 00164 class K, // key type 00165 class Accessor, // element to key 00166 template <class> class Comparator = OpEqComp // comparison func 00167 > 00168 class WvHashTable : public WvHashTableBase 00169 { 00170 // copy constructor: not defined anywhere! 00171 WvHashTable(const WvHashTable &h); 00172 protected: 00173 typedef Comparator<K> MyComparator; 00174 00175 unsigned hash(const T *data) 00176 { return WvHash(*Accessor::get_key(data)); } 00177 00178 virtual bool compare(const void *key, const void *elem) const 00179 { return MyComparator::compare((const K *)key, 00180 Accessor::get_key((const T *)elem)); } 00181 00182 public: 00188 WvHashTable(unsigned _numslots) : WvHashTableBase(_numslots) 00189 { wvslots = new WvList<T>[numslots]; setup(); } 00190 00191 WvList<T> *sl() 00192 { return (WvList<T> *)wvslots; } 00193 00194 virtual ~WvHashTable() 00195 { shutdown(); deletev sl(); } 00196 00197 void add(T *data, bool autofree) 00198 { sl()[hash(data) % numslots].append(data, autofree); } 00199 00200 WvLink *getlink(const K &key) 00201 { return prevlink(wvslots, &key, WvHash(key))->next; } 00202 00203 T *operator[] (const K &key) const 00204 { return (T *)genfind(wvslots, &key, WvHash(key)); } 00205 00209 bool get_autofree(const K &key) const 00210 { 00211 WvLink *l = getlink(key); 00212 if (l) 00213 return l->get_autofree(); 00214 return false; 00215 } 00216 00217 bool get_autofree(const T *data) const 00218 { 00219 return get_autofree(hash(data)); 00220 } 00221 00225 void set_autofree(const K &key, bool autofree) 00226 { 00227 WvLink *l = getlink(key); 00228 if (l) 00229 l->set_autofree(autofree); 00230 } 00231 00232 void set_autofree(const T *data, bool autofree) 00233 { 00234 set_autofree(hash(data), autofree); 00235 } 00236 00237 void remove(const T *data) 00238 { 00239 unsigned h = hash(data); 00240 WvLink *l = prevlink(wvslots, Accessor::get_key(data), h); 00241 if (l && l->next) sl()[h % numslots].unlink_after(l); 00242 } 00243 00244 void zap() 00245 { 00246 deletev sl(); 00247 wvslots = new WvList<T>[numslots]; 00248 } 00249 00250 class Iter : public WvHashTableBase::IterBase 00251 { 00252 public: 00253 Iter(WvHashTable &_tbl) : IterBase(_tbl) 00254 { } 00255 Iter(const Iter &other) : IterBase(other) 00256 { } 00257 T *ptr() const 00258 { return (T *)link->data; } 00259 WvIterStuff(T); 00260 }; 00261 00262 typedef class WvSorter<T, WvHashTableBase, WvHashTableBase::IterBase> 00263 Sorter; 00264 }; 00265 00266 00267 // ****************************************** 00268 // WvDict and WvTable 00269 00270 00271 #define DeclareWvDict2(_classname_, _type_, _ftype_, _field_) \ 00272 __WvDict_base(_classname_, _type_, _ftype_, &obj->_field_) 00273 00274 #define DeclareWvDict(_type_, _ftype_, _field_) \ 00275 DeclareWvDict2(_type_##Dict, _type_, _ftype_, _field_) 00276 00277 #define DeclareWvTable2(_classname_, _type_) \ 00278 __WvDict_base(_classname_, _type_, _type_, obj) 00279 00280 #define DeclareWvTable(_type_) \ 00281 DeclareWvTable2(_type_##Table, _type_) 00282 00283 00284 #define __WvDict_base(_classname_, _type_, _ftype_, _field_) \ 00285 template <class T, class K> \ 00286 struct _classname_##Accessor \ 00287 { \ 00288 static const K *get_key(const T *obj) \ 00289 { return _field_; } \ 00290 }; \ 00291 \ 00292 typedef WvHashTable<_type_, _ftype_, \ 00293 _classname_##Accessor<_type_, _ftype_> > _classname_ 00294 00295 #endif // __WVHASHTABLE_H