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 // Author: Mike Brasher (mbrasher@bmc.com) 33 // 34 // Modified By: 35 // 36 //%///////////////////////////////////////////////////////////////////////////// 37 38 #include <cstring> 39 #include "HashTable.h" 40 41 PEGASUS_NAMESPACE_BEGIN 42 43 //////////////////////////////////////////////////////////////////////////////// 44 //
45 mike 1.21 // Hash routines
46 mike 1.10 // 47 //////////////////////////////////////////////////////////////////////////////// 48 49 Uint32 HashFunc<String>::hash(const String& str) 50 {
51 mike 1.21 // Caution: do not change this hash algorithm since hash codes are stored 52 // in the repository. Any change here will break backwards compatibility 53 // of the repository. 54
55 mike 1.10 Uint32 h = 0;
56 mike 1.21 const Uint16* p = (const Uint16)str.getChar16Data(); 57 Uint32 n = str.size(); 58 59 while (n--) 60 h = 5 h + p++; 61 62 return h; 63 } 64 65 static const Uint8 _toLowerTable[256] = 66 { 67 0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07, 68 0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F, 69 0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17, 70 0x18,0x19,0x1A,0x1B,0x1C,0x1D,0x1E,0x1F, 71 0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27, 72 0x28,0x29,0x2A,0x2B,0x2C,0x2D,0x2E,0x2F, 73 0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37, 74 0x38,0x39,0x3A,0x3B,0x3C,0x3D,0x3E,0x3F, 75 0x40,0x61,0x62,0x63,0x64,0x65,0x66,0x67, 76 0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F, 77 mike 1.21 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77, 78 0x78,0x79,0x7A,0x5B,0x5C,0x5D,0x5E,0x5F, 79 0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67, 80 0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F, 81 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77, 82 0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x7E,0x7F, 83 0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87, 84 0x88,0x89,0x8A,0x8B,0x8C,0x8D,0x8E,0x8F, 85 0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97, 86 0x98,0x99,0x9A,0x9B,0x9C,0x9D,0x9E,0x9F, 87 0xA0,0xA1,0xA2,0xA3,0xA4,0xA5,0xA6,0xA7, 88 0xA8,0xA9,0xAA,0xAB,0xAC,0xAD,0xAE,0xAF, 89 0xB0,0xB1,0xB2,0xB3,0xB4,0xB5,0xB6,0xB7, 90 0xB8,0xB9,0xBA,0xBB,0xBC,0xBD,0xBE,0xBF, 91 0xC0,0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7, 92 0xC8,0xC9,0xCA,0xCB,0xCC,0xCD,0xCE,0xCF, 93 0xD0,0xD1,0xD2,0xD3,0xD4,0xD5,0xD6,0xD7, 94 0xD8,0xD9,0xDA,0xDB,0xDC,0xDD,0xDE,0xDF, 95 0xE0,0xE1,0xE2,0xE3,0xE4,0xE5,0xE6,0xE7, 96 0xE8,0xE9,0xEA,0xEB,0xEC,0xED,0xEE,0xEF, 97 0xF0,0xF1,0xF2,0xF3,0xF4,0xF5,0xF6,0xF7, 98 mike 1.21 0xF8,0xF9,0xFA,0xFB,0xFC,0xFD,0xFE,0xFF, 99 }; 100 101 Uint32 HashLowerCaseFunc::hash(const String& str) 102 { 103 Uint16 p = (Uint16*)str.getChar16Data(); 104 Uint32 h = 0; 105 Uint32 n = str.size(); 106 107 while (n >= 4) 108 { 109 h = ((h << 9) \| (h >> 23)) ^ (Uint32)_toLowerTable[p[0] & 0x007F]; 110 h = ((h << 9) \| (h >> 23)) ^ (Uint32)_toLowerTable[p[1] & 0x007F]; 111 h = ((h << 9) \| (h >> 23)) ^ (Uint32)_toLowerTable[p[2] & 0x007F]; 112 h = ((h << 9) \| (h >> 23)) ^ (Uint32)_toLowerTable[p[3] & 0x007F]; 113 n -= 4; 114 p += 4; 115 }
116 mike 1.10
117 mike 1.21 while (p) 118 h = ((h << 9) \| (h >> 23)) ^ (Uint32)_toLowerTable[p++ & 0x007F];
119 mike 1.10 120 return h; 121 } 122 123 //////////////////////////////////////////////////////////////////////////////// 124 // 125 // _HashTableRep::_BucketBase 126 // 127 //////////////////////////////////////////////////////////////////////////////// 128 129 _BucketBase::~_BucketBase() 130 { 131 132 } 133 134 //////////////////////////////////////////////////////////////////////////////// 135 // 136 // _HashTableIteratorBase 137 // 138 //////////////////////////////////////////////////////////////////////////////// 139 140 mike 1.10 _HashTableIteratorBase _HashTableIteratorBase::operator++(int) 141 { 142 _HashTableIteratorBase tmp = this; 143 operator++(); 144 return tmp; 145 } 146 147 _HashTableIteratorBase& _HashTableIteratorBase::operator++() 148 { 149 // At the end? 150 151 if (!_bucket) 152 return this; 153 154 // More buckets this chain? 155 156 if ((_bucket = _bucket->next)) 157 return this; 158 159 // Find the next non-empty chain: 160 161 mike 1.10 _bucket = 0; 162 163 while (_first != _last) 164 { 165 if (_first) 166 { 167 _bucket = _first++; 168 break; 169 } 170 171 _first++; 172 } 173 174 return this; 175 } 176 177 _HashTableIteratorBase::_HashTableIteratorBase( 178 _BucketBase first, 179 _BucketBase last) : _first(first), _last(last) 180 { 181 _bucket = 0; 182 mike 1.10 183 while (_first != last) 184 { 185 if (_first) 186 { 187 _bucket = _first++; 188 break; 189 } 190 191 _first++; 192 } 193 } 194 195 //////////////////////////////////////////////////////////////////////////////// 196 // 197 // _HashTableRep 198 // 199 //////////////////////////////////////////////////////////////////////////////// 200 201 _HashTableRep::_HashTableRep(Uint32 numChains) : _size(0), _numChains(numChains) 202 { 203 mike 1.10 if (numChains < 8) 204 numChains = 8; 205 206 _chains = new _BucketBase[_numChains]; 207 memset(_chains, 0, sizeof(_BucketBase) * _numChains); 208 } 209 210 _HashTableRep::_HashTableRep(const _HashTableRep& x) 211 { 212 _size = 0; 213 _numChains = 0; 214 _chains = 0; 215 operator=(x); 216 } 217 218 _HashTableRep::~_HashTableRep() 219 { 220 clear();
221 kumpf 1.23 delete [] _chains;
222 mike 1.10 } 223 224 _HashTableRep& _HashTableRep::operator=(const _HashTableRep& x) 225 { 226 if (this == &x) 227 return *this; 228 229 // Destroy the old representation: 230 231 clear(); 232
233 kumpf 1.23 delete [] _chains;
234 mike 1.10 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 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 mike 1.10 curr = curr->next; 256 } 257 } 258 } 259 260 return this; 261 } 262 263 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 mike 1.10 277 if (_numChains) 278 memset(_chains, 0, sizeof(_BucketBase) _numChains); 279 } 280 281 Boolean _HashTableRep::insert( 282 Uint32 hashCode, 283 _BucketBase* bucket, 284 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 mike 1.10 } 298 299 last = b; 300 } 301 302 // Insert bucket: 303 304 bucket->next = 0; 305 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