WvStreams
|
00001 /* -*- Mode: C++ -*- 00002 * Worldvisions Weaver Software: 00003 * Copyright (C) 1997-2003 Net Integration Technologies, Inc. 00004 * 00005 * A hash table container. 00006 */ 00007 #ifndef __WVSCATTERHASH_H 00008 #define __WVSCATTERHASH_H 00009 00010 #include "wvhash.h" 00011 #include "wvsorter.h" 00012 #include "wvxplc.h" // for deletev. ick. 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 /******* IterBase ******/ 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 /* FIXME: Couldn't this be a *little* clearer? */ 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 //{ return (hash + attempt * attempt) % numslots; } 00112 { return (hash + attempt*hash2) % numslots; } 00113 00114 size_t used; 00115 size_t num; 00116 }; 00117 00118 00119 template < 00120 class T, // element type 00121 class K, // key type 00122 class Accessor, // element to key 00123 template <class> class Comparator = OpEqComp // comparison func 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