00001
00002
00003
00004
00005
00006
00007
00008 #include "wvscatterhash.h"
00009
00010
00011 const unsigned WvScatterHashBase::prime_numbers[] = {2u, 5u, 11u, 17u, 31u, 67u, 127u, 251u, 509u, 1021u, 2039u, 4093u, 8191u, 16381u, 32749u, 65521u, 131071u, 262139u, 524287u, 1048573u, 2097143u, 4194301u, 8388593u, 16777213u, 33554393u, 67108859u, 134217689u, 268435399u, 536870909u, 1073741789u, 2147483647u, 4294967281u};
00012
00013 WvScatterHashBase::pair WvScatterHashBase::null_pair;
00014
00015
00016
00017 WvScatterHashBase::WvScatterHashBase(unsigned _numslots)
00018 {
00019 num = 0;
00020 used = 0;
00021
00022 if (_numslots == 0)
00023 prime_index = 2;
00024 else
00025 {
00026 prime_index = 1;
00027 while ((_numslots >>= 1) != 0)
00028 prime_index++;
00029 }
00030
00031 numslots = prime_numbers[prime_index];
00032 xslots = new pair[numslots];
00033 memset(xslots, 0, numslots * sizeof(pair));
00034 }
00035
00036 size_t WvScatterHashBase::slowcount() const
00037 {
00038 unsigned count = 0;
00039 for (unsigned index = 0; index < numslots; index++)
00040 {
00041 if (IS_OCCUPIED(xslots[index]))
00042 count++;
00043 }
00044
00045 return count;
00046 }
00047
00048 void WvScatterHashBase::rebuild()
00049 {
00050 if (!(numslots * REBUILD_LOAD_FACTOR <= used + 1))
00051 return;
00052
00053 unsigned oldnumslots = numslots;
00054
00055 if (numslots * RESIZE_LOAD_FACTOR <= num + 1)
00056 numslots = prime_numbers[++prime_index];
00057
00058 pair *tmpslots = xslots;
00059 xslots = new pair[numslots];
00060 memset(xslots, 0, numslots * sizeof(pair));
00061 used = num = 0;
00062
00063 for (unsigned i = 0; i < oldnumslots; i++)
00064 {
00065 if (IS_OCCUPIED(tmpslots[i]))
00066 _add(tmpslots[i].data, IS_AUTO_FREE(tmpslots[i]));
00067 }
00068
00069 delete[] tmpslots;
00070 }
00071
00072 void WvScatterHashBase::_add(void *data, bool auto_free)
00073 {
00074 _add(data, do_hash(data), auto_free);
00075 }
00076
00077 void WvScatterHashBase::_add(void *data, unsigned hash, bool auto_free)
00078 {
00079 rebuild();
00080 unsigned slot = hash % numslots;
00081
00082 if (IS_OCCUPIED(xslots[slot]))
00083 {
00084 unsigned attempt = 0;
00085 unsigned hash2 = second_hash(hash);
00086
00087 while (IS_OCCUPIED(xslots[slot]))
00088 slot = curhash(hash, hash2, ++attempt);
00089 }
00090
00091 num++;
00092 if (!IS_DELETED(xslots[slot]))
00093 used++;
00094
00095 xslots[slot].data = data;
00096 xslots[slot].status = auto_free ? 3 : 2;
00097 }
00098
00099 void WvScatterHashBase::_remove(const void *data, unsigned hash)
00100 {
00101 pair *res = genfind(data, hash);
00102
00103 if (res != &null_pair)
00104 {
00105 if (IS_AUTO_FREE((*res)))
00106 do_delete(res->data);
00107 res->status = 1;
00108 num--;
00109 }
00110 }
00111
00112 void WvScatterHashBase::_zap()
00113 {
00114 for (unsigned i = 0; i < numslots; i++)
00115 {
00116 if (IS_AUTO_FREE(xslots[i]))
00117 do_delete(xslots[i].data);
00118
00119 xslots[i].status = 0;
00120 }
00121
00122 used = num = 0;
00123 }
00124
00125 void WvScatterHashBase::_set_autofree(const void *data,
00126 unsigned hash, bool auto_free)
00127 {
00128 pair *res = genfind(data, hash);
00129
00130 if (res)
00131 res->status = auto_free ? 3 : 2;
00132 }
00133
00134 bool WvScatterHashBase::_get_autofree(const void *data, unsigned hash)
00135 {
00136 pair *res = genfind(data, hash);
00137
00138 if (res)
00139 return IS_AUTO_FREE((*res));
00140
00141 assert(0 && "You checked auto_free of a nonexistant thing.");
00142 return false;
00143 }
00144
00145 struct WvScatterHashBase::pair *WvScatterHashBase::genfind
00146 (const void *data, unsigned hash) const
00147 {
00148 unsigned slot = hash % numslots;
00149
00150 if (IS_OCCUPIED(xslots[slot]) && compare(data, xslots[slot].data))
00151 return &xslots[slot];
00152
00153 unsigned attempt = 0;
00154 unsigned hash2 = second_hash(hash);
00155
00156 while (xslots[slot].status)
00157 {
00158 slot = curhash(hash, hash2, ++attempt);
00159
00160 if (IS_OCCUPIED(xslots[slot]) && compare(data, xslots[slot].data))
00161 return &xslots[slot];
00162 }
00163
00164 return &null_pair;
00165 }