XalanMap< Key, Value, KeyTraits > Class Template Reference

Xalan implementation of a hashtable. More...

List of all members.

Classes

• struct Entry

Public Types

• enum { eDefaultMinBuckets = 29u, eDefaultEraseThreshold = 50u, eMinimumBucketSize = 5u }
• typedef Key key_type

  Each map entry is stored in a linked list where an entry consists of a pointer to the key/value pair and a flag to indicate whether the entry has been erased.
  

• typedef Value data_type
• typedef size_t size_type
• typedef XALAN_STD_QUALIFIER
  pair< const key_type,
  data_type > value_type
• typedef XalanList< Entry > EntryListType
• typedef XalanVector< typename
  EntryListType::iterator > BucketType
• typedef XalanVector
  < BucketType,
  ConstructWithMemoryManagerTraits
  < BucketType > > BucketTableType
• typedef EntryListType::iterator EntryListIterator
• typedef BucketTableType::iterator TableIterator
• typedef BucketType::iterator BucketIterator
• typedef XalanMapIterator
  < XalanMapIteratorTraits
  < value_type >, typename
  EntryListType::iterator > iterator
• typedef XalanMapIterator
  < XalanMapConstIteratorTraits
  < value_type >, typename
  EntryListType::iterator > const_iterator
• typedef
  MemoryManagedConstructionTraits
  < key_type >::Constructor FirstConstructor
• typedef
  MemoryManagedConstructionTraits
  < data_type >::Constructor SecondConstructor

Public Member Functions

• XalanMap (MemoryManagerType &theMemoryManager, float loadFactor=0.75, size_type minBuckets=eDefaultMinBuckets, size_type eraseThreshold=eDefaultEraseThreshold)
• XalanMap (const XalanMap &theRhs, MemoryManagerType &theMemoryManager)
• MemoryManagerType & getMemoryManager ()
• ~XalanMap ()
• XalanMap & operator= (const XalanMap &theRhs)
• size_type size () const
• bool empty () const
• iterator begin ()
• const_iterator begin () const
• iterator end ()
• const_iterator end () const
• iterator find (const key_type &key)
• const_iterator find (const key_type &key) const
• data_type & operator[] (const key_type &key)
• void insert (const value_type &value)
• void insert (const key_type &key, const data_type &data)
• void erase (iterator pos)
• size_type erase (const key_type &key)
• void clear ()
• void swap (XalanMap &theRhs)

Protected Member Functions

• iterator doCreateEntry (const key_type &key, const data_type *data=0)
• void doRemoveEntry (const iterator &toRemovePos)
• void doRemoveEntries ()
• void doErase (iterator pos)
• size_type doHash (const Key &key, size_type modulus) const
• size_type doHash (const Key &key) const
• void rehash ()
• value_type * allocate (size_type size)
• void deallocate (value_type *pointer)
• void compactBuckets ()

Static Protected Member Functions

• static size_type calculateNewBucketCapacity (size_type theCurrentSize, size_type theExtraCapacity)

Protected Attributes

• KeyTraits::Hasher m_hash
• KeyTraits::Comparator m_equals
• MemoryManagerType * m_memoryManager
• float m_loadFactor
• const size_type m_minBuckets
• size_type m_size
• EntryListType m_entries
• EntryListType m_freeEntries
• BucketTableType m_buckets
• size_type m_eraseCount
• size_type m_eraseThreshold

---

Detailed Description

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>
class XalanMap< Key, Value, KeyTraits >

Xalan implementation of a hashtable.

---

Member Typedef Documentation

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef BucketType::iterator XalanMap< Key, Value, KeyTraits >::BucketIterator

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef XalanVector<BucketType, ConstructWithMemoryManagerTraits<BucketType> > XalanMap< Key, Value, KeyTraits >::BucketTableType

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef XalanVector<typename EntryListType::iterator> XalanMap< Key, Value, KeyTraits >::BucketType

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef XalanMapIterator< XalanMapConstIteratorTraits<value_type>, typename EntryListType::iterator> XalanMap< Key, Value, KeyTraits >::const_iterator

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef Value XalanMap< Key, Value, KeyTraits >::data_type

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef EntryListType::iterator XalanMap< Key, Value, KeyTraits >::EntryListIterator

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef XalanList<Entry> XalanMap< Key, Value, KeyTraits >::EntryListType

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef MemoryManagedConstructionTraits<key_type>::Constructor XalanMap< Key, Value, KeyTraits >::FirstConstructor

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef XalanMapIterator< XalanMapIteratorTraits<value_type>, typename EntryListType::iterator> XalanMap< Key, Value, KeyTraits >::iterator

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef Key XalanMap< Key, Value, KeyTraits >::key_type

Each map entry is stored in a linked list where an entry consists of a pointer to the key/value pair and a flag to indicate whether the entry has been erased.

The hash buckets are a vector of pointers into the entry list. Deleted entries are spliced into another list and marked 'erased'.

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef MemoryManagedConstructionTraits<data_type>::Constructor XalanMap< Key, Value, KeyTraits >::SecondConstructor

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef size_t XalanMap< Key, Value, KeyTraits >::size_type

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef BucketTableType::iterator XalanMap< Key, Value, KeyTraits >::TableIterator

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

