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