Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.10

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

Interpreting class diagrams

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

dot

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

Apache Logo