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 
39 namespace XALAN_CPP_NAMESPACE {
40 
41 #if defined(_MSC_VER)
42 #pragma warning(push)
43 #pragma warning(disable: 4189)
44 #endif
45 
46 typedef size_t size_type;
47 
48 template <class Key>
50 {
51 public:
52  size_type operator()(const Key& key) const
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 
67 template <class Key>
69 {
71  typedef std::equal_to<Key> Comparator;
72 };
73 
74 
75 template <class Key>
77 {
78 
79  size_type operator() (const Key * key) const
80  {
81  assert (key != 0);
82  return key->hash();
83  }
84 };
85 
86 template <class Key>
88 {
89 
90  size_type operator() (const Key& key) const
91  {
92  return key.hash();
93  }
94 };
95 
96 
97 
98 template <class Value>
100 {
101  typedef Value value_type;
102  typedef Value& reference;
103  typedef Value* pointer;
104 };
105 
106 template <class Value>
108 {
109  typedef Value value_type;
110  typedef const Value& reference;
111  typedef const Value* pointer;
112 };
113 
114 template <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 
121  typedef ptrdiff_t difference_type;
122  typedef std::bidirectional_iterator_tag iterator_category;
123 
124  typedef XalanMapIterator<
126  BaseIterator> Iterator;
127 
128  XalanMapIterator(const Iterator & theRhs) :
129  baseIterator(theRhs.baseIterator)
130  {
131  }
132 
133  XalanMapIterator(const BaseIterator & theRhs) :
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 
161  bool operator==(const XalanMapIterator& theRhs) const
162  {
163  return theRhs.baseIterator == baseIterator;
164  }
165 
166  bool operator!=(const XalanMapIterator& theRhs) const
167  {
168  return !(theRhs == *this);
169  }
170 
171  BaseIterator baseIterator;
172 };
173 
174 
175 
176 /**
177  * Xalan implementation of a hashtable.
178  *
179  */
180 template <
181  class Key,
182  class Value,
183  class KeyTraits = XalanMapKeyTraits<Key>,
184  class KeyConstructionTraits = MemoryManagedConstructionTraits<Key>,
185  class ValueConstructionTraits = MemoryManagedConstructionTraits<Value> >
186 class XalanMap
187 {
188 public:
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;
198  typedef Value data_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 
208  Entry(value_type* theValue) :
209  value(theValue),
210  erased(false)
211  {
212  }
213  };
214 
216 
219 
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),
271  theMemoryManager),
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&
311  operator=(const XalanMap& theRhs)
312  {
313  XalanMap theTemp(theRhs, *m_memoryManager);
314 
315  swap(theTemp);
316 
317  return *this;
318  }
319 
320  size_type size() const
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 
350  iterator find(const key_type& key)
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 
375  const_iterator find(const key_type& key) const
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 
408  void erase(iterator pos)
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 
450  void swap(XalanMap& theRhs)
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 
473 protected:
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 
531  void doRemoveEntry(const iterator & toRemovePos)
532  {
533  value_type& toRemove = *toRemovePos;
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 
575  size_type
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 
596  BucketTableType temp(
597  theNewSize,
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
645  size_type theCurrentSize,
646  size_type theExtraCapacity)
647  {
648  assert(theExtraCapacity > theCurrentSize);
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 :
657  theExtraCapacity;
658  }
659 
660  void
662  {
663  for(TableIterator i = m_buckets.begin();
664  i != m_buckets.end();
665  ++i)
666  {
667  BucketType& theCurrentBucket = *i;
668 
669  BucketIterator j = theCurrentBucket.begin();
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.
686  const size_type theCurrentSize =
687  theCurrentBucket.size();
688 
689  const size_type theExtraCapacity =
690  theCurrentBucket.capacity() - theCurrentSize;
691 
692  if (theExtraCapacity > theCurrentSize)
693  {
694  const size_type theNewCapacity =
695  calculateNewBucketCapacity(
696  theCurrentSize,
697  theExtraCapacity);
698 
699  // Create a copy of the bucket, and
700  // give it the new capacity of the extra
701  // capacity.
702  BucketType theTempBucket(
703  theCurrentBucket,
704  *m_memoryManager,
705  theNewCapacity);
706 
707  theCurrentBucket.swap(theTempBucket);
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 
719  double m_loadFactor;
720 
722 
724 
726 
728 
730 
732 
734 
735 private:
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 
xalanc::XalanMap::FirstConstructor
KeyConstructionTraits::Constructor FirstConstructor
Definition: XalanMap.hpp:231
xalanc::XalanMap::XalanMap
XalanMap(const XalanMap &theRhs, MemoryManager &theMemoryManager)
Definition: XalanMap.hpp:259
xalanc::XalanMapConstIteratorTraits::reference
const typedef Value & reference
Definition: XalanMap.hpp:110
xalanc::XalanMapIterator::XalanMapIterator
XalanMapIterator(const BaseIterator &theRhs)
Definition: XalanMap.hpp:133
xalanc::XalanMapKeyTraits::Hasher
XalanHasher< Key > Hasher
Definition: XalanMap.hpp:70
XALAN_CPP_NAMESPACE
#define XALAN_CPP_NAMESPACE
Xalan-C++ namespace, including major and minor version.
Definition: XalanVersion.hpp:76
xalanc::XalanMap::doHash
size_type doHash(const Key &key) const
Definition: XalanMap.hpp:585
xalanc::XalanMap::erase
size_type erase(const key_type &key)
Definition: XalanMap.hpp:416
xalanc::XalanMap::size_type
size_t size_type
Definition: XalanMap.hpp:199
xalanc::XalanMap::Entry
Definition: XalanMap.hpp:203
xalanc::XalanMapIterator::operator->
pointer operator->() const
Definition: XalanMap.hpp:156
xalanc::XalanVector::begin
iterator begin()
Definition: XalanVector.hpp:649
xalanc::XalanMap::compactBuckets
void compactBuckets()
Definition: XalanMap.hpp:661
xalanc::XalanMapIterator::Iterator
XalanMapIterator< XalanMapIteratorTraits< value_type >, BaseIterator > Iterator
Definition: XalanMap.hpp:126
xalanc::XalanMapConstIteratorTraits
Definition: XalanMap.hpp:107
xalanc::XalanHasher
Definition: XalanMap.hpp:49
xalanc::XalanMap::doErase
void doErase(iterator pos)
Definition: XalanMap.hpp:559
xalanc::XalanMap::deallocate
void deallocate(value_type *pointer)
Definition: XalanMap.hpp:636
xalanc::XalanVector
Definition: XalanVector.hpp:58
xalanc::XalanMap::TableIterator
BucketTableType::iterator TableIterator
Definition: XalanMap.hpp:221
xalanc::XalanMap::m_buckets
BucketTableType m_buckets
Definition: XalanMap.hpp:729
xalanc::XalanMap::m_minBuckets
const size_type m_minBuckets
Definition: XalanMap.hpp:721
xalanc::XalanMap::find
iterator find(const key_type &key)
Definition: XalanMap.hpp:350
xalanc::XalanMap::EntryListType
XalanList< Entry > EntryListType
Definition: XalanMap.hpp:215
xalanc::XalanMap::Entry::erased
bool erased
Definition: XalanMap.hpp:206
xalanc::MemoryManagedConstructionTraits
Definition: XalanMemoryManagement.hpp:576
xalanc::swap
void swap(XalanVector< Type > &theLHS, XalanVector< Type > &theRHS)
Definition: XalanVector.hpp:1107
XalanList.hpp
xalanc::size_type
size_t size_type
Definition: XalanMap.hpp:46
xalanc::XalanMap::allocate
value_type * allocate(size_type size)
Definition: XalanMap.hpp:622
xalanc::XalanMap::getMemoryManager
MemoryManager & getMemoryManager()
Definition: XalanMap.hpp:287
xalanc::XalanMap::key_type
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
XalanVector.hpp
xalanc::XalanMap::calculateNewBucketCapacity
static size_type calculateNewBucketCapacity(size_type theCurrentSize, size_type theExtraCapacity)
Definition: XalanMap.hpp:644
xalanc::XalanMapIterator::operator++
XalanMapIterator & operator++()
Definition: XalanMap.hpp:145
xalanc::XalanMap::m_equals
KeyTraits::Comparator m_equals
Definition: XalanMap.hpp:715
xalanc::XalanMapIterator::operator*
reference operator*() const
Definition: XalanMap.hpp:151
xalanc::XalanMapKeyTraits::Comparator
std::equal_to< Key > Comparator
Definition: XalanMap.hpp:71
xalanc::XalanMapConstIteratorTraits::pointer
const typedef Value * pointer
Definition: XalanMap.hpp:111
xalanc::XalanMap::Entry::value
value_type * value
Definition: XalanMap.hpp:205
xalanc::XalanMapIterator::value_type
XalanMapTraits::value_type value_type
Definition: XalanMap.hpp:117
xalanc::XalanMap::const_iterator
XalanMapIterator< XalanMapConstIteratorTraits< value_type >, typename EntryListType::iterator > const_iterator
Definition: XalanMap.hpp:229
xalanc::XalanMap::BucketIterator
BucketType::iterator BucketIterator
Definition: XalanMap.hpp:222
xalanc::XalanMap::insert
void insert(const value_type &value)
Definition: XalanMap.hpp:393
xalanc::XalanMap::begin
const_iterator begin() const
Definition: XalanMap.hpp:335
xalanc::XalanVector::size
size_type size() const
Definition: XalanVector.hpp:534
xalanc::XalanMap::insert
void insert(const key_type &key, const data_type &data)
Definition: XalanMap.hpp:398
xalanc::XalanHasher::operator()
size_type operator()(const Key &key) const
Definition: XalanMap.hpp:52
xalanc::XalanMap::~XalanMap
~XalanMap()
Definition: XalanMap.hpp:294
xalanc::XalanVector< BucketType, ConstructWithMemoryManagerTraits< BucketType > >::iterator
value_type * iterator
Definition: XalanVector.hpp:71
xalanc::XalanMap::empty
bool empty() const
Definition: XalanMap.hpp:325
xalanc::XalanMapConstIteratorTraits::value_type
Value value_type
Definition: XalanMap.hpp:109
xalanc::XalanVector::push_back
void push_back(const value_type &data)
Definition: XalanVector.hpp:209
xalanc::XalanMapIteratorTraits
Definition: XalanMap.hpp:99
xalanc::XalanMap::end
const_iterator end() const
Definition: XalanMap.hpp:345
xalanc::XalanMap::doRemoveEntry
void doRemoveEntry(const iterator &toRemovePos)
Definition: XalanMap.hpp:531
xalanc::XalanVector::erase
iterator erase(iterator theFirst, iterator theLast)
Definition: XalanVector.hpp:231
xalanc::XalanMapIteratorTraits::reference
Value & reference
Definition: XalanMap.hpp:102
xalanc::XalanMap::rehash
void rehash()
Definition: XalanMap.hpp:590
xalanc::XalanMap::SecondConstructor
ValueConstructionTraits::Constructor SecondConstructor
Definition: XalanMap.hpp:232
xalanc::XalanMap::doHash
size_type doHash(const Key &key, size_type modulus) const
Definition: XalanMap.hpp:576
xalanc::XalanMap::begin
iterator begin()
Definition: XalanMap.hpp:330
xalanc::XalanMapIterator::operator!=
bool operator!=(const XalanMapIterator &theRhs) const
Definition: XalanMap.hpp:166
xalanc::XalanMapIterator::baseIterator
BaseIterator baseIterator
Definition: XalanMap.hpp:171
xalanc::XalanMap::m_hash
KeyTraits::Hasher m_hash
Definition: XalanMap.hpp:713
xalanc::XalanMap::m_freeEntries
EntryListType m_freeEntries
Definition: XalanMap.hpp:727
xalanc::XalanListIteratorBase
Definition: XalanList.hpp:63
xalanc::XalanMap
Xalan implementation of a hashtable.
Definition: XalanMap.hpp:186
xalanc::XalanMap::size
size_type size() const
Definition: XalanMap.hpp:320
xalanc::XalanMapIterator::XalanMapIterator
XalanMapIterator(const Iterator &theRhs)
Definition: XalanMap.hpp:128
xalanc::XalanMap::clear
void clear()
Definition: XalanMap.hpp:432
xalanc::XalanMapIterator::pointer
XalanMapTraits::pointer pointer
Definition: XalanMap.hpp:119
xalanc::XalanHashMemberReference
Definition: XalanMap.hpp:87
xalanc::XalanMapIteratorTraits::pointer
Value * pointer
Definition: XalanMap.hpp:103
xalanc::XalanMap::XalanMap
XalanMap(MemoryManager &theMemoryManager, double loadFactor=0.75, size_type minBuckets=eDefaultMinBuckets, size_type eraseThreshold=eDefaultEraseThreshold)
Definition: XalanMap.hpp:242
xalanc::XalanMapIteratorTraits::value_type
Value value_type
Definition: XalanMap.hpp:101
xalanc::XalanMap::erase
void erase(iterator pos)
Definition: XalanMap.hpp:408
xalanc::XalanMap::doCreateEntry
iterator doCreateEntry(const key_type &key, const data_type *data=0)
Definition: XalanMap.hpp:475
xalanc::XalanMap::data_type
Value data_type
Definition: XalanMap.hpp:198
xalanc::XalanMap::m_entries
EntryListType m_entries
Definition: XalanMap.hpp:725
xalanc::XalanMap::end
iterator end()
Definition: XalanMap.hpp:340
xalanc::XalanMap::doRemoveEntries
void doRemoveEntries()
Definition: XalanMap.hpp:550
xalanc::XalanMap::Entry::Entry
Entry(value_type *theValue)
Definition: XalanMap.hpp:208
xalanc::XalanMap::m_size
size_type m_size
Definition: XalanMap.hpp:723
xalanc::XalanMap::swap
void swap(XalanMap &theRhs)
Definition: XalanMap.hpp:450
xalanc::XalanMapIterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: XalanMap.hpp:122
xalanc::XalanMapKeyTraits
Definition: XalanMap.hpp:68
xalanc::XalanMap::EntryListIterator
EntryListType::iterator EntryListIterator
Definition: XalanMap.hpp:220
xalanc::XalanMap::operator[]
data_type & operator[](const key_type &key)
Definition: XalanMap.hpp:380
xalanc::XalanMap::m_eraseCount
size_type m_eraseCount
Definition: XalanMap.hpp:731
xalanc::insert
XalanDOMString & insert(XalanDOMString &theString, XalanDOMString::size_type thePosition, const XalanDOMString &theStringToInsert)
Insert a string into another string.
Definition: DOMStringHelper.hpp:2418
xalanc::XalanMapIterator::reference
XalanMapTraits::reference reference
Definition: XalanMap.hpp:118
xalanc::XalanVector::end
iterator end()
Definition: XalanVector.hpp:665
xalanc::XalanMap::m_memoryManager
MemoryManager * m_memoryManager
Definition: XalanMap.hpp:717
xalanc::XalanMapIterator::difference_type
ptrdiff_t difference_type
Definition: XalanMap.hpp:121
PlatformDefinitions.hpp
xalanc::XalanSourceTreeElement
Definition: XalanSourceTreeElement.hpp:46
xalanc::XalanMap::m_eraseThreshold
size_type m_eraseThreshold
Definition: XalanMap.hpp:733
xalanc::XalanMap::BucketType
XalanVector< typename EntryListType::iterator > BucketType
Definition: XalanMap.hpp:217
xalanc::XalanMapIterator::operator==
bool operator==(const XalanMapIterator &theRhs) const
Definition: XalanMap.hpp:161
xalanc::XalanMap::iterator
XalanMapIterator< XalanMapIteratorTraits< value_type >, typename EntryListType::iterator > iterator
Definition: XalanMap.hpp:226
xalanc::XalanMapIterator
Definition: XalanMap.hpp:115
xalanc::XalanVector::swap
void swap(ThisType &theOther)
Definition: XalanVector.hpp:814
xalanc::XalanMap::value_type
std::pair< const key_type, data_type > value_type
Definition: XalanMap.hpp:201
xalanc::XalanMap::BucketTableType
XalanVector< BucketType, ConstructWithMemoryManagerTraits< BucketType > > BucketTableType
Definition: XalanMap.hpp:218
xalanc::XalanMap::m_loadFactor
double m_loadFactor
Definition: XalanMap.hpp:719
xalanc::XalanHashMemberPointer
Definition: XalanMap.hpp:76
xalanc::XalanMapIterator::operator++
XalanMapIterator operator++(int)
Definition: XalanMap.hpp:138
xalanc::XalanList< Entry >
xalanc::XalanMap::operator=
XalanMap & operator=(const XalanMap &theRhs)
Definition: XalanMap.hpp:311
xalanc::XalanMap::find
const_iterator find(const key_type &key) const
Definition: XalanMap.hpp:375
xalanc::XalanVector::capacity
size_type capacity() const
Definition: XalanVector.hpp:592