[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: NameIdPool.c 568078 2007-08-21 11:43:25Z amassari $ |
---|
| 20 | */ |
---|
| 21 | |
---|
| 22 | |
---|
| 23 | // --------------------------------------------------------------------------- |
---|
| 24 | // Includes |
---|
| 25 | // --------------------------------------------------------------------------- |
---|
| 26 | #if defined(XERCES_TMPLSINC) |
---|
| 27 | #include <xercesc/util/NameIdPool.hpp> |
---|
| 28 | #endif |
---|
| 29 | |
---|
| 30 | #include <xercesc/util/IllegalArgumentException.hpp> |
---|
| 31 | #include <xercesc/util/NoSuchElementException.hpp> |
---|
| 32 | #include <xercesc/util/RuntimeException.hpp> |
---|
| 33 | #include <new> |
---|
| 34 | #include <assert.h> |
---|
| 35 | |
---|
| 36 | XERCES_CPP_NAMESPACE_BEGIN |
---|
| 37 | |
---|
| 38 | // --------------------------------------------------------------------------- |
---|
| 39 | // NameIdPoolBucketElem: Constructors and Destructor |
---|
| 40 | // --------------------------------------------------------------------------- |
---|
| 41 | template <class TElem> NameIdPoolBucketElem<TElem>:: |
---|
| 42 | NameIdPoolBucketElem(TElem* const value |
---|
| 43 | , NameIdPoolBucketElem<TElem>* const next) : |
---|
| 44 | fData(value) |
---|
| 45 | , fNext(next) |
---|
| 46 | { |
---|
| 47 | } |
---|
| 48 | |
---|
| 49 | template <class TElem> NameIdPoolBucketElem<TElem>::~NameIdPoolBucketElem() |
---|
| 50 | { |
---|
| 51 | // Nothing to do |
---|
| 52 | } |
---|
| 53 | |
---|
| 54 | |
---|
| 55 | // --------------------------------------------------------------------------- |
---|
| 56 | // NameIdPool: Constructors and Destructor |
---|
| 57 | // --------------------------------------------------------------------------- |
---|
| 58 | template <class TElem> |
---|
| 59 | NameIdPool<TElem>::NameIdPool( const unsigned int hashModulus |
---|
| 60 | , const unsigned int initSize |
---|
| 61 | , MemoryManager* const manager) : |
---|
| 62 | fMemoryManager(manager) |
---|
| 63 | , fBucketList(0) |
---|
| 64 | , fIdPtrs(0) |
---|
| 65 | , fIdPtrsCount(initSize) |
---|
| 66 | , fIdCounter(0) |
---|
| 67 | , fHashModulus(hashModulus) |
---|
| 68 | { |
---|
| 69 | if (!fHashModulus) |
---|
| 70 | ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_ZeroModulus, fMemoryManager); |
---|
| 71 | |
---|
| 72 | // Allocate the bucket list and zero them |
---|
| 73 | fBucketList = (NameIdPoolBucketElem<TElem>**) fMemoryManager->allocate |
---|
| 74 | ( |
---|
| 75 | fHashModulus * sizeof(NameIdPoolBucketElem<TElem>*) |
---|
| 76 | ); //new NameIdPoolBucketElem<TElem>*[fHashModulus]; |
---|
| 77 | memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus); |
---|
| 78 | |
---|
| 79 | // |
---|
| 80 | // Allocate the initial id pointers array. We don't have to zero them |
---|
| 81 | // out since the fIdCounter value tells us which ones are valid. The |
---|
| 82 | // zeroth element is never used (and represents an invalid pool id.) |
---|
| 83 | // |
---|
| 84 | if (!fIdPtrsCount) |
---|
| 85 | fIdPtrsCount = 256; |
---|
| 86 | fIdPtrs = (TElem**) fMemoryManager->allocate |
---|
| 87 | ( |
---|
| 88 | fIdPtrsCount * sizeof(TElem*) |
---|
| 89 | ); //new TElem*[fIdPtrsCount]; |
---|
| 90 | fIdPtrs[0] = 0; |
---|
| 91 | } |
---|
| 92 | |
---|
| 93 | template <class TElem> NameIdPool<TElem>::~NameIdPool() |
---|
| 94 | { |
---|
| 95 | // |
---|
| 96 | // Delete the id pointers list. The stuff it points to will be cleaned |
---|
| 97 | // up when we clean the bucket lists. |
---|
| 98 | // |
---|
| 99 | fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs; |
---|
| 100 | |
---|
| 101 | // Remove all elements then delete the bucket list |
---|
| 102 | removeAll(); |
---|
| 103 | fMemoryManager->deallocate(fBucketList); //delete [] fBucketList; |
---|
| 104 | } |
---|
| 105 | |
---|
| 106 | |
---|
| 107 | // --------------------------------------------------------------------------- |
---|
| 108 | // NameIdPool: Element management |
---|
| 109 | // --------------------------------------------------------------------------- |
---|
| 110 | template <class TElem> bool |
---|
| 111 | NameIdPool<TElem>::containsKey(const XMLCh* const key) const |
---|
| 112 | { |
---|
| 113 | unsigned int hashVal; |
---|
| 114 | const NameIdPoolBucketElem<TElem>* findIt = findBucketElem(key, hashVal); |
---|
| 115 | return (findIt != 0); |
---|
| 116 | } |
---|
| 117 | |
---|
| 118 | |
---|
| 119 | template <class TElem> void NameIdPool<TElem>::removeAll() |
---|
| 120 | { |
---|
| 121 | if (fIdCounter == 0) return; |
---|
| 122 | |
---|
| 123 | // Clean up the buckets first |
---|
| 124 | for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++) |
---|
| 125 | { |
---|
| 126 | NameIdPoolBucketElem<TElem>* curElem = fBucketList[buckInd]; |
---|
| 127 | NameIdPoolBucketElem<TElem>* nextElem; |
---|
| 128 | while (curElem) |
---|
| 129 | { |
---|
| 130 | // Save the next element before we hose this one |
---|
| 131 | nextElem = curElem->fNext; |
---|
| 132 | |
---|
| 133 | delete curElem->fData; |
---|
| 134 | // destructor is empty... |
---|
| 135 | // curElem->~NameIdPoolBucketElem(); |
---|
| 136 | fMemoryManager->deallocate(curElem); |
---|
| 137 | |
---|
| 138 | curElem = nextElem; |
---|
| 139 | } |
---|
| 140 | |
---|
| 141 | // Empty out the bucket |
---|
| 142 | fBucketList[buckInd] = 0; |
---|
| 143 | } |
---|
| 144 | |
---|
| 145 | // Reset the id counter |
---|
| 146 | fIdCounter = 0; |
---|
| 147 | } |
---|
| 148 | |
---|
| 149 | |
---|
| 150 | // --------------------------------------------------------------------------- |
---|
| 151 | // NameIdPool: Getters |
---|
| 152 | // --------------------------------------------------------------------------- |
---|
| 153 | template <class TElem> TElem* |
---|
| 154 | NameIdPool<TElem>::getByKey(const XMLCh* const key) |
---|
| 155 | { |
---|
| 156 | unsigned int hashVal; |
---|
| 157 | NameIdPoolBucketElem<TElem>* findIt = findBucketElem(key, hashVal); |
---|
| 158 | if (!findIt) |
---|
| 159 | return 0; |
---|
| 160 | return findIt->fData; |
---|
| 161 | } |
---|
| 162 | |
---|
| 163 | template <class TElem> const TElem* |
---|
| 164 | NameIdPool<TElem>::getByKey(const XMLCh* const key) const |
---|
| 165 | { |
---|
| 166 | unsigned int hashVal; |
---|
| 167 | const NameIdPoolBucketElem<TElem>* findIt = findBucketElem(key, hashVal); |
---|
| 168 | if (!findIt) |
---|
| 169 | return 0; |
---|
| 170 | return findIt->fData; |
---|
| 171 | } |
---|
| 172 | |
---|
| 173 | template <class TElem> TElem* |
---|
| 174 | NameIdPool<TElem>::getById(const unsigned int elemId) |
---|
| 175 | { |
---|
| 176 | // If its either zero or beyond our current id, its an error |
---|
| 177 | if (!elemId || (elemId > fIdCounter)) |
---|
| 178 | ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager); |
---|
| 179 | |
---|
| 180 | return fIdPtrs[elemId]; |
---|
| 181 | } |
---|
| 182 | |
---|
| 183 | template <class TElem> |
---|
| 184 | const TElem* NameIdPool<TElem>::getById(const unsigned int elemId) const |
---|
| 185 | { |
---|
| 186 | // If its either zero or beyond our current id, its an error |
---|
| 187 | if (!elemId || (elemId > fIdCounter)) |
---|
| 188 | ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager); |
---|
| 189 | |
---|
| 190 | return fIdPtrs[elemId]; |
---|
| 191 | } |
---|
| 192 | |
---|
| 193 | template <class TElem> |
---|
| 194 | MemoryManager* NameIdPool<TElem>::getMemoryManager() const |
---|
| 195 | { |
---|
| 196 | return fMemoryManager; |
---|
| 197 | } |
---|
| 198 | |
---|
| 199 | // --------------------------------------------------------------------------- |
---|
| 200 | // NameIdPool: Setters |
---|
| 201 | // --------------------------------------------------------------------------- |
---|
| 202 | template <class TElem> |
---|
| 203 | unsigned int NameIdPool<TElem>::put(TElem* const elemToAdopt) |
---|
| 204 | { |
---|
| 205 | // First see if the key exists already. If so, its an error |
---|
| 206 | unsigned int hashVal; |
---|
| 207 | if (findBucketElem(elemToAdopt->getKey(), hashVal)) |
---|
| 208 | { |
---|
| 209 | ThrowXMLwithMemMgr1 |
---|
| 210 | ( |
---|
| 211 | IllegalArgumentException |
---|
| 212 | , XMLExcepts::Pool_ElemAlreadyExists |
---|
| 213 | , elemToAdopt->getKey() |
---|
| 214 | , fMemoryManager |
---|
| 215 | ); |
---|
| 216 | } |
---|
| 217 | |
---|
| 218 | // Create a new bucket element and add it to the appropriate list |
---|
| 219 | NameIdPoolBucketElem<TElem>* newBucket = |
---|
| 220 | new (fMemoryManager->allocate(sizeof(NameIdPoolBucketElem<TElem>))) |
---|
| 221 | NameIdPoolBucketElem<TElem>(elemToAdopt,fBucketList[hashVal]); |
---|
| 222 | fBucketList[hashVal] = newBucket; |
---|
| 223 | |
---|
| 224 | // |
---|
| 225 | // Give this new one the next available id and add to the pointer list. |
---|
| 226 | // Expand the list if that is now required. |
---|
| 227 | // |
---|
| 228 | if (fIdCounter + 1 == fIdPtrsCount) |
---|
| 229 | { |
---|
| 230 | // Create a new count 1.5 times larger and allocate a new array |
---|
| 231 | unsigned int newCount = (unsigned int)(fIdPtrsCount * 1.5); |
---|
| 232 | TElem** newArray = (TElem**) fMemoryManager->allocate |
---|
| 233 | ( |
---|
| 234 | newCount * sizeof(TElem*) |
---|
| 235 | ); //new TElem*[newCount]; |
---|
| 236 | |
---|
| 237 | // Copy over the old contents to the new array |
---|
| 238 | memcpy(newArray, fIdPtrs, fIdPtrsCount * sizeof(TElem*)); |
---|
| 239 | |
---|
| 240 | // Ok, toss the old array and store the new data |
---|
| 241 | fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs; |
---|
| 242 | fIdPtrs = newArray; |
---|
| 243 | fIdPtrsCount = newCount; |
---|
| 244 | } |
---|
| 245 | const unsigned int retId = ++fIdCounter; |
---|
| 246 | fIdPtrs[retId] = elemToAdopt; |
---|
| 247 | |
---|
| 248 | // Set the id on the passed element |
---|
| 249 | elemToAdopt->setId(retId); |
---|
| 250 | |
---|
| 251 | // Return the id that we gave to this element |
---|
| 252 | return retId; |
---|
| 253 | } |
---|
| 254 | |
---|
| 255 | |
---|
| 256 | // --------------------------------------------------------------------------- |
---|
| 257 | // NameIdPool: Private methods |
---|
| 258 | // --------------------------------------------------------------------------- |
---|
| 259 | template <class TElem> |
---|
| 260 | NameIdPoolBucketElem<TElem>* NameIdPool<TElem>:: |
---|
| 261 | findBucketElem(const XMLCh* const key, unsigned int& hashVal) |
---|
| 262 | { |
---|
| 263 | // Hash the key |
---|
| 264 | hashVal = XMLString::hash(key, fHashModulus, fMemoryManager); |
---|
| 265 | |
---|
| 266 | assert(hashVal < fHashModulus); |
---|
| 267 | |
---|
| 268 | // Search that bucket for the key |
---|
| 269 | NameIdPoolBucketElem<TElem>* curElem = fBucketList[hashVal]; |
---|
| 270 | while (curElem) |
---|
| 271 | { |
---|
| 272 | if (XMLString::equals(key, curElem->fData->getKey())) |
---|
| 273 | return curElem; |
---|
| 274 | curElem = curElem->fNext; |
---|
| 275 | } |
---|
| 276 | return 0; |
---|
| 277 | } |
---|
| 278 | |
---|
| 279 | template <class TElem> |
---|
| 280 | const NameIdPoolBucketElem<TElem>* NameIdPool<TElem>:: |
---|
| 281 | findBucketElem(const XMLCh* const key, unsigned int& hashVal) const |
---|
| 282 | { |
---|
| 283 | // Hash the key |
---|
| 284 | hashVal = XMLString::hash(key, fHashModulus, fMemoryManager); |
---|
| 285 | |
---|
| 286 | assert(hashVal < fHashModulus); |
---|
| 287 | |
---|
| 288 | // Search that bucket for the key |
---|
| 289 | const NameIdPoolBucketElem<TElem>* curElem = fBucketList[hashVal]; |
---|
| 290 | while (curElem) |
---|
| 291 | { |
---|
| 292 | if (XMLString::equals(key, curElem->fData->getKey())) |
---|
| 293 | return curElem; |
---|
| 294 | |
---|
| 295 | curElem = curElem->fNext; |
---|
| 296 | } |
---|
| 297 | return 0; |
---|
| 298 | } |
---|
| 299 | |
---|
| 300 | |
---|
| 301 | |
---|
| 302 | // --------------------------------------------------------------------------- |
---|
| 303 | // NameIdPoolEnumerator: Constructors and Destructor |
---|
| 304 | // --------------------------------------------------------------------------- |
---|
| 305 | template <class TElem> NameIdPoolEnumerator<TElem>:: |
---|
| 306 | NameIdPoolEnumerator(NameIdPool<TElem>* const toEnum |
---|
| 307 | , MemoryManager* const manager) : |
---|
| 308 | |
---|
| 309 | XMLEnumerator<TElem>() |
---|
| 310 | , fCurIndex(0) |
---|
| 311 | , fToEnum(toEnum) |
---|
| 312 | , fMemoryManager(manager) |
---|
| 313 | { |
---|
| 314 | Reset(); |
---|
| 315 | } |
---|
| 316 | |
---|
| 317 | template <class TElem> NameIdPoolEnumerator<TElem>:: |
---|
| 318 | NameIdPoolEnumerator(const NameIdPoolEnumerator<TElem>& toCopy) : |
---|
| 319 | XMLEnumerator<TElem>(toCopy) |
---|
| 320 | , XMemory(toCopy) |
---|
| 321 | , fCurIndex(toCopy.fCurIndex) |
---|
| 322 | , fToEnum(toCopy.fToEnum) |
---|
| 323 | , fMemoryManager(toCopy.fMemoryManager) |
---|
| 324 | { |
---|
| 325 | } |
---|
| 326 | |
---|
| 327 | template <class TElem> NameIdPoolEnumerator<TElem>::~NameIdPoolEnumerator() |
---|
| 328 | { |
---|
| 329 | // We don't own the pool being enumerated, so no cleanup required |
---|
| 330 | } |
---|
| 331 | |
---|
| 332 | |
---|
| 333 | // --------------------------------------------------------------------------- |
---|
| 334 | // NameIdPoolEnumerator: Public operators |
---|
| 335 | // --------------------------------------------------------------------------- |
---|
| 336 | template <class TElem> NameIdPoolEnumerator<TElem>& NameIdPoolEnumerator<TElem>:: |
---|
| 337 | operator=(const NameIdPoolEnumerator<TElem>& toAssign) |
---|
| 338 | { |
---|
| 339 | if (this == &toAssign) |
---|
| 340 | return *this; |
---|
| 341 | fMemoryManager = toAssign.fMemoryManager; |
---|
| 342 | fCurIndex = toAssign.fCurIndex; |
---|
| 343 | fToEnum = toAssign.fToEnum; |
---|
| 344 | return *this; |
---|
| 345 | } |
---|
| 346 | |
---|
| 347 | // --------------------------------------------------------------------------- |
---|
| 348 | // NameIdPoolEnumerator: Enum interface |
---|
| 349 | // --------------------------------------------------------------------------- |
---|
| 350 | template <class TElem> bool NameIdPoolEnumerator<TElem>:: |
---|
| 351 | hasMoreElements() const |
---|
| 352 | { |
---|
| 353 | // If our index is zero or past the end, then we are done |
---|
| 354 | if (!fCurIndex || (fCurIndex > fToEnum->fIdCounter)) |
---|
| 355 | return false; |
---|
| 356 | return true; |
---|
| 357 | } |
---|
| 358 | |
---|
| 359 | template <class TElem> TElem& NameIdPoolEnumerator<TElem>::nextElement() |
---|
| 360 | { |
---|
| 361 | // If our index is zero or past the end, then we are done |
---|
| 362 | if (!fCurIndex || (fCurIndex > fToEnum->fIdCounter)) |
---|
| 363 | ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager); |
---|
| 364 | |
---|
| 365 | // Return the current element and bump the index |
---|
| 366 | return *fToEnum->fIdPtrs[fCurIndex++]; |
---|
| 367 | } |
---|
| 368 | |
---|
| 369 | |
---|
| 370 | template <class TElem> void NameIdPoolEnumerator<TElem>::Reset() |
---|
| 371 | { |
---|
| 372 | // |
---|
| 373 | // Find the next available bucket element in the pool. We use the id |
---|
| 374 | // array since its very easy to enumerator through by just maintaining |
---|
| 375 | // an index. If the id counter is zero, then its empty and we leave the |
---|
| 376 | // current index to zero. |
---|
| 377 | // |
---|
| 378 | fCurIndex = fToEnum->fIdCounter ? 1:0; |
---|
| 379 | } |
---|
| 380 | |
---|
| 381 | template <class TElem> int NameIdPoolEnumerator<TElem>::size() const |
---|
| 382 | { |
---|
| 383 | return fToEnum->fIdCounter; |
---|
| 384 | } |
---|
| 385 | |
---|
| 386 | XERCES_CPP_NAMESPACE_END |
---|