WvStreams
wvhashtable.h
1/* -*- Mode: C++ -*-
2 * Worldvisions Weaver Software:
3 * Copyright (C) 1997-2002 Net Integration Technologies, Inc.
4 *
5 * A hash table container. See also wvscatterhash.h, which is newer, faster,
6 * and better.
7 */
8#ifndef __WVHASHTABLE_H
9#define __WVHASHTABLE_H
10
11#include "wvhash.h"
12#include "wvlinklist.h"
13#include "wvtypetraits.h"
14#include <assert.h>
15
89{
90 // Copy constructor - not defined anywhere!
92protected:
93 WvHashTableBase(unsigned _numslots);
94 virtual ~WvHashTableBase() {};
95 WvHashTableBase& operator= (const WvHashTableBase &t);
96 void setup()
97 { /* default: do nothing */ }
98 void shutdown()
99 { /* default: do nothing */ }
100 WvLink *prevlink(WvListBase *slots, const void *data, unsigned hash) const;
101 void *genfind(WvListBase *slots, const void *data, unsigned hash) const;
102
103
104
105 virtual bool compare(const void *key, const void *elem) const = 0;
106public:
107 unsigned numslots;
108 WvListBase *wvslots;
109
114 size_t count() const;
115
120 bool isempty() const;
121
122 // base class for the auto-declared hash table iterators
124 {
125 public:
126 WvHashTableBase *tbl;
127 unsigned tblindex;
128 WvLink *link;
129
130 IterBase(WvHashTableBase &_tbl) : tbl(& _tbl)
131 { }
132 IterBase(const IterBase &other) : tbl(other.tbl),
133 tblindex(other.tblindex), link(other.link)
134 { }
135 void rewind()
136 { tblindex = 0; link = &tbl->wvslots[0].head; }
137 WvLink *next();
138 WvLink *cur() const
139 { return link; }
140 void *vptr() const
141 { return link->data; }
142
146 bool get_autofree() const
147 {
148 return link->get_autofree();
149 }
150
154 void set_autofree(bool autofree)
155 {
156 link->set_autofree(autofree);
157 }
158 };
159};
160
161
162template <
163 class T, // element type
164 class K, // key type
165 class Accessor, // element to key
166 template <class> class Comparator = OpEqComp // comparison func
167>
169{
170 // copy constructor: not defined anywhere!
171 WvHashTable(const WvHashTable &h);
172protected:
173 typedef Comparator<K> MyComparator;
174
175 unsigned hash(const T *data)
176 { return WvHash(*Accessor::get_key(data)); }
177
178 virtual bool compare(const void *key, const void *elem) const
179 { return MyComparator::compare((const K *)key,
180 Accessor::get_key((const T *)elem)); }
181
182public:
188 WvHashTable(unsigned _numslots) : WvHashTableBase(_numslots)
189 { wvslots = new WvList<T>[numslots]; setup(); }
190
191 WvList<T> *sl()
192 { return (WvList<T> *)wvslots; }
193
194 virtual ~WvHashTable()
195 { shutdown(); deletev sl(); }
196
197 void add(T *data, bool autofree)
198 { sl()[hash(data) % numslots].append(data, autofree); }
199
200 WvLink *getlink(const K &key)
201 { return prevlink(wvslots, &key, WvHash(key))->next; }
202
203 T *operator[] (const K &key) const
204 { return (T *)genfind(wvslots, &key, WvHash(key)); }
205
209 bool get_autofree(const K &key) const
210 {
211 WvLink *l = getlink(key);
212 if (l)
213 return l->get_autofree();
214 return false;
215 }
216
217 bool get_autofree(const T *data) const
218 {
219 return get_autofree(hash(data));
220 }
221
225 void set_autofree(const K &key, bool autofree)
226 {
227 WvLink *l = getlink(key);
228 if (l)
229 l->set_autofree(autofree);
230 }
231
232 void set_autofree(const T *data, bool autofree)
233 {
234 set_autofree(hash(data), autofree);
235 }
236
237 void remove(const T *data)
238 {
239 unsigned h = hash(data);
240 WvLink *l = prevlink(wvslots, Accessor::get_key(data), h);
241 if (l && l->next) sl()[h % numslots].unlink_after(l);
242 }
243
244 void zap()
245 {
246 deletev sl();
247 wvslots = new WvList<T>[numslots];
248 }
249
251 {
252 public:
253 Iter(WvHashTable &_tbl) : IterBase(_tbl)
254 { }
255 Iter(const Iter &other) : IterBase(other)
256 { }
257 T *ptr() const
258 { return (T *)link->data; }
259 WvIterStuff(T);
260 };
261
263 Sorter;
264};
265
266
267// ******************************************
268// WvDict and WvTable
269
270
271#define DeclareWvDict2(_classname_, _type_, _ftype_, _field_) \
272 __WvDict_base(_classname_, _type_, _ftype_, &obj->_field_)
273
274#define DeclareWvDict(_type_, _ftype_, _field_) \
275 DeclareWvDict2(_type_##Dict, _type_, _ftype_, _field_)
276
277#define DeclareWvTable2(_classname_, _type_) \
278 __WvDict_base(_classname_, _type_, _type_, obj)
279
280#define DeclareWvTable(_type_) \
281 DeclareWvTable2(_type_##Table, _type_)
282
283
284#define __WvDict_base(_classname_, _type_, _ftype_, _field_) \
285 template <class T, class K> \
286 struct _classname_##Accessor \
287 { \
288 static const K *get_key(const T *obj) \
289 { return _field_; } \
290 }; \
291 \
292 typedef WvHashTable<_type_, _ftype_, \
293 _classname_##Accessor<_type_, _ftype_> > _classname_
294
295#endif // __WVHASHTABLE_H
bool get_autofree() const
Returns the state of autofree for the current element.
Definition: wvhashtable.h:146
void set_autofree(bool autofree)
Sets the state of autofree for the current element.
Definition: wvhashtable.h:154
A small, efficient, type-safe hash table (also known as dictionary) container class.
Definition: wvhashtable.h:89
size_t count() const
Returns the number of elements in the hash table.
Definition: wvhashtable.cc:51
bool isempty() const
Returns true if the hash table is empty.
Definition: wvhashtable.cc:61
void set_autofree(const K &key, bool autofree)
Sets the state of autofree for the element associated with key.
Definition: wvhashtable.h:225
bool get_autofree(const K &key) const
Returns the state of autofree for the element associated with key.
Definition: wvhashtable.h:209
WvHashTable(unsigned _numslots)
Creates a hash table.
Definition: wvhashtable.h:188
A linked list container class.
Definition: wvlinklist.h:198
#define deletev
Remplacement for delete[].
Definition: delete.h:129