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 }