typedef XALAN_STD_QUALIFIER pair<const key_type, data_type> XalanMap< Key, Value, KeyTraits >::value_type

---

Member Enumeration Documentation

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

anonymous enum

Enumerator:

eDefaultMinBuckets
eDefaultEraseThreshold
eMinimumBucketSize

---

Constructor & Destructor Documentation

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

XalanMap< Key, Value, KeyTraits >::XalanMap	(	MemoryManagerType &	theMemoryManager,
		float	loadFactor = 0.75,
		size_type	minBuckets = eDefaultMinBuckets,
		size_type	eraseThreshold = eDefaultEraseThreshold
	)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

XalanMap< Key, Value, KeyTraits >::XalanMap	(	const XalanMap< Key, Value, KeyTraits > &	theRhs,
		MemoryManagerType &	theMemoryManager
	)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

XalanMap< Key, Value, KeyTraits >::~XalanMap

(

)

---

Member Function Documentation

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

value_type* XalanMap< Key, Value, KeyTraits >::allocate

(

size_type

size

)

[protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

iterator XalanMap< Key, Value, KeyTraits >::begin

(

)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

const_iterator XalanMap< Key, Value, KeyTraits >::begin

(

)

const

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

static size_type XalanMap< Key, Value, KeyTraits >::calculateNewBucketCapacity	(	size_type	theCurrentSize,
		size_type	theExtraCapacity
	)		[static, protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

void XalanMap< Key, Value, KeyTraits >::clear

(

)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

void XalanMap< Key, Value, KeyTraits >::compactBuckets

(

)

[protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

void XalanMap< Key, Value, KeyTraits >::deallocate

(

value_type *

pointer

)

[protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

iterator XalanMap< Key, Value, KeyTraits >::doCreateEntry	(	const key_type &	key,
		const data_type *	data = 0
	)		[protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

void XalanMap< Key, Value, KeyTraits >::doErase

(

iterator

pos

)

[protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

size_type XalanMap< Key, Value, KeyTraits >::doHash	(	const Key &	key,
		size_type	modulus
	)		const [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

size_type XalanMap< Key, Value, KeyTraits >::doHash

(

const Key &

key

)

const [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

void XalanMap< Key, Value, KeyTraits >::doRemoveEntries

(

)

[protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

void XalanMap< Key, Value, KeyTraits >::doRemoveEntry

(

const iterator &

toRemovePos

)

[protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

bool XalanMap< Key, Value, KeyTraits >::empty

(

)

const

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

const_iterator XalanMap< Key, Value, KeyTraits >::end

(

)

const

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

iterator XalanMap< Key, Value, KeyTraits >::end

(

)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

void XalanMap< Key, Value, KeyTraits >::erase

(

iterator

pos

)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

size_type XalanMap< Key, Value, KeyTraits >::erase

(

const key_type &

key

)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

iterator XalanMap< Key, Value, KeyTraits >::find

(

const key_type &

key

)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

const_iterator XalanMap< Key, Value, KeyTraits >::find

(

const key_type &

key

)

const

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

MemoryManagerType& XalanMap< Key, Value, KeyTraits >::getMemoryManager

(

)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

void XalanMap< Key, Value, KeyTraits >::insert

(

const value_type &

value

)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

void XalanMap< Key, Value, KeyTraits >::insert	(	const key_type &	key,
		const data_type &	data
	)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

XalanMap& XalanMap< Key, Value, KeyTraits >::operator=

(

const XalanMap< Key, Value, KeyTraits > &

theRhs

)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

data_type& XalanMap< Key, Value, KeyTraits >::operator[]

(

const key_type &

key

)

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

void XalanMap< Key, Value, KeyTraits >::rehash

(

)

[protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

size_type XalanMap< Key, Value, KeyTraits >::size

(

)

const

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

void XalanMap< Key, Value, KeyTraits >::swap

(

XalanMap< Key, Value, KeyTraits > &

theRhs

)

---

Member Data Documentation

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

BucketTableType XalanMap< Key, Value, KeyTraits >::m_buckets [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

EntryListType XalanMap< Key, Value, KeyTraits >::m_entries [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

KeyTraits::Comparator XalanMap< Key, Value, KeyTraits >::m_equals [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

size_type XalanMap< Key, Value, KeyTraits >::m_eraseCount [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

size_type XalanMap< Key, Value, KeyTraits >::m_eraseThreshold [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

EntryListType XalanMap< Key, Value, KeyTraits >::m_freeEntries [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

KeyTraits::Hasher XalanMap< Key, Value, KeyTraits >::m_hash [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

float XalanMap< Key, Value, KeyTraits >::m_loadFactor [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

MemoryManagerType* XalanMap< Key, Value, KeyTraits >::m_memoryManager [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

const size_type XalanMap< Key, Value, KeyTraits >::m_minBuckets [protected]

template<class Key, class Value, class KeyTraits = XalanMapKeyTraits<Key>>

size_type XalanMap< Key, Value, KeyTraits >::m_size [protected]

---

The documentation for this class was generated from the following file:

• XalanMap.hpp