WvStreams
include/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{
24public:
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
80protected:
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
106private:
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
119template <
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>
125class WvScatterHash : public WvScatterHashBase
126{
127protected:
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
143public:
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
180 class Iter : public WvScatterHashBase::IterBase
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
194 typedef class WvSorter<T, WvScatterHashBase, WvScatterHashBase::IterBase>
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