[188] | 1 | /*
|
---|
| 2 | * The Apache Software License, Version 1.1
|
---|
| 3 | *
|
---|
| 4 | * Copyright (c) 1999-2000 The Apache Software Foundation. All rights
|
---|
| 5 | * reserved.
|
---|
| 6 | *
|
---|
| 7 | * Redistribution and use in source and binary forms, with or without
|
---|
| 8 | * modification, are permitted provided that the following conditions
|
---|
| 9 | * are met:
|
---|
| 10 | *
|
---|
| 11 | * 1. Redistributions of source code must retain the above copyright
|
---|
| 12 | * notice, this list of conditions and the following disclaimer.
|
---|
| 13 | *
|
---|
| 14 | * 2. Redistributions in binary form must reproduce the above copyright
|
---|
| 15 | * notice, this list of conditions and the following disclaimer in
|
---|
| 16 | * the documentation and/or other materials provided with the
|
---|
| 17 | * distribution.
|
---|
| 18 | *
|
---|
| 19 | * 3. The end-user documentation included with the redistribution,
|
---|
| 20 | * if any, must include the following acknowledgment:
|
---|
| 21 | * "This product includes software developed by the
|
---|
| 22 | * Apache Software Foundation (http://www.apache.org/)."
|
---|
| 23 | * Alternately, this acknowledgment may appear in the software itself,
|
---|
| 24 | * if and wherever such third-party acknowledgments normally appear.
|
---|
| 25 | *
|
---|
| 26 | * 4. The names "Xerces" and "Apache Software Foundation" must
|
---|
| 27 | * not be used to endorse or promote products derived from this
|
---|
| 28 | * software without prior written permission. For written
|
---|
| 29 | * permission, please contact apache\@apache.org.
|
---|
| 30 | *
|
---|
| 31 | * 5. Products derived from this software may not be called "Apache",
|
---|
| 32 | * nor may "Apache" appear in their name, without prior written
|
---|
| 33 | * permission of the Apache Software Foundation.
|
---|
| 34 | *
|
---|
| 35 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
|
---|
| 36 | * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
|
---|
| 37 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
|
---|
| 38 | * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
|
---|
| 39 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
|
---|
| 40 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
|
---|
| 41 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
|
---|
| 42 | * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
|
---|
| 43 | * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
|
---|
| 44 | * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
|
---|
| 45 | * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
---|
| 46 | * SUCH DAMAGE.
|
---|
| 47 | * ====================================================================
|
---|
| 48 | *
|
---|
| 49 | * This software consists of voluntary contributions made by many
|
---|
| 50 | * individuals on behalf of the Apache Software Foundation, and was
|
---|
| 51 | * originally based on software copyright (c) 1999, International
|
---|
| 52 | * Business Machines, Inc., http://www.ibm.com . For more information
|
---|
| 53 | * on the Apache Software Foundation, please see
|
---|
| 54 | * <http://www.apache.org/>.
|
---|
| 55 | */
|
---|
| 56 |
|
---|
| 57 | /**
|
---|
| 58 | * $Log: RefHashTableOf.c,v $
|
---|
| 59 | * Revision 1.13 2004/01/29 11:48:46 cargilld
|
---|
| 60 | * Code cleanup changes to get rid of various compiler diagnostic messages.
|
---|
| 61 | *
|
---|
| 62 | * Revision 1.12 2003/12/17 00:18:35 cargilld
|
---|
| 63 | * Update to memory management so that the static memory manager (one used to call Initialize) is only for static data.
|
---|
| 64 | *
|
---|
| 65 | * Revision 1.11 2003/08/20 11:51:39 gareth
|
---|
| 66 | * Reorderd initializer list to prevent compiler warning.
|
---|
| 67 | *
|
---|
| 68 | * Revision 1.10 2003/05/18 14:02:05 knoaman
|
---|
| 69 | * Memory manager implementation: pass per instance manager.
|
---|
| 70 | *
|
---|
| 71 | * Revision 1.9 2003/05/16 21:36:59 knoaman
|
---|
| 72 | * Memory manager implementation: Modify constructors to pass in the memory manager.
|
---|
| 73 | *
|
---|
| 74 | * Revision 1.8 2003/05/15 19:04:35 knoaman
|
---|
| 75 | * Partial implementation of the configurable memory manager.
|
---|
| 76 | *
|
---|
| 77 | * Revision 1.7 2003/05/15 10:37:08 gareth
|
---|
| 78 | * Optimization. We now resize the hash when appropriate. Patch by Nathan Codding.
|
---|
| 79 | *
|
---|
| 80 | * Revision 1.6 2002/11/04 15:22:04 tng
|
---|
| 81 | * C++ Namespace Support.
|
---|
| 82 | *
|
---|
| 83 | * Revision 1.5 2002/07/11 18:49:53 knoaman
|
---|
| 84 | * Add setAdoptElements method.
|
---|
| 85 | * Rename removeBucketElemSafe to orphanKey.
|
---|
| 86 | *
|
---|
| 87 | * Revision 1.4 2002/07/05 11:31:04 tng
|
---|
| 88 | * Fix typo.
|
---|
| 89 | *
|
---|
| 90 | * Revision 1.3 2002/07/04 15:24:57 tng
|
---|
| 91 | * DOM L3: add transferElement and removeBucketElemSafe for use in DOMDocument::renameNode.
|
---|
| 92 | *
|
---|
| 93 | * Revision 1.2 2002/06/12 17:14:03 tng
|
---|
| 94 | * Add function cleanup, reinitialize and nextElementKey for ease of use.
|
---|
| 95 | *
|
---|
| 96 | * Revision 1.1.1.1 2002/02/01 22:22:12 peiyongz
|
---|
| 97 | * sane_include
|
---|
| 98 | *
|
---|
| 99 | * Revision 1.9 2001/07/19 18:43:18 peiyongz
|
---|
| 100 | * fix: detect null poiniter in enumerator's ctor.
|
---|
| 101 | *
|
---|
| 102 | * Revision 1.8 2001/06/04 13:45:04 tng
|
---|
| 103 | * The "hash" argument clashes with STL hash. Fixed by Pei Yong Zhang.
|
---|
| 104 | *
|
---|
| 105 | * Revision 1.7 2000/09/06 00:24:16 andyh
|
---|
| 106 | * Clean up misc compiler warnings
|
---|
| 107 | *
|
---|
| 108 | * Revision 1.6 2000/07/07 22:16:50 jpolast
|
---|
| 109 | * remove old put(value) function. use put(key,value) instead.
|
---|
| 110 | *
|
---|
| 111 | * Revision 1.5 2000/06/29 18:27:09 jpolast
|
---|
| 112 | * bug fix for passing hasher class references to constructor
|
---|
| 113 | *
|
---|
| 114 | * Revision 1.4 2000/06/27 22:11:12 jpolast
|
---|
| 115 | * added more general functionality to hashtables.
|
---|
| 116 | * able to specify which hasher to use.
|
---|
| 117 | * default: HashXMLCh [hashes XMLCh* strings]
|
---|
| 118 | *
|
---|
| 119 | * future todo: make hasher class references static so only
|
---|
| 120 | * one instance of a hasher is ever created.
|
---|
| 121 | *
|
---|
| 122 | * Revision 1.3 2000/03/02 19:54:44 roddey
|
---|
| 123 | * This checkin includes many changes done while waiting for the
|
---|
| 124 | * 1.1.0 code to be finished. I can't list them all here, but a list is
|
---|
| 125 | * available elsewhere.
|
---|
| 126 | *
|
---|
| 127 | * Revision 1.2 2000/02/06 07:48:03 rahulj
|
---|
| 128 | * Year 2K copyright swat.
|
---|
| 129 | *
|
---|
| 130 | * Revision 1.1.1.1 1999/11/09 01:04:59 twl
|
---|
| 131 | * Initial checkin
|
---|
| 132 | *
|
---|
| 133 | * Revision 1.2 1999/11/08 20:45:12 rahul
|
---|
| 134 | * Swat for adding in Product name and CVS comment log variable.
|
---|
| 135 | *
|
---|
| 136 | */
|
---|
| 137 |
|
---|
| 138 |
|
---|
| 139 | // ---------------------------------------------------------------------------
|
---|
| 140 | // Include
|
---|
| 141 | // ---------------------------------------------------------------------------
|
---|
| 142 | #if defined(XERCES_TMPLSINC)
|
---|
| 143 | #include <xercesc/util/RefHashTableOf.hpp>
|
---|
| 144 | #endif
|
---|
| 145 |
|
---|
| 146 | #include <xercesc/util/NullPointerException.hpp>
|
---|
| 147 |
|
---|
| 148 | XERCES_CPP_NAMESPACE_BEGIN
|
---|
| 149 |
|
---|
| 150 | // ---------------------------------------------------------------------------
|
---|
| 151 | // RefHashTableOf: Constructors and Destructor
|
---|
| 152 | // ---------------------------------------------------------------------------
|
---|
| 153 | template <class TVal>
|
---|
| 154 | RefHashTableOf<TVal>::RefHashTableOf( const unsigned int modulus
|
---|
| 155 | , const bool adoptElems
|
---|
| 156 | , MemoryManager* const manager)
|
---|
| 157 |
|
---|
| 158 | : fMemoryManager(manager)
|
---|
| 159 | , fAdoptedElems(adoptElems)
|
---|
| 160 | , fBucketList(0)
|
---|
| 161 | , fHashModulus(modulus)
|
---|
| 162 | , fInitialModulus(modulus)
|
---|
| 163 | , fCount(0)
|
---|
| 164 | , fHash(0)
|
---|
| 165 |
|
---|
| 166 | {
|
---|
| 167 | initialize(modulus);
|
---|
| 168 |
|
---|
| 169 | // create default hasher
|
---|
| 170 | fHash = new (fMemoryManager) HashXMLCh();
|
---|
| 171 | }
|
---|
| 172 |
|
---|
| 173 | template <class TVal>
|
---|
| 174 | RefHashTableOf<TVal>::RefHashTableOf( const unsigned int modulus
|
---|
| 175 | , const bool adoptElems
|
---|
| 176 | , HashBase* hashBase
|
---|
| 177 | , MemoryManager* const manager)
|
---|
| 178 |
|
---|
| 179 | : fMemoryManager(manager)
|
---|
| 180 | , fAdoptedElems(adoptElems)
|
---|
| 181 | , fBucketList(0)
|
---|
| 182 | , fHashModulus(modulus)
|
---|
| 183 | , fInitialModulus(modulus)
|
---|
| 184 | , fCount(0)
|
---|
| 185 | , fHash(0)
|
---|
| 186 | {
|
---|
| 187 | initialize(modulus);
|
---|
| 188 | // set hasher
|
---|
| 189 | fHash = hashBase;
|
---|
| 190 | }
|
---|
| 191 |
|
---|
| 192 | template <class TVal>
|
---|
| 193 | RefHashTableOf<TVal>::RefHashTableOf(const unsigned int modulus
|
---|
| 194 | , MemoryManager* const manager)
|
---|
| 195 |
|
---|
| 196 | : fMemoryManager(manager)
|
---|
| 197 | , fAdoptedElems(true)
|
---|
| 198 | , fBucketList(0)
|
---|
| 199 | , fHashModulus(modulus)
|
---|
| 200 | , fInitialModulus(modulus)
|
---|
| 201 | , fCount(0)
|
---|
| 202 | , fHash(0)
|
---|
| 203 | {
|
---|
| 204 | initialize(modulus);
|
---|
| 205 |
|
---|
| 206 | // create default hasher
|
---|
| 207 | fHash = new (fMemoryManager) HashXMLCh();
|
---|
| 208 | }
|
---|
| 209 |
|
---|
| 210 | template <class TVal> void RefHashTableOf<TVal>::initialize(const unsigned int modulus)
|
---|
| 211 | {
|
---|
| 212 | if (modulus == 0)
|
---|
| 213 | ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
|
---|
| 214 |
|
---|
| 215 | // Allocate the bucket list and zero them
|
---|
| 216 | fBucketList = (RefHashTableBucketElem<TVal>**) fMemoryManager->allocate
|
---|
| 217 | (
|
---|
| 218 | fHashModulus * sizeof(RefHashTableBucketElem<TVal>*)
|
---|
| 219 | ); //new RefHashTableBucketElem<TVal>*[fHashModulus];
|
---|
| 220 | for (unsigned int index = 0; index < fHashModulus; index++)
|
---|
| 221 | fBucketList[index] = 0;
|
---|
| 222 | }
|
---|
| 223 |
|
---|
| 224 | template <class TVal> RefHashTableOf<TVal>::~RefHashTableOf()
|
---|
| 225 | {
|
---|
| 226 | removeAll();
|
---|
| 227 |
|
---|
| 228 | // Then delete the bucket list & hasher
|
---|
| 229 | fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
|
---|
| 230 | delete fHash;
|
---|
| 231 | }
|
---|
| 232 |
|
---|
| 233 |
|
---|
| 234 | // ---------------------------------------------------------------------------
|
---|
| 235 | // RefHashTableOf: Element management
|
---|
| 236 | // ---------------------------------------------------------------------------
|
---|
| 237 | template <class TVal> bool RefHashTableOf<TVal>::isEmpty() const
|
---|
| 238 | {
|
---|
| 239 | // Just check the bucket list for non-empty elements
|
---|
| 240 | for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++)
|
---|
| 241 | {
|
---|
| 242 | if (fBucketList[buckInd] != 0)
|
---|
| 243 | return false;
|
---|
| 244 | }
|
---|
| 245 | return true;
|
---|
| 246 | }
|
---|
| 247 |
|
---|
| 248 | template <class TVal> bool RefHashTableOf<TVal>::
|
---|
| 249 | containsKey(const void* const key) const
|
---|
| 250 | {
|
---|
| 251 | unsigned int hashVal;
|
---|
| 252 | const RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
|
---|
| 253 | return (findIt != 0);
|
---|
| 254 | }
|
---|
| 255 |
|
---|
| 256 | template <class TVal> void RefHashTableOf<TVal>::
|
---|
| 257 | removeKey(const void* const key)
|
---|
| 258 | {
|
---|
| 259 | unsigned int hashVal;
|
---|
| 260 | removeBucketElem(key, hashVal);
|
---|
| 261 | }
|
---|
| 262 |
|
---|
| 263 | template <class TVal> void RefHashTableOf<TVal>::removeAll()
|
---|
| 264 | {
|
---|
| 265 | // Clean up the buckets first
|
---|
| 266 | for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++)
|
---|
| 267 | {
|
---|
| 268 | // Get the bucket list head for this entry
|
---|
| 269 | RefHashTableBucketElem<TVal>* curElem = fBucketList[buckInd];
|
---|
| 270 | RefHashTableBucketElem<TVal>* nextElem;
|
---|
| 271 | while (curElem)
|
---|
| 272 | {
|
---|
| 273 | // Save the next element before we hose this one
|
---|
| 274 | nextElem = curElem->fNext;
|
---|
| 275 |
|
---|
| 276 | // If we adopted the data, then delete it too
|
---|
| 277 | // (Note: the userdata hash table instance has data type of void *.
|
---|
| 278 | // This will generate compiler warnings here on some platforms, but they
|
---|
| 279 | // can be ignored since fAdoptedElements is false.
|
---|
| 280 | if (fAdoptedElems)
|
---|
| 281 | delete curElem->fData;
|
---|
| 282 |
|
---|
| 283 | // Then delete the current element and move forward
|
---|
| 284 | delete curElem;
|
---|
| 285 | curElem = nextElem;
|
---|
| 286 | }
|
---|
| 287 |
|
---|
| 288 | // Clean out this entry
|
---|
| 289 | fBucketList[buckInd] = 0;
|
---|
| 290 | }
|
---|
| 291 |
|
---|
| 292 | fCount = 0;
|
---|
| 293 | }
|
---|
| 294 |
|
---|
| 295 | // This method returns the data associated with a key. The key entry is deleted. The caller
|
---|
| 296 | // now owns the returned data (case of hashtable adopting the data).
|
---|
| 297 | // This function is called by transferElement so that the undeleted data can be transferred
|
---|
| 298 | // to a new key which will own that data.
|
---|
| 299 | template <class TVal> TVal* RefHashTableOf<TVal>::
|
---|
| 300 | orphanKey(const void* const key)
|
---|
| 301 | {
|
---|
| 302 | // Hash the key
|
---|
| 303 | TVal* retVal = 0;
|
---|
| 304 | unsigned int hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager);
|
---|
| 305 | if (hashVal > fHashModulus)
|
---|
| 306 | ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey, fMemoryManager);
|
---|
| 307 |
|
---|
| 308 | //
|
---|
| 309 | // Search the given bucket for this key. Keep up with the previous
|
---|
| 310 | // element so we can patch around it.
|
---|
| 311 | //
|
---|
| 312 | RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
|
---|
| 313 | RefHashTableBucketElem<TVal>* lastElem = 0;
|
---|
| 314 |
|
---|
| 315 | while (curElem)
|
---|
| 316 | {
|
---|
| 317 | if (fHash->equals(key, curElem->fKey))
|
---|
| 318 | {
|
---|
| 319 | if (!lastElem)
|
---|
| 320 | {
|
---|
| 321 | // It was the first in the bucket
|
---|
| 322 | fBucketList[hashVal] = curElem->fNext;
|
---|
| 323 | }
|
---|
| 324 | else
|
---|
| 325 | {
|
---|
| 326 | // Patch around the current element
|
---|
| 327 | lastElem->fNext = curElem->fNext;
|
---|
| 328 | }
|
---|
| 329 |
|
---|
| 330 | retVal = curElem->fData;
|
---|
| 331 |
|
---|
| 332 | // Delete the current element
|
---|
| 333 | delete curElem;
|
---|
| 334 | break;
|
---|
| 335 | }
|
---|
| 336 |
|
---|
| 337 | // Move both pointers upwards
|
---|
| 338 | lastElem = curElem;
|
---|
| 339 | curElem = curElem->fNext;
|
---|
| 340 | }
|
---|
| 341 |
|
---|
| 342 | // We never found that key
|
---|
| 343 | if (!retVal)
|
---|
| 344 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
|
---|
| 345 |
|
---|
| 346 | return retVal;
|
---|
| 347 | }
|
---|
| 348 |
|
---|
| 349 | //
|
---|
| 350 | // cleanup():
|
---|
| 351 | // similar to destructor
|
---|
| 352 | // called to cleanup the memory, in case destructor cannot be called
|
---|
| 353 | //
|
---|
| 354 | template <class TElem> void RefHashTableOf<TElem>::cleanup()
|
---|
| 355 | {
|
---|
| 356 | removeAll();
|
---|
| 357 |
|
---|
| 358 | // Then delete the bucket list & hasher
|
---|
| 359 | fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
|
---|
| 360 | fBucketList = 0;
|
---|
| 361 | delete fHash;
|
---|
| 362 | }
|
---|
| 363 |
|
---|
| 364 | //
|
---|
| 365 | // reinitialize():
|
---|
| 366 | // similar to constructor
|
---|
| 367 | // called to re-construct the fElemList from scratch again
|
---|
| 368 | //
|
---|
| 369 | template <class TElem> void RefHashTableOf<TElem>::reinitialize(HashBase* hashBase)
|
---|
| 370 | {
|
---|
| 371 | if (fBucketList || fHash)
|
---|
| 372 | cleanup();
|
---|
| 373 |
|
---|
| 374 | fHashModulus = fInitialModulus;
|
---|
| 375 | initialize(fHashModulus);
|
---|
| 376 |
|
---|
| 377 | if (hashBase)
|
---|
| 378 | fHash = hashBase;
|
---|
| 379 | else
|
---|
| 380 | fHash = new (fMemoryManager) HashXMLCh(); // create default hasher
|
---|
| 381 | }
|
---|
| 382 |
|
---|
| 383 |
|
---|
| 384 |
|
---|
| 385 | // this function transfer the data from key1 to key2
|
---|
| 386 | // this is equivalent to calling
|
---|
| 387 | // 1. get(key1) to retrieve the data,
|
---|
| 388 | // 2. removeKey(key1),
|
---|
| 389 | // 3. and then put(key2, data)
|
---|
| 390 | // except that the data is not deleted in "removeKey" even it is adopted so that it
|
---|
| 391 | // can be transferred to key2.
|
---|
| 392 | // whatever key2 has originally will be purged (if adopted)
|
---|
| 393 | template <class TElem> void RefHashTableOf<TElem>::transferElement(const void* const key1, void* key2)
|
---|
| 394 | {
|
---|
| 395 | put(key2, orphanKey(key1));
|
---|
| 396 | }
|
---|
| 397 |
|
---|
| 398 |
|
---|
| 399 | // ---------------------------------------------------------------------------
|
---|
| 400 | // RefHashTableOf: Getters
|
---|
| 401 | // ---------------------------------------------------------------------------
|
---|
| 402 | template <class TVal> TVal* RefHashTableOf<TVal>::get(const void* const key)
|
---|
| 403 | {
|
---|
| 404 | unsigned int hashVal;
|
---|
| 405 | RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
|
---|
| 406 | if (!findIt)
|
---|
| 407 | return 0;
|
---|
| 408 | return findIt->fData;
|
---|
| 409 | }
|
---|
| 410 |
|
---|
| 411 | template <class TVal> const TVal* RefHashTableOf<TVal>::
|
---|
| 412 | get(const void* const key) const
|
---|
| 413 | {
|
---|
| 414 | unsigned int hashVal;
|
---|
| 415 | const RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
|
---|
| 416 | if (!findIt)
|
---|
| 417 | return 0;
|
---|
| 418 | return findIt->fData;
|
---|
| 419 | }
|
---|
| 420 |
|
---|
| 421 | template <class TVal>
|
---|
| 422 | MemoryManager* RefHashTableOf<TVal>::getMemoryManager() const
|
---|
| 423 | {
|
---|
| 424 | return fMemoryManager;
|
---|
| 425 | }
|
---|
| 426 |
|
---|
| 427 |
|
---|
| 428 | // ---------------------------------------------------------------------------
|
---|
| 429 | // RefHashTableOf: Getters
|
---|
| 430 | // ---------------------------------------------------------------------------
|
---|
| 431 | template <class TVal>
|
---|
| 432 | void RefHashTableOf<TVal>::setAdoptElements(const bool aValue)
|
---|
| 433 | {
|
---|
| 434 | fAdoptedElems = aValue;
|
---|
| 435 | }
|
---|
| 436 |
|
---|
| 437 | // ---------------------------------------------------------------------------
|
---|
| 438 | // RefHashTableOf: Putters
|
---|
| 439 | // ---------------------------------------------------------------------------
|
---|
| 440 | template <class TVal> void RefHashTableOf<TVal>::put(void* key, TVal* const valueToAdopt)
|
---|
| 441 | {
|
---|
| 442 | // Apply 0.75 load factor to find threshold.
|
---|
| 443 | unsigned int threshold = fHashModulus * 3 / 4;
|
---|
| 444 |
|
---|
| 445 | // If we've grown too big, expand the table and rehash.
|
---|
| 446 | if (fCount >= threshold)
|
---|
| 447 | rehash();
|
---|
| 448 |
|
---|
| 449 | // First see if the key exists already
|
---|
| 450 | unsigned int hashVal;
|
---|
| 451 | RefHashTableBucketElem<TVal>* newBucket = findBucketElem(key, hashVal);
|
---|
| 452 |
|
---|
| 453 | //
|
---|
| 454 | // If so,then update its value. If not, then we need to add it to
|
---|
| 455 | // the right bucket
|
---|
| 456 | //
|
---|
| 457 | if (newBucket)
|
---|
| 458 | {
|
---|
| 459 | if (fAdoptedElems)
|
---|
| 460 | delete newBucket->fData;
|
---|
| 461 | newBucket->fData = valueToAdopt;
|
---|
| 462 | newBucket->fKey = key;
|
---|
| 463 | }
|
---|
| 464 | else
|
---|
| 465 | {
|
---|
| 466 | newBucket = new (fMemoryManager) RefHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]);
|
---|
| 467 | fBucketList[hashVal] = newBucket;
|
---|
| 468 | }
|
---|
| 469 |
|
---|
| 470 | fCount++;
|
---|
| 471 | }
|
---|
| 472 |
|
---|
| 473 |
|
---|
| 474 |
|
---|
| 475 | // ---------------------------------------------------------------------------
|
---|
| 476 | // RefHashTableOf: Private methods
|
---|
| 477 | // ---------------------------------------------------------------------------
|
---|
| 478 | template <class TVal> void RefHashTableOf<TVal>::rehash()
|
---|
| 479 | {
|
---|
| 480 | unsigned int index;
|
---|
| 481 | unsigned int oldMod = fHashModulus;
|
---|
| 482 | fHashModulus *= 2;
|
---|
| 483 |
|
---|
| 484 | RefHashTableBucketElem<TVal>** oldBucketList = fBucketList;
|
---|
| 485 |
|
---|
| 486 | fBucketList = (RefHashTableBucketElem<TVal>**) fMemoryManager->allocate
|
---|
| 487 | (
|
---|
| 488 | fHashModulus * sizeof(RefHashTableBucketElem<TVal>*)
|
---|
| 489 | );//new RefHashTableBucketElem<TVal>*[fHashModulus];
|
---|
| 490 | for (index = 0; index < fHashModulus; index++)
|
---|
| 491 | fBucketList[index] = 0;
|
---|
| 492 |
|
---|
| 493 |
|
---|
| 494 | // Rehash all existing entries.
|
---|
| 495 | for (index = 0; index < oldMod; index++)
|
---|
| 496 | {
|
---|
| 497 | // Get the bucket list head for this entry
|
---|
| 498 | RefHashTableBucketElem<TVal>* curElem = oldBucketList[index];
|
---|
| 499 | RefHashTableBucketElem<TVal>* nextElem;
|
---|
| 500 | while (curElem)
|
---|
| 501 | {
|
---|
| 502 | // Save the next element before we detach this one
|
---|
| 503 | nextElem = curElem->fNext;
|
---|
| 504 |
|
---|
| 505 | unsigned int hashVal = fHash->getHashVal(curElem->fKey, fHashModulus, fMemoryManager);
|
---|
| 506 | if (hashVal > fHashModulus)
|
---|
| 507 | ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey, fMemoryManager);
|
---|
| 508 |
|
---|
| 509 | RefHashTableBucketElem<TVal>* newHeadElem = fBucketList[hashVal];
|
---|
| 510 |
|
---|
| 511 | // Insert at the start of this bucket's list.
|
---|
| 512 | curElem->fNext = newHeadElem;
|
---|
| 513 | fBucketList[hashVal] = curElem;
|
---|
| 514 |
|
---|
| 515 | curElem = nextElem;
|
---|
| 516 | }
|
---|
| 517 | }
|
---|
| 518 |
|
---|
| 519 | fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList;
|
---|
| 520 |
|
---|
| 521 | }
|
---|
| 522 |
|
---|
| 523 | template <class TVal> RefHashTableBucketElem<TVal>* RefHashTableOf<TVal>::
|
---|
| 524 | findBucketElem(const void* const key, unsigned int& hashVal)
|
---|
| 525 | {
|
---|
| 526 | // Hash the key
|
---|
| 527 | hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager);
|
---|
| 528 | if (hashVal > fHashModulus)
|
---|
| 529 | ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey, fMemoryManager);
|
---|
| 530 |
|
---|
| 531 | // Search that bucket for the key
|
---|
| 532 | RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
|
---|
| 533 | while (curElem)
|
---|
| 534 | {
|
---|
| 535 | if (fHash->equals(key, curElem->fKey))
|
---|
| 536 | return curElem;
|
---|
| 537 |
|
---|
| 538 | curElem = curElem->fNext;
|
---|
| 539 | }
|
---|
| 540 | return 0;
|
---|
| 541 | }
|
---|
| 542 |
|
---|
| 543 | template <class TVal> const RefHashTableBucketElem<TVal>* RefHashTableOf<TVal>::
|
---|
| 544 | findBucketElem(const void* const key, unsigned int& hashVal) const
|
---|
| 545 | {
|
---|
| 546 | // Hash the key
|
---|
| 547 | hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager);
|
---|
| 548 | if (hashVal > fHashModulus)
|
---|
| 549 | ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey, fMemoryManager);
|
---|
| 550 |
|
---|
| 551 | // Search that bucket for the key
|
---|
| 552 | const RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
|
---|
| 553 | while (curElem)
|
---|
| 554 | {
|
---|
| 555 | if (fHash->equals(key, curElem->fKey))
|
---|
| 556 | return curElem;
|
---|
| 557 |
|
---|
| 558 | curElem = curElem->fNext;
|
---|
| 559 | }
|
---|
| 560 | return 0;
|
---|
| 561 | }
|
---|
| 562 |
|
---|
| 563 |
|
---|
| 564 | template <class TVal> void RefHashTableOf<TVal>::
|
---|
| 565 | removeBucketElem(const void* const key, unsigned int& hashVal)
|
---|
| 566 | {
|
---|
| 567 | // Hash the key
|
---|
| 568 | hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager);
|
---|
| 569 | if (hashVal > fHashModulus)
|
---|
| 570 | ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey, fMemoryManager);
|
---|
| 571 |
|
---|
| 572 | //
|
---|
| 573 | // Search the given bucket for this key. Keep up with the previous
|
---|
| 574 | // element so we can patch around it.
|
---|
| 575 | //
|
---|
| 576 | RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
|
---|
| 577 | RefHashTableBucketElem<TVal>* lastElem = 0;
|
---|
| 578 |
|
---|
| 579 | while (curElem)
|
---|
| 580 | {
|
---|
| 581 | if (fHash->equals(key, curElem->fKey))
|
---|
| 582 | {
|
---|
| 583 | if (!lastElem)
|
---|
| 584 | {
|
---|
| 585 | // It was the first in the bucket
|
---|
| 586 | fBucketList[hashVal] = curElem->fNext;
|
---|
| 587 | }
|
---|
| 588 | else
|
---|
| 589 | {
|
---|
| 590 | // Patch around the current element
|
---|
| 591 | lastElem->fNext = curElem->fNext;
|
---|
| 592 | }
|
---|
| 593 |
|
---|
| 594 | // If we adopted the elements, then delete the data
|
---|
| 595 | if (fAdoptedElems)
|
---|
| 596 | delete curElem->fData;
|
---|
| 597 |
|
---|
| 598 | // Delete the current element
|
---|
| 599 | delete curElem;
|
---|
| 600 |
|
---|
| 601 | fCount--;
|
---|
| 602 |
|
---|
| 603 | return;
|
---|
| 604 | }
|
---|
| 605 |
|
---|
| 606 | // Move both pointers upwards
|
---|
| 607 | lastElem = curElem;
|
---|
| 608 | curElem = curElem->fNext;
|
---|
| 609 | }
|
---|
| 610 |
|
---|
| 611 | // We never found that key
|
---|
| 612 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
|
---|
| 613 | }
|
---|
| 614 |
|
---|
| 615 |
|
---|
| 616 |
|
---|
| 617 | // ---------------------------------------------------------------------------
|
---|
| 618 | // RefHashTableOfEnumerator: Constructors and Destructor
|
---|
| 619 | // ---------------------------------------------------------------------------
|
---|
| 620 | template <class TVal> RefHashTableOfEnumerator<TVal>::
|
---|
| 621 | RefHashTableOfEnumerator(RefHashTableOf<TVal>* const toEnum
|
---|
| 622 | , const bool adopt
|
---|
| 623 | , MemoryManager* const manager)
|
---|
| 624 | : fAdopted(adopt), fCurElem(0), fCurHash((unsigned int)-1), fToEnum(toEnum)
|
---|
| 625 | , fMemoryManager(manager)
|
---|
| 626 | {
|
---|
| 627 | if (!toEnum)
|
---|
| 628 | ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager);
|
---|
| 629 |
|
---|
| 630 | //
|
---|
| 631 | // Find the next available bucket element in the hash table. If it
|
---|
| 632 | // comes back zero, that just means the table is empty.
|
---|
| 633 | //
|
---|
| 634 | // Note that the -1 in the current hash tells it to start from the
|
---|
| 635 | // beginning.
|
---|
| 636 | //
|
---|
| 637 | findNext();
|
---|
| 638 | }
|
---|
| 639 |
|
---|
| 640 | template <class TVal> RefHashTableOfEnumerator<TVal>::~RefHashTableOfEnumerator()
|
---|
| 641 | {
|
---|
| 642 | if (fAdopted)
|
---|
| 643 | delete fToEnum;
|
---|
| 644 | }
|
---|
| 645 |
|
---|
| 646 |
|
---|
| 647 | template <class TVal> RefHashTableOfEnumerator<TVal>::
|
---|
| 648 | RefHashTableOfEnumerator(const RefHashTableOfEnumerator<TVal>& toCopy) :
|
---|
| 649 | fAdopted(toCopy.fAdopted)
|
---|
| 650 | , fCurElem(toCopy.fCurElem)
|
---|
| 651 | , fCurHash(toCopy.fCurHash)
|
---|
| 652 | , fToEnum(toCopy.fToEnum)
|
---|
| 653 | , fMemoryManager(toCopy.fMemoryManager)
|
---|
| 654 | {
|
---|
| 655 | }
|
---|
| 656 | // ---------------------------------------------------------------------------
|
---|
| 657 | // RefHashTableOfEnumerator: Enum interface
|
---|
| 658 | // ---------------------------------------------------------------------------
|
---|
| 659 | template <class TVal> bool RefHashTableOfEnumerator<TVal>::hasMoreElements() const
|
---|
| 660 | {
|
---|
| 661 | //
|
---|
| 662 | // If our current has is at the max and there are no more elements
|
---|
| 663 | // in the current bucket, then no more elements.
|
---|
| 664 | //
|
---|
| 665 | if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
|
---|
| 666 | return false;
|
---|
| 667 | return true;
|
---|
| 668 | }
|
---|
| 669 |
|
---|
| 670 | template <class TVal> TVal& RefHashTableOfEnumerator<TVal>::nextElement()
|
---|
| 671 | {
|
---|
| 672 | // Make sure we have an element to return
|
---|
| 673 | if (!hasMoreElements())
|
---|
| 674 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
|
---|
| 675 |
|
---|
| 676 | //
|
---|
| 677 | // Save the current element, then move up to the next one for the
|
---|
| 678 | // next time around.
|
---|
| 679 | //
|
---|
| 680 | RefHashTableBucketElem<TVal>* saveElem = fCurElem;
|
---|
| 681 | findNext();
|
---|
| 682 |
|
---|
| 683 | return *saveElem->fData;
|
---|
| 684 | }
|
---|
| 685 |
|
---|
| 686 | template <class TVal> void* RefHashTableOfEnumerator<TVal>::nextElementKey()
|
---|
| 687 | {
|
---|
| 688 | // Make sure we have an element to return
|
---|
| 689 | if (!hasMoreElements())
|
---|
| 690 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
|
---|
| 691 |
|
---|
| 692 | //
|
---|
| 693 | // Save the current element, then move up to the next one for the
|
---|
| 694 | // next time around.
|
---|
| 695 | //
|
---|
| 696 | RefHashTableBucketElem<TVal>* saveElem = fCurElem;
|
---|
| 697 | findNext();
|
---|
| 698 |
|
---|
| 699 | return saveElem->fKey;
|
---|
| 700 | }
|
---|
| 701 |
|
---|
| 702 | template <class TVal> void RefHashTableOfEnumerator<TVal>::Reset()
|
---|
| 703 | {
|
---|
| 704 | fCurHash = (unsigned int)-1;
|
---|
| 705 | fCurElem = 0;
|
---|
| 706 | findNext();
|
---|
| 707 | }
|
---|
| 708 |
|
---|
| 709 |
|
---|
| 710 |
|
---|
| 711 | // ---------------------------------------------------------------------------
|
---|
| 712 | // RefHashTableOfEnumerator: Private helper methods
|
---|
| 713 | // ---------------------------------------------------------------------------
|
---|
| 714 | template <class TVal> void RefHashTableOfEnumerator<TVal>::findNext()
|
---|
| 715 | {
|
---|
| 716 | //
|
---|
| 717 | // If there is a current element, move to its next element. If this
|
---|
| 718 | // hits the end of the bucket, the next block will handle the rest.
|
---|
| 719 | //
|
---|
| 720 | if (fCurElem)
|
---|
| 721 | fCurElem = fCurElem->fNext;
|
---|
| 722 |
|
---|
| 723 | //
|
---|
| 724 | // If the current element is null, then we have to move up to the
|
---|
| 725 | // next hash value. If that is the hash modulus, then we cannot
|
---|
| 726 | // go further.
|
---|
| 727 | //
|
---|
| 728 | if (!fCurElem)
|
---|
| 729 | {
|
---|
| 730 | fCurHash++;
|
---|
| 731 | if (fCurHash == fToEnum->fHashModulus)
|
---|
| 732 | return;
|
---|
| 733 |
|
---|
| 734 | // Else find the next non-empty bucket
|
---|
| 735 | while (true)
|
---|
| 736 | {
|
---|
| 737 | if (fToEnum->fBucketList[fCurHash])
|
---|
| 738 | break;
|
---|
| 739 |
|
---|
| 740 | // Bump to the next hash value. If we max out return
|
---|
| 741 | fCurHash++;
|
---|
| 742 | if (fCurHash == fToEnum->fHashModulus)
|
---|
| 743 | return;
|
---|
| 744 | }
|
---|
| 745 | fCurElem = fToEnum->fBucketList[fCurHash];
|
---|
| 746 | }
|
---|
| 747 | }
|
---|
| 748 |
|
---|
| 749 | XERCES_CPP_NAMESPACE_END
|
---|