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