Xalan-C++ API Reference 1.12.0
XalanMap.hpp
Go to the documentation of this file.
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19#if !defined(XALANMAP_HEADER_GUARD_1357924680)
20#define XALANMAP_HEADER_GUARD_1357924680
21
22
23// Base include file. Must be first.
25
26
27
28#include <cstddef>
29#include <algorithm>
30#include <functional>
31#include <utility>
32
33
36
37
38
39namespace XALAN_CPP_NAMESPACE {
40
41#if defined(_MSC_VER)
42#pragma warning(push)
43#pragma warning(disable: 4189)
44#endif
45
46typedef size_t size_type;
47
48template <class Key>
50{
51public:
53 {
54 const char *byteArray = reinterpret_cast<const char*>(&key);
55
56 size_type result = 0;
57
58 for (size_type i = 0; i < sizeof(Key); ++i)
59 {
60 result = (result << 1) ^ byteArray[i];
61 }
62
63 return result;
64 }
65};
66
67template <class Key>
69{
71 typedef std::equal_to<Key> Comparator;
72};
73
74
75template <class Key>
77{
78
80 {
81 assert (key != 0);
82 return key->hash();
83 }
84};
85
86template <class Key>
88{
89
91 {
92 return key.hash();
93 }
94};
95
96
97
98template <class Value>
100{
102 typedef Value& reference;
103 typedef Value* pointer;
104};
105
106template <class Value>
108{
110 typedef const Value& reference;
111 typedef const Value* pointer;
112};
113
114template <class XalanMapTraits, class BaseIterator>
116{
117 typedef typename XalanMapTraits::value_type value_type;
118 typedef typename XalanMapTraits::reference reference;
119 typedef typename XalanMapTraits::pointer pointer;
120
122 typedef std::bidirectional_iterator_tag iterator_category;
123
124 typedef XalanMapIterator<
127
129 baseIterator(theRhs.baseIterator)
130 {
131 }
132
134 baseIterator(theRhs)
135 {
136 }
137
139 {
140 XalanMapIterator temp(*this);
141 ++baseIterator;
142 return temp;
143 }
144
146 {
147 ++baseIterator;
148 return *this;
149 }
150
152 {
153 return *baseIterator->value;
154 }
155
157 {
158 return baseIterator->value;
159 }
160
162 {
163 return theRhs.baseIterator == baseIterator;
164 }
165
167 {
168 return !(theRhs == *this);
169 }
170
172};
173
174
175
176/**
177 * Xalan implementation of a hashtable.
178 *
179 */
180template <
181 class Key,
182 class Value,
187{
188public:
189 /**
190 * Each map entry is stored in a linked list where an entry
191 * consists of a pointer to the key/value pair and a flag to indicate
192 * whether the entry has been erased.
193 * The hash buckets are a vector of pointers into the entry list.
194 * Deleted entries are spliced into another list and marked 'erased'.
195 */
196
197 typedef Key key_type;
199 typedef size_t size_type;
200
201 typedef std::pair<const key_type, data_type> value_type;
202
203 struct Entry
204 {
206 bool erased;
207
209 value(theValue),
210 erased(false)
211 {
212 }
213 };
214
216
219
222 typedef typename BucketType::iterator BucketIterator;
223
224 typedef XalanMapIterator<
227 typedef XalanMapIterator<
230
231 typedef typename KeyConstructionTraits::Constructor FirstConstructor;
232 typedef typename ValueConstructionTraits::Constructor SecondConstructor;
233
234 enum
235 {
236 eDefaultMinBuckets = 29u,
237 eDefaultEraseThreshold = 50u,
238 eMinimumBucketSize = 5u
239 };
240
241
243 MemoryManager& theMemoryManager,
244 double loadFactor = 0.75,
245 size_type minBuckets = eDefaultMinBuckets,
246 size_type eraseThreshold = eDefaultEraseThreshold) :
247 m_memoryManager(&theMemoryManager),
248 m_loadFactor(loadFactor),
249 m_minBuckets(minBuckets),
250 m_size(0),
251 m_entries(theMemoryManager),
252 m_freeEntries(theMemoryManager),
253 m_buckets(theMemoryManager),
254 m_eraseCount(0),
255 m_eraseThreshold(eraseThreshold)
256 {
257 }
258
260 const XalanMap& theRhs,
261 MemoryManager& theMemoryManager) :
262 m_memoryManager(&theMemoryManager),
263 m_loadFactor(theRhs.m_loadFactor),
264 m_minBuckets(theRhs.m_minBuckets),
265 m_size(0),
266 m_entries(theMemoryManager),
267 m_freeEntries(theMemoryManager),
268 m_buckets(
269 size_type(m_loadFactor * theRhs.size()) + 1,
270 BucketType(*m_memoryManager),
272 m_eraseCount(0),
273 m_eraseThreshold(theRhs.m_eraseThreshold)
274 {
275 const_iterator entry = theRhs.begin();
276
277 while(entry != theRhs.end())
278 {
279 insert(*entry);
280 ++entry;
281 }
282
283 assert(m_size == theRhs.m_size);
284 }
285
286 MemoryManager&
288 {
289 assert (m_memoryManager != 0);
290
291 return *m_memoryManager;
292 }
293
295 {
296 doRemoveEntries();
297
298 if (!m_buckets.empty())
299 {
300 EntryListIterator toRemove = m_freeEntries.begin();
301
302 while(toRemove != m_freeEntries.end())
303 {
304 deallocate(toRemove->value);
305 ++toRemove;
306 }
307 }
308 }
309
310 XalanMap&
312 {
313 XalanMap theTemp(theRhs, *m_memoryManager);
314
315 swap(theTemp);
316
317 return *this;
318 }
319
321 {
322 return m_size;
323 }
324
325 bool empty() const
326 {
327 return m_size == 0;
328 }
329
331 {
332 return m_entries.begin();
333 }
334
336 {
337 return const_cast<XalanMap*>(this)->begin();
338 }
339
341 {
342 return m_entries.end();
343 }
344
346 {
347 return const_cast<XalanMap*>(this)->end();
348 }
349
351 {
352 if (m_size != 0)
353 {
354 assert(m_buckets.empty() == false);
355
356 const size_type index = doHash(key);
357 assert(index < m_buckets.size());
358
359 BucketType& bucket = m_buckets[index];
360 BucketIterator pos = bucket.begin();
361
362 while (pos != bucket.end())
363 {
364 if (!(*pos)->erased && m_equals(key, (*pos)->value->first))
365 {
366 return iterator(*pos);
367 }
368 ++pos;
369 }
370 }
371
372 return end();
373 }
374
376 {
377 return const_cast<XalanMap *>(this)->find(key);
378 }
379
381 {
382 iterator pos = find(key);
383
384 if (pos == end())
385 {
386 pos = doCreateEntry(key);
387 }
388
389 return (*pos).second;
390 }
391
392 void
393 insert(const value_type& value)
394 {
395 insert(value.first, value.second);
396 }
397
398 void insert(const key_type& key, const data_type& data)
399 {
400 const const_iterator pos = find(key);
401
402 if (pos == end())
403 {
404 doCreateEntry(key, &data);
405 }
406 }
407
409 {
410 if (pos != end())
411 {
412 doErase(pos);
413 }
414 }
415
417 {
418 const iterator pos = find(key);
419
420 if (pos != end())
421 {
422 doErase(pos);
423
424 return 1;
425 }
426 else
427 {
428 return 0;
429 }
430 }
431
432 void clear()
433 {
434 doRemoveEntries();
435
436 TableIterator bucketPos = m_buckets.begin();
437
438 while (bucketPos != m_buckets.end())
439 {
440 bucketPos->clear();
441 ++bucketPos;
442 }
443
444 m_eraseCount = 0;
445
446 assert(0 == m_size);
447 assert(m_entries.empty());
448 }
449
451 {
452 const size_type tempSize = m_size;
453 m_size = theRhs.m_size;
454 theRhs.m_size = tempSize;
455
456 MemoryManager* const tempMemoryManager = m_memoryManager;
457 m_memoryManager = theRhs.m_memoryManager;
458 theRhs.m_memoryManager = tempMemoryManager;
459
460 const size_type tempEraseCount = m_eraseCount;
461 m_eraseCount = theRhs.m_eraseCount;
462 theRhs.m_eraseCount = tempEraseCount;
463
464 const size_type tempEraseTheshold = m_eraseThreshold;
465 m_eraseThreshold = theRhs.m_eraseThreshold;
466 theRhs.m_eraseThreshold = tempEraseTheshold;
467
468 m_entries.swap(theRhs.m_entries);
469 m_freeEntries.swap(theRhs.m_freeEntries);
470 m_buckets.swap(theRhs.m_buckets);
471 }
472
473protected:
474
475 iterator doCreateEntry(const key_type & key, const data_type* data = 0)
476 {
477 // if there are no buckets, create initial minimum set of buckets
478 if (m_buckets.empty())
479 {
480 m_buckets.insert(
481 m_buckets.begin(),
482 m_minBuckets,
483 BucketType(*m_memoryManager));
484 }
485
486 // if the load factor has been reached, rehash
487 if (size_type(m_loadFactor * size()) > m_buckets.size())
488 {
489 rehash();
490 }
491
492 const size_type index = doHash(key);
493
494 if (m_freeEntries.empty())
495 {
496 m_freeEntries.push_back(Entry(allocate(1)));
497 }
498
499 // insert a new entry as the first position in the bucket
500 Entry& newEntry = m_freeEntries.back();
501 newEntry.erased = false;
502
503 FirstConstructor::construct(
504 const_cast<key_type*>(&newEntry.value->first),
505 key,
506 *m_memoryManager);
507
508 if (data != 0)
509 {
510 SecondConstructor::construct(
511 &newEntry.value->second,
512 *data,
513 *m_memoryManager);
514 }
515 else
516 {
517 SecondConstructor::construct(
518 &newEntry.value->second,
519 *m_memoryManager);
520 }
521
522 m_entries.splice(m_entries.end(), m_freeEntries, --m_freeEntries.end());
523
524 m_buckets[index].push_back(--m_entries.end());
525
526 ++m_size;
527
528 return iterator(--m_entries.end());
529 }
530
532 {
534#if defined(_MSC_VER) && _MSC_VER <= 1300
535 toRemove.value_type::~value_type();
536#else
537 toRemove.~value_type();
538#endif
539 m_freeEntries.splice(
540 m_freeEntries.end(),
541 m_entries,
542 toRemovePos.baseIterator);
543
544 toRemovePos.baseIterator->erased = true;
545
546 --m_size;
547 }
548
549 void
551 {
552 while(size() > 0)
553 {
554 doRemoveEntry(begin());
555 }
556 }
557
558 void
560 {
561 assert(pos != end());
562
563 doRemoveEntry(pos);
564
565 ++m_eraseCount;
566
567 if (m_eraseCount == m_eraseThreshold)
568 {
569 compactBuckets();
570
571 m_eraseCount = 0;
572 }
573 }
574
577 const Key& key,
578 size_type modulus) const
579 {
580 assert(modulus != 0);
581
582 return m_hash(key) % modulus;
583 }
584
585 size_type doHash(const Key & key) const
586 {
587 return doHash(key, m_buckets.size());
588 }
589
590 void rehash()
591 {
592 // grow the number of buckets by 60%
593 const size_type theNewSize = size_type(1.6 * size());
594 assert(theNewSize != 0);
595
598 BucketType(*m_memoryManager),
599 *m_memoryManager);
600
601 // rehash each entry assign to bucket and insert into list
602 EntryListIterator entryPos = m_entries.begin();
603
604 while (entryPos != m_entries.end())
605 {
606 const size_type index =
607 doHash(
608 entryPos->value->first,
609 theNewSize);
610
611 temp[index].push_back(entryPos);
612
613 ++entryPos;
614 }
615
616 // Now that we've rebuilt the buckets, swap the rebuilt
617 // buckets with our existing buckets.
618 m_buckets.swap(temp);
619 }
620
621 value_type*
623 {
624 const size_type theBytesNeeded = size * sizeof(value_type);
625
626 assert(m_memoryManager != 0);
627
628 void* pointer = m_memoryManager->allocate(theBytesNeeded);
629
630 assert(pointer != 0);
631
632 return reinterpret_cast<value_type*>(pointer);
633 }
634
635 void
637 {
638 assert(m_memoryManager != 0);
639
640 m_memoryManager->deallocate(pointer);
641 }
642
643 static size_type
647 {
649
650 // We'll use the current extra capacity a convenient number.
651 // Perhaps a better choice would be to determine how much
652 // of the extra capacity to keep, but we really need to
653 // figure out how to keep the buckets compacted during
654 // removal of an item.
655 return theCurrentSize == 0 ?
656 eMinimumBucketSize :
658 }
659
660 void
662 {
663 for(TableIterator i = m_buckets.begin();
664 i != m_buckets.end();
665 ++i)
666 {
668
670
671 while(j != theCurrentBucket.end())
672 {
673 if ((*j)->erased == true)
674 {
675 j = theCurrentBucket.erase(j);
676 }
677 else
678 {
679 ++j;
680 }
681 }
682
683 // Now we should do something if the
684 // bucket has a much greater capacity
685 // than the number of items in it.
687 theCurrentBucket.size();
688
690 theCurrentBucket.capacity() - theCurrentSize;
691
693 {
695 calculateNewBucketCapacity(
698
699 // Create a copy of the bucket, and
700 // give it the new capacity of the extra
701 // capacity.
704 *m_memoryManager,
706
708 }
709 }
710 }
711
712 // Data members...
713 typename KeyTraits::Hasher m_hash;
714
715 typename KeyTraits::Comparator m_equals;
716
717 MemoryManager* m_memoryManager;
718
720
722
724
726
728
730
732
734
735private:
736
737 // These are not implemented.
738 XalanMap();
739
740 XalanMap(const XalanMap&);
741};
742
743
744
745#if defined(_MSC_VER)
746#pragma warning(pop)
747#endif
748
749
750
751}
752
753
754
755#endif // XALANMAP_HEADER_GUARD_1357924680
756
#define XALAN_CPP_NAMESPACE
Xalan-C++ namespace, including major and minor version.
size_type operator()(const Key &key) const
Definition XalanMap.hpp:52
Xalan implementation of a hashtable.
Definition XalanMap.hpp:187
MemoryManager * m_memoryManager
Definition XalanMap.hpp:717
void erase(iterator pos)
Definition XalanMap.hpp:408
data_type & operator[](const key_type &key)
Definition XalanMap.hpp:380
void doRemoveEntries()
Definition XalanMap.hpp:550
void swap(XalanMap &theRhs)
Definition XalanMap.hpp:450
size_type m_size
Definition XalanMap.hpp:723
XalanMapIterator< XalanMapIteratorTraits< value_type >, typename EntryListType::iterator > iterator
Definition XalanMap.hpp:226
KeyConstructionTraits::Constructor FirstConstructor
Definition XalanMap.hpp:231
size_type m_eraseThreshold
Definition XalanMap.hpp:733
const_iterator begin() const
Definition XalanMap.hpp:335
iterator doCreateEntry(const key_type &key, const data_type *data=0)
Definition XalanMap.hpp:475
size_type doHash(const Key &key) const
Definition XalanMap.hpp:585
iterator find(const key_type &key)
Definition XalanMap.hpp:350
const_iterator find(const key_type &key) const
Definition XalanMap.hpp:375
XalanVector< BucketType, ConstructWithMemoryManagerTraits< BucketType > > BucketTableType
Definition XalanMap.hpp:218
size_type erase(const key_type &key)
Definition XalanMap.hpp:416
KeyTraits::Hasher m_hash
Definition XalanMap.hpp:713
BucketTableType::iterator TableIterator
Definition XalanMap.hpp:221
EntryListType m_entries
Definition XalanMap.hpp:725
BucketType::iterator BucketIterator
Definition XalanMap.hpp:222
std::pair< const key_type, data_type > value_type
Definition XalanMap.hpp:201
void insert(const value_type &value)
Definition XalanMap.hpp:393
iterator end()
Definition XalanMap.hpp:340
bool empty() const
Definition XalanMap.hpp:325
void compactBuckets()
Definition XalanMap.hpp:661
XalanVector< typename EntryListType::iterator > BucketType
Definition XalanMap.hpp:217
value_type * allocate(size_type size)
Definition XalanMap.hpp:622
void insert(const key_type &key, const data_type &data)
Definition XalanMap.hpp:398
Key key_type
Each map entry is stored in a linked list where an entry consists of a pointer to the key/value pair ...
Definition XalanMap.hpp:197
const_iterator end() const
Definition XalanMap.hpp:345
XalanMap(const XalanMap &theRhs, MemoryManager &theMemoryManager)
Definition XalanMap.hpp:259
ValueConstructionTraits::Constructor SecondConstructor
Definition XalanMap.hpp:232
void deallocate(value_type *pointer)
Definition XalanMap.hpp:636
size_type size() const
Definition XalanMap.hpp:320
XalanList< Entry > EntryListType
Definition XalanMap.hpp:215
KeyTraits::Comparator m_equals
Definition XalanMap.hpp:715
XalanMap(MemoryManager &theMemoryManager, double loadFactor=0.75, size_type minBuckets=eDefaultMinBuckets, size_type eraseThreshold=eDefaultEraseThreshold)
Definition XalanMap.hpp:242
XalanMapIterator< XalanMapConstIteratorTraits< value_type >, typename EntryListType::iterator > const_iterator
Definition XalanMap.hpp:229
void doErase(iterator pos)
Definition XalanMap.hpp:559
XalanMap & operator=(const XalanMap &theRhs)
Definition XalanMap.hpp:311
BucketTableType m_buckets
Definition XalanMap.hpp:729
EntryListType::iterator EntryListIterator
Definition XalanMap.hpp:220
size_type m_eraseCount
Definition XalanMap.hpp:731
iterator begin()
Definition XalanMap.hpp:330
const size_type m_minBuckets
Definition XalanMap.hpp:721
void doRemoveEntry(const iterator &toRemovePos)
Definition XalanMap.hpp:531
EntryListType m_freeEntries
Definition XalanMap.hpp:727
size_type doHash(const Key &key, size_type modulus) const
Definition XalanMap.hpp:576
MemoryManager & getMemoryManager()
Definition XalanMap.hpp:287
static size_type calculateNewBucketCapacity(size_type theCurrentSize, size_type theExtraCapacity)
Definition XalanMap.hpp:644
XalanDOMString & insert(XalanDOMString &theString, XalanDOMString::size_type thePosition, const XalanDOMString &theStringToInsert)
Insert a string into another string.
void swap(XalanVector< Type > &theLHS, XalanVector< Type > &theRHS)
size_t size_type
Definition XalanMap.hpp:46
XalanMapTraits::reference reference
Definition XalanMap.hpp:118
bool operator==(const XalanMapIterator &theRhs) const
Definition XalanMap.hpp:161
XalanMapIterator(const BaseIterator &theRhs)
Definition XalanMap.hpp:133
BaseIterator baseIterator
Definition XalanMap.hpp:171
XalanMapTraits::pointer pointer
Definition XalanMap.hpp:119
reference operator*() const
Definition XalanMap.hpp:151
XalanMapIterator< XalanMapIteratorTraits< value_type >, BaseIterator > Iterator
Definition XalanMap.hpp:126
XalanMapIterator(const Iterator &theRhs)
Definition XalanMap.hpp:128
XalanMapTraits::value_type value_type
Definition XalanMap.hpp:117
std::bidirectional_iterator_tag iterator_category
Definition XalanMap.hpp:122
pointer operator->() const
Definition XalanMap.hpp:156
bool operator!=(const XalanMapIterator &theRhs) const
Definition XalanMap.hpp:166
XalanMapIterator operator++(int)
Definition XalanMap.hpp:138
XalanMapIterator & operator++()
Definition XalanMap.hpp:145
std::equal_to< Key > Comparator
Definition XalanMap.hpp:71
XalanHasher< Key > Hasher
Definition XalanMap.hpp:70
Entry(value_type *theValue)
Definition XalanMap.hpp:208