XalanMap< Key, Value, KeyTraits > Class Template Reference

Xalan implementation of a hashtable. More...

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. More...
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  )

staticprotected

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>>

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

(

)

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>>

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