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

Return to HashTable.cpp CVS log

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

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

No CVS admin address has been configured