Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | 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 Tue Oct 5 01:09:20 2004 for WvStreams by doxygen 1.3.7