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

Return to HashTable.cpp CVS log

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

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

No CVS admin address has been configured