00001
00002
00003
00004
00005
00006
00007 #ifndef __WVHASHTABLE_H
00008 #define __WVHASHTABLE_H
00009
00010 #include "wvlinklist.h"
00011 #include "wvstring.h"
00012
00013
00014 unsigned WvHash(WvStringParm s);
00015 unsigned WvHash(const char *s);
00016 unsigned WvHash(const int &i);
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090 class WvHashTableBase
00091 {
00092
00093 WvHashTableBase(const WvHashTableBase &t);
00094 protected:
00095 WvHashTableBase(unsigned _numslots);
00096 virtual ~WvHashTableBase() {};
00097 WvHashTableBase& operator= (const WvHashTableBase &t);
00098 void setup()
00099 { }
00100 void shutdown()
00101 { }
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
00112
00113
00114 size_t count() const;
00115
00116
00117
00118
00119
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 };
00143 };
00144
00145
00146
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
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,
00166 class K,
00167 class Accessor,
00168 template <class> class Comparator = OpEqComp
00169 >
00170 class WvHashTable : public WvHashTableBase
00171 {
00172
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
00187
00188
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
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
00270
00271
00272
00273
00274
00275
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
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
00307
00308
00309
00310
00311
00312
00313 template
00314 <
00315 typename TKey,
00316 typename TData,
00317 template <class> class Comparator = OpEqComp,
00318
00319
00320
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
00338
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
00349 WvMap(const WvMap &m);
00350
00351 public:
00352
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