00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
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 #ifndef __WVHASHTABLE_H
00068 #define __WVHASHTABLE_H
00069
00070 #include "wvlinklist.h"
00071
00072
00073 class WvString;
00074
00075
00076 unsigned WvHash(const WvString &s);
00077 unsigned WvHash(const char *s);
00078 unsigned WvHash(const int &i);
00079
00080
00081
00082 class WvHashTableBase
00083 {
00084 protected:
00085 typedef bool Comparator(const void *, const void *);
00086
00087 WvHashTableBase(unsigned _numslots);
00088 WvHashTableBase(const WvHashTableBase &t);
00089 WvHashTableBase& operator= (const WvHashTableBase &t);
00090 void setup()
00091 { }
00092 void shutdown()
00093 { }
00094 WvLink *prevlink(WvListBase *slots, const void *data,
00095 unsigned hash, Comparator *comp);
00096 void *genfind(WvListBase *slots, const void *data,
00097 unsigned hash, Comparator *comp);
00098 public:
00099 unsigned numslots;
00100 WvListBase *slots;
00101
00102 size_t count() const;
00103
00104
00105 class IterBase
00106 {
00107 public:
00108 WvHashTableBase *tbl;
00109 unsigned tblindex;
00110 WvLink *link;
00111
00112 IterBase(WvHashTableBase &_tbl)
00113 { tbl = &_tbl; }
00114 void rewind()
00115 { tblindex = 0; link = &tbl->slots[0].head; }
00116 WvLink *next();
00117 WvLink *cur() const
00118 { return link; }
00119 };
00120 };
00121
00122
00123
00124
00125 typedef const void *WvFieldPointer(const void *obj);
00126
00127 template <class _type_, class _ftype_, WvFieldPointer *fptr>
00128 class WvHashTable : public WvHashTableBase
00129 {
00130 protected:
00131
00132
00133 unsigned hash(const _type_ *data)
00134 { return WvHash(*(const _ftype_ *)fptr(data)); }
00135 static bool comparator(const void *key, const void *elem)
00136 { return *(_ftype_ *)key == *(const _ftype_ *)fptr((const _type_ *)elem); }
00137
00138 public:
00139 WvHashTable(unsigned _numslots) : WvHashTableBase(_numslots)
00140 { slots = new WvList<_type_>[numslots]; setup(); }
00141
00142 WvList<_type_> *sl()
00143 { return (WvList<_type_> *)slots; }
00144
00145 ~WvHashTable()
00146 { shutdown(); delete[] sl(); }
00147
00148 void add(_type_ *data, bool auto_free)
00149 { sl()[hash(data) % numslots].append(data, auto_free); }
00150
00151 _type_ *operator[] (const _ftype_ &key)
00152 { return (_type_ *)genfind(slots, &key, WvHash(key), comparator); }
00153
00154 void remove(const _type_ *data)
00155 {
00156 unsigned h = hash(data);
00157 WvLink *l = prevlink(slots, fptr(data), h, comparator);
00158 if (l && l->next) sl()[h % numslots].unlink_after(l);
00159 }
00160
00161 void zap()
00162 {
00163 delete[] sl();
00164 slots = new WvList<_type_>[numslots];
00165 }
00166
00167 class Iter : public WvHashTableBase::IterBase
00168 {
00169 public:
00170 Iter(WvHashTable &_tbl) : IterBase(_tbl)
00171 { }
00172 _type_ *ptr() const
00173 { return (_type_ *)link->data; }
00174 WvIterStuff(_type_);
00175 };
00176
00177 typedef class WvSorter<_type_,WvHashTableBase,WvHashTableBase::IterBase>
00178 Sorter;
00179 };
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190 #define __WvDict_base(_classname_, _type_, _ftype_, _field_, _extra_) \
00191 struct _classname_##_hack \
00192 { \
00193 static inline const void *_classname_##_fptr_(const void *obj) \
00194 { return &((*(const _type_ *)obj) _field_); } \
00195 }; \
00196 \
00197 typedef WvHashTable<_type_, _ftype_, \
00198 _classname_##_hack::_classname_##_fptr_> \
00199 _classname_##Base; \
00200 \
00201 class _classname_ : public _classname_##Base \
00202 { \
00203 public: \
00204 _classname_(unsigned _numslots) : _classname_##Base(_numslots) \
00205 { } \
00206 void add(_type_ *data, bool auto_free) \
00207 { _classname_##Base::add(data, auto_free); }; \
00208 _extra_ \
00209 };
00210
00211
00212 #define DeclareWvDict3(_type_, _newname_, _ftype_, _field_, _extra_) \
00213 __WvDict_base(_newname_, _type_, _ftype_, . _field_, _extra_)
00214 #define DeclareWvDict2(_type_, _ftype_, _field_, _extra_) \
00215 DeclareWvDict3(_type_, _type_##Dict, _ftype_, _field_, _extra_)
00216 #define DeclareWvDict(_type_, _ftype_, _field_) \
00217 DeclareWvDict2(_type_, _ftype_, _field_, )
00218
00219 #define DeclareWvTable3(_type_, _newname_, _extra_) \
00220 __WvDict_base(_newname_, _type_, _type_, , _extra_)
00221 #define DeclareWvTable2(_type_, _extra_) \
00222 DeclareWvTable3(_type_, _type_##Table, _extra_)
00223 #define DeclareWvTable(_type_) DeclareWvTable2(_type_, )
00224
00225
00226 #endif // __WVHASHTABLE_H