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 <assert.h>
00014
00087 class WvHashTableBase
00088 {
00089
00090 WvHashTableBase(const WvHashTableBase &t);
00091 protected:
00092 WvHashTableBase(unsigned _numslots);
00093 virtual ~WvHashTableBase() {};
00094 WvHashTableBase& operator= (const WvHashTableBase &t);
00095 void setup()
00096 { }
00097 void shutdown()
00098 { }
00099 WvLink *prevlink(WvListBase *slots, const void *data, unsigned hash) const;
00100 void *genfind(WvListBase *slots, const void *data, unsigned hash) const;
00101
00102 virtual bool compare(const void *key, const void *elem) const = 0;
00103 public:
00104 unsigned numslots;
00105 WvListBase *wvslots;
00106
00111 size_t count() const;
00112
00117 bool isempty() const;
00118
00119
00120 class IterBase
00121 {
00122 public:
00123 WvHashTableBase *tbl;
00124 unsigned tblindex;
00125 WvLink *link;
00126
00127 IterBase(WvHashTableBase &_tbl) : tbl(& _tbl)
00128 { }
00129 IterBase(const IterBase &other) : tbl(other.tbl),
00130 tblindex(other.tblindex), link(other.link)
00131 { }
00132 void rewind()
00133 { tblindex = 0; link = &tbl->wvslots[0].head; }
00134 WvLink *next();
00135 WvLink *cur() const
00136 { return link; }
00137 void *vptr() const
00138 { return link->data; }
00139 };
00140 };
00141
00142
00143 template <
00144 class T,
00145 class K,
00146 class Accessor,
00147 template <class> class Comparator = OpEqComp
00148 >
00149 class WvHashTable : public WvHashTableBase
00150 {
00151
00152 WvHashTable(const WvHashTable &h);
00153 protected:
00154 typedef Comparator<K> MyComparator;
00155
00156 unsigned hash(const T *data)
00157 { return WvHash(*Accessor::get_key(data)); }
00158
00159 virtual bool compare(const void *key, const void *elem) const
00160 { return MyComparator::compare((const K *)key,
00161 Accessor::get_key((const T *)elem)); }
00162
00163 public:
00169 WvHashTable(unsigned _numslots) : WvHashTableBase(_numslots)
00170 { wvslots = new WvList<T>[numslots]; setup(); }
00171
00172 WvList<T> *sl()
00173 { return (WvList<T> *)wvslots; }
00174
00175 virtual ~WvHashTable()
00176 { shutdown(); deletev sl(); }
00177
00178 void add(T *data, bool auto_free)
00179 { sl()[hash(data) % numslots].append(data, auto_free); }
00180
00181 WvLink *getlink(const K &key)
00182 { return prevlink(wvslots, &key, WvHash(key))->next; }
00183
00184 T *operator[] (const K &key) const
00185 { return (T *)genfind(wvslots, &key, WvHash(key)); }
00186
00187 void remove(const T *data)
00188 {
00189 unsigned h = hash(data);
00190 WvLink *l = prevlink(wvslots, Accessor::get_key(data), h);
00191 if (l && l->next) sl()[h % numslots].unlink_after(l);
00192 }
00193
00194 void zap()
00195 {
00196 deletev sl();
00197 wvslots = new WvList<T>[numslots];
00198 }
00199
00200 class Iter : public WvHashTableBase::IterBase
00201 {
00202 public:
00203 Iter(WvHashTable &_tbl) : IterBase(_tbl)
00204 { }
00205 Iter(const Iter &other) : IterBase(other)
00206 { }
00207 T *ptr() const
00208 { return (T *)link->data; }
00209 WvIterStuff(T);
00210 };
00211
00212 typedef class WvSorter<T, WvHashTableBase, WvHashTableBase::IterBase>
00213 Sorter;
00214 };
00215
00216
00217
00218
00219
00220
00221 #define DeclareWvDict2(_classname_, _type_, _ftype_, _field_) \
00222 __WvDict_base(_classname_, _type_, _ftype_, &obj->_field_)
00223
00224 #define DeclareWvDict(_type_, _ftype_, _field_) \
00225 DeclareWvDict2(_type_##Dict, _type_, _ftype_, _field_)
00226
00227 #define DeclareWvTable2(_classname_, _type_) \
00228 __WvDict_base(_classname_, _type_, _type_, obj)
00229
00230 #define DeclareWvTable(_type_) \
00231 DeclareWvTable2(_type_##Table, _type_)
00232
00233
00234 #define __WvDict_base(_classname_, _type_, _ftype_, _field_) \
00235 template <class T, class K> \
00236 struct _classname_##Accessor \
00237 { \
00238 static const K *get_key(const T *obj) \
00239 { return _field_; } \
00240 }; \
00241 \
00242 typedef WvHashTable<_type_, _ftype_, \
00243 _classname_##Accessor<_type_, _ftype_> > _classname_
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255 template<typename TKey, typename _TData>
00256 class WvMapPair
00257 {
00258 typedef _TData TData;
00259 public:
00260 TKey key;
00261 TData data;
00262 WvMapPair(const TKey &_key, const TData &_data, bool _auto_free)
00263 : key(_key), data(_data) { };
00264 };
00265
00266
00267
00268 template<typename TKey, typename _TData>
00269 class WvMapPair<TKey, _TData*>
00270 {
00271 typedef _TData* TData;
00272 public:
00273 TKey key;
00274 TData data;
00275 WvMapPair(const TKey &_key, const TData &_data, bool _auto_free)
00276 : key(_key), data(_data), auto_free(_auto_free) { };
00277 virtual ~WvMapPair()
00278 { if (auto_free) delete data; };
00279 protected:
00280 bool auto_free;
00281 };
00282
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292 template
00293 <
00294 typename TKey,
00295 typename TData,
00296 template <class> class Comparator = OpEqComp,
00297
00298
00299
00300 template
00301 <
00302 class,
00303 class,
00304 class,
00305 template <class> class
00306 > class BackendHash = WvHashTable
00307 >
00308 class WvMap : public BackendHash<WvMapPair<TKey, TData>, TKey,
00309 WvMap<TKey, TData, Comparator, BackendHash>, Comparator>
00310 {
00311 protected:
00312 typedef WvMapPair<TKey, TData> MyPair;
00313 typedef WvMap<TKey, TData, Comparator, BackendHash> MyMap;
00314 typedef BackendHash<MyPair, TKey, MyMap, Comparator> MyHashTable;
00315
00316
00317
00318 mutable MyPair* last_accessed;
00319 MyPair* find_helper(const TKey &key) const
00320 {
00321 if (last_accessed &&
00322 Comparator<TKey>::compare(&last_accessed->key, &key))
00323 return last_accessed;
00324 return last_accessed = MyHashTable::operator[](key);
00325 }
00326
00327
00328 WvMap(const WvMap &m);
00329
00330 public:
00331
00332 static const TKey *get_key(const MyPair *obj)
00333 { return &obj->key; }
00334
00335 WvMap(int s) : MyHashTable(s), last_accessed(NULL) { };
00336 TData *find(const TKey &key) const
00337 {
00338 MyPair* p = find_helper(key);
00339 return p ? &p->data : (TData*)NULL;
00340 }
00341 MyPair *find_pair(const TKey &key) const
00342 {
00343 return find_helper(key);
00344 }
00345 TData &operator[](const TKey &key) const
00346 {
00347 MyPair* p = find_helper(key);
00348 assert(p && "WvMap: operator[] called with a non-existent key");
00349 return p->data;
00350 }
00351 bool exists(const TKey &key) const
00352 { return find_helper(key); }
00353 void set(const TKey &key, const TData &data, bool auto_free = false)
00354 {
00355 if (find_helper(key))
00356 remove(key);
00357 add(key, data, auto_free);
00358 }
00359 void add(const TKey &key, const TData &data, bool auto_free = false)
00360 { MyHashTable::add(new MyPair(key, data, auto_free), true); }
00361 void remove(const TKey &key)
00362 {
00363 last_accessed = NULL;
00364 MyHashTable::remove(MyHashTable::operator[](key));
00365 }
00366 void zap()
00367 {
00368 MyHashTable::zap();
00369 last_accessed = NULL;
00370 }
00371 typedef typename MyHashTable::Iter Iter;
00372 };
00373
00374
00375 #endif // __WVHASHTABLE_H