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