1// This may look like C code, but it is really -*- C++ -*- 2/* 3Copyright (C) 1988 Free Software Foundation 4 written by Doug Lea (dl@rocky.oswego.edu) 5 based on code by Doug Schmidt 6 7This file is part of GNU CC. 8 9GNU CC is distributed in the hope that it will be useful, 10but WITHOUT ANY WARRANTY. No author or distributor 11accepts responsibility to anyone for the consequences of using it 12or for whether it serves any particular purpose or works at all, 13unless he says so in writing. Refer to the GNU CC General Public 14License for full details. 15 16Everyone is granted permission to copy, modify and redistribute 17GNU CC, but only under the conditions described in the 18GNU CC General Public License. A copy of this license is 19supposed to have been given to you along with GNU CC so you 20can know your rights and responsibilities. It should be in a 21file named COPYING. Among other things, the copyright notice 22and this notice must be preserved on all copies. 23*/ 24 25#ifdef __GNUG__ 26#pragma implementation 27#endif 28#include <stream.h> 29#include "<T>.VOHSet.h" 30 31 32/* codes for status fields */ 33#define EMPTYCELL 0 34#define VALIDCELL 1 35#define DELETEDCELL 2 36 37 38<T>VOHSet::<T>VOHSet(int sz) 39{ 40// The size of the hash table is always the smallest power of 2 >= the size 41// indicated by the user. This allows several optimizations, including 42// the use of actual double hashing and elimination of the mod instruction. 43 44 size = 1; 45 while (size < sz) size <<= 1; 46 tab = new <T>[size]; 47 status = new char[size]; 48 for (int i = 0; i < size; ++i) status[i] = EMPTYCELL; 49 count = cnt = 0; 50} 51 52<T>VOHSet::<T>VOHSet(<T>VOHSet& a) 53{ 54 tab = new <T>[size = a.size]; 55 status = new char[size]; 56 for (int i = 0; i < size; ++i) status[i] = EMPTYCELL; 57 count = cnt = 0; 58 for (Pix p = a.first(); p; a.next(p)) add(a(p)); 59} 60 61Pix <T>VOHSet::seek(<T&> key) 62{ 63// Uses ordered double hashing to perform a search of the table. 64// This greatly speeds up the average-case time for an unsuccessful search. 65 66 unsigned hashval = <T>HASH(key); 67 68 // We can avoid the mod operation since size is a power of 2. 69 unsigned h = hashval & (size - 1); 70 71 // The increment must be odd, since all odd numbers are relatively 72 // prime to a power of 2!! 73 unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1)); 74 75 // There is always at least 1 empty cell, so this loop is guaranteed to halt! 76 while (status[h] != EMPTYCELL) 77 { 78 int cmp = <T>CMP (key, tab[h]); 79 if (cmp == 0) 80 { 81 if (status[h] == VALIDCELL) 82 return Pix(&tab[h]); 83 else 84 return 0; 85 } 86 else if (cmp > 0) 87 return 0; 88 else 89 h = ((h + inc) & (size - 1)); 90 } 91 return 0; 92} 93 94// This adds an item if it doesn't already exist. By performing the initial 95// comparison we assure that the table always contains at least 1 empty 96// spot. This speeds up later searching by a constant factor. 97// The insertion algorithm uses ordered double hashing. See Standish's 98// 1980 ``Data Structure's Techniques'' book for details. 99 100Pix <T>VOHSet::add(<T&> x) 101{ 102 if (size <= cnt+1) 103 resize(); 104 105 unsigned hashval = <T>HASH(x); 106 unsigned h = hashval & (size - 1); 107 108 if (status[h] != VALIDCELL) // save some work if possible 109 { 110 if (status[h] == EMPTYCELL) 111 cnt++; 112 count++; 113 tab[h] = x; 114 status[h] = VALIDCELL; 115 return Pix(&tab[h]); 116 } 117 int cmp = <T>CMP(x, tab[h]); 118 if (cmp == 0) 119 return Pix(&tab[h]); 120 121 <T> item = x; 122 Pix mypix = 0; 123 unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1)); 124 125 for (;;) 126 { 127 if (cmp < 0) 128 { 129 <T> temp = tab[h]; 130 tab[h] = item; 131 item = temp; 132 if (mypix == 0) mypix = Pix(&tab[h]); 133 inc = ((((<T>HASH(item) / size) << 1) + 1) & (size - 1)); 134 h = ((h + inc) & (size - 1)); 135 cmp = <T>CMP(item, tab[h]); 136 } 137 else 138 h = ((h + inc) & (size - 1)); 139 if (status[h] != VALIDCELL) 140 { 141 if (status[h] == EMPTYCELL) 142 cnt++; 143 count++; 144 tab[h] = item; 145 status[h] = VALIDCELL; 146 return (mypix == 0)? Pix(&tab[h]) : mypix; 147 } 148 } 149} 150 151 152void <T>VOHSet::del(<T&> key) 153{ 154// This performs a deletion by marking the item's status field. 155// Note that we only decrease the count, *not* the cnt, since this 156// would cause trouble for subsequent steps in the algorithm. See 157// Reingold and Hanson's ``Data Structure's'' book for a justification 158// of this approach. 159 160 unsigned hashval = <T>HASH(key); 161 unsigned h = hashval & (size - 1); 162 unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1)); 163 164 while (status[h] != EMPTYCELL) 165 { 166 int cmp = <T>CMP(key, tab[h]); 167 if (cmp < 0) 168 h = ((h + inc) & (size - 1)); 169 else if (status[h] == VALIDCELL && cmp == 0) 170 { 171 status[h] = DELETEDCELL; 172 count--; 173 return; 174 } 175 else 176 return; 177 } 178} 179 180void <T>VOHSet::clear() 181{ 182 for (int i = 0; i < size; ++i) status[i] = EMPTYCELL; 183 count = cnt = 0; 184} 185 186void <T>VOHSet::resize(int newsize) 187{ 188 if (newsize <= count) 189 newsize = count; 190 int s = 1; 191 while (s <= newsize) s <<= 1; 192 newsize = s; 193 194 <T>* oldtab = tab; 195 char* oldstatus = status; 196 int oldsize = size; 197 tab = new <T>[size = newsize]; 198 status = new char[size]; 199 for (int i = 0; i < size; ++i) status[i] = EMPTYCELL; 200 count = cnt = 0; 201 202 for (i = 0; i < oldsize; ++i) if (oldstatus[i] == VALIDCELL) add(oldtab[i]); 203 delete [oldsize] oldtab; 204 delete oldstatus; 205} 206 207Pix <T>VOHSet::first() 208{ 209 for (int pos = 0; pos < size; ++pos) 210 if (status[pos] == VALIDCELL) return Pix(&tab[pos]); 211 return 0; 212} 213 214void <T>VOHSet::next(Pix& i) 215{ 216 if (i == 0) return; 217 int pos = ((unsigned)i - (unsigned)tab) / sizeof(<T>) + 1; 218 for (; pos < size; ++pos) 219 if (status[pos] == VALIDCELL) 220 { 221 i = Pix(&tab[pos]); 222 return; 223 } 224 i = 0; 225} 226 227 228int <T>VOHSet:: operator == (<T>VOHSet& b) 229{ 230 if (count != b.count) 231 return 0; 232 else 233 { 234 for (int i = 0; i < size; ++i) 235 if (status[i] == VALIDCELL && b.seek(tab[i]) == 0) 236 return 0; 237 for (i = 0; i < b.size; ++i) 238 if (b.status[i] == VALIDCELL && seek(b.tab[i]) == 0) 239 return 0; 240 return 1; 241 } 242} 243 244int <T>VOHSet:: operator != (<T>VOHSet& b) 245{ 246 return !(*this == b); 247} 248 249int <T>VOHSet::operator <= (<T>VOHSet& b) 250{ 251 if (count > b.count) 252 return 0; 253 else 254 { 255 for (int i = 0; i < size; ++i) 256 if (status[i] == VALIDCELL && b.seek(tab[i]) == 0) 257 return 0; 258 return 1; 259 } 260} 261 262void <T>VOHSet::operator |= (<T>VOHSet& b) 263{ 264 if (&b == this || b.count == 0) 265 return; 266 for (int i = 0; i < b.size; ++i) 267 if (b.status[i] == VALIDCELL) add(b.tab[i]); 268} 269 270void <T>VOHSet::operator &= (<T>VOHSet& b) 271{ 272 if (&b == this || count == 0) 273 return; 274 for (int i = 0; i < size; ++i) 275 { 276 if (status[i] == VALIDCELL && b.seek(tab[i]) == 0) 277 { 278 status[i] = DELETEDCELL; 279 --count; 280 } 281 } 282} 283 284void <T>VOHSet::operator -= (<T>VOHSet& b) 285{ 286 for (int i = 0; i < size; ++i) 287 { 288 if (status[i] == VALIDCELL && b.seek(tab[i]) != 0) 289 { 290 status[i] = DELETEDCELL; 291 --count; 292 } 293 } 294} 295 296int <T>VOHSet::OK() 297{ 298 int v = tab != 0; 299 v &= status != 0; 300 int n = 0; 301 for (int i = 0; i < size; ++i) 302 { 303 if (status[i] == VALIDCELL) ++n; 304 else if (status[i] != DELETEDCELL && status[i] != EMPTYCELL) 305 v = 0; 306 } 307 v &= n == count; 308 if (!v) error("invariant failure"); 309 return v; 310} 311 312 313 314