pegasus/src/Pegasus/Common/HashTable.cpp - annotate

Return to HashTable.cpp CVS log

Up to [Pegasus] / pegasus / src / Pegasus / Common

1 karl 1.22 //%2006////////////////////////////////////////////////////////////////////////
2 mike 1.10 //
3 karl 1.14 // Copyright (c) 2000, 2001, 2002 BMC Software; Hewlett-Packard Development 4 // Company, L.P.; IBM Corp.; The Open Group; Tivoli Systems. 5 // Copyright (c) 2003 BMC Software; Hewlett-Packard Development Company, L.P.;
6 karl 1.13 // IBM Corp.; EMC Corporation, The Open Group.
7 karl 1.14 // Copyright (c) 2004 BMC Software; Hewlett-Packard Development Company, L.P.; 8 // IBM Corp.; EMC Corporation; VERITAS Software Corporation; The Open Group.
9 karl 1.15 // Copyright (c) 2005 Hewlett-Packard Development Company, L.P.; IBM Corp.; 10 // EMC Corporation; VERITAS Software Corporation; The Open Group.
11 karl 1.22 // Copyright (c) 2006 Hewlett-Packard Development Company, L.P.; IBM Corp.; 12 // EMC Corporation; Symantec Corporation; The Open Group.
13 mike 1.10 // 14 // Permission is hereby granted, free of charge, to any person obtaining a copy
15 kumpf 1.12 // of this software and associated documentation files (the "Software"), to 16 // deal in the Software without restriction, including without limitation the 17 // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
18 mike 1.10 // sell copies of the Software, and to permit persons to whom the Software is 19 // furnished to do so, subject to the following conditions: 20 //
21 kumpf 1.12 // THE ABOVE COPYRIGHT NOTICE AND THIS PERMISSION NOTICE SHALL BE INCLUDED IN
22 mike 1.10 // ALL COPIES OR SUBSTANTIAL PORTIONS OF THE SOFTWARE. THE SOFTWARE IS PROVIDED 23 // "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
24 kumpf 1.12 // LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR 25 // PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 26 // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
27 mike 1.10 // ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 28 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 29 // 30 //============================================================================== 31 // 32 //%///////////////////////////////////////////////////////////////////////////// 33 34 #include <cstring> 35 #include "HashTable.h" 36 37 PEGASUS_NAMESPACE_BEGIN 38 39 //////////////////////////////////////////////////////////////////////////////// 40 //
41 mike 1.21 // Hash routines
42 mike 1.10 // 43 //////////////////////////////////////////////////////////////////////////////// 44 45 Uint32 HashFunc<String>::hash(const String& str) 46 {
47 mike 1.21 // Caution: do not change this hash algorithm since hash codes are stored 48 // in the repository. Any change here will break backwards compatibility 49 // of the repository. 50
51 mike 1.10 Uint32 h = 0;
52 mike 1.21 const Uint16* p = (const Uint16)str.getChar16Data(); 53 Uint32 n = str.size(); 54 55 while (n--) 56 h = 5 h + *p++; 57 58 return h; 59 } 60
61 kumpf 1.24 static const Uint8 _toLowerTable[256] =
62 mike 1.21 { 63 0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07, 64 0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F, 65 0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17, 66 0x18,0x19,0x1A,0x1B,0x1C,0x1D,0x1E,0x1F, 67 0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27, 68 0x28,0x29,0x2A,0x2B,0x2C,0x2D,0x2E,0x2F, 69 0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37, 70 0x38,0x39,0x3A,0x3B,0x3C,0x3D,0x3E,0x3F, 71 0x40,0x61,0x62,0x63,0x64,0x65,0x66,0x67, 72 0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F, 73 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77, 74 0x78,0x79,0x7A,0x5B,0x5C,0x5D,0x5E,0x5F, 75 0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67, 76 0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F, 77 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77, 78 0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x7E,0x7F, 79 0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87, 80 0x88,0x89,0x8A,0x8B,0x8C,0x8D,0x8E,0x8F, 81 0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97, 82 0x98,0x99,0x9A,0x9B,0x9C,0x9D,0x9E,0x9F, 83 mike 1.21 0xA0,0xA1,0xA2,0xA3,0xA4,0xA5,0xA6,0xA7, 84 0xA8,0xA9,0xAA,0xAB,0xAC,0xAD,0xAE,0xAF, 85 0xB0,0xB1,0xB2,0xB3,0xB4,0xB5,0xB6,0xB7, 86 0xB8,0xB9,0xBA,0xBB,0xBC,0xBD,0xBE,0xBF, 87 0xC0,0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7, 88 0xC8,0xC9,0xCA,0xCB,0xCC,0xCD,0xCE,0xCF, 89 0xD0,0xD1,0xD2,0xD3,0xD4,0xD5,0xD6,0xD7, 90 0xD8,0xD9,0xDA,0xDB,0xDC,0xDD,0xDE,0xDF, 91 0xE0,0xE1,0xE2,0xE3,0xE4,0xE5,0xE6,0xE7, 92 0xE8,0xE9,0xEA,0xEB,0xEC,0xED,0xEE,0xEF, 93 0xF0,0xF1,0xF2,0xF3,0xF4,0xF5,0xF6,0xF7, 94 0xF8,0xF9,0xFA,0xFB,0xFC,0xFD,0xFE,0xFF, 95 }; 96 97 Uint32 HashLowerCaseFunc::hash(const String& str) 98 { 99 Uint16* p = (Uint16*)str.getChar16Data(); 100 Uint32 h = 0; 101 Uint32 n = str.size(); 102 103 while (n >= 4) 104 mike 1.21 {
105 kumpf 1.24 h = ((h << 9) \| (h >> 23)) ^ (Uint32)_toLowerTable[p[0] & 0x007F]; 106 h = ((h << 9) \| (h >> 23)) ^ (Uint32)_toLowerTable[p[1] & 0x007F]; 107 h = ((h << 9) \| (h >> 23)) ^ (Uint32)_toLowerTable[p[2] & 0x007F]; 108 h = ((h << 9) \| (h >> 23)) ^ (Uint32)_toLowerTable[p[3] & 0x007F]; 109 n -= 4; 110 p += 4;
111 mike 1.21 }
112 mike 1.10
113 mike 1.21 while (*p)
114 kumpf 1.24 h = ((h << 9) \| (h >> 23)) ^ (Uint32)_toLowerTable[*p++ & 0x007F];
115 mike 1.10 116 return h; 117 } 118 119 //////////////////////////////////////////////////////////////////////////////// 120 // 121 // _HashTableRep::_BucketBase 122 // 123 //////////////////////////////////////////////////////////////////////////////// 124 125 _BucketBase::~_BucketBase() 126 { 127 128 } 129 130 //////////////////////////////////////////////////////////////////////////////// 131 // 132 // _HashTableIteratorBase 133 // 134 //////////////////////////////////////////////////////////////////////////////// 135 136 mike 1.10 _HashTableIteratorBase _HashTableIteratorBase::operator++(int) 137 { 138 _HashTableIteratorBase tmp = this; 139 operator++(); 140 return tmp; 141 } 142 143 _HashTableIteratorBase& _HashTableIteratorBase::operator++() 144 { 145 // At the end? 146 147 if (!_bucket) 148 return this; 149 150 // More buckets this chain? 151 152 if ((_bucket = _bucket->next)) 153 return this; 154 155 // Find the next non-empty chain: 156 157 mike 1.10 _bucket = 0; 158 159 while (_first != _last) 160 { 161 if (_first)
162 kumpf 1.24 { 163 _bucket = *_first++; 164 break; 165 }
166 mike 1.10
167 kumpf 1.24 _first++;
168 mike 1.10 } 169 170 return *this; 171 } 172 173 _HashTableIteratorBase::_HashTableIteratorBase(
174 kumpf 1.24 _BucketBase** first,
175 mike 1.10 _BucketBase** last) : _first(first), _last(last) 176 { 177 _bucket = 0; 178 179 while (_first != last) 180 { 181 if (*_first)
182 kumpf 1.24 { 183 _bucket = *_first++; 184 break; 185 }
186 mike 1.10
187 kumpf 1.24 _first++;
188 mike 1.10 } 189 } 190 191 //////////////////////////////////////////////////////////////////////////////// 192 // 193 // _HashTableRep 194 // 195 //////////////////////////////////////////////////////////////////////////////// 196 197 _HashTableRep::_HashTableRep(Uint32 numChains) : _size(0), _numChains(numChains) 198 { 199 if (numChains < 8)
200 kumpf 1.24 numChains = 8;
201 mike 1.10 202 _chains = new _BucketBase[_numChains]; 203 memset(_chains, 0, sizeof(_BucketBase) * _numChains); 204 } 205 206 _HashTableRep::_HashTableRep(const _HashTableRep& x) 207 { 208 _size = 0; 209 _numChains = 0; 210 _chains = 0; 211 operator=(x); 212 } 213 214 _HashTableRep::~_HashTableRep() 215 { 216 clear();
217 kumpf 1.23 delete [] _chains;
218 mike 1.10 } 219 220 _HashTableRep& _HashTableRep::operator=(const _HashTableRep& x) 221 { 222 if (this == &x)
223 kumpf 1.24 return *this;
224 mike 1.10 225 // Destroy the old representation: 226 227 clear(); 228
229 kumpf 1.23 delete [] _chains;
230 mike 1.10 231 // Create chain array: 232 233 _chains = new _BucketBase[_numChains = x._numChains]; 234 memset(_chains, 0, sizeof(_BucketBase) * _numChains); 235 _size = x._size; 236 237 // Copy over the buckets: 238 239 for (Uint32 i = 0; i < _numChains; i++) 240 {
241 kumpf 1.24 if (x._chains[i]) 242 { 243 _chains[i] = x._chains[i]->clone(); 244 245 _BucketBase* curr = _chains[i]; 246 _BucketBase* next = x._chains[i]->next; 247 248 for (; next; next = next->next) 249 { 250 curr->next = next->clone(); 251 curr = curr->next; 252 } 253 }
254 mike 1.10 } 255 256 return *this; 257 } 258 259 void _HashTableRep::clear() 260 { 261 for (Uint32 i = 0; i < _numChains; i++) 262 {
263 kumpf 1.24 for (_BucketBase* bucket = _chains[i]; bucket; ) 264 { 265 _BucketBase* next = bucket->next; 266 delete bucket; 267 bucket = next; 268 }
269 mike 1.10 } 270 271 _size = 0; 272 273 if (_numChains)
274 kumpf 1.24 memset(_chains, 0, sizeof(_BucketBase) _numChains);
275 mike 1.10 } 276 277 Boolean _HashTableRep::insert(
278 kumpf 1.24 Uint32 hashCode, 279 _BucketBase* bucket,
280 mike 1.10 const void* key) 281 { 282 // Check for duplicate entry with same key: 283 284 Uint32 i = hashCode % _numChains; 285 _BucketBase* last = 0; 286 287 for (_BucketBase* b = _chains[i]; b; b = b->next) 288 {
289 kumpf 1.24 if (b->equal(key)) 290 { 291 delete bucket; 292 return false; 293 }
294 mike 1.10
295 kumpf 1.24 last = b;
296 mike 1.10 } 297 298 // Insert bucket: 299 300 bucket->next = 0; 301 302 if (last)
303 kumpf 1.24 last->next = bucket;
304 mike 1.10 else
305 kumpf 1.24 _chains[i] = bucket;
306 mike 1.10 307 _size++; 308 return true; 309 } 310 311 const _BucketBase* _HashTableRep::lookup(
312 kumpf 1.24 Uint32 hashCode,
313 mike 1.11 const void* key) const
314 mike 1.10 {
315 gs.keenan 1.16 #ifdef PEGASUS_OS_VMS
316 gs.keenan 1.19
317 gs.keenan 1.16 // This is to prevent a crash when the hash 318 // code hasn't been initialized!
319 gs.keenan 1.19 320 if (_numChains == 0) 321 { 322 return 0; 323 }
324 gs.keenan 1.16 #endif
325 mike 1.10 Uint32 i = hashCode % _numChains; 326 327 for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next) 328 {
329 kumpf 1.24 if (bucket->equal(key)) 330 return bucket;
331 mike 1.10 } 332 333 // Not found! 334 return 0; 335 } 336 337 Boolean _HashTableRep::remove(Uint32 hashCode, const void* key) 338 {
339 dave.sudlik 1.20 Uint32 i = hashCode % _numChains; 340 341 _BucketBase* prev = 0; 342 343 for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
344 mike 1.10 {
345 dave.sudlik 1.20 if (bucket->equal(key)) 346 { 347 if (prev) 348 prev->next = bucket->next; 349 else 350 _chains[i] = bucket->next;
351 mike 1.10
352 dave.sudlik 1.20 delete bucket; 353 _size--; 354 return true; 355 } 356 prev = bucket;
357 mike 1.10 } 358 359 return false; 360 } 361 362 PEGASUS_NAMESPACE_END

No CVS admin address has been configured