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!
92 protected:
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;
106 public:
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
123  class IterBase
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 
162 template <
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);
172 protected:
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 
182 public:
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
WvHashTableBase
A small, efficient, type-safe hash table (also known as dictionary) container class.
Definition: wvhashtable.h:88
WvHashTableBase::IterBase::get_autofree
bool get_autofree() const
Returns the state of autofree for the current element.
Definition: wvhashtable.h:146
WvListBase
Definition: wvlinklist.h:21
WvHashTable
Definition: wvhashtable.h:168
WvHashTableBase::count
size_t count() const
Returns the number of elements in the hash table.
Definition: wvhashtable.cc:51
WvHashTableBase::isempty
bool isempty() const
Returns true if the hash table is empty.
Definition: wvhashtable.cc:61
deletev
#define deletev
Remplacement for delete[].
Definition: delete.h:129
WvHashTable::Iter
Definition: wvhashtable.h:250
WvHashTable::set_autofree
void set_autofree(const K &key, bool autofree)
Sets the state of autofree for the element associated with key.
Definition: wvhashtable.h:225
WvHashTable::WvHashTable
WvHashTable(unsigned _numslots)
Creates a hash table.
Definition: wvhashtable.h:188
WvHashTableBase::IterBase::set_autofree
void set_autofree(bool autofree)
Sets the state of autofree for the current element.
Definition: wvhashtable.h:154
OpEqComp
Definition: wvhash.h:21
WvHashTable::get_autofree
bool get_autofree(const K &key) const
Returns the state of autofree for the element associated with key.
Definition: wvhashtable.h:209
WvSorter
Definition: wvsorter.h:56
WvList
A linked list container class.
Definition: wvlinklist.h:197
WvHashTableBase::IterBase
Definition: wvhashtable.h:123