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$
20 */
21
22
23 // ---------------------------------------------------------------------------
24 // Include
25 // ---------------------------------------------------------------------------
26 #if defined(XERCES_TMPLSINC)
27 #include <xercesc/util/Hash2KeysSetOf.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 // Hash2KeysSetOf: Constructors and Destructor
39 // ---------------------------------------------------------------------------
40
41 template <class THasher>
Hash2KeysSetOf(const XMLSize_t modulus,MemoryManager * const manager)42 Hash2KeysSetOf<THasher>::Hash2KeysSetOf(
43 const XMLSize_t modulus,
44 MemoryManager* const manager)
45
46 : fMemoryManager(manager)
47 , fBucketList(0)
48 , fHashModulus(modulus)
49 , fCount(0)
50 , fAvailable(0)
51 {
52 initialize(modulus);
53 }
54
55 template <class THasher>
Hash2KeysSetOf(const XMLSize_t modulus,const THasher & hasher,MemoryManager * const manager)56 Hash2KeysSetOf<THasher>::Hash2KeysSetOf(
57 const XMLSize_t modulus,
58 const THasher& hasher,
59 MemoryManager* const manager)
60
61 : fMemoryManager(manager)
62 , fBucketList(0)
63 , fHashModulus(modulus)
64 , fCount(0)
65 , fAvailable(0)
66 , fHasher (hasher)
67 {
68 initialize(modulus);
69 }
70
71 template <class THasher>
initialize(const XMLSize_t modulus)72 void Hash2KeysSetOf<THasher>::initialize(const XMLSize_t modulus)
73 {
74 if (modulus == 0)
75 ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
76
77 // Allocate the bucket list and zero them
78 fBucketList = (Hash2KeysSetBucketElem**) fMemoryManager->allocate
79 (
80 fHashModulus * sizeof(Hash2KeysSetBucketElem*)
81 ); //new Hash2KeysSetBucketElem*[fHashModulus];
82 memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus);
83 }
84
85 template <class THasher>
~Hash2KeysSetOf()86 Hash2KeysSetOf<THasher>::~Hash2KeysSetOf()
87 {
88 Hash2KeysSetBucketElem* nextElem;
89 if(!isEmpty())
90 {
91 // Clean up the buckets first
92 for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
93 {
94 // Get the bucket list head for this entry
95 Hash2KeysSetBucketElem* curElem = fBucketList[buckInd];
96 while (curElem)
97 {
98 // Save the next element before we hose this one
99 nextElem = curElem->fNext;
100 fMemoryManager->deallocate(curElem);
101 curElem = nextElem;
102 }
103
104 // Clean out this entry
105 fBucketList[buckInd] = 0;
106 }
107 }
108 // Then delete the list of available blocks
109 Hash2KeysSetBucketElem* curElem = fAvailable;
110 while (curElem)
111 {
112 // Save the next element before we hose this one
113 nextElem = curElem->fNext;
114 fMemoryManager->deallocate(curElem);
115 curElem = nextElem;
116 }
117 fAvailable = 0;
118
119 // Then delete the bucket list & hasher
120 fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
121 fBucketList = 0;
122 }
123
124
125 // ---------------------------------------------------------------------------
126 // Hash2KeysSetOf: Element management
127 // ---------------------------------------------------------------------------
128 template <class THasher>
isEmpty()129 bool Hash2KeysSetOf<THasher>::isEmpty() const
130 {
131 return (fCount==0);
132 }
133
134 template <class THasher>
containsKey(const void * const key1,const int key2)135 bool Hash2KeysSetOf<THasher>::containsKey(const void* const key1, const int key2) const
136 {
137 XMLSize_t hashVal;
138 const Hash2KeysSetBucketElem* findIt = findBucketElem(key1, key2, hashVal);
139 return (findIt != 0);
140 }
141
142 template <class THasher>
removeKey(const void * const key1,const int key2)143 void Hash2KeysSetOf<THasher>::removeKey(const void* const key1, const int key2)
144 {
145 // Hash the key
146 XMLSize_t hashVal = fHasher.getHashVal(key1, fHashModulus);
147 assert(hashVal < fHashModulus);
148
149 //
150 // Search the given bucket for this key. Keep up with the previous
151 // element so we can patch around it.
152 //
153 Hash2KeysSetBucketElem* curElem = fBucketList[hashVal];
154 Hash2KeysSetBucketElem* lastElem = 0;
155
156 while (curElem)
157 {
158 if((key2==curElem->fKey2) && (fHasher.equals(key1, curElem->fKey1)))
159 {
160 if (!lastElem)
161 {
162 // It was the first in the bucket
163 fBucketList[hashVal] = curElem->fNext;
164 }
165 else
166 {
167 // Patch around the current element
168 lastElem->fNext = curElem->fNext;
169 }
170
171 // Move the current element to the list of available blocks
172 curElem->fNext=fAvailable;
173 fAvailable=curElem;
174
175 fCount--;
176 return;
177 }
178
179 // Move both pointers upwards
180 lastElem = curElem;
181 curElem = curElem->fNext;
182 }
183
184 // We never found that key
185 ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
186 }
187
188 template <class THasher>
189 void Hash2KeysSetOf<THasher>::
removeKey(const void * const key1)190 removeKey(const void* const key1)
191 {
192 // Hash the key
193 XMLSize_t hashVal = fHasher.getHashVal(key1, fHashModulus);
194 assert(hashVal < fHashModulus);
195
196 //
197 // Search the given bucket for this key. Keep up with the previous
198 // element so we can patch around it.
199 //
200 Hash2KeysSetBucketElem* curElem = fBucketList[hashVal];
201 Hash2KeysSetBucketElem* lastElem = 0;
202
203 while (curElem)
204 {
205 if(fHasher.equals(key1, curElem->fKey1))
206 {
207 if (!lastElem)
208 {
209 // It was the first in the bucket
210 fBucketList[hashVal] = curElem->fNext;
211 }
212 else
213 {
214 // Patch around the current element
215 lastElem->fNext = curElem->fNext;
216 }
217
218 Hash2KeysSetBucketElem* toBeDeleted=curElem;
219 curElem = curElem->fNext;
220
221 // Move the current element to the list of available blocks
222 toBeDeleted->fNext=fAvailable;
223 fAvailable=toBeDeleted;
224
225 fCount--;
226 }
227 else
228 {
229 // Move both pointers upwards
230 lastElem = curElem;
231 curElem = curElem->fNext;
232 }
233 }
234 }
235
236 template <class THasher>
removeAll()237 void Hash2KeysSetOf<THasher>::removeAll()
238 {
239 if(isEmpty())
240 return;
241
242 for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
243 {
244 if(fBucketList[buckInd]!=0)
245 {
246 // Advance to the end of the chain, and connect it to the list of
247 // available blocks
248 Hash2KeysSetBucketElem* curElem = fBucketList[buckInd];
249 while (curElem->fNext)
250 curElem = curElem->fNext;
251 curElem->fNext=fAvailable;
252 fAvailable=fBucketList[buckInd];
253 fBucketList[buckInd] = 0;
254 }
255 }
256 fCount=0;
257 }
258
259 // ---------------------------------------------------------------------------
260 // Hash2KeysSetOf: Getters
261 // ---------------------------------------------------------------------------
262 template <class THasher>
getMemoryManager()263 MemoryManager* Hash2KeysSetOf<THasher>::getMemoryManager() const
264 {
265 return fMemoryManager;
266 }
267
268 template <class THasher>
getHashModulus()269 XMLSize_t Hash2KeysSetOf<THasher>::getHashModulus() const
270 {
271 return fHashModulus;
272 }
273
274 // ---------------------------------------------------------------------------
275 // Hash2KeysSetOf: Putters
276 // ---------------------------------------------------------------------------
277 template <class THasher>
put(const void * key1,int key2)278 void Hash2KeysSetOf<THasher>::put(const void* key1, int key2)
279 {
280 // Apply 4 load factor to find threshold.
281 XMLSize_t threshold = fHashModulus * 4;
282
283 // If we've grown too big, expand the table and rehash.
284 if (fCount >= threshold)
285 rehash();
286
287 // First see if the key exists already
288 XMLSize_t hashVal;
289 Hash2KeysSetBucketElem* newBucket = findBucketElem(key1, key2, hashVal);
290
291 //
292 // If so,then update its value. If not, then we need to add it to
293 // the right bucket
294 //
295 if (newBucket)
296 {
297 newBucket->fKey1 = key1;
298 newBucket->fKey2 = key2;
299 }
300 else
301 {
302 if(fAvailable==0)
303 newBucket = (Hash2KeysSetBucketElem*)fMemoryManager->allocate(sizeof(Hash2KeysSetBucketElem));
304 else
305 {
306 newBucket = fAvailable;
307 fAvailable = fAvailable->fNext;
308 }
309 newBucket->fKey1 = key1;
310 newBucket->fKey2 = key2;
311 newBucket->fNext = fBucketList[hashVal];
312 fBucketList[hashVal] = newBucket;
313 fCount++;
314 }
315 }
316
317 template <class THasher>
putIfNotPresent(const void * key1,int key2)318 bool Hash2KeysSetOf<THasher>::putIfNotPresent(const void* key1, int key2)
319 {
320 // First see if the key exists already
321 XMLSize_t hashVal;
322 Hash2KeysSetBucketElem* newBucket = findBucketElem(key1, key2, hashVal);
323
324 //
325 // If so,then update its value. If not, then we need to add it to
326 // the right bucket
327 //
328 if (newBucket)
329 return false;
330
331 // Apply 4 load factor to find threshold.
332 XMLSize_t threshold = fHashModulus * 4;
333
334 // If we've grown too big, expand the table and rehash.
335 if (fCount >= threshold)
336 rehash();
337
338 if(fAvailable==0)
339 newBucket = (Hash2KeysSetBucketElem*)fMemoryManager->allocate(sizeof(Hash2KeysSetBucketElem));
340 else
341 {
342 newBucket = fAvailable;
343 fAvailable = fAvailable->fNext;
344 }
345 newBucket->fKey1 = key1;
346 newBucket->fKey2 = key2;
347 newBucket->fNext = fBucketList[hashVal];
348 fBucketList[hashVal] = newBucket;
349 fCount++;
350 return true;
351 }
352
353
354 // ---------------------------------------------------------------------------
355 // Hash2KeysSetOf: Private methods
356 // ---------------------------------------------------------------------------
357 template <class THasher>
358 inline Hash2KeysSetBucketElem* Hash2KeysSetOf<THasher>::
findBucketElem(const void * const key1,const int key2,XMLSize_t & hashVal)359 findBucketElem(const void* const key1, const int key2, XMLSize_t& hashVal)
360 {
361 // Hash the key
362 hashVal = fHasher.getHashVal(key1, fHashModulus);
363 assert(hashVal < fHashModulus);
364
365 // Search that bucket for the key
366 Hash2KeysSetBucketElem* curElem = fBucketList[hashVal];
367 while (curElem)
368 {
369 if((key2==curElem->fKey2) && (fHasher.equals(key1, curElem->fKey1)))
370 return curElem;
371
372 curElem = curElem->fNext;
373 }
374 return 0;
375 }
376
377 template <class THasher>
378 inline const Hash2KeysSetBucketElem* Hash2KeysSetOf<THasher>::
findBucketElem(const void * const key1,const int key2,XMLSize_t & hashVal)379 findBucketElem(const void* const key1, const int key2, XMLSize_t& hashVal) const
380 {
381 // Hash the key
382 hashVal = fHasher.getHashVal(key1, fHashModulus);
383 assert(hashVal < fHashModulus);
384
385 // Search that bucket for the key
386 const Hash2KeysSetBucketElem* curElem = fBucketList[hashVal];
387 while (curElem)
388 {
389 if((key2==curElem->fKey2) && (fHasher.equals(key1, curElem->fKey1)))
390 return curElem;
391
392 curElem = curElem->fNext;
393 }
394 return 0;
395 }
396
397
398 template <class THasher>
399 void Hash2KeysSetOf<THasher>::
rehash()400 rehash()
401 {
402 const XMLSize_t newMod = (fHashModulus * 8)+1;
403
404 Hash2KeysSetBucketElem** newBucketList =
405 (Hash2KeysSetBucketElem**) fMemoryManager->allocate
406 (
407 newMod * sizeof(Hash2KeysSetBucketElem*)
408 );//new Hash2KeysSetBucketElem*[fHashModulus];
409
410 // Make sure the new bucket list is destroyed if an
411 // exception is thrown.
412 ArrayJanitor<Hash2KeysSetBucketElem*> guard(newBucketList, fMemoryManager);
413
414 memset(newBucketList, 0, newMod * sizeof(newBucketList[0]));
415
416 // Rehash all existing entries.
417 for (XMLSize_t index = 0; index < fHashModulus; index++)
418 {
419 // Get the bucket list head for this entry
420 Hash2KeysSetBucketElem* curElem = fBucketList[index];
421 while (curElem)
422 {
423 // Save the next element before we detach this one
424 Hash2KeysSetBucketElem* nextElem = curElem->fNext;
425
426 const XMLSize_t hashVal = fHasher.getHashVal(curElem->fKey1, newMod);
427 assert(hashVal < newMod);
428
429 Hash2KeysSetBucketElem* newHeadElem = newBucketList[hashVal];
430
431 // Insert at the start of this bucket's list.
432 curElem->fNext = newHeadElem;
433 newBucketList[hashVal] = curElem;
434
435 curElem = nextElem;
436 }
437 }
438
439 Hash2KeysSetBucketElem** const oldBucketList = fBucketList;
440
441 // Everything is OK at this point, so update the
442 // member variables.
443 fBucketList = guard.release();
444 fHashModulus = newMod;
445
446 // Delete the old bucket list.
447 fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList;
448
449 }
450
451
452
453 // ---------------------------------------------------------------------------
454 // Hash2KeysSetOfEnumerator: Constructors and Destructor
455 // ---------------------------------------------------------------------------
456 template <class THasher>
457 Hash2KeysSetOfEnumerator<THasher>::
Hash2KeysSetOfEnumerator(Hash2KeysSetOf<THasher> * const toEnum,const bool adopt,MemoryManager * const manager)458 Hash2KeysSetOfEnumerator(Hash2KeysSetOf<THasher>* const toEnum
459 , const bool adopt
460 , MemoryManager* const manager)
461 : fAdopted(adopt), fCurElem(0), fCurHash((XMLSize_t)-1), fToEnum(toEnum)
462 , fMemoryManager(manager)
463 , fLockPrimaryKey(0)
464 {
465 if (!toEnum)
466 ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager);
467
468 //
469 // Find the next available bucket element in the hash table. If it
470 // comes back zero, that just means the table is empty.
471 //
472 // Note that the -1 in the current hash tells it to start
473 // from the beginning.
474 //
475 findNext();
476 }
477
478 template <class THasher>
~Hash2KeysSetOfEnumerator()479 Hash2KeysSetOfEnumerator<THasher>::~Hash2KeysSetOfEnumerator()
480 {
481 if (fAdopted)
482 delete fToEnum;
483 }
484
485
486 // ---------------------------------------------------------------------------
487 // Hash2KeysSetOfEnumerator: Enum interface
488 // ---------------------------------------------------------------------------
489 template <class THasher>
hasMoreElements()490 bool Hash2KeysSetOfEnumerator<THasher>::hasMoreElements() const
491 {
492 //
493 // If our current has is at the max and there are no more elements
494 // in the current bucket, then no more elements.
495 //
496 if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
497 return false;
498 return true;
499 }
500
501 template <class THasher>
nextElementKey(const void * & retKey1,int & retKey2)502 void Hash2KeysSetOfEnumerator<THasher>::nextElementKey(const void*& retKey1, int& retKey2)
503 {
504 // Make sure we have an element to return
505 if (!hasMoreElements())
506 ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
507
508 //
509 // Save the current element, then move up to the next one for the
510 // next time around.
511 //
512 Hash2KeysSetBucketElem* saveElem = fCurElem;
513 findNext();
514
515 retKey1 = saveElem->fKey1;
516 retKey2 = saveElem->fKey2;
517
518 return;
519 }
520
521 template <class THasher>
Reset()522 void Hash2KeysSetOfEnumerator<THasher>::Reset()
523 {
524 if(fLockPrimaryKey)
525 fCurHash=fToEnum->fHasher.getHashVal(fLockPrimaryKey, fToEnum->fHashModulus);
526 else
527 fCurHash = (XMLSize_t)-1;
528
529 fCurElem = 0;
530 findNext();
531 }
532
533
534 template <class THasher>
setPrimaryKey(const void * key)535 void Hash2KeysSetOfEnumerator<THasher>::setPrimaryKey(const void* key)
536 {
537 fLockPrimaryKey=key;
538 Reset();
539 }
540
541 // ---------------------------------------------------------------------------
542 // Hash2KeysSetOfEnumerator: Private helper methods
543 // ---------------------------------------------------------------------------
544 template <class THasher>
findNext()545 void Hash2KeysSetOfEnumerator<THasher>::findNext()
546 {
547 // Code to execute if we have to return only values with the primary key
548 if(fLockPrimaryKey)
549 {
550 if(!fCurElem)
551 fCurElem = fToEnum->fBucketList[fCurHash];
552 else
553 fCurElem = fCurElem->fNext;
554 while (fCurElem && (!fToEnum->fHasher.equals(fLockPrimaryKey, fCurElem->fKey1)))
555 fCurElem = fCurElem->fNext;
556 // if we didn't found it, make so hasMoreElements() returns false
557 if(!fCurElem)
558 fCurHash = fToEnum->fHashModulus;
559 return;
560 }
561 //
562 // If there is a current element, move to its next element. If this
563 // hits the end of the bucket, the next block will handle the rest.
564 //
565 if (fCurElem)
566 fCurElem = fCurElem->fNext;
567
568 //
569 // If the current element is null, then we have to move up to the
570 // next hash value. If that is the hash modulus, then we cannot
571 // go further.
572 //
573 if (!fCurElem)
574 {
575 fCurHash++;
576 if (fCurHash == fToEnum->fHashModulus)
577 return;
578
579 // Else find the next non-empty bucket
580 while (fToEnum->fBucketList[fCurHash]==0)
581 {
582 // Bump to the next hash value. If we max out return
583 fCurHash++;
584 if (fCurHash == fToEnum->fHashModulus)
585 return;
586 }
587 fCurElem = fToEnum->fBucketList[fCurHash];
588 }
589 }
590
591 XERCES_CPP_NAMESPACE_END
592