RadixTree< T > Class Template Reference

A key/value dictionary for string keys. More...

#include <RadixTree.h>

Inheritance diagram for RadixTree< T >:

Collaboration diagram for RadixTree< T >:

Classes
class	Node

Public Types
typedef ::Iterator< T, Node >	Iterator
typedef Iterator::Const	ConstIterator
typedef Result< T, bool >	LookupType

Public Member Functions
	RadixTree ()
	RadixTree (const RadixTree< T > &x)
	RadixTree (bool bCaseSensitive)
	~RadixTree ()
RadixTree &	operator= (const RadixTree &x)
size_t	count () const
void	insert (const String &key, const T &value)
MUST_USE_RESULT bool	lookup (const String &key, T &value) const
template<typename U = T>
pedigree_std::enable_if< pedigree_std::is_same< U, T >::value &&!pedigree_std::is_same< U, void * >::value, LookupType >::type	lookup (const String &key) const
void	remove (const String &key)
void	clear ()
Iterator	erase (Iterator iter)
Iterator	begin ()
ConstIterator	begin () const
Iterator	end ()
ConstIterator	end () const
void	dump (void(*emit_line)(const char *s)) const

Private Member Functions
Node *	cloneNode (Node *node, Node *parent)
Node *	getNewNode ()
void	returnNode (Node *p)

Private Attributes
size_t	m_nItems
Node *	m_pRoot
const bool	m_bCaseSensitive
ObjectPool< Node >	m_NodePool

Detailed Description

template<class T>
class RadixTree< T >

A key/value dictionary for string keys.

Dictionary class, aka Map for string keys. This is implemented as a Radix Tree - also known as a Patricia Trie.

Definition at line 46 of file RadixTree.h.

Member Typedef Documentation

ConstIterator

template<class T >

typedef Iterator::Const RadixTree< T >::ConstIterator

Type of the constant bidirectional iterator

Definition at line 183 of file RadixTree.h.

Iterator

template<class T >

typedef ::Iterator<T, Node> RadixTree< T >::Iterator

Type of the bidirectional iterator

Definition at line 181 of file RadixTree.h.

LookupType

template<class T >

typedef Result<T, bool> RadixTree< T >::LookupType

Definition at line 184 of file RadixTree.h.

Member Function Documentation

begin() [1/2]

template<class T >

Iterator RadixTree< T >::begin ( )

inline

Get an iterator pointing to the beginning of the List

Returns

iterator pointing to the beginning of the List

Definition at line 250 of file RadixTree.h.

begin() [2/2]

template<class T >

ConstIterator RadixTree< T >::begin ( ) const

inline

Get a constant iterator pointing to the beginning of the List

Returns

constant iterator pointing to the beginning of the List

Definition at line 258 of file RadixTree.h.

end() [1/2]

template<class T >

Iterator RadixTree< T >::end ( )

inline

Get an iterator pointing to the end of the List + 1

Returns

iterator pointing to the end of the List + 1

Definition at line 266 of file RadixTree.h.

end() [2/2]

template<class T >

ConstIterator RadixTree< T >::end ( ) const

inline

Get a constant iterator pointing to the end of the List + 1

Returns

constant iterator pointing to the end of the List + 1

Definition at line 271 of file RadixTree.h.

erase()

template<class T >

Iterator RadixTree< T >::erase ( Iterator  iter )

inline

Erase one Element

Definition at line 240 of file RadixTree.h.

References Iterator< originalT, Struct, FunctionPrev, FunctionNext, T >::__getNode(), and RadixTree< T >::Node::next().

getNewNode()

template<class T >

Node * RadixTree< T >::getNewNode ( )

inlineprivate

Obtain a new Node with the same case-sensitive flag.

Definition at line 282 of file RadixTree.h.

References RadixTree< T >::Node::m_pParent, and RadixTree< T >::Node::m_pParentTree.

lookup()

template<class T >

template<typename U = T>

pedigree_std::enable_if< pedigree_std::is_same< U, T >::value &&!pedigree_std::is_same< U, void * >::value, LookupType >::type RadixTree< T >::lookup ( const String &  key ) const

inline

Ergonomic lookup for locally instantiated trees.

RadixTree<void *> is explicitly instantiated by the kernel and consumed by modules built with another compiler, so its aggregate Result-returning overload is intentionally unavailable.

Definition at line 226 of file RadixTree.h.

returnNode()

template<class T >

void RadixTree< T >::returnNode ( Node *  p )

inlineprivate

Return a Node so it can be allocated again.

Definition at line 289 of file RadixTree.h.

References RadixTree< T >::Node::m_bHasValue, RadixTree< T >::Node::m_Key, RadixTree< T >::Node::m_pParent, and RadixTree< T >::Node::value.

Referenced by RadixTree< T >::RadixTree().

Here is the caller graph for this function:

Member Data Documentation

m_bCaseSensitive

template<class T >

const bool RadixTree< T >::m_bCaseSensitive

private

Whether matches are case-sensitive or not.

Definition at line 306 of file RadixTree.h.

Referenced by RadixTree< T >::Node::matchKey().

m_nItems

template<class T >

size_t RadixTree< T >::m_nItems

private

Number of items in the tree.

Definition at line 302 of file RadixTree.h.

Referenced by RadixTree< T >::RadixTree().

m_NodePool

template<class T >

ObjectPool<Node> RadixTree< T >::m_NodePool

private

Pool of node objects (to reduce impact of lots of node allocs/deallocs).

Definition at line 309 of file RadixTree.h.

m_pRoot

template<class T >

Node* RadixTree< T >::m_pRoot

private

The tree's root.

Definition at line 304 of file RadixTree.h.

Referenced by RadixTree< T >::RadixTree().

---

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

• RadixTree.h