19 #if !defined(XALANMAP_HEADER_GUARD_1357924680) 20 #define XALANMAP_HEADER_GUARD_1357924680 39 XALAN_CPP_NAMESPACE_BEGIN
43 #pragma warning(disable: 4189) 49 class XalanHasher :
public XALAN_STD_QUALIFIER unary_function<Key, size_type>
54 const char *byteArray =
reinterpret_cast<const char*
>(&key);
58 for (
size_type i = 0; i <
sizeof(Key); ++i)
60 result = (result << 1) ^ byteArray[i];
98 template <
class Value>
106 template <
class Value>
114 template <
class XalanMapTraits,
class BaseIterator>
119 typedef typename XalanMapTraits::pointer
pointer;
129 baseIterator(theRhs.baseIterator)
153 return *baseIterator->value;
158 return baseIterator->value;
168 return !(theRhs == *
this);
201 typedef XALAN_STD_QUALIFIER pair<const key_type, data_type>
value_type;
236 eDefaultMinBuckets = 29u,
237 eDefaultEraseThreshold = 50u,
238 eMinimumBucketSize = 5u
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),
251 m_entries(theMemoryManager),
252 m_freeEntries(theMemoryManager),
253 m_buckets(theMemoryManager),
255 m_eraseThreshold(eraseThreshold)
261 MemoryManager& theMemoryManager) :
262 m_memoryManager(&theMemoryManager),
263 m_loadFactor(theRhs.m_loadFactor),
264 m_minBuckets(theRhs.m_minBuckets),
266 m_entries(theMemoryManager),
267 m_freeEntries(theMemoryManager),
269 size_type(m_loadFactor * theRhs.size()) + 1,
270 BucketType(*m_memoryManager),
273 m_eraseThreshold(theRhs.m_eraseThreshold)
275 const_iterator entry = theRhs.
begin();
277 while(entry != theRhs.
end())
283 assert(m_size == theRhs.
m_size);
289 assert (m_memoryManager != 0);
291 return *m_memoryManager;
298 if (!m_buckets.empty())
300 EntryListIterator toRemove = m_freeEntries.begin();
302 while(toRemove != m_freeEntries.end())
304 deallocate(toRemove->value);
313 XalanMap theTemp(theRhs, *m_memoryManager);
332 return m_entries.begin();
337 return const_cast<XalanMap*
>(
this)->begin();
342 return m_entries.end();
345 const_iterator
end()
const 347 return const_cast<XalanMap*
>(
this)->end();
350 iterator
find(
const key_type& key)
354 assert(m_buckets.empty() ==
false);
356 const size_type index = doHash(key);
357 assert(index < m_buckets.size());
359 BucketType& bucket = m_buckets[index];
360 BucketIterator pos = bucket.begin();
362 while (pos != bucket.end())
364 if (!(*pos)->erased && m_equals(key, (*pos)->value->first))
366 return iterator(*pos);
375 const_iterator
find(
const key_type& key)
const 377 return const_cast<XalanMap *
>(
this)->find(key);
382 iterator pos = find(key);
386 pos = doCreateEntry(key);
389 return (*pos).second;
395 insert(value.first, value.second);
398 void insert(
const key_type& key,
const data_type& data)
400 const const_iterator pos = find(key);
404 doCreateEntry(key, &data);
416 size_type
erase(
const key_type& key)
418 const iterator pos = find(key);
436 TableIterator bucketPos = m_buckets.begin();
438 while (bucketPos != m_buckets.end())
447 assert(m_entries.empty());
452 const size_type tempSize = m_size;
456 MemoryManager*
const tempMemoryManager = m_memoryManager;
460 const size_type tempEraseCount = m_eraseCount;
464 const size_type tempEraseTheshold = m_eraseThreshold;
478 if (m_buckets.empty())
483 BucketType(*m_memoryManager));
487 if (
size_type(m_loadFactor * size()) > m_buckets.size())
492 const size_type index = doHash(key);
494 if (m_freeEntries.empty())
496 m_freeEntries.push_back(Entry(allocate(1)));
500 Entry& newEntry = m_freeEntries.back();
501 newEntry.erased =
false;
503 FirstConstructor::construct(
504 const_cast<key_type*>(&newEntry.value->first),
510 SecondConstructor::construct(
511 &newEntry.value->second,
517 SecondConstructor::construct(
518 &newEntry.value->second,
522 m_entries.splice(m_entries.end(), m_freeEntries, --m_freeEntries.end());
524 m_buckets[index].push_back(--m_entries.end());
528 return iterator(--m_entries.end());
533 value_type& toRemove = *toRemovePos;
534 #if defined(_MSC_VER) && _MSC_VER <= 1300 535 toRemove.value_type::~value_type();
537 toRemove.~value_type();
539 m_freeEntries.splice(
554 doRemoveEntry(begin());
561 assert(pos != end());
567 if (m_eraseCount == m_eraseThreshold)
578 size_type modulus)
const 580 assert(modulus != 0);
582 return m_hash(key) % modulus;
587 return doHash(key, m_buckets.size());
593 const size_type theNewSize =
size_type(1.6 * size());
594 assert(theNewSize != 0);
596 BucketTableType temp(
598 BucketType(*m_memoryManager),
602 EntryListIterator entryPos = m_entries.begin();
604 while (entryPos != m_entries.end())
606 const size_type index =
608 entryPos->value->first,
618 m_buckets.swap(temp);
624 const size_type theBytesNeeded = size *
sizeof(value_type);
626 assert(m_memoryManager != 0);
628 void* pointer = m_memoryManager->allocate(theBytesNeeded);
630 assert(pointer != 0);
632 return reinterpret_cast<value_type*
>(pointer);
638 assert(m_memoryManager != 0);
640 m_memoryManager->deallocate(pointer);
645 size_type theCurrentSize,
646 size_type theExtraCapacity)
648 assert(theExtraCapacity > theCurrentSize);
655 return theCurrentSize == 0 ?
663 for(TableIterator i = m_buckets.begin();
664 i != m_buckets.end();
667 BucketType& theCurrentBucket = *i;
669 BucketIterator j = theCurrentBucket.
begin();
671 while(j != theCurrentBucket.
end())
673 if ((*j)->erased ==
true)
675 j = theCurrentBucket.
erase(j);
686 const size_type theCurrentSize =
687 theCurrentBucket.
size();
689 const size_type theExtraCapacity =
690 theCurrentBucket.
capacity() - theCurrentSize;
692 if (theExtraCapacity > theCurrentSize)
694 const size_type theNewCapacity =
695 calculateNewBucketCapacity(
702 BucketType theTempBucket(
707 theCurrentBucket.
swap(theTempBucket);
745 #if defined(_MSC_VER) 751 XALAN_CPP_NAMESPACE_END
755 #endif // XALANMAP_HEADER_GUARD_1357924680
size_type m_eraseThreshold
XalanMap & operator=(const XalanMap &theRhs)
ptrdiff_t difference_type
iterator doCreateEntry(const key_type &key, const data_type *data=0)
size_type operator()(const Key &key) const
void doErase(iterator pos)
XalanMapTraits::pointer pointer
XalanMap(const XalanMap &theRhs, MemoryManager &theMemoryManager)
BucketTableType m_buckets
XalanMapTraits::value_type value_type
XalanMapIterator(const Iterator &theRhs)
size_type erase(const key_type &key)
size_type capacity() const
static size_type calculateNewBucketCapacity(size_type theCurrentSize, size_type theExtraCapacity)
data_type & operator[](const key_type &key)
MemoryManager * m_memoryManager
XalanMapIterator< XalanMapIteratorTraits< value_type >, typename EntryListType::iterator > iterator
BucketTableType::iterator TableIterator
void doRemoveEntry(const iterator &toRemovePos)
XalanList< Entry > EntryListType
size_type doHash(const Key &key) const
value_type * allocate(size_type size)
iterator find(const key_type &key)
void push_back(const value_type &data)
XalanHasher< Key > Hasher
bool operator==(const XalanMapIterator &theRhs) const
XalanMapIterator & operator++()
pointer operator->() const
XalanMapIterator operator++(int)
XalanVector< typename EntryListType::iterator > BucketType
bool operator!=(const XalanMapIterator &theRhs) const
XalanMapTraits::reference reference
const size_type m_minBuckets
KeyConstructionTraits::Constructor FirstConstructor
BaseIterator baseIterator
void swap(XalanVector< Type > &theLHS, XalanVector< Type > &theRHS)
XALAN_CPP_NAMESPACE_BEGIN typedef size_t size_type
ValueConstructionTraits::Constructor SecondConstructor
EntryListType m_freeEntries
void insert(const value_type &value)
void deallocate(value_type *pointer)
const_iterator end() const
iterator erase(iterator theFirst, iterator theLast)
const_iterator begin() const
XalanMapIterator< XalanMapIteratorTraits< value_type >, BaseIterator > Iterator
void swap(XalanMap &theRhs)
void insert(const key_type &key, const data_type &data)
XALAN_STD_QUALIFIER equal_to< Key > Comparator
XalanMapIterator< XalanMapConstIteratorTraits< value_type >, typename EntryListType::iterator > const_iterator
void swap(ThisType &theOther)
Key key_type
Each map entry is stored in a linked list where an entry consists of a pointer to the key/value pair ...
BucketType::iterator BucketIterator
XALAN_STD_QUALIFIER pair< const key_type, data_type > value_type
KeyTraits::Comparator m_equals
Xalan implementation of a hashtable.
reference operator*() const
MemoryManager & getMemoryManager()
XalanMapIterator(const BaseIterator &theRhs)
XALAN_STD_QUALIFIER bidirectional_iterator_tag iterator_category
size_type doHash(const Key &key, size_type modulus) const
XalanVector< BucketType, ConstructWithMemoryManagerTraits< BucketType > > BucketTableType
const_iterator find(const key_type &key) const
XalanDOMString & insert(XalanDOMString &theString, XalanDOMString::size_type thePosition, const XalanDOMString &theStringToInsert)
Insert a string into another string.
EntryListType::iterator EntryListIterator
Entry(value_type *theValue)
XalanMap(MemoryManager &theMemoryManager, double loadFactor=0.75, size_type minBuckets=eDefaultMinBuckets, size_type eraseThreshold=eDefaultEraseThreshold)