[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: ValueHashTableOf.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/ValueHashTableOf.hpp> |
---|
| 28 | #endif |
---|
| 29 | |
---|
| 30 | #include <xercesc/util/NullPointerException.hpp> |
---|
| 31 | #include <assert.h> |
---|
| 32 | #include <new> |
---|
| 33 | |
---|
| 34 | XERCES_CPP_NAMESPACE_BEGIN |
---|
| 35 | |
---|
| 36 | // --------------------------------------------------------------------------- |
---|
| 37 | // ValueHashTableOf: Constructors and Destructor |
---|
| 38 | // --------------------------------------------------------------------------- |
---|
| 39 | template <class TVal> |
---|
| 40 | ValueHashTableOf<TVal>::ValueHashTableOf( const unsigned int modulus |
---|
| 41 | , HashBase* hashBase |
---|
| 42 | , MemoryManager* const manager) |
---|
| 43 | : fMemoryManager(manager) |
---|
| 44 | , fBucketList(0) |
---|
| 45 | , fHashModulus(modulus) |
---|
| 46 | , fHash(0) |
---|
| 47 | { |
---|
| 48 | initialize(modulus); |
---|
| 49 | // set hasher |
---|
| 50 | fHash = hashBase; |
---|
| 51 | } |
---|
| 52 | |
---|
| 53 | template <class TVal> |
---|
| 54 | ValueHashTableOf<TVal>::ValueHashTableOf( const unsigned int modulus |
---|
| 55 | , MemoryManager* const manager) |
---|
| 56 | : fMemoryManager(manager) |
---|
| 57 | , fBucketList(0) |
---|
| 58 | , fHashModulus(modulus) |
---|
| 59 | , fHash(0) |
---|
| 60 | { |
---|
| 61 | initialize(modulus); |
---|
| 62 | |
---|
| 63 | // create default hasher |
---|
| 64 | fHash = new (fMemoryManager) HashXMLCh(); |
---|
| 65 | } |
---|
| 66 | |
---|
| 67 | template <class TVal> void ValueHashTableOf<TVal>::initialize(const unsigned int modulus) |
---|
| 68 | { |
---|
| 69 | if (modulus == 0) |
---|
| 70 | ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager); |
---|
| 71 | |
---|
| 72 | // Allocate the bucket list and zero them |
---|
| 73 | fBucketList = (ValueHashTableBucketElem<TVal>**) fMemoryManager->allocate |
---|
| 74 | ( |
---|
| 75 | fHashModulus * sizeof(ValueHashTableBucketElem<TVal>*) |
---|
| 76 | ); //new ValueHashTableBucketElem<TVal>*[fHashModulus]; |
---|
| 77 | memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus); |
---|
| 78 | } |
---|
| 79 | |
---|
| 80 | template <class TVal> ValueHashTableOf<TVal>::~ValueHashTableOf() |
---|
| 81 | { |
---|
| 82 | removeAll(); |
---|
| 83 | |
---|
| 84 | // Then delete the bucket list & hasher |
---|
| 85 | fMemoryManager->deallocate(fBucketList); //delete [] fBucketList; |
---|
| 86 | delete fHash; |
---|
| 87 | } |
---|
| 88 | |
---|
| 89 | |
---|
| 90 | // --------------------------------------------------------------------------- |
---|
| 91 | // ValueHashTableOf: Element management |
---|
| 92 | // --------------------------------------------------------------------------- |
---|
| 93 | template <class TVal> bool ValueHashTableOf<TVal>::isEmpty() const |
---|
| 94 | { |
---|
| 95 | // Just check the bucket list for non-empty elements |
---|
| 96 | for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++) |
---|
| 97 | { |
---|
| 98 | if (fBucketList[buckInd] != 0) |
---|
| 99 | return false; |
---|
| 100 | } |
---|
| 101 | return true; |
---|
| 102 | } |
---|
| 103 | |
---|
| 104 | template <class TVal> bool ValueHashTableOf<TVal>:: |
---|
| 105 | containsKey(const void* const key) const |
---|
| 106 | { |
---|
| 107 | unsigned int hashVal; |
---|
| 108 | const ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal); |
---|
| 109 | return (findIt != 0); |
---|
| 110 | } |
---|
| 111 | |
---|
| 112 | template <class TVal> void ValueHashTableOf<TVal>:: |
---|
| 113 | removeKey(const void* const key) |
---|
| 114 | { |
---|
| 115 | unsigned int hashVal; |
---|
| 116 | removeBucketElem(key, hashVal); |
---|
| 117 | } |
---|
| 118 | |
---|
| 119 | template <class TVal> void ValueHashTableOf<TVal>::removeAll() |
---|
| 120 | { |
---|
| 121 | // Clean up the buckets first |
---|
| 122 | for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++) |
---|
| 123 | { |
---|
| 124 | // Get the bucket list head for this entry |
---|
| 125 | ValueHashTableBucketElem<TVal>* curElem = fBucketList[buckInd]; |
---|
| 126 | ValueHashTableBucketElem<TVal>* nextElem; |
---|
| 127 | while (curElem) |
---|
| 128 | { |
---|
| 129 | // Save the next element before we hose this one |
---|
| 130 | nextElem = curElem->fNext; |
---|
| 131 | |
---|
| 132 | // delete the current element and move forward |
---|
| 133 | // destructor is empty... |
---|
| 134 | // curElem->~ValueHashTableBucketElem(); |
---|
| 135 | fMemoryManager->deallocate(curElem); |
---|
| 136 | curElem = nextElem; |
---|
| 137 | } |
---|
| 138 | |
---|
| 139 | // Clean out this entry |
---|
| 140 | fBucketList[buckInd] = 0; |
---|
| 141 | } |
---|
| 142 | } |
---|
| 143 | |
---|
| 144 | |
---|
| 145 | // --------------------------------------------------------------------------- |
---|
| 146 | // ValueHashTableOf: Getters |
---|
| 147 | // --------------------------------------------------------------------------- |
---|
| 148 | template <class TVal> TVal& ValueHashTableOf<TVal>::get(const void* const key, MemoryManager* const manager) |
---|
| 149 | { |
---|
| 150 | unsigned int hashVal; |
---|
| 151 | ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal); |
---|
| 152 | if (!findIt) |
---|
| 153 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, manager); |
---|
| 154 | |
---|
| 155 | return findIt->fData; |
---|
| 156 | } |
---|
| 157 | |
---|
| 158 | template <class TVal> const TVal& ValueHashTableOf<TVal>:: |
---|
| 159 | get(const void* const key) const |
---|
| 160 | { |
---|
| 161 | unsigned int hashVal; |
---|
| 162 | const ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal); |
---|
| 163 | if (!findIt) |
---|
| 164 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager); |
---|
| 165 | |
---|
| 166 | return findIt->fData; |
---|
| 167 | } |
---|
| 168 | |
---|
| 169 | |
---|
| 170 | // --------------------------------------------------------------------------- |
---|
| 171 | // ValueHashTableOf: Putters |
---|
| 172 | // --------------------------------------------------------------------------- |
---|
| 173 | template <class TVal> void ValueHashTableOf<TVal>::put(void* key, const TVal& valueToAdopt) |
---|
| 174 | { |
---|
| 175 | // First see if the key exists already |
---|
| 176 | unsigned int hashVal; |
---|
| 177 | ValueHashTableBucketElem<TVal>* newBucket = findBucketElem(key, hashVal); |
---|
| 178 | |
---|
| 179 | // |
---|
| 180 | // If so,then update its value. If not, then we need to add it to |
---|
| 181 | // the right bucket |
---|
| 182 | // |
---|
| 183 | if (newBucket) |
---|
| 184 | { |
---|
| 185 | newBucket->fData = valueToAdopt; |
---|
| 186 | newBucket->fKey = key; |
---|
| 187 | } |
---|
| 188 | else |
---|
| 189 | { |
---|
| 190 | newBucket = |
---|
| 191 | new (fMemoryManager->allocate(sizeof(ValueHashTableBucketElem<TVal>))) |
---|
| 192 | ValueHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]); |
---|
| 193 | fBucketList[hashVal] = newBucket; |
---|
| 194 | } |
---|
| 195 | } |
---|
| 196 | |
---|
| 197 | |
---|
| 198 | |
---|
| 199 | // --------------------------------------------------------------------------- |
---|
| 200 | // ValueHashTableOf: Private methods |
---|
| 201 | // --------------------------------------------------------------------------- |
---|
| 202 | template <class TVal> ValueHashTableBucketElem<TVal>* ValueHashTableOf<TVal>:: |
---|
| 203 | findBucketElem(const void* const key, unsigned int& hashVal) |
---|
| 204 | { |
---|
| 205 | // Hash the key |
---|
| 206 | hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager); |
---|
| 207 | assert(hashVal < fHashModulus); |
---|
| 208 | |
---|
| 209 | // Search that bucket for the key |
---|
| 210 | ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal]; |
---|
| 211 | while (curElem) |
---|
| 212 | { |
---|
| 213 | if (fHash->equals(key, curElem->fKey)) |
---|
| 214 | return curElem; |
---|
| 215 | |
---|
| 216 | curElem = curElem->fNext; |
---|
| 217 | } |
---|
| 218 | return 0; |
---|
| 219 | } |
---|
| 220 | |
---|
| 221 | template <class TVal> const ValueHashTableBucketElem<TVal>* ValueHashTableOf<TVal>:: |
---|
| 222 | findBucketElem(const void* const key, unsigned int& hashVal) const |
---|
| 223 | { |
---|
| 224 | // Hash the key |
---|
| 225 | hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager); |
---|
| 226 | assert(hashVal < fHashModulus); |
---|
| 227 | |
---|
| 228 | // Search that bucket for the key |
---|
| 229 | const ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal]; |
---|
| 230 | while (curElem) |
---|
| 231 | { |
---|
| 232 | if (fHash->equals(key, curElem->fKey)) |
---|
| 233 | return curElem; |
---|
| 234 | |
---|
| 235 | curElem = curElem->fNext; |
---|
| 236 | } |
---|
| 237 | return 0; |
---|
| 238 | } |
---|
| 239 | |
---|
| 240 | |
---|
| 241 | template <class TVal> void ValueHashTableOf<TVal>:: |
---|
| 242 | removeBucketElem(const void* const key, unsigned int& hashVal) |
---|
| 243 | { |
---|
| 244 | // Hash the key |
---|
| 245 | hashVal = fHash->getHashVal(key, fHashModulus); |
---|
| 246 | assert(hashVal < fHashModulus); |
---|
| 247 | |
---|
| 248 | // |
---|
| 249 | // Search the given bucket for this key. Keep up with the previous |
---|
| 250 | // element so we can patch around it. |
---|
| 251 | // |
---|
| 252 | ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal]; |
---|
| 253 | ValueHashTableBucketElem<TVal>* lastElem = 0; |
---|
| 254 | |
---|
| 255 | while (curElem) |
---|
| 256 | { |
---|
| 257 | if (fHash->equals(key, curElem->fKey)) |
---|
| 258 | { |
---|
| 259 | if (!lastElem) |
---|
| 260 | { |
---|
| 261 | // It was the first in the bucket |
---|
| 262 | fBucketList[hashVal] = curElem->fNext; |
---|
| 263 | } |
---|
| 264 | else |
---|
| 265 | { |
---|
| 266 | // Patch around the current element |
---|
| 267 | lastElem->fNext = curElem->fNext; |
---|
| 268 | } |
---|
| 269 | |
---|
| 270 | // Delete the current element |
---|
| 271 | // delete curElem; |
---|
| 272 | // destructor is empty... |
---|
| 273 | // curElem->~ValueHashTableBucketElem(); |
---|
| 274 | fMemoryManager->deallocate(curElem); |
---|
| 275 | |
---|
| 276 | return; |
---|
| 277 | } |
---|
| 278 | |
---|
| 279 | // Move both pointers upwards |
---|
| 280 | lastElem = curElem; |
---|
| 281 | curElem = curElem->fNext; |
---|
| 282 | } |
---|
| 283 | |
---|
| 284 | // We never found that key |
---|
| 285 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager); |
---|
| 286 | } |
---|
| 287 | |
---|
| 288 | |
---|
| 289 | |
---|
| 290 | |
---|
| 291 | // --------------------------------------------------------------------------- |
---|
| 292 | // ValueHashTableOfEnumerator: Constructors and Destructor |
---|
| 293 | // --------------------------------------------------------------------------- |
---|
| 294 | template <class TVal> ValueHashTableOfEnumerator<TVal>:: |
---|
| 295 | ValueHashTableOfEnumerator(ValueHashTableOf<TVal>* const toEnum |
---|
| 296 | , const bool adopt |
---|
| 297 | , MemoryManager* const manager) |
---|
| 298 | : fAdopted(adopt), fCurElem(0), fCurHash((unsigned int)-1), fToEnum(toEnum), fMemoryManager(manager) |
---|
| 299 | { |
---|
| 300 | if (!toEnum) |
---|
| 301 | ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, manager); |
---|
| 302 | |
---|
| 303 | // |
---|
| 304 | // Find the next available bucket element in the hash table. If it |
---|
| 305 | // comes back zero, that just means the table is empty. |
---|
| 306 | // |
---|
| 307 | // Note that the -1 in the current hash tells it to start from the |
---|
| 308 | // beginning. |
---|
| 309 | // |
---|
| 310 | findNext(); |
---|
| 311 | } |
---|
| 312 | |
---|
| 313 | template <class TVal> ValueHashTableOfEnumerator<TVal>::~ValueHashTableOfEnumerator() |
---|
| 314 | { |
---|
| 315 | if (fAdopted) |
---|
| 316 | delete fToEnum; |
---|
| 317 | } |
---|
| 318 | |
---|
| 319 | |
---|
| 320 | // --------------------------------------------------------------------------- |
---|
| 321 | // ValueHashTableOfEnumerator: Enum interface |
---|
| 322 | // --------------------------------------------------------------------------- |
---|
| 323 | template <class TVal> bool ValueHashTableOfEnumerator<TVal>::hasMoreElements() const |
---|
| 324 | { |
---|
| 325 | // |
---|
| 326 | // If our current has is at the max and there are no more elements |
---|
| 327 | // in the current bucket, then no more elements. |
---|
| 328 | // |
---|
| 329 | if (!fCurElem && (fCurHash == fToEnum->fHashModulus)) |
---|
| 330 | return false; |
---|
| 331 | return true; |
---|
| 332 | } |
---|
| 333 | |
---|
| 334 | template <class TVal> TVal& ValueHashTableOfEnumerator<TVal>::nextElement() |
---|
| 335 | { |
---|
| 336 | // Make sure we have an element to return |
---|
| 337 | if (!hasMoreElements()) |
---|
| 338 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager); |
---|
| 339 | |
---|
| 340 | // |
---|
| 341 | // Save the current element, then move up to the next one for the |
---|
| 342 | // next time around. |
---|
| 343 | // |
---|
| 344 | ValueHashTableBucketElem<TVal>* saveElem = fCurElem; |
---|
| 345 | findNext(); |
---|
| 346 | |
---|
| 347 | return saveElem->fData; |
---|
| 348 | } |
---|
| 349 | |
---|
| 350 | template <class TVal> void* ValueHashTableOfEnumerator<TVal>::nextElementKey() |
---|
| 351 | { |
---|
| 352 | // Make sure we have an element to return |
---|
| 353 | if (!hasMoreElements()) |
---|
| 354 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager); |
---|
| 355 | |
---|
| 356 | // |
---|
| 357 | // Save the current element, then move up to the next one for the |
---|
| 358 | // next time around. |
---|
| 359 | // |
---|
| 360 | ValueHashTableBucketElem<TVal>* saveElem = fCurElem; |
---|
| 361 | findNext(); |
---|
| 362 | |
---|
| 363 | return saveElem->fKey; |
---|
| 364 | } |
---|
| 365 | |
---|
| 366 | |
---|
| 367 | template <class TVal> void ValueHashTableOfEnumerator<TVal>::Reset() |
---|
| 368 | { |
---|
| 369 | fCurHash = (unsigned int)-1; |
---|
| 370 | fCurElem = 0; |
---|
| 371 | findNext(); |
---|
| 372 | } |
---|
| 373 | |
---|
| 374 | |
---|
| 375 | |
---|
| 376 | // --------------------------------------------------------------------------- |
---|
| 377 | // ValueHashTableOfEnumerator: Private helper methods |
---|
| 378 | // --------------------------------------------------------------------------- |
---|
| 379 | template <class TVal> void ValueHashTableOfEnumerator<TVal>::findNext() |
---|
| 380 | { |
---|
| 381 | // |
---|
| 382 | // If there is a current element, move to its next element. If this |
---|
| 383 | // hits the end of the bucket, the next block will handle the rest. |
---|
| 384 | // |
---|
| 385 | if (fCurElem) |
---|
| 386 | fCurElem = fCurElem->fNext; |
---|
| 387 | |
---|
| 388 | // |
---|
| 389 | // If the current element is null, then we have to move up to the |
---|
| 390 | // next hash value. If that is the hash modulus, then we cannot |
---|
| 391 | // go further. |
---|
| 392 | // |
---|
| 393 | if (!fCurElem) |
---|
| 394 | { |
---|
| 395 | fCurHash++; |
---|
| 396 | if (fCurHash == fToEnum->fHashModulus) |
---|
| 397 | return; |
---|
| 398 | |
---|
| 399 | // Else find the next non-empty bucket |
---|
| 400 | while (fToEnum->fBucketList[fCurHash]==0) |
---|
| 401 | { |
---|
| 402 | // Bump to the next hash value. If we max out return |
---|
| 403 | fCurHash++; |
---|
| 404 | if (fCurHash == fToEnum->fHashModulus) |
---|
| 405 | return; |
---|
| 406 | } |
---|
| 407 | fCurElem = fToEnum->fBucketList[fCurHash]; |
---|
| 408 | } |
---|
| 409 | } |
---|
| 410 | |
---|
| 411 | XERCES_CPP_NAMESPACE_END |
---|