WvStreams
wvscatterhash.h
1 /* -*- Mode: C++ -*-
2  * Worldvisions Weaver Software:
3  * Copyright (C) 1997-2003 Net Integration Technologies, Inc.
4  *
5  * A hash table container.
6  */
7 #ifndef __WVSCATTERHASH_H
8 #define __WVSCATTERHASH_H
9 
10 #include "wvhash.h"
11 #include "wvsorter.h"
12 #include "wvxplc.h" // for deletev. ick.
13 #include <sys/types.h>
14 
15 #define REBUILD_LOAD_FACTOR 0.45
16 #define RESIZE_LOAD_FACTOR 0.4
17 
18 #define IS_OCCUPIED(x) ((x) >> 1)
19 #define IS_AUTO_FREE(x) ((x) == 3)
20 #define IS_DELETED(x) ((x) == 1)
21 
23 {
24 public:
25  WvScatterHashBase(unsigned _numslots);
26  virtual ~WvScatterHashBase() { deletev xslots; deletev xstatus; }
27 
28  static const unsigned null_idx = (unsigned)-1;
29  static const unsigned prime_numbers[];
30 
31  size_t count() const { return num; }
32  bool isempty() const { return !num; }
33  size_t slowcount() const;
34 
35  /******* IterBase ******/
36  class IterBase
37  {
38  public:
39  IterBase(WvScatterHashBase &_table) : table(&_table) { }
40 
41  IterBase(const IterBase &other)
42  : table(other.table), index(other.index) { }
43 
44  void rewind() { index = 0; }
45  bool cur()
46  { return index <= table->numslots; }
47  void *vptr()
48  { return get(); }
49 
50  bool next()
51  {
52  if (!table)
53  return false;
54 
55  /* FIXME: Couldn't this be a *little* clearer? */
56  while (++index <= table->numslots &&
57  !IS_OCCUPIED(table->xstatus[index-1])) { }
58 
59  return index <= table->numslots;
60  }
61 
62  bool get_autofree() const
63  {
64  return IS_AUTO_FREE(table->xstatus[index-1]);
65  }
66 
67  void set_autofree(bool autofree)
68  {
69  table->xstatus[index-1] = autofree ? 3 : 2;
70  }
71 
72  protected:
73  void *get() const { return table->xslots[index-1]; }
74 
75  WvScatterHashBase *table;
76  unsigned index;
77  };
78 
79 
80 protected:
81  virtual unsigned do_hash(const void *data) = 0;
82  virtual void do_delete(void *data) = 0;
83 
84  friend class IterBase;
85 
86  typedef void *Slot;
87  typedef unsigned char Status;
88 
89  Slot *xslots;
90  Status *xstatus;
91  int prime_index;
92  unsigned numslots;
93 
94  unsigned genfind(const void *data, unsigned hash) const;
95  Slot genfind_or_null(const void *data, unsigned hash) const;
96  void _add(void *data, bool autofree);
97  void _add(void *data, unsigned hash, bool autofree);
98  void _remove(const void *data, unsigned hash);
99  void _zap();
100  void _set_autofree(const void *data, unsigned hash, bool autofree);
101  bool _get_autofree(const void *data, unsigned hash);
102 
103  virtual bool compare(const void *key, const void *elem) const = 0;
104 
105 
106 private:
107  void rebuild();
108  unsigned second_hash(unsigned hash) const
109  { return (hash % (numslots - 1)) + 1; }
110  unsigned curhash(unsigned hash, unsigned hash2, unsigned attempt) const
111  //{ return (hash + attempt * attempt) % numslots; }
112  { return (hash + attempt*hash2) % numslots; }
113 
114  size_t used;
115  size_t num;
116 };
117 
118 
119 template <
120  class T, // element type
121  class K, // key type
122  class Accessor, // element to key
123  template <class> class Comparator = OpEqComp // comparison func
124 >
126 {
127 protected:
128  typedef Comparator<K> MyComparator;
129 
130  virtual bool compare(const void *key, const void *elem) const
131  { return MyComparator::compare((const K *)key,
132  Accessor::get_key((const T *)elem)); }
133 
134  unsigned hash(const T *data)
135  { return WvHash(*Accessor::get_key(data)); }
136 
137  virtual unsigned do_hash(const void *data)
138  { return hash((const T *)data); }
139 
140  virtual void do_delete(void *data)
141  { delete (T *)data; }
142 
143 public:
144  WvScatterHash(unsigned _numslots = 0) : WvScatterHashBase(_numslots) { }
145  virtual ~WvScatterHash() { _zap(); }
146 
147  T *operator[] (const K &key) const
148  { return (T *)(genfind_or_null(&key, WvHash(key))); }
149 
150  void add(const T *data, bool autofree = false)
151  { _add((void *)data, hash(data), autofree); }
152 
153  void remove(const T *data)
154  { _remove(Accessor::get_key(data), hash(data)); }
155 
156  void set_autofree(const K &key, bool autofree)
157  {
158  _set_autofree(key, WvHash(key), autofree);
159  }
160 
161  void set_autofree(const T *data, bool autofree)
162  {
163  _set_autofree(Accessor::get_key(data), hash(data), autofree);
164  }
165 
166  bool get_autofree(const K &key)
167  {
168  return _get_autofree(key, WvHash(key));
169  }
170 
171  bool get_autofree(const T *data)
172  {
173  return _get_autofree(Accessor::get_key(data), hash(data));
174  }
175 
176  void zap()
177  { _zap(); }
178 
179 
181  {
182  public:
183  Iter(WvScatterHash &_table) : IterBase(_table) { }
184  Iter(const Iter &other) : IterBase(other) { }
185 
186  unsigned char *getstatus() { return &xstatus[index-1]; }
187 
188  T *ptr() const
189  { return (T *)(get()); }
190 
191  WvIterStuff(T);
192  };
193 
195  Sorter;
196 };
197 
198 
199 #define DeclareWvScatterDict2(_classname_, _type_, _ftype_, _field_) \
200  __WvScatterDict_base(_classname_, _type_, _ftype_, &obj->_field_)
201 
202 #define DeclareWvScatterDict(_type_, _ftype_, _field_) \
203  DeclareWvScatterDict2(_type_##Dict, _type_, _ftype_, _field_)
204 
205 #define DeclareWvScatterTable2(_classname_, _type_) \
206  __WvScatterDict_base(_classname_, _type_, _type_, obj)
207 
208 #define DeclareWvScatterTable(_type_) \
209  DeclareWvScatterTable2(_type_##Table, _type_)
210 
211 
212 #define __WvScatterDict_base(_classname_, _type_, _ftype_, _field_) \
213  template <class T, class K> \
214  struct _classname_##Accessor \
215  { \
216  static const K *get_key(const T *obj) \
217  { return _field_; } \
218  }; \
219  \
220  typedef WvScatterHash<_type_, _ftype_, \
221  _classname_##Accessor<_type_, _ftype_> > _classname_
222 
223 
224 #endif //_WVSCATTERHASH_H
WvScatterHashBase::IterBase
Definition: wvscatterhash.h:36
WvScatterHash::Iter
Definition: wvscatterhash.h:180
WvScatterHashBase
Definition: wvscatterhash.h:22
deletev
#define deletev
Remplacement for delete[].
Definition: delete.h:129
WvScatterHash
Definition: wvscatterhash.h:125
OpEqComp
Definition: wvhash.h:21
WvSorter
Definition: wvsorter.h:56