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

wvscatterhash.cc

Go to the documentation of this file.
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 
00010 // Prime numbers close to powers of 2
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 // we do not accept the _numslots value directly.  Instead, we find the
00016 // next number of xslots which is >= _numslots and take the closest prime number
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 }

Generated on Wed Dec 15 15:08:11 2004 for WvStreams by  doxygen 1.3.9.1