7 #ifndef __WVSCATTERHASH_H
8 #define __WVSCATTERHASH_H
13 #include <sys/types.h>
15 #define REBUILD_LOAD_FACTOR 0.45
16 #define RESIZE_LOAD_FACTOR 0.4
18 #define IS_OCCUPIED(x) ((x) >> 1)
19 #define IS_AUTO_FREE(x) ((x) == 3)
20 #define IS_DELETED(x) ((x) == 1)
28 static const unsigned null_idx = (unsigned)-1;
29 static const unsigned prime_numbers[];
31 size_t count()
const {
return num; }
32 bool isempty()
const {
return !num; }
33 size_t slowcount()
const;
42 : table(other.table), index(other.index) { }
44 void rewind() { index = 0; }
46 {
return index <= table->numslots; }
56 while (++index <= table->numslots &&
57 !IS_OCCUPIED(table->xstatus[index-1])) { }
59 return index <= table->numslots;
62 bool get_autofree()
const
64 return IS_AUTO_FREE(table->xstatus[index-1]);
67 void set_autofree(
bool autofree)
69 table->xstatus[index-1] = autofree ? 3 : 2;
73 void *get()
const {
return table->xslots[index-1]; }
81 virtual unsigned do_hash(
const void *data) = 0;
82 virtual void do_delete(
void *data) = 0;
87 typedef unsigned char Status;
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);
100 void _set_autofree(
const void *data,
unsigned hash,
bool autofree);
101 bool _get_autofree(
const void *data,
unsigned hash);
103 virtual bool compare(
const void *key,
const void *elem)
const = 0;
108 unsigned second_hash(
unsigned hash)
const
109 {
return (hash % (numslots - 1)) + 1; }
110 unsigned curhash(
unsigned hash,
unsigned hash2,
unsigned attempt)
const
112 {
return (hash + attempt*hash2) % numslots; }
123 template <
class>
class Comparator =
OpEqComp
128 typedef Comparator<K> MyComparator;
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)); }
134 unsigned hash(
const T *data)
135 {
return WvHash(*Accessor::get_key(data)); }
137 virtual unsigned do_hash(
const void *data)
138 {
return hash((
const T *)data); }
140 virtual void do_delete(
void *data)
141 {
delete (T *)data; }
147 T *operator[] (
const K &key)
const
148 {
return (T *)(genfind_or_null(&key, WvHash(key))); }
150 void add(
const T *data,
bool autofree =
false)
151 { _add((
void *)data, hash(data), autofree); }
153 void remove(
const T *data)
154 { _remove(Accessor::get_key(data), hash(data)); }
156 void set_autofree(
const K &key,
bool autofree)
158 _set_autofree(key, WvHash(key), autofree);
161 void set_autofree(
const T *data,
bool autofree)
163 _set_autofree(Accessor::get_key(data), hash(data), autofree);
166 bool get_autofree(
const K &key)
168 return _get_autofree(key, WvHash(key));
171 bool get_autofree(
const T *data)
173 return _get_autofree(Accessor::get_key(data), hash(data));
186 unsigned char *getstatus() {
return &xstatus[index-1]; }
189 {
return (T *)(get()); }
199 #define DeclareWvScatterDict2(_classname_, _type_, _ftype_, _field_) \
200 __WvScatterDict_base(_classname_, _type_, _ftype_, &obj->_field_)
202 #define DeclareWvScatterDict(_type_, _ftype_, _field_) \
203 DeclareWvScatterDict2(_type_##Dict, _type_, _ftype_, _field_)
205 #define DeclareWvScatterTable2(_classname_, _type_) \
206 __WvScatterDict_base(_classname_, _type_, _type_, obj)
208 #define DeclareWvScatterTable(_type_) \
209 DeclareWvScatterTable2(_type_##Table, _type_)
212 #define __WvScatterDict_base(_classname_, _type_, _ftype_, _field_) \
213 template <class T, class K> \
214 struct _classname_##Accessor \
216 static const K *get_key(const T *obj) \
217 { return _field_; } \
220 typedef WvScatterHash<_type_, _ftype_, \
221 _classname_##Accessor<_type_, _ftype_> > _classname_
224 #endif //_WVSCATTERHASH_H