utils/wvscatterhash.cc

   1 /*
   2  * Worldvisions Weaver Software:
   3  *   Copyright (C) 1997-2003 Net Integration Technologies, Inc.
   4  *
   5  * A hash table container.
   6  */
   7
   8 #include "wvscatterhash.h"
   9 #include <assert.h>
  10
  11 // Prime numbers close to powers of 2
  12 const unsigned WvScatterHashBase::prime_numbers[]
  13     = {2u, 5u, 11u, 17u,
  14        31u, 67u, 127u, 251u,
  15        509u, 1021u, 2039u, 4093u,
  16        8191u, 16381u, 32749u, 65521u,
  17        131071u, 262139u, 524287u, 1048573u,
  18        2097143u, 4194301u, 8388593u, 16777213u,
  19        33554393u, 67108859u, 134217689u, 268435399u,
  20        536870909u, 1073741789u, 2147483647u, 4294967281u};
  21
  22 // we do not accept the _numslots value directly.  Instead, we find the
  23 // next number of xslots which is >= _numslots and take the closest prime
  24 // number
  25 WvScatterHashBase::WvScatterHashBase(unsigned _numslots)
  26 {
  27     num = 0;
  28     used = 0;
  29
  30     if (_numslots == 0)
  31         prime_index = 0;
  32     else
  33     {
  34         prime_index = 1;
  35         while ((_numslots >>= 1) != 0)
  36             prime_index++;
  37     }
  38
  39     numslots = prime_numbers[prime_index];
  40     xslots = new Slot[numslots];
  41     xstatus = new Status[numslots];
  42     memset(xslots, 0, numslots * sizeof(xslots[0]));
  43     memset(xstatus, 0, numslots * sizeof(xstatus[0]));
  44 }
  45
  46 size_t WvScatterHashBase::slowcount() const
  47 {
  48     unsigned count = 0;
  49     for (unsigned index = 0; index < numslots; index++)
  50     {
  51         if (IS_OCCUPIED(xstatus[index]))
  52             count++;
  53     }
  54
  55     return count;
  56 }
  57
  58 void WvScatterHashBase::rebuild()
  59 {
  60     if (!(numslots * REBUILD_LOAD_FACTOR <= used + 1))
  61         return;
  62
  63     unsigned oldnumslots = numslots;
  64
  65     if (numslots * RESIZE_LOAD_FACTOR <= num + 1)
  66         numslots = prime_numbers[++prime_index];
  67
  68     Slot *tmpslots = xslots;
  69     Status *tmpstatus = xstatus;
  70     xslots = new Slot[numslots];
  71     xstatus = new Status[numslots];
  72     memset(xslots, 0, numslots * sizeof(xslots[0]));
  73     memset(xstatus, 0, numslots * sizeof(xstatus[0]));
  74     used = num = 0;
  75
  76     for (unsigned i = 0; i < oldnumslots; i++)
  77     {
  78         if (IS_OCCUPIED(tmpstatus[i]))
  79             _add(tmpslots[i], IS_AUTO_FREE(tmpstatus[i]));
  80     }
  81
  82     deletev tmpslots;
  83     deletev tmpstatus;
  84 }
  85
  86 void WvScatterHashBase::_add(void *data, bool auto_free)
  87 {
  88     _add(data, do_hash(data), auto_free);
  89 }
  90
  91 void WvScatterHashBase::_add(void *data, unsigned hash, bool auto_free)
  92 {
  93     rebuild();
  94     unsigned slot = hash % numslots;
  95
  96     if (IS_OCCUPIED(xstatus[slot]))
  97     {
  98         unsigned attempt = 0;
  99         unsigned hash2 = second_hash(hash);
 100
 101         while (IS_OCCUPIED(xstatus[slot]))
 102             slot = curhash(hash, hash2, ++attempt);
 103     }
 104
 105     num++;
 106     if (!IS_DELETED(xstatus[slot]))
 107         used++;
 108
 109     xslots[slot] = data;
 110     xstatus[slot] = auto_free ? 3 : 2;
 111 }
 112
 113 void WvScatterHashBase::_remove(const void *data, unsigned hash)
 114 {
 115     unsigned res = genfind(data, hash);
 116
 117     if (res != null_idx)
 118     {
 119         if (IS_AUTO_FREE(xstatus[res]))
 120             do_delete(xslots[res]);
 121         xstatus[res] = 1;
 122         num--;
 123     }
 124 }
 125
 126 void WvScatterHashBase::_zap()
 127 {
 128     for (unsigned i = 0; i < numslots; i++)
 129     {
 130         if (IS_AUTO_FREE(xstatus[i]))
 131             do_delete(xslots[i]);
 132
 133         xstatus[i] = 0;
 134     }
 135
 136     used = num = 0;
 137 }
 138
 139 void WvScatterHashBase::_set_autofree(const void *data,
 140     unsigned hash, bool auto_free)
 141 {
 142     unsigned res = genfind(data, hash);
 143
 144     if (res != null_idx)
 145         xstatus[res] = auto_free ? 3 : 2;
 146 }
 147
 148 bool WvScatterHashBase::_get_autofree(const void *data, unsigned hash)
 149 {
 150     unsigned res = genfind(data, hash);
 151
 152     if (res != null_idx)
 153         return IS_AUTO_FREE(xstatus[res]);
 154
 155     assert(0 && "You checked auto_free of a nonexistant thing.");
 156     return false;
 157 }
 158
 159 unsigned WvScatterHashBase::genfind(const void *data, unsigned hash) const
 160 {
 161     unsigned slot = hash % numslots;
 162
 163     if (IS_OCCUPIED(xstatus[slot]) && compare(data, xslots[slot]))
 164         return slot;
 165
 166     unsigned attempt = 0;
 167     unsigned hash2 = second_hash(hash);
 168
 169     while (xstatus[slot])
 170     {
 171         slot = curhash(hash, hash2, ++attempt);
 172
 173         if (IS_OCCUPIED(xstatus[slot]) && compare(data, xslots[slot]))
 174             return slot;
 175     }
 176
 177     return null_idx;
 178 }
 179
 180
 181 void *WvScatterHashBase::genfind_or_null(const void *data, unsigned hash) const
 182 {
 183     unsigned slot = genfind(data, hash);
 184     if (slot == null_idx)
 185         return NULL;
 186     else
 187         return xslots[slot];
 188 }