00001
00002
00003
00004
00005
00006
00007 #ifndef __WVSCATTERHASH_H
00008 #define __WVSCATTERHASH_H
00009
00010 #include "wvhash.h"
00011 #include "wvsorter.h"
00012 #include "wvxplc.h"
00013 #include <sys/types.h>
00014
00015 #define REBUILD_LOAD_FACTOR 0.45
00016 #define RESIZE_LOAD_FACTOR 0.4
00017
00018 #define IS_OCCUPIED(x) ((x) >> 1)
00019 #define IS_AUTO_FREE(x) ((x) == 3)
00020 #define IS_DELETED(x) ((x) == 1)
00021
00022 class WvScatterHashBase
00023 {
00024 public:
00025 WvScatterHashBase(unsigned _numslots);
00026 virtual ~WvScatterHashBase() { deletev xslots; deletev xstatus; }
00027
00028 static const unsigned null_idx = (unsigned)-1;
00029 static const unsigned prime_numbers[];
00030
00031 size_t count() const { return num; }
00032 bool isempty() const { return !num; }
00033 size_t slowcount() const;
00034
00035
00036 class IterBase
00037 {
00038 public:
00039 IterBase(WvScatterHashBase &_table) : table(&_table) { }
00040
00041 IterBase(const IterBase &other)
00042 : table(other.table), index(other.index) { }
00043
00044 void rewind() { index = 0; }
00045 bool cur()
00046 { return index <= table->numslots; }
00047 void *vptr()
00048 { return get(); }
00049
00050 bool next()
00051 {
00052 if (!table)
00053 return false;
00054
00055
00056 while (++index <= table->numslots &&
00057 !IS_OCCUPIED(table->xstatus[index-1])) { }
00058
00059 return index <= table->numslots;
00060 }
00061
00062 bool get_autofree() const
00063 {
00064 return IS_AUTO_FREE(table->xstatus[index-1]);
00065 }
00066
00067 void set_autofree(bool autofree)
00068 {
00069 table->xstatus[index-1] = autofree ? 3 : 2;
00070 }
00071
00072 protected:
00073 void *get() const { return table->xslots[index-1]; }
00074
00075 WvScatterHashBase *table;
00076 unsigned index;
00077 };
00078
00079
00080 protected:
00081 virtual unsigned do_hash(const void *data) = 0;
00082 virtual void do_delete(void *data) = 0;
00083
00084 friend class IterBase;
00085
00086 typedef void *Slot;
00087 typedef unsigned char Status;
00088
00089 Slot *xslots;
00090 Status *xstatus;
00091 int prime_index;
00092 unsigned numslots;
00093
00094 unsigned genfind(const void *data, unsigned hash) const;
00095 Slot genfind_or_null(const void *data, unsigned hash) const;
00096 void _add(void *data, bool autofree);
00097 void _add(void *data, unsigned hash, bool autofree);
00098 void _remove(const void *data, unsigned hash);
00099 void _zap();
00100 void _set_autofree(const void *data, unsigned hash, bool autofree);
00101 bool _get_autofree(const void *data, unsigned hash);
00102
00103 virtual bool compare(const void *key, const void *elem) const = 0;
00104
00105
00106 private:
00107 void rebuild();
00108 unsigned second_hash(unsigned hash) const
00109 { return (hash % (numslots - 1)) + 1; }
00110 unsigned curhash(unsigned hash, unsigned hash2, unsigned attempt) const
00111
00112 { return (hash + attempt*hash2) % numslots; }
00113
00114 size_t used;
00115 size_t num;
00116 };
00117
00118
00119 template <
00120 class T,
00121 class K,
00122 class Accessor,
00123 template <class> class Comparator = OpEqComp
00124 >
00125 class WvScatterHash : public WvScatterHashBase
00126 {
00127 protected:
00128 typedef Comparator<K> MyComparator;
00129
00130 virtual bool compare(const void *key, const void *elem) const
00131 { return MyComparator::compare((const K *)key,
00132 Accessor::get_key((const T *)elem)); }
00133
00134 unsigned hash(const T *data)
00135 { return WvHash(*Accessor::get_key(data)); }
00136
00137 virtual unsigned do_hash(const void *data)
00138 { return hash((const T *)data); }
00139
00140 virtual void do_delete(void *data)
00141 { delete (T *)data; }
00142
00143 public:
00144 WvScatterHash(unsigned _numslots = 0) : WvScatterHashBase(_numslots) { }
00145 virtual ~WvScatterHash() { _zap(); }
00146
00147 T *operator[] (const K &key) const
00148 { return (T *)(genfind_or_null(&key, WvHash(key))); }
00149
00150 void add(const T *data, bool autofree = false)
00151 { _add((void *)data, hash(data), autofree); }
00152
00153 void remove(const T *data)
00154 { _remove(Accessor::get_key(data), hash(data)); }
00155
00156 void set_autofree(const K &key, bool autofree)
00157 {
00158 _set_autofree(key, WvHash(key), autofree);
00159 }
00160
00161 void set_autofree(const T *data, bool autofree)
00162 {
00163 _set_autofree(Accessor::get_key(data), hash(data), autofree);
00164 }
00165
00166 bool get_autofree(const K &key)
00167 {
00168 return _get_autofree(key, WvHash(key));
00169 }
00170
00171 bool get_autofree(const T *data)
00172 {
00173 return _get_autofree(Accessor::get_key(data), hash(data));
00174 }
00175
00176 void zap()
00177 { _zap(); }
00178
00179
00180 class Iter : public WvScatterHashBase::IterBase
00181 {
00182 public:
00183 Iter(WvScatterHash &_table) : IterBase(_table) { }
00184 Iter(const Iter &other) : IterBase(other) { }
00185
00186 unsigned char *getstatus() { return &xstatus[index-1]; }
00187
00188 T *ptr() const
00189 { return (T *)(get()); }
00190
00191 WvIterStuff(T);
00192 };
00193
00194 typedef class WvSorter<T, WvScatterHashBase, WvScatterHashBase::IterBase>
00195 Sorter;
00196 };
00197
00198
00199 #define DeclareWvScatterDict2(_classname_, _type_, _ftype_, _field_) \
00200 __WvScatterDict_base(_classname_, _type_, _ftype_, &obj->_field_)
00201
00202 #define DeclareWvScatterDict(_type_, _ftype_, _field_) \
00203 DeclareWvScatterDict2(_type_##Dict, _type_, _ftype_, _field_)
00204
00205 #define DeclareWvScatterTable2(_classname_, _type_) \
00206 __WvScatterDict_base(_classname_, _type_, _type_, obj)
00207
00208 #define DeclareWvScatterTable(_type_) \
00209 DeclareWvScatterTable2(_type_##Table, _type_)
00210
00211
00212 #define __WvScatterDict_base(_classname_, _type_, _ftype_, _field_) \
00213 template <class T, class K> \
00214 struct _classname_##Accessor \
00215 { \
00216 static const K *get_key(const T *obj) \
00217 { return _field_; } \
00218 }; \
00219 \
00220 typedef WvScatterHash<_type_, _ftype_, \
00221 _classname_##Accessor<_type_, _ftype_> > _classname_
00222
00223
00224 #endif //_WVSCATTERHASH_H