[2674] | 1 | /* |
---|
| 2 | * Licensed to the Apache Software Foundation (ASF) under one or more |
---|
| 3 | * contributor license agreements. See the NOTICE file distributed with |
---|
| 4 | * this work for additional information regarding copyright ownership. |
---|
| 5 | * The ASF licenses this file to You under the Apache License, Version 2.0 |
---|
| 6 | * (the "License"); you may not use this file except in compliance with |
---|
| 7 | * the License. You may obtain a copy of the License at |
---|
| 8 | * |
---|
| 9 | * http://www.apache.org/licenses/LICENSE-2.0 |
---|
| 10 | * |
---|
| 11 | * Unless required by applicable law or agreed to in writing, software |
---|
| 12 | * distributed under the License is distributed on an "AS IS" BASIS, |
---|
| 13 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
---|
| 14 | * See the License for the specific language governing permissions and |
---|
| 15 | * limitations under the License. |
---|
| 16 | */ |
---|
| 17 | |
---|
| 18 | /* |
---|
| 19 | * $Id: RefHashTableOf.c 568078 2007-08-21 11:43:25Z amassari $ |
---|
| 20 | */ |
---|
| 21 | |
---|
| 22 | |
---|
| 23 | // --------------------------------------------------------------------------- |
---|
| 24 | // Include |
---|
| 25 | // --------------------------------------------------------------------------- |
---|
| 26 | #if defined(XERCES_TMPLSINC) |
---|
| 27 | #include <xercesc/util/RefHashTableOf.hpp> |
---|
| 28 | #endif |
---|
| 29 | |
---|
| 30 | #include <xercesc/util/Janitor.hpp> |
---|
| 31 | #include <xercesc/util/NullPointerException.hpp> |
---|
| 32 | #include <assert.h> |
---|
| 33 | #include <new> |
---|
| 34 | |
---|
| 35 | XERCES_CPP_NAMESPACE_BEGIN |
---|
| 36 | |
---|
| 37 | // --------------------------------------------------------------------------- |
---|
| 38 | // RefHashTableOf: Constructors and Destructor |
---|
| 39 | // --------------------------------------------------------------------------- |
---|
| 40 | template <class TVal> |
---|
| 41 | RefHashTableOf<TVal>::RefHashTableOf( const unsigned int modulus |
---|
| 42 | , const bool adoptElems |
---|
| 43 | , MemoryManager* const manager) |
---|
| 44 | |
---|
| 45 | : fMemoryManager(manager) |
---|
| 46 | , fAdoptedElems(adoptElems) |
---|
| 47 | , fBucketList(0) |
---|
| 48 | , fHashModulus(modulus) |
---|
| 49 | , fInitialModulus(modulus) |
---|
| 50 | , fCount(0) |
---|
| 51 | , fHash(0) |
---|
| 52 | |
---|
| 53 | { |
---|
| 54 | initialize(modulus); |
---|
| 55 | |
---|
| 56 | // create default hasher |
---|
| 57 | fHash = new (fMemoryManager) HashXMLCh(); |
---|
| 58 | } |
---|
| 59 | |
---|
| 60 | template <class TVal> |
---|
| 61 | RefHashTableOf<TVal>::RefHashTableOf( const unsigned int modulus |
---|
| 62 | , const bool adoptElems |
---|
| 63 | , HashBase* hashBase |
---|
| 64 | , MemoryManager* const manager) |
---|
| 65 | |
---|
| 66 | : fMemoryManager(manager) |
---|
| 67 | , fAdoptedElems(adoptElems) |
---|
| 68 | , fBucketList(0) |
---|
| 69 | , fHashModulus(modulus) |
---|
| 70 | , fInitialModulus(modulus) |
---|
| 71 | , fCount(0) |
---|
| 72 | , fHash(0) |
---|
| 73 | { |
---|
| 74 | initialize(modulus); |
---|
| 75 | // set hasher |
---|
| 76 | fHash = hashBase; |
---|
| 77 | } |
---|
| 78 | |
---|
| 79 | template <class TVal> |
---|
| 80 | RefHashTableOf<TVal>::RefHashTableOf(const unsigned int modulus |
---|
| 81 | , MemoryManager* const manager) |
---|
| 82 | |
---|
| 83 | : fMemoryManager(manager) |
---|
| 84 | , fAdoptedElems(true) |
---|
| 85 | , fBucketList(0) |
---|
| 86 | , fHashModulus(modulus) |
---|
| 87 | , fInitialModulus(modulus) |
---|
| 88 | , fCount(0) |
---|
| 89 | , fHash(0) |
---|
| 90 | { |
---|
| 91 | initialize(modulus); |
---|
| 92 | |
---|
| 93 | // create default hasher |
---|
| 94 | fHash = new (fMemoryManager) HashXMLCh(); |
---|
| 95 | } |
---|
| 96 | |
---|
| 97 | template <class TVal> void RefHashTableOf<TVal>::initialize(const unsigned int modulus) |
---|
| 98 | { |
---|
| 99 | if (modulus == 0) |
---|
| 100 | ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager); |
---|
| 101 | |
---|
| 102 | // Allocate the bucket list and zero them |
---|
| 103 | fBucketList = (RefHashTableBucketElem<TVal>**) fMemoryManager->allocate |
---|
| 104 | ( |
---|
| 105 | fHashModulus * sizeof(RefHashTableBucketElem<TVal>*) |
---|
| 106 | ); //new RefHashTableBucketElem<TVal>*[fHashModulus]; |
---|
| 107 | for (unsigned int index = 0; index < fHashModulus; index++) |
---|
| 108 | fBucketList[index] = 0; |
---|
| 109 | } |
---|
| 110 | |
---|
| 111 | template <class TVal> RefHashTableOf<TVal>::~RefHashTableOf() |
---|
| 112 | { |
---|
| 113 | cleanup(); |
---|
| 114 | } |
---|
| 115 | |
---|
| 116 | |
---|
| 117 | // --------------------------------------------------------------------------- |
---|
| 118 | // RefHashTableOf: Element management |
---|
| 119 | // --------------------------------------------------------------------------- |
---|
| 120 | template <class TVal> bool RefHashTableOf<TVal>::isEmpty() const |
---|
| 121 | { |
---|
| 122 | return fCount==0; |
---|
| 123 | } |
---|
| 124 | |
---|
| 125 | template <class TVal> bool RefHashTableOf<TVal>:: |
---|
| 126 | containsKey(const void* const key) const |
---|
| 127 | { |
---|
| 128 | unsigned int hashVal; |
---|
| 129 | const RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal); |
---|
| 130 | return (findIt != 0); |
---|
| 131 | } |
---|
| 132 | |
---|
| 133 | template <class TVal> void RefHashTableOf<TVal>:: |
---|
| 134 | removeKey(const void* const key) |
---|
| 135 | { |
---|
| 136 | // Hash the key |
---|
| 137 | unsigned int hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager); |
---|
| 138 | assert(hashVal < fHashModulus); |
---|
| 139 | |
---|
| 140 | // |
---|
| 141 | // Search the given bucket for this key. Keep up with the previous |
---|
| 142 | // element so we can patch around it. |
---|
| 143 | // |
---|
| 144 | RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal]; |
---|
| 145 | RefHashTableBucketElem<TVal>* lastElem = 0; |
---|
| 146 | |
---|
| 147 | while (curElem) |
---|
| 148 | { |
---|
| 149 | if (fHash->equals(key, curElem->fKey)) |
---|
| 150 | { |
---|
| 151 | if (!lastElem) |
---|
| 152 | { |
---|
| 153 | // It was the first in the bucket |
---|
| 154 | fBucketList[hashVal] = curElem->fNext; |
---|
| 155 | } |
---|
| 156 | else |
---|
| 157 | { |
---|
| 158 | // Patch around the current element |
---|
| 159 | lastElem->fNext = curElem->fNext; |
---|
| 160 | } |
---|
| 161 | |
---|
| 162 | // If we adopted the data, then delete it too |
---|
| 163 | // (Note: the userdata hash table instance has data type of void *. |
---|
| 164 | // This will generate compiler warnings here on some platforms, but they |
---|
| 165 | // can be ignored since fAdoptedElements is false. |
---|
| 166 | if (fAdoptedElems) |
---|
| 167 | delete curElem->fData; |
---|
| 168 | |
---|
| 169 | // Then delete the current element and move forward |
---|
| 170 | // delete curElem; |
---|
| 171 | // destructor doesn't do anything... |
---|
| 172 | // curElem->~RefHashTableBucketElem(); |
---|
| 173 | fMemoryManager->deallocate(curElem); |
---|
| 174 | |
---|
| 175 | fCount--; |
---|
| 176 | |
---|
| 177 | return; |
---|
| 178 | } |
---|
| 179 | |
---|
| 180 | // Move both pointers upwards |
---|
| 181 | lastElem = curElem; |
---|
| 182 | curElem = curElem->fNext; |
---|
| 183 | } |
---|
| 184 | |
---|
| 185 | // We never found that key |
---|
| 186 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager); |
---|
| 187 | } |
---|
| 188 | |
---|
| 189 | template <class TVal> void RefHashTableOf<TVal>::removeAll() |
---|
| 190 | { |
---|
| 191 | if(isEmpty()) |
---|
| 192 | return; |
---|
| 193 | |
---|
| 194 | // Clean up the buckets first |
---|
| 195 | for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++) |
---|
| 196 | { |
---|
| 197 | // Get the bucket list head for this entry |
---|
| 198 | RefHashTableBucketElem<TVal>* curElem = fBucketList[buckInd]; |
---|
| 199 | RefHashTableBucketElem<TVal>* nextElem; |
---|
| 200 | while (curElem) |
---|
| 201 | { |
---|
| 202 | // Save the next element before we hose this one |
---|
| 203 | nextElem = curElem->fNext; |
---|
| 204 | |
---|
| 205 | // If we adopted the data, then delete it too |
---|
| 206 | // (Note: the userdata hash table instance has data type of void *. |
---|
| 207 | // This will generate compiler warnings here on some platforms, but they |
---|
| 208 | // can be ignored since fAdoptedElements is false. |
---|
| 209 | if (fAdoptedElems) |
---|
| 210 | delete curElem->fData; |
---|
| 211 | |
---|
| 212 | // Then delete the current element and move forward |
---|
| 213 | // delete curElem; |
---|
| 214 | // destructor doesn't do anything... |
---|
| 215 | // curElem->~RefHashTableBucketElem(); |
---|
| 216 | fMemoryManager->deallocate(curElem); |
---|
| 217 | curElem = nextElem; |
---|
| 218 | } |
---|
| 219 | |
---|
| 220 | // Clean out this entry |
---|
| 221 | fBucketList[buckInd] = 0; |
---|
| 222 | } |
---|
| 223 | |
---|
| 224 | fCount = 0; |
---|
| 225 | } |
---|
| 226 | |
---|
| 227 | // This method returns the data associated with a key. The key entry is deleted. The caller |
---|
| 228 | // now owns the returned data (case of hashtable adopting the data). |
---|
| 229 | // This function is called by transferElement so that the undeleted data can be transferred |
---|
| 230 | // to a new key which will own that data. |
---|
| 231 | template <class TVal> TVal* RefHashTableOf<TVal>:: |
---|
| 232 | orphanKey(const void* const key) |
---|
| 233 | { |
---|
| 234 | // Hash the key |
---|
| 235 | TVal* retVal = 0; |
---|
| 236 | unsigned int hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager); |
---|
| 237 | assert(hashVal < fHashModulus); |
---|
| 238 | |
---|
| 239 | // |
---|
| 240 | // Search the given bucket for this key. Keep up with the previous |
---|
| 241 | // element so we can patch around it. |
---|
| 242 | // |
---|
| 243 | RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal]; |
---|
| 244 | RefHashTableBucketElem<TVal>* lastElem = 0; |
---|
| 245 | |
---|
| 246 | while (curElem) |
---|
| 247 | { |
---|
| 248 | if (fHash->equals(key, curElem->fKey)) |
---|
| 249 | { |
---|
| 250 | if (!lastElem) |
---|
| 251 | { |
---|
| 252 | // It was the first in the bucket |
---|
| 253 | fBucketList[hashVal] = curElem->fNext; |
---|
| 254 | } |
---|
| 255 | else |
---|
| 256 | { |
---|
| 257 | // Patch around the current element |
---|
| 258 | lastElem->fNext = curElem->fNext; |
---|
| 259 | } |
---|
| 260 | |
---|
| 261 | retVal = curElem->fData; |
---|
| 262 | |
---|
| 263 | // Delete the current element |
---|
| 264 | // delete curElem; |
---|
| 265 | // destructor doesn't do anything... |
---|
| 266 | // curElem->~RefHashTableBucketElem(); |
---|
| 267 | fMemoryManager->deallocate(curElem); |
---|
| 268 | break; |
---|
| 269 | } |
---|
| 270 | |
---|
| 271 | // Move both pointers upwards |
---|
| 272 | lastElem = curElem; |
---|
| 273 | curElem = curElem->fNext; |
---|
| 274 | } |
---|
| 275 | |
---|
| 276 | // We never found that key |
---|
| 277 | if (!retVal) |
---|
| 278 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager); |
---|
| 279 | |
---|
| 280 | return retVal; |
---|
| 281 | } |
---|
| 282 | |
---|
| 283 | // |
---|
| 284 | // cleanup(): |
---|
| 285 | // similar to destructor |
---|
| 286 | // called to cleanup the memory, in case destructor cannot be called |
---|
| 287 | // |
---|
| 288 | template <class TVal> void RefHashTableOf<TVal>::cleanup() |
---|
| 289 | { |
---|
| 290 | removeAll(); |
---|
| 291 | |
---|
| 292 | // Then delete the bucket list & hasher |
---|
| 293 | fMemoryManager->deallocate(fBucketList); //delete [] fBucketList; |
---|
| 294 | fBucketList = 0; |
---|
| 295 | delete fHash; |
---|
| 296 | } |
---|
| 297 | |
---|
| 298 | // |
---|
| 299 | // reinitialize(): |
---|
| 300 | // similar to constructor |
---|
| 301 | // called to re-construct the fElemList from scratch again |
---|
| 302 | // |
---|
| 303 | template <class TVal> void RefHashTableOf<TVal>::reinitialize(HashBase* hashBase) |
---|
| 304 | { |
---|
| 305 | if (fBucketList || fHash) |
---|
| 306 | cleanup(); |
---|
| 307 | |
---|
| 308 | fHashModulus = fInitialModulus; |
---|
| 309 | initialize(fHashModulus); |
---|
| 310 | |
---|
| 311 | if (hashBase) |
---|
| 312 | fHash = hashBase; |
---|
| 313 | else |
---|
| 314 | fHash = new (fMemoryManager) HashXMLCh(); // create default hasher |
---|
| 315 | } |
---|
| 316 | |
---|
| 317 | |
---|
| 318 | |
---|
| 319 | // this function transfer the data from key1 to key2 |
---|
| 320 | // this is equivalent to calling |
---|
| 321 | // 1. get(key1) to retrieve the data, |
---|
| 322 | // 2. removeKey(key1), |
---|
| 323 | // 3. and then put(key2, data) |
---|
| 324 | // except that the data is not deleted in "removeKey" even it is adopted so that it |
---|
| 325 | // can be transferred to key2. |
---|
| 326 | // whatever key2 has originally will be purged (if adopted) |
---|
| 327 | template <class TVal> void RefHashTableOf<TVal>::transferElement(const void* const key1, void* key2) |
---|
| 328 | { |
---|
| 329 | put(key2, orphanKey(key1)); |
---|
| 330 | } |
---|
| 331 | |
---|
| 332 | |
---|
| 333 | // --------------------------------------------------------------------------- |
---|
| 334 | // RefHashTableOf: Getters |
---|
| 335 | // --------------------------------------------------------------------------- |
---|
| 336 | template <class TVal> TVal* RefHashTableOf<TVal>::get(const void* const key) |
---|
| 337 | { |
---|
| 338 | unsigned int hashVal; |
---|
| 339 | RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal); |
---|
| 340 | if (!findIt) |
---|
| 341 | return 0; |
---|
| 342 | return findIt->fData; |
---|
| 343 | } |
---|
| 344 | |
---|
| 345 | template <class TVal> const TVal* RefHashTableOf<TVal>:: |
---|
| 346 | get(const void* const key) const |
---|
| 347 | { |
---|
| 348 | unsigned int hashVal; |
---|
| 349 | const RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal); |
---|
| 350 | if (!findIt) |
---|
| 351 | return 0; |
---|
| 352 | return findIt->fData; |
---|
| 353 | } |
---|
| 354 | |
---|
| 355 | template <class TVal> |
---|
| 356 | MemoryManager* RefHashTableOf<TVal>::getMemoryManager() const |
---|
| 357 | { |
---|
| 358 | return fMemoryManager; |
---|
| 359 | } |
---|
| 360 | |
---|
| 361 | template <class TVal> |
---|
| 362 | unsigned int RefHashTableOf<TVal>::getHashModulus() const |
---|
| 363 | { |
---|
| 364 | return fHashModulus; |
---|
| 365 | } |
---|
| 366 | |
---|
| 367 | template <class TVal> |
---|
| 368 | unsigned int RefHashTableOf<TVal>::getCount() const |
---|
| 369 | { |
---|
| 370 | return fCount; |
---|
| 371 | } |
---|
| 372 | |
---|
| 373 | // --------------------------------------------------------------------------- |
---|
| 374 | // RefHashTableOf: Getters |
---|
| 375 | // --------------------------------------------------------------------------- |
---|
| 376 | template <class TVal> |
---|
| 377 | void RefHashTableOf<TVal>::setAdoptElements(const bool aValue) |
---|
| 378 | { |
---|
| 379 | fAdoptedElems = aValue; |
---|
| 380 | } |
---|
| 381 | |
---|
| 382 | // --------------------------------------------------------------------------- |
---|
| 383 | // RefHashTableOf: Putters |
---|
| 384 | // --------------------------------------------------------------------------- |
---|
| 385 | template <class TVal> void RefHashTableOf<TVal>::put(void* key, TVal* const valueToAdopt) |
---|
| 386 | { |
---|
| 387 | // Apply 0.75 load factor to find threshold. |
---|
| 388 | unsigned int threshold = fHashModulus * 3 / 4; |
---|
| 389 | |
---|
| 390 | // If we've grown too big, expand the table and rehash. |
---|
| 391 | if (fCount >= threshold) |
---|
| 392 | rehash(); |
---|
| 393 | |
---|
| 394 | // First see if the key exists already |
---|
| 395 | unsigned int hashVal; |
---|
| 396 | RefHashTableBucketElem<TVal>* newBucket = findBucketElem(key, hashVal); |
---|
| 397 | |
---|
| 398 | // |
---|
| 399 | // If so,then update its value. If not, then we need to add it to |
---|
| 400 | // the right bucket |
---|
| 401 | // |
---|
| 402 | if (newBucket) |
---|
| 403 | { |
---|
| 404 | if (fAdoptedElems) |
---|
| 405 | delete newBucket->fData; |
---|
| 406 | newBucket->fData = valueToAdopt; |
---|
| 407 | newBucket->fKey = key; |
---|
| 408 | } |
---|
| 409 | else |
---|
| 410 | { |
---|
| 411 | //newBucket = new (fMemoryManager) RefHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]); |
---|
| 412 | newBucket = |
---|
| 413 | new (fMemoryManager->allocate(sizeof(RefHashTableBucketElem<TVal>))) |
---|
| 414 | RefHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]); |
---|
| 415 | fBucketList[hashVal] = newBucket; |
---|
| 416 | fCount++; |
---|
| 417 | } |
---|
| 418 | } |
---|
| 419 | |
---|
| 420 | |
---|
| 421 | |
---|
| 422 | // --------------------------------------------------------------------------- |
---|
| 423 | // RefHashTableOf: Private methods |
---|
| 424 | // --------------------------------------------------------------------------- |
---|
| 425 | template <class TVal> void RefHashTableOf<TVal>::rehash() |
---|
| 426 | { |
---|
| 427 | const unsigned int newMod = fHashModulus * 2; |
---|
| 428 | |
---|
| 429 | RefHashTableBucketElem<TVal>** newBucketList = |
---|
| 430 | (RefHashTableBucketElem<TVal>**) fMemoryManager->allocate |
---|
| 431 | ( |
---|
| 432 | newMod * sizeof(RefHashTableBucketElem<TVal>*) |
---|
| 433 | );//new RefHashTableBucketElem<TVal>*[newMod]; |
---|
| 434 | |
---|
| 435 | // Make sure the new bucket list is destroyed if an |
---|
| 436 | // exception is thrown. |
---|
| 437 | ArrayJanitor<RefHashTableBucketElem<TVal>*> guard(newBucketList, fMemoryManager); |
---|
| 438 | |
---|
| 439 | memset(newBucketList, 0, newMod * sizeof(newBucketList[0])); |
---|
| 440 | |
---|
| 441 | |
---|
| 442 | // Rehash all existing entries. |
---|
| 443 | for (unsigned int index = 0; index < fHashModulus; index++) |
---|
| 444 | { |
---|
| 445 | // Get the bucket list head for this entry |
---|
| 446 | RefHashTableBucketElem<TVal>* curElem = fBucketList[index]; |
---|
| 447 | |
---|
| 448 | while (curElem) |
---|
| 449 | { |
---|
| 450 | // Save the next element before we detach this one |
---|
| 451 | RefHashTableBucketElem<TVal>* const nextElem = curElem->fNext; |
---|
| 452 | |
---|
| 453 | const unsigned int hashVal = fHash->getHashVal(curElem->fKey, newMod, fMemoryManager); |
---|
| 454 | assert(hashVal < newMod); |
---|
| 455 | |
---|
| 456 | RefHashTableBucketElem<TVal>* const newHeadElem = newBucketList[hashVal]; |
---|
| 457 | |
---|
| 458 | // Insert at the start of this bucket's list. |
---|
| 459 | curElem->fNext = newHeadElem; |
---|
| 460 | newBucketList[hashVal] = curElem; |
---|
| 461 | |
---|
| 462 | curElem = nextElem; |
---|
| 463 | } |
---|
| 464 | } |
---|
| 465 | |
---|
| 466 | RefHashTableBucketElem<TVal>** const oldBucketList = fBucketList; |
---|
| 467 | |
---|
| 468 | // Everything is OK at this point, so update the |
---|
| 469 | // member variables. |
---|
| 470 | fBucketList = guard.release(); |
---|
| 471 | fHashModulus = newMod; |
---|
| 472 | |
---|
| 473 | // Delete the old bucket list. |
---|
| 474 | fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList; |
---|
| 475 | |
---|
| 476 | } |
---|
| 477 | |
---|
| 478 | template <class TVal> RefHashTableBucketElem<TVal>* RefHashTableOf<TVal>:: |
---|
| 479 | findBucketElem(const void* const key, unsigned int& hashVal) |
---|
| 480 | { |
---|
| 481 | // Hash the key |
---|
| 482 | hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager); |
---|
| 483 | assert(hashVal < fHashModulus); |
---|
| 484 | |
---|
| 485 | // Search that bucket for the key |
---|
| 486 | RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal]; |
---|
| 487 | while (curElem) |
---|
| 488 | { |
---|
| 489 | if (fHash->equals(key, curElem->fKey)) |
---|
| 490 | return curElem; |
---|
| 491 | |
---|
| 492 | curElem = curElem->fNext; |
---|
| 493 | } |
---|
| 494 | return 0; |
---|
| 495 | } |
---|
| 496 | |
---|
| 497 | template <class TVal> const RefHashTableBucketElem<TVal>* RefHashTableOf<TVal>:: |
---|
| 498 | findBucketElem(const void* const key, unsigned int& hashVal) const |
---|
| 499 | { |
---|
| 500 | // Hash the key |
---|
| 501 | hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager); |
---|
| 502 | assert(hashVal < fHashModulus); |
---|
| 503 | |
---|
| 504 | // Search that bucket for the key |
---|
| 505 | const RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal]; |
---|
| 506 | while (curElem) |
---|
| 507 | { |
---|
| 508 | if (fHash->equals(key, curElem->fKey)) |
---|
| 509 | return curElem; |
---|
| 510 | |
---|
| 511 | curElem = curElem->fNext; |
---|
| 512 | } |
---|
| 513 | return 0; |
---|
| 514 | } |
---|
| 515 | |
---|
| 516 | |
---|
| 517 | // --------------------------------------------------------------------------- |
---|
| 518 | // RefHashTableOfEnumerator: Constructors and Destructor |
---|
| 519 | // --------------------------------------------------------------------------- |
---|
| 520 | template <class TVal> RefHashTableOfEnumerator<TVal>:: |
---|
| 521 | RefHashTableOfEnumerator(RefHashTableOf<TVal>* const toEnum |
---|
| 522 | , const bool adopt |
---|
| 523 | , MemoryManager* const manager) |
---|
| 524 | : fAdopted(adopt), fCurElem(0), fCurHash((unsigned int)-1), fToEnum(toEnum) |
---|
| 525 | , fMemoryManager(manager) |
---|
| 526 | { |
---|
| 527 | if (!toEnum) |
---|
| 528 | ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager); |
---|
| 529 | |
---|
| 530 | // |
---|
| 531 | // Find the next available bucket element in the hash table. If it |
---|
| 532 | // comes back zero, that just means the table is empty. |
---|
| 533 | // |
---|
| 534 | // Note that the -1 in the current hash tells it to start from the |
---|
| 535 | // beginning. |
---|
| 536 | // |
---|
| 537 | findNext(); |
---|
| 538 | } |
---|
| 539 | |
---|
| 540 | template <class TVal> RefHashTableOfEnumerator<TVal>::~RefHashTableOfEnumerator() |
---|
| 541 | { |
---|
| 542 | if (fAdopted) |
---|
| 543 | delete fToEnum; |
---|
| 544 | } |
---|
| 545 | |
---|
| 546 | |
---|
| 547 | template <class TVal> RefHashTableOfEnumerator<TVal>:: |
---|
| 548 | RefHashTableOfEnumerator(const RefHashTableOfEnumerator<TVal>& toCopy) : |
---|
| 549 | XMLEnumerator<TVal>(toCopy) |
---|
| 550 | , XMemory(toCopy) |
---|
| 551 | , fAdopted(toCopy.fAdopted) |
---|
| 552 | , fCurElem(toCopy.fCurElem) |
---|
| 553 | , fCurHash(toCopy.fCurHash) |
---|
| 554 | , fToEnum(toCopy.fToEnum) |
---|
| 555 | , fMemoryManager(toCopy.fMemoryManager) |
---|
| 556 | { |
---|
| 557 | } |
---|
| 558 | // --------------------------------------------------------------------------- |
---|
| 559 | // RefHashTableOfEnumerator: Enum interface |
---|
| 560 | // --------------------------------------------------------------------------- |
---|
| 561 | template <class TVal> bool RefHashTableOfEnumerator<TVal>::hasMoreElements() const |
---|
| 562 | { |
---|
| 563 | // |
---|
| 564 | // If our current has is at the max and there are no more elements |
---|
| 565 | // in the current bucket, then no more elements. |
---|
| 566 | // |
---|
| 567 | if (!fCurElem && (fCurHash == fToEnum->fHashModulus)) |
---|
| 568 | return false; |
---|
| 569 | return true; |
---|
| 570 | } |
---|
| 571 | |
---|
| 572 | template <class TVal> TVal& RefHashTableOfEnumerator<TVal>::nextElement() |
---|
| 573 | { |
---|
| 574 | // Make sure we have an element to return |
---|
| 575 | if (!hasMoreElements()) |
---|
| 576 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager); |
---|
| 577 | |
---|
| 578 | // |
---|
| 579 | // Save the current element, then move up to the next one for the |
---|
| 580 | // next time around. |
---|
| 581 | // |
---|
| 582 | RefHashTableBucketElem<TVal>* saveElem = fCurElem; |
---|
| 583 | findNext(); |
---|
| 584 | |
---|
| 585 | return *saveElem->fData; |
---|
| 586 | } |
---|
| 587 | |
---|
| 588 | template <class TVal> void* RefHashTableOfEnumerator<TVal>::nextElementKey() |
---|
| 589 | { |
---|
| 590 | // Make sure we have an element to return |
---|
| 591 | if (!hasMoreElements()) |
---|
| 592 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager); |
---|
| 593 | |
---|
| 594 | // |
---|
| 595 | // Save the current element, then move up to the next one for the |
---|
| 596 | // next time around. |
---|
| 597 | // |
---|
| 598 | RefHashTableBucketElem<TVal>* saveElem = fCurElem; |
---|
| 599 | findNext(); |
---|
| 600 | |
---|
| 601 | return saveElem->fKey; |
---|
| 602 | } |
---|
| 603 | |
---|
| 604 | template <class TVal> void RefHashTableOfEnumerator<TVal>::Reset() |
---|
| 605 | { |
---|
| 606 | fCurHash = (unsigned int)-1; |
---|
| 607 | fCurElem = 0; |
---|
| 608 | findNext(); |
---|
| 609 | } |
---|
| 610 | |
---|
| 611 | |
---|
| 612 | |
---|
| 613 | // --------------------------------------------------------------------------- |
---|
| 614 | // RefHashTableOfEnumerator: Private helper methods |
---|
| 615 | // --------------------------------------------------------------------------- |
---|
| 616 | template <class TVal> void RefHashTableOfEnumerator<TVal>::findNext() |
---|
| 617 | { |
---|
| 618 | // |
---|
| 619 | // If there is a current element, move to its next element. If this |
---|
| 620 | // hits the end of the bucket, the next block will handle the rest. |
---|
| 621 | // |
---|
| 622 | if (fCurElem) |
---|
| 623 | fCurElem = fCurElem->fNext; |
---|
| 624 | |
---|
| 625 | // |
---|
| 626 | // If the current element is null, then we have to move up to the |
---|
| 627 | // next hash value. If that is the hash modulus, then we cannot |
---|
| 628 | // go further. |
---|
| 629 | // |
---|
| 630 | if (!fCurElem) |
---|
| 631 | { |
---|
| 632 | fCurHash++; |
---|
| 633 | if (fCurHash == fToEnum->fHashModulus) |
---|
| 634 | return; |
---|
| 635 | |
---|
| 636 | // Else find the next non-empty bucket |
---|
| 637 | while (fToEnum->fBucketList[fCurHash]==0) |
---|
| 638 | { |
---|
| 639 | // Bump to the next hash value. If we max out return |
---|
| 640 | fCurHash++; |
---|
| 641 | if (fCurHash == fToEnum->fHashModulus) |
---|
| 642 | return; |
---|
| 643 | } |
---|
| 644 | fCurElem = fToEnum->fBucketList[fCurHash]; |
---|
| 645 | } |
---|
| 646 | } |
---|
| 647 | |
---|
| 648 | XERCES_CPP_NAMESPACE_END |
---|