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