WvStreams
|
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 }