Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.11


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 XALAN_CPP_NAMESPACE_BEGIN
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>
49 class XalanHasher : public XALAN_STD_QUALIFIER unary_function<Key, size_type>
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 XALAN_STD_QUALIFIER 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 XALAN_STD_QUALIFIER 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 XALAN_STD_QUALIFIER 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  {
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,
271  theMemoryManager),
272  m_eraseCount(0),
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  {
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;
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;
466  theRhs.m_eraseThreshold = tempEraseTheshold;
467 
468  m_entries.swap(theRhs.m_entries);
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  {
481  m_buckets.begin(),
482  m_minBuckets,
484  }
485 
486  // if the load factor has been reached, rehash
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 
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
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 
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,
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 ?
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 =
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,
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 XALAN_CPP_NAMESPACE_END
752 
753 
754 
755 #endif // XALANMAP_HEADER_GUARD_1357924680
756 
XalanMap::doErase
void doErase(iterator pos)
Definition: XalanMap.hpp:559
XalanMap::iterator
XalanMapIterator< XalanMapIteratorTraits< value_type >, typename EntryListType::iterator > iterator
Definition: XalanMap.hpp:226
XalanMap::TableIterator
BucketTableType::iterator TableIterator
Definition: XalanMap.hpp:221
XalanMap::Entry
Definition: XalanMap.hpp:204
XalanMap::getMemoryManager
MemoryManager & getMemoryManager()
Definition: XalanMap.hpp:287
XalanMapIterator::iterator_category
XALAN_STD_QUALIFIER bidirectional_iterator_tag iterator_category
Definition: XalanMap.hpp:122
XalanMapIterator::XalanMapIterator
XalanMapIterator(const BaseIterator &theRhs)
Definition: XalanMap.hpp:133
XalanMap::doCreateEntry
iterator doCreateEntry(const key_type &key, const data_type *data=0)
Definition: XalanMap.hpp:475
XalanMap::clear
void clear()
Definition: XalanMap.hpp:432
XalanMapKeyTraits::Comparator
XALAN_STD_QUALIFIER equal_to< Key > Comparator
Definition: XalanMap.hpp:71
XalanMapIterator::value_type
XalanMapTraits::value_type value_type
Definition: XalanMap.hpp:117
XalanMap::operator[]
data_type & operator[](const key_type &key)
Definition: XalanMap.hpp:380
MemoryManagedConstructionTraits
Definition: XalanMemoryManagement.hpp:585
XalanMap::doHash
size_type doHash(const Key &key, size_type modulus) const
Definition: XalanMap.hpp:576
XalanHasher::operator()
size_type operator()(const Key &key) const
Definition: XalanMap.hpp:52
XalanMapConstIteratorTraits
Definition: XalanMap.hpp:108
XalanMap::m_eraseThreshold
size_type m_eraseThreshold
Definition: XalanMap.hpp:733
XalanVector< BucketType, ConstructWithMemoryManagerTraits< BucketType > >::iterator
value_type * iterator
Definition: XalanVector.hpp:88
XalanMapIterator::difference_type
ptrdiff_t difference_type
Definition: XalanMap.hpp:121
XalanMap::XalanMap
XalanMap(const XalanMap &theRhs, MemoryManager &theMemoryManager)
Definition: XalanMap.hpp:259
XalanMap::BucketTableType
XalanVector< BucketType, ConstructWithMemoryManagerTraits< BucketType > > BucketTableType
Definition: XalanMap.hpp:218
XalanMapIteratorTraits
Definition: XalanMap.hpp:100
XalanVector::push_back
void push_back(const value_type &data)
Definition: XalanVector.hpp:249
XalanHashMemberReference::operator()
size_type operator()(const Key &key) const
Definition: XalanMap.hpp:90
XalanMapIteratorTraits::pointer
Value * pointer
Definition: XalanMap.hpp:103
XalanMapIterator::XalanMapIterator
XalanMapIterator(const Iterator &theRhs)
Definition: XalanMap.hpp:128
XalanVector::capacity
size_type capacity() const
Definition: XalanVector.hpp:632
XalanMap::XalanMap
XalanMap(MemoryManager &theMemoryManager, double loadFactor=0.75, size_type minBuckets=eDefaultMinBuckets, size_type eraseThreshold=eDefaultEraseThreshold)
Definition: XalanMap.hpp:242
XalanMapIterator::pointer
XalanMapTraits::pointer pointer
Definition: XalanMap.hpp:119
XalanMap::m_memoryManager
MemoryManager * m_memoryManager
Definition: XalanMap.hpp:717
XalanVector::end
iterator end()
Definition: XalanVector.hpp:705
XalanList.hpp
XalanMapConstIteratorTraits::pointer
const Value * pointer
Definition: XalanMap.hpp:111
XalanMap::find
iterator find(const key_type &key)
Definition: XalanMap.hpp:350
XalanMapIterator::operator++
XalanMapIterator & operator++()
Definition: XalanMap.hpp:145
XalanMapIterator::operator==
bool operator==(const XalanMapIterator &theRhs) const
Definition: XalanMap.hpp:161
XalanList::end
iterator end()
Definition: XalanList.hpp:280
XalanMap::allocate
value_type * allocate(size_type size)
Definition: XalanMap.hpp:622
XalanMap::find
const_iterator find(const key_type &key) const
Definition: XalanMap.hpp:375
XalanVector.hpp
XalanMapIterator::operator->
pointer operator->() const
Definition: XalanMap.hpp:156
XalanMapKeyTraits::Hasher
XalanHasher< Key > Hasher
Definition: XalanMap.hpp:70
XalanMap::BucketType
XalanVector< typename EntryListType::iterator > BucketType
Definition: XalanMap.hpp:217
XalanMap::eMinimumBucketSize
@ eMinimumBucketSize
Definition: XalanMap.hpp:238
XalanMap::m_size
size_type m_size
Definition: XalanMap.hpp:723
XalanMapIterator::baseIterator
BaseIterator baseIterator
Definition: XalanMap.hpp:171
XalanMap::~XalanMap
~XalanMap()
Definition: XalanMap.hpp:294
XalanMapConstIteratorTraits::reference
const Value & reference
Definition: XalanMap.hpp:110
XalanMapIteratorTraits::reference
Value & reference
Definition: XalanMap.hpp:102
XalanMap::end
iterator end()
Definition: XalanMap.hpp:340
XalanVector::size
size_type size() const
Definition: XalanVector.hpp:574
XalanMap::empty
bool empty() const
Definition: XalanMap.hpp:325
XalanSourceTreeElement
Definition: XalanSourceTreeElement.hpp:47
XalanMapConstIteratorTraits::value_type
Value value_type
Definition: XalanMap.hpp:109
XalanMap::rehash
void rehash()
Definition: XalanMap.hpp:590
XalanMap
Xalan implementation of a hashtable.
Definition: XalanMap.hpp:187
XalanMap::eDefaultMinBuckets
@ eDefaultMinBuckets
Definition: XalanMap.hpp:236
XalanMapIterator::operator++
XalanMapIterator operator++(int)
Definition: XalanMap.hpp:138
XalanList::splice
void splice(iterator pos, ThisType &list, iterator toInsert)
Definition: XalanList.hpp:384
XalanHashMemberPointer::operator()
size_type operator()(const Key *key) const
Definition: XalanMap.hpp:79
XalanVector::erase
iterator erase(iterator theFirst, iterator theLast)
Definition: XalanVector.hpp:271
XalanMap::m_buckets
BucketTableType m_buckets
Definition: XalanMap.hpp:729
XalanMap::BucketIterator
BucketType::iterator BucketIterator
Definition: XalanMap.hpp:222
XalanMap::doRemoveEntries
void doRemoveEntries()
Definition: XalanMap.hpp:550
XalanMapIteratorTraits::value_type
Value value_type
Definition: XalanMap.hpp:101
XalanMap::end
const_iterator end() const
Definition: XalanMap.hpp:345
XalanHashMemberReference
Definition: XalanMap.hpp:88
XalanMap::eDefaultEraseThreshold
@ eDefaultEraseThreshold
Definition: XalanMap.hpp:237
XalanHashMemberPointer
Definition: XalanMap.hpp:77
XalanMap::erase
size_type erase(const key_type &key)
Definition: XalanMap.hpp:416
XalanMap::Entry::Entry
Entry(value_type *theValue)
Definition: XalanMap.hpp:208
XalanMap::size_type
size_t size_type
Definition: XalanMap.hpp:199
XalanMap::begin
const_iterator begin() const
Definition: XalanMap.hpp:335
XalanVector::begin
iterator begin()
Definition: XalanVector.hpp:689
XalanMapKeyTraits
Definition: XalanMap.hpp:69
XalanMap::m_loadFactor
double m_loadFactor
Definition: XalanMap.hpp:719
XalanMap::insert
void insert(const value_type &value)
Definition: XalanMap.hpp:393
XalanMap::compactBuckets
void compactBuckets()
Definition: XalanMap.hpp:661
XalanVector::insert
void insert(iterator thePosition, const_iterator theFirst, const_iterator theLast)
Definition: XalanVector.hpp:299
XalanMap::m_minBuckets
const size_type m_minBuckets
Definition: XalanMap.hpp:721
XalanVector
Definition: XalanVector.hpp:59
XalanMapIterator
Definition: XalanMap.hpp:116
XalanMapIterator::operator!=
bool operator!=(const XalanMapIterator &theRhs) const
Definition: XalanMap.hpp:166
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
XalanList::empty
bool empty() const
Definition: XalanList.hpp:341
XalanMap::erase
void erase(iterator pos)
Definition: XalanMap.hpp:408
XalanMapIterator::reference
XalanMapTraits::reference reference
Definition: XalanMap.hpp:118
XalanList< Entry >
XalanMap::insert
void insert(const key_type &key, const data_type &data)
Definition: XalanMap.hpp:398
size_type
XALAN_CPP_NAMESPACE_BEGIN typedef size_t size_type
Definition: XalanMap.hpp:46
XalanMap::m_equals
KeyTraits::Comparator m_equals
Definition: XalanMap.hpp:715
XalanMap::const_iterator
XalanMapIterator< XalanMapConstIteratorTraits< value_type >, typename EntryListType::iterator > const_iterator
Definition: XalanMap.hpp:229
XalanList::swap
void swap(ThisType &theRHS)
Definition: XalanList.hpp:451
XalanList::push_back
void push_back(const value_type &data)
Definition: XalanList.hpp:347
XalanMap::m_entries
EntryListType m_entries
Definition: XalanMap.hpp:725
XalanMap::SecondConstructor
ValueConstructionTraits::Constructor SecondConstructor
Definition: XalanMap.hpp:232
XalanMap::m_freeEntries
EntryListType m_freeEntries
Definition: XalanMap.hpp:727
XalanVector::empty
bool empty() const
Definition: XalanVector.hpp:640
XalanMap::m_eraseCount
size_type m_eraseCount
Definition: XalanMap.hpp:731
XalanMap::begin
iterator begin()
Definition: XalanMap.hpp:330
XalanMap::data_type
Value data_type
Definition: XalanMap.hpp:198
XalanMap::operator=
XalanMap & operator=(const XalanMap &theRhs)
Definition: XalanMap.hpp:311
XalanMap::value_type
XALAN_STD_QUALIFIER pair< const key_type, data_type > value_type
Definition: XalanMap.hpp:201
XalanMap::swap
void swap(XalanMap &theRhs)
Definition: XalanMap.hpp:450
XalanMapIterator::Iterator
XalanMapIterator< XalanMapIteratorTraits< value_type >, BaseIterator > Iterator
Definition: XalanMap.hpp:126
PlatformDefinitions.hpp
XalanMap::size
size_type size() const
Definition: XalanMap.hpp:320
XalanMap::Entry::value
value_type * value
Definition: XalanMap.hpp:205
XalanList::back
reference back()
Definition: XalanList.hpp:322
XalanMap::deallocate
void deallocate(value_type *pointer)
Definition: XalanMap.hpp:636
XalanMap::FirstConstructor
KeyConstructionTraits::Constructor FirstConstructor
Definition: XalanMap.hpp:231
XalanListIteratorBase
Definition: XalanList.hpp:64
XalanList::begin
iterator begin()
Definition: XalanList.hpp:268
XalanMap::m_hash
KeyTraits::Hasher m_hash
Definition: XalanMap.hpp:713
XalanMap::calculateNewBucketCapacity
static size_type calculateNewBucketCapacity(size_type theCurrentSize, size_type theExtraCapacity)
Definition: XalanMap.hpp:644
XalanMapIterator::operator*
reference operator*() const
Definition: XalanMap.hpp:151
XalanMap::doRemoveEntry
void doRemoveEntry(const iterator &toRemovePos)
Definition: XalanMap.hpp:531
XalanMap::EntryListIterator
EntryListType::iterator EntryListIterator
Definition: XalanMap.hpp:220
XalanMap::Entry::erased
bool erased
Definition: XalanMap.hpp:206
XalanVector::swap
void swap(ThisType &theOther)
Definition: XalanVector.hpp:854
XalanMap::EntryListType
XalanList< Entry > EntryListType
Definition: XalanMap.hpp:215
XalanMap::doHash
size_type doHash(const Key &key) const
Definition: XalanMap.hpp:585
XalanHasher
Definition: XalanMap.hpp:50

Interpreting class diagrams

Doxygen and GraphViz are used to generate this API documentation from the Xalan-C header files.

Xalan-C++ XSLT Processor Version 1.11
Copyright © 1999-2012 The Apache Software Foundation.
All Rights Reserved.

Apache Logo