00001
00002
00003
00004
00005
00006
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
00091 WvHashTableBase(const WvHashTableBase &t);
00092 protected:
00093 WvHashTableBase(unsigned _numslots);
00094 virtual ~WvHashTableBase() {};
00095 WvHashTableBase& operator= (const WvHashTableBase &t);
00096 void setup()
00097 { }
00098 void shutdown()
00099 { }
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
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,
00164 class K,
00165 class Accessor,
00166 template <class> class Comparator = OpEqComp
00167 >
00168 class WvHashTable : public WvHashTableBase
00169 {
00170
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
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
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305 template<typename TKey, typename _TData>
00306 class WvMapPair
00307 {
00308 typedef _TData TData;
00309 public:
00310 TKey key;
00311 TData data;
00312 WvMapPair(const TKey &_key, const TData &_data, bool _autofree)
00313 : key(_key), data(_data) { };
00314 };
00315
00316
00317
00318 template<typename TKey, typename _TData>
00319 class WvMapPair<TKey, _TData*>
00320 {
00321 typedef _TData* TData;
00322 public:
00323 TKey key;
00324 TData data;
00325 WvMapPair(const TKey &_key, const TData &_data, bool _autofree)
00326 : key(_key), data(_data), autofree(_autofree) { };
00327 virtual ~WvMapPair()
00328 { if (autofree) WvTraits<_TData>::release(data); };
00329 protected:
00330 bool autofree;
00331 };
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342 template
00343 <
00344 typename TKey,
00345 typename TData,
00346 template <class> class Comparator = OpEqComp,
00347
00348
00349
00350 template
00351 <
00352 class,
00353 class,
00354 class,
00355 template <class> class
00356 > class BackendHash = WvHashTable
00357 >
00358 class WvMap : public BackendHash<WvMapPair<TKey, TData>, TKey,
00359 WvMap<TKey, TData, Comparator, BackendHash>, Comparator>
00360 {
00361 protected:
00362 typedef WvMapPair<TKey, TData> MyPair;
00363 typedef WvMap<TKey, TData, Comparator, BackendHash> MyMap;
00364 typedef BackendHash<MyPair, TKey, MyMap, Comparator> MyHashTable;
00365
00366
00367
00368 mutable MyPair* last_accessed;
00369 MyPair* find_helper(const TKey &key) const
00370 {
00371 if (last_accessed &&
00372 Comparator<TKey>::compare(&last_accessed->key, &key))
00373 return last_accessed;
00374 return last_accessed = MyHashTable::operator[](key);
00375 }
00376
00377
00378 WvMap(const WvMap &m);
00379
00380 public:
00381
00382 static const TKey *get_key(const MyPair *obj)
00383 { return &obj->key; }
00384
00385 WvMap(int s) : MyHashTable(s), last_accessed(NULL) { };
00386 TData *find(const TKey &key) const
00387 {
00388 MyPair* p = find_helper(key);
00389 return p ? &p->data : (TData*)NULL;
00390 }
00391 MyPair *find_pair(const TKey &key) const
00392 {
00393 return find_helper(key);
00394 }
00395 TData &operator[](const TKey &key) const
00396 {
00397 MyPair* p = find_helper(key);
00398 assert(p && "WvMap: operator[] called with a non-existent key");
00399 return p->data;
00400 }
00401 bool exists(const TKey &key) const
00402 { return find_helper(key); }
00403 void set(const TKey &key, const TData &data, bool autofree = false)
00404 {
00405 if (find_helper(key))
00406 remove(key);
00407 add(key, data, autofree);
00408 }
00409 void add(const TKey &key, const TData &data, bool autofree = false)
00410 { MyHashTable::add(new MyPair(key, data, autofree), true); }
00411 void remove(const TKey &key)
00412 {
00413 last_accessed = NULL;
00414 MyHashTable::remove(MyHashTable::operator[](key));
00415 }
00416 void zap()
00417 {
00418 MyHashTable::zap();
00419 last_accessed = NULL;
00420 }
00421 typedef typename MyHashTable::Iter Iter;
00422 };
00423
00424
00425 #endif // __WVHASHTABLE_H