Xalan-C++ API Documentation

The Xalan C++ XSLT Processor Version 1.10

Classes | Public Types | Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes | List of all members
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< EntryEntryListType
 
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)
 
MemoryManagerTypegetMemoryManager ()
 
 ~XalanMap ()
 
XalanMapoperator= (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_typeoperator[] (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_typeallocate (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
 
MemoryManagerTypem_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:

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