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 6This file is part of GNU CC. 7 8GNU CC is distributed in the hope that it will be useful, 9but WITHOUT ANY WARRANTY. No author or distributor 10accepts responsibility to anyone for the consequences of using it 11or for whether it serves any particular purpose or works at all, 12unless he says so in writing. Refer to the GNU CC General Public 13License for full details. 14 15Everyone is granted permission to copy, modify and redistribute 16GNU CC, but only under the conditions described in the 17GNU CC General Public License. A copy of this license is 18supposed to have been given to you along with GNU CC so you 19can know your rights and responsibilities. It should be in a 20file named COPYING. Among other things, the copyright notice 21and this notice must be preserved on all copies. 22*/ 23 24#ifdef __GNUG__ 25#pragma implementation 26#endif 27#include "<T>.CHSet.h" 28 29// A CHSet is implemented as an array (tab) of buckets, each of which 30// contains a pointer to a list of <T>CHNodes. Each node contains a 31// pointer to the next node in the list, and a pointer to the <T>. 32// The end of the list is marked by a next node pointer which is odd 33// when considered as an integer (least significant bit = 1). The 34// assumption is that CHNodes will all begin on even addresses. If 35// the odd pointer is right-shifted by one bit, it becomes the index 36// within the tab array of the next bucket (that is, bucket i has 37// next bucket pointer 2*(i+1)+1). 38 39// The bucket pointers are initialized by the constructor and 40// used to support the next(Pix&) method. 41 42// This implementation is not portable to machines with different 43// pointer and integer sizes, or on which CHNodes might be aligned on 44// odd byte boundaries, but allows the same pointer to be used for 45// chaining within a bucket and to the next bucket. 46 47 48static inline int goodCHptr(<T>CHNode* t) 49{ 50 return ((((unsigned)t) & 1) == 0); 51} 52 53static inline <T>CHNode* index_to_CHptr(int i) 54{ 55 return (<T>CHNode*)((i << 1) + 1); 56} 57 58static inline int CHptr_to_index(<T>CHNode* t) 59{ 60 return ( ((unsigned) t) >> 1); 61} 62 63<T>CHSet::<T>CHSet(unsigned int sz) 64{ 65 tab = (<T>CHNode**)(new <T>CHNodePtr[size = sz]); 66 for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1); 67 count = 0; 68} 69 70<T>CHSet::<T>CHSet(<T>CHSet& a) 71{ 72 tab = (<T>CHNode**)(new <T>CHNodePtr[size = a.size]); 73 for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1); 74 count = 0; 75 for (Pix p = a.first(); p; a.next(p)) add(a(p)); 76} 77 78 79Pix <T>CHSet::seek(<T&> key) 80{ 81 unsigned int h = <T>HASH(key) % size; 82 83 for (<T>CHNode* t = tab[h]; goodCHptr(t); t = t->tl) 84 if (<T>EQ(key, t->hd)) 85 return Pix(t); 86 87 return 0; 88} 89 90 91Pix <T>CHSet::add(<T&> item) 92{ 93 unsigned int h = <T>HASH(item) % size; 94 95 for (<T>CHNode* t = tab[h]; goodCHptr(t); t = t->tl) 96 if (<T>EQ(item, t->hd)) 97 return Pix(t); 98 99 ++count; 100 t = new <T>CHNode(item, tab[h]); 101 tab[h] = t; 102 return Pix(t); 103} 104 105 106void <T>CHSet::del(<T&> key) 107{ 108 unsigned int h = <T>HASH(key) % size; 109 110 <T>CHNode* t = tab[h]; 111 <T>CHNode* trail = t; 112 while (goodCHptr(t)) 113 { 114 if (<T>EQ(key, t->hd)) 115 { 116 if (trail == t) 117 tab[h] = t->tl; 118 else 119 trail->tl = t->tl; 120 delete t; 121 --count; 122 return; 123 } 124 trail = t; 125 t = t->tl; 126 } 127} 128 129 130void <T>CHSet::clear() 131{ 132 for (unsigned int i = 0; i < size; ++i) 133 { 134 <T>CHNode* p = tab[i]; 135 tab[i] = index_to_CHptr(i+1); 136 while (goodCHptr(p)) 137 { 138 <T>CHNode* nxt = p->tl; 139 delete(p); 140 p = nxt; 141 } 142 } 143 count = 0; 144} 145 146Pix <T>CHSet::first() 147{ 148 for (unsigned int i = 0; i < size; ++i) if (goodCHptr(tab[i])) return Pix(tab[i]); 149 return 0; 150} 151 152void <T>CHSet::next(Pix& p) 153{ 154 if (p == 0) return; 155 <T>CHNode* t = ((<T>CHNode*)p)->tl; 156 if (goodCHptr(t)) 157 p = Pix(t); 158 else 159 { 160 for (unsigned int i = CHptr_to_index(t); i < size; ++i) 161 { 162 if (goodCHptr(tab[i])) 163 { 164 p = Pix(tab[i]); 165 return; 166 } 167 } 168 p = 0; 169 } 170} 171 172int <T>CHSet::operator == (<T>CHSet& b) 173{ 174 if (count != b.count) 175 return 0; 176 else 177 { 178 <T>CHNode* p; 179 for (unsigned int i = 0; i < size; ++i) 180 for (p = tab[i]; goodCHptr(p); p = p->tl) 181 if (b.seek(p->hd) == 0) 182 return 0; 183 for (i = 0; i < b.size; ++i) 184 for (p = b.tab[i]; goodCHptr(p); p = p->tl) 185 if (seek(p->hd) == 0) 186 return 0; 187 return 1; 188 } 189} 190 191int <T>CHSet::operator <= (<T>CHSet& b) 192{ 193 if (count > b.count) 194 return 0; 195 else 196 { 197 for (unsigned int i = 0; i < size; ++i) 198 for (<T>CHNode* p = tab[i]; goodCHptr(p); p = p->tl) 199 if (b.seek(p->hd) == 0) 200 return 0; 201 return 1; 202 } 203} 204 205void <T>CHSet::operator |= (<T>CHSet& b) 206{ 207 if (&b == this || b.count == 0) 208 return; 209 for (unsigned int i = 0; i < b.size; ++i) 210 for (<T>CHNode* p = b.tab[i]; goodCHptr(p); p = p->tl) 211 add(p->hd); 212} 213 214void <T>CHSet::operator &= (<T>CHSet& b) 215{ 216 for (unsigned int i = 0; i < size; ++i) 217 { 218 <T>CHNode* t = tab[i]; 219 <T>CHNode* trail = t; 220 while (goodCHptr(t)) 221 { 222 <T>CHNode* nxt = t->tl; 223 if (b.seek(t->hd) == 0) 224 { 225 if (trail == tab[i]) 226 trail = tab[i] = nxt; 227 else 228 trail->tl = nxt; 229 delete t; 230 --count; 231 } 232 else 233 trail = t; 234 t = nxt; 235 } 236 } 237} 238 239void <T>CHSet::operator -= (<T>CHSet& b) 240{ 241 for (unsigned int i = 0; i < size; ++i) 242 { 243 <T>CHNode* t = tab[i]; 244 <T>CHNode* trail = t; 245 while (goodCHptr(t)) 246 { 247 <T>CHNode* nxt = t->tl; 248 if (b.seek(t->hd) != 0) 249 { 250 if (trail == tab[i]) 251 trail = tab[i] = nxt; 252 else 253 trail->tl = nxt; 254 delete t; 255 --count; 256 } 257 else 258 trail = t; 259 t = nxt; 260 } 261 } 262} 263 264int <T>CHSet::OK() 265{ 266 int v = tab != 0; 267 int n = 0; 268 for (unsigned int i = 0; i < size; ++i) 269 { 270 for (<T>CHNode* p = tab[i]; goodCHptr(p); p = p->tl) ++n; 271 v &= CHptr_to_index(p) == i + 1; 272 } 273 v &= count == n; 274 if (!v) error("invariant failure"); 275 return v; 276} 277