Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

wvscatterhash.h

Go to the documentation of this file.
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 <sys/types.h> 00011 00012 // Some standard WvHash functions are useful from wvhashtable.h 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 /******* IterBase ******/ 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 /* FIXME: Couldn't this be a *little* clearer? */ 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 //{ return (hash + attempt * attempt) % numslots; } 00109 { return (hash + attempt*hash2) % numslots; } 00110 00111 size_t used; 00112 size_t num; 00113 }; 00114 00115 00116 template < 00117 class T, // element type 00118 class K, // key type 00119 class Accessor, // element to key 00120 template <class> class Comparator = OpEqComp // comparison func 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

Generated on Tue Oct 5 01:09:20 2004 for WvStreams by doxygen 1.3.7