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 konrad.r 1.17 if (_chains) 222 delete [] _chains;
223 mike 1.10 } 224 225 _HashTableRep& _HashTableRep::operator=(const _HashTableRep& x) 226 { 227 if (this == &x) 228 return this; 229 230 // Destroy the old representation: 231 232 clear(); 233 234 if (_chains) 235 delete [] _chains; 236 237 // Create chain array: 238 239 _chains = new _BucketBase[_numChains = x._numChains]; 240 memset(_chains, 0, sizeof(_BucketBase) _numChains); 241 _size = x._size; 242 243 // Copy over the buckets: 244 mike 1.10 245 for (Uint32 i = 0; i < _numChains; i++) 246 { 247 if (x._chains[i]) 248 { 249 _chains[i] = x._chains[i]->clone(); 250 251 _BucketBase* curr = _chains[i]; 252 _BucketBase* next = x._chains[i]->next; 253 254 for (; next; next = next->next) 255 { 256 curr->next = next->clone(); 257 curr = curr->next; 258 } 259 } 260 } 261 262 return this; 263 } 264 265 mike 1.10 void _HashTableRep::clear() 266 { 267 for (Uint32 i = 0; i < _numChains; i++) 268 { 269 for (_BucketBase bucket = _chains[i]; bucket; ) 270 { 271 _BucketBase* next = bucket->next; 272 delete bucket; 273 bucket = next; 274 } 275 } 276 277 _size = 0; 278 279 if (_numChains) 280 memset(_chains, 0, sizeof(_BucketBase) _numChains); 281 } 282 283 Boolean _HashTableRep::insert( 284 Uint32 hashCode, 285 _BucketBase* bucket, 286 mike 1.10 const void* key) 287 { 288 // Check for duplicate entry with same key: 289 290 Uint32 i = hashCode % _numChains; 291 _BucketBase* last = 0; 292 293 for (_BucketBase* b = _chains[i]; b; b = b->next) 294 { 295 if (b->equal(key)) 296 { 297 delete bucket; 298 return false; 299 } 300 301 last = b; 302 } 303 304 // Insert bucket: 305 306 bucket->next = 0; 307 mike 1.10 308 if (last) 309 last->next = bucket; 310 else 311 _chains[i] = bucket; 312 313 _size++; 314 return true; 315 } 316 317 const _BucketBase* _HashTableRep::lookup( 318 Uint32 hashCode,
319 mike 1.11 const void* key) const
320 mike 1.10 {
321 gs.keenan 1.16 #ifdef PEGASUS_OS_VMS
322 gs.keenan 1.19
323 gs.keenan 1.16 // This is to prevent a crash when the hash 324 // code hasn't been initialized!
325 gs.keenan 1.19 326 if (_numChains == 0) 327 { 328 return 0; 329 }
330 gs.keenan 1.16 #endif
331 mike 1.10 Uint32 i = hashCode % _numChains; 332 333 for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next) 334 { 335 if (bucket->equal(key)) 336 return bucket; 337 } 338 339 // Not found! 340 return 0; 341 } 342 343 Boolean _HashTableRep::remove(Uint32 hashCode, const void* key) 344 {
345 dave.sudlik 1.20 Uint32 i = hashCode % _numChains; 346 347 _BucketBase* prev = 0; 348 349 for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
350 mike 1.10 {
351 dave.sudlik 1.20 if (bucket->equal(key)) 352 { 353 if (prev) 354 prev->next = bucket->next; 355 else 356 _chains[i] = bucket->next;
357 mike 1.10
358 dave.sudlik 1.20 delete bucket; 359 _size--; 360 return true; 361 } 362 prev = bucket;
363 mike 1.10 } 364 365 return false; 366 } 367 368 PEGASUS_NAMESPACE_END

No CVS admin address has been configured