Tree< K, E > Class Template Reference

A key/value dictionary. More...

#include <Tree.h>

Inheritance diagram for Tree< K, E >:

Collaboration diagram for Tree< K, E >:

Classes
class	IteratorNode
struct	Node

Public Types
typedef ::TreeIterator< E, IteratorNode,&IteratorNode::previous,&IteratorNode::next, K >	Iterator
typedef E const *	ConstIterator

Public Member Functions
	Tree ()
	Tree (const Tree &x)
	~Tree ()
Tree &	operator= (const Tree &x)
size_t	count () const
void	insert (const K &key, const E &value)
void	insert (const K &key, E &&value)
E	lookup (const K &key) const
const E &	lookupRef (const K &key, const E &failed=E()) const
bool	contains (const K &key) const
void	remove (const K &key)
void	clear ()
void	erase (Iterator iter)
Iterator	begin ()
ConstIterator	begin () const
Iterator	end ()
ConstIterator	end () const

Private Member Functions
void	copyFrom (const Tree &other)
void	rotateLeft (Node *n)
void	rotateRight (Node *n)
size_t	height (Node *n)
int	balanceFactor (Node *n)
void	rebalanceNode (Node *n)
void	traverseNode_Insert (Node *n)
void	traverseNode_Remove (Node *n)
Node *	createInsertionNode (const K &key)

Private Attributes
Node *	root
size_t	nItems
IteratorNode *	m_Begin

Detailed Description

template<class K, class E>
class Tree< K, E >

A key/value dictionary.

Dictionary class, aka Map. This is implemented as an AVL self-balancing binary search tree.

Definition at line 33 of file Tree.h.

Member Typedef Documentation

template<class K, class E>

typedef E const* Tree< K, E >::ConstIterator

Constant random-access iterator for the Tree

Definition at line 133 of file Tree.h.

Constructor & Destructor Documentation

template<class K, class E>

Tree< K, E >::Tree ( )

inline

The default constructor, does nothing

Definition at line 136 of file Tree.h.

template<class K, class E>

Tree< K, E >::Tree ( const Tree< K, E > &  x )

inline

The copy-constructor

Parameters

[in]

x

the reference object to copy

Definition at line 142 of file Tree.h.

template<class K, class E>

Tree< K, E >::~Tree ( )

inline

The destructor, deallocates memory

Definition at line 148 of file Tree.h.

Member Function Documentation

template<class K, class E>

Iterator Tree< K, E >::begin ( )

inline

Get an iterator pointing to the beginning of the Vector

Returns

iterator pointing to the beginning of the Vector

Definition at line 326 of file Tree.h.

Referenced by PosixSubsystem::copyDescriptors(), PosixSubsystem::freeMultipleFds(), UserManager::getGroup(), UserManager::getUser(), SymbolTable::lookup(), PosixSubsystem::PosixSubsystem(), PosixSubsystem::~PosixSubsystem(), and VFS::~VFS().

Here is the caller graph for this function:

template<class K, class E>

ConstIterator Tree< K, E >::begin ( ) const

inline

Get a constant iterator pointing to the beginning of the Vector

Returns

constant iterator pointing to the beginning of the Vector

Definition at line 342 of file Tree.h.

template<class K, class E>

void Tree< K, E >::clear ( )

inline

Clear the Vector

Definition at line 305 of file Tree.h.

Referenced by PosixSubsystem::freeMultipleFds(), and PosixSubsystem::~PosixSubsystem().

Here is the caller graph for this function:

template<class K, class E>

bool Tree< K, E >::contains ( const K &  key ) const

inline

Reports whether a given key exists in the tree.

Returns

true if the key exists, false otherwise.

Definition at line 226 of file Tree.h.

template<class K, class E>

size_t Tree< K, E >::count ( ) const

inline

Get the number of elements in the Tree

Returns

the number of elements in the Tree

Definition at line 165 of file Tree.h.

template<class K, class E>

Iterator Tree< K, E >::end ( )

inline

Get an iterator pointing to the last element + 1

Returns

iterator pointing to the last element + 1

Definition at line 348 of file Tree.h.

Referenced by PosixSubsystem::copyDescriptors(), PosixSubsystem::freeMultipleFds(), UserManager::getGroup(), UserManager::getUser(), SymbolTable::lookup(), PosixSubsystem::PosixSubsystem(), PosixSubsystem::~PosixSubsystem(), and VFS::~VFS().

Here is the caller graph for this function:

template<class K, class E>

ConstIterator Tree< K, E >::end ( ) const

inline

Get a constant iterator pointing to the last element + 1

Returns

constant iterator pointing to the last element + 1

Definition at line 354 of file Tree.h.

template<class K, class E>

void Tree< K, E >::erase ( Iterator  iter )

inline

Erase one Element

Definition at line 316 of file Tree.h.

template<class K, class E>

void Tree< K, E >::insert ( const K &  key, const E &  value  )

inline

Add an element to the Tree.

Parameters

[in]	key	the key
[in]	value	the element

Definition at line 173 of file Tree.h.

Referenced by VFS::addAlias(), PosixSubsystem::addFileDescriptor(), PosixSubsystem::PosixThread::addThreadData(), PosixSubsystem::copyDescriptors(), UserManager::getGroup(), SymbolTable::getOrInsertTree(), NetworkFilter::installCallback(), VFS::mount(), PosixSubsystem::PosixSubsystem(), and PosixSyscallManager::syscall().

Here is the caller graph for this function:

template<class K, class E>

void Tree< K, E >::insert ( const K &  key, E &&  value  )

inline

Move an element into the Tree.

Parameters

[in]	key	the key
[in]	value	the element

Definition at line 183 of file Tree.h.

template<class K, class E>

E Tree< K, E >::lookup ( const K &  key ) const

inline

Attempts to find an element with the given key.

Returns

the element found, or NULL if not found.

Definition at line 192 of file Tree.h.

Referenced by VFS::addAlias(), PosixSubsystem::PosixThread::addThreadData(), NetworkFilter::filter(), PosixSubsystem::freeFd(), PosixSubsystem::getFileDescriptor(), UserManager::getGroup(), PosixSubsystem::PosixThread::getThreadData(), UserManager::getUser(), NetworkFilter::installCallback(), VFS::mount(), VFS::removeAllAliases(), and PosixSyscallManager::syscall().

Here is the caller graph for this function:

template<class K, class E>

const E& Tree< K, E >::lookupRef ( const K &  key, const E &  failed = E()  ) const

inline

Attempts to find an element with the given key.

Returns

a reference to the element found.

Definition at line 209 of file Tree.h.

Referenced by SymbolTable::getOrInsertTree(), and SymbolTable::lookup().

Here is the caller graph for this function:

template<class K, class E>

Tree& Tree< K, E >::operator= ( const Tree< K, E > &  x )

inline

The assignment operator

Parameters

[in]

x

the object that should be copied

Definition at line 156 of file Tree.h.

template<class K, class E>

void Tree< K, E >::remove ( const K &  key )

inline

Attempts to remove an element with the given key.

Definition at line 242 of file Tree.h.

Referenced by PosixSubsystem::freeFd(), PosixSubsystem::freeMultipleFds(), SymbolTable::insertShared(), VFS::removeAllAliases(), and PosixSubsystem::PosixThread::removeThreadData().

Here is the caller graph for this function:

---

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

• Tree.h