WvStreams
wvscatterhash.cc
00001 /*  
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2003 Net Integration Technologies, Inc.
00004  *  
00005  * A hash table container.
00006  */ 
00007 
00008 #include "wvscatterhash.h"
00009 #include <assert.h>
00010 
00011 // Prime numbers close to powers of 2
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 // we do not accept the _numslots value directly.  Instead, we find the
00023 // next number of xslots which is >= _numslots and take the closest prime
00024 // number
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 }