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 Iterator::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)

bool	tryInsert (const K &key, const E &value)

bool	tryInsert (const K &key, E &&value)

E	lookup (const K &key) const

E *	find (const K &key)

const E &	lookupRef (const K &key, const E &failed=E()) const

bool	lowerBound (const K &key, K &foundKey, E &foundValue) const

bool	floorBound (const K &key, K &foundKey, E &foundValue) const

bool	contains (const K &key) const

void	remove (const K &key)

bool	take (const K &key, E &element)

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, bool &inserted)

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

◆ ConstIterator

template<class K , class E >

typedef Iterator::Const Tree< K, E >::ConstIterator

Constant random-access iterator for the Tree

Definition at line 112 of file Tree.h.

◆ Iterator

template<class K , class E >

typedef ::TreeIterator<E, IteratorNode, &IteratorNode::previous, &IteratorNode::next, K> Tree< K, E >::Iterator

Definition at line 110 of file Tree.h.

Constructor & Destructor Documentation

◆ Tree() [1/2]

template<class K , class E >

Tree< K, E >::Tree ( )

inline

The default constructor, does nothing

Definition at line 115 of file Tree.h.

◆ Tree() [2/2]

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 119 of file Tree.h.

◆ ~Tree()

template<class K , class E >

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

inline

The destructor, deallocates memory

Definition at line 124 of file Tree.h.

Member Function Documentation

◆ balanceFactor()

template<class K , class E >

int Tree< K, E >::balanceFactor ( Node * n )

inlineprivate

Definition at line 515 of file Tree.h.

◆ begin() [1/2]

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 402 of file Tree.h.

Referenced by CacheManager::acquireCache(), PosixSubsystem::acquireNextFileDescriptor(), MemoryMappedFile::clone(), PosixSubsystem::copyDescriptors(), Ext2Filesystem::deviceRemoved(), DynamicLinker::DynamicLinker(), CacheManager::executeRequest(), PosixSubsystem::freeMultipleFds(), VFS::getFilesystemAt(), UserManager::getGroup(), UserManager::getUser(), Scheduler::hasActiveSyscallLocked(), SymbolTable::lookup(), PosixSubsystem::PosixSubsystem(), MemoryMapManager::prepareFileResize(), VFS::removeEphemeralFiles(), Scheduler::sampleLoadAverage(), MemoryMappedFile::setPermissions(), Ext2Filesystem::shutdown(), MemoryMappedFile::stageSlice(), Ext2Filesystem::sync(), VFS::syncAll(), PosixSubsystem::~PosixSubsystem(), and VFS::~VFS().

Here is the caller graph for this function:

◆ begin() [2/2]

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 417 of file Tree.h.

◆ clear()

template<class K , class E >

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

inline

Clear the Vector

Definition at line 383 of file Tree.h.

Referenced by MemoryMappedFile::clearMappings(), Ext2Filesystem::shutdown(), PosixSubsystem::~PosixSubsystem(), and VFS::~VFS().

Here is the caller graph for this function:

◆ contains()

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 287 of file Tree.h.

Referenced by MappingList< Object >::reserveBack(), and MemoryMappedFile::split().

Here is the caller graph for this function:

◆ copyFrom()

template<class K , class E >

void Tree< K, E >::copyFrom ( const Tree< K, E > & other )

inlineprivate

Definition at line 437 of file Tree.h.

◆ count()

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 142 of file Tree.h.

Referenced by MemoryMappedFile::getMappingCount(), MemoryMapManager::prepareFileResize(), Scheduler::sampleLoadAverage(), CacheManager::shutdown(), MemoryMappedFile::stageSlice(), Ext2Filesystem::sync(), and VFS::syncAll().

Here is the caller graph for this function:

◆ createInsertionNode()

template<class K , class E >

Node * Tree< K, E >::createInsertionNode	(	const K &	key,
		bool &	inserted
	)

inlineprivate

Definition at line 572 of file Tree.h.

◆ end() [1/2]

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 427 of file Tree.h.

Referenced by CacheManager::acquireCache(), PosixSubsystem::acquireNextFileDescriptor(), MemoryMappedFile::clone(), PosixSubsystem::copyDescriptors(), Ext2Filesystem::deviceRemoved(), DynamicLinker::DynamicLinker(), CacheManager::executeRequest(), PosixSubsystem::freeMultipleFds(), VFS::getFilesystemAt(), UserManager::getGroup(), UserManager::getUser(), Scheduler::hasActiveSyscallLocked(), SymbolTable::lookup(), PosixSubsystem::PosixSubsystem(), MemoryMapManager::prepareFileResize(), VFS::removeEphemeralFiles(), Scheduler::sampleLoadAverage(), MemoryMappedFile::setPermissions(), Ext2Filesystem::shutdown(), MemoryMappedFile::stageSlice(), Ext2Filesystem::sync(), VFS::syncAll(), PosixSubsystem::~PosixSubsystem(), and VFS::~VFS().

Here is the caller graph for this function:

◆ end() [2/2]

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 432 of file Tree.h.

◆ erase()

template<class K , class E >

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

inline

Erase one Element

Definition at line 393 of file Tree.h.

◆ find()

template<class K , class E >

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

inline

Returns a mutable value, or nullptr if the key is absent. Insertions and rotations preserve the pointer; removing its key or clearing the tree does not.

Definition at line 208 of file Tree.h.

◆ floorBound()

template<class K , class E >

bool Tree< K, E >::floorBound	(	const K &	key,
		K &	foundKey,
		E &	foundValue
	)		const

inline

Copies the greatest key less than or equal to the query and its value. Returns false without changing outputs if absent.

Definition at line 263 of file Tree.h.

◆ height()

template<class K , class E >

size_t Tree< K, E >::height ( Node * n )

inlineprivate

Definition at line 485 of file Tree.h.

◆ insert() [1/2]

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 149 of file Tree.h.

Referenced by DeviceHashTree::add(), PosixSubsystem::addFileDescriptor(), Scheduler::addThread(), PosixSubsystem::PosixThread::addThreadData(), MemoryMapManager::clone(), PosixSubsystem::copyDescriptors(), PosixSubsystem::duplicateFileDescriptor(), SymbolTable::getOrInsertTree(), PosixSubsystem::installFileDescriptor(), PosixSubsystem::PosixSubsystem(), FatFilesystem::setClusterEntry(), and MemoryMappedFile::trackMapping().

Here is the caller graph for this function:

◆ insert() [2/2]

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 160 of file Tree.h.

◆ lookup()

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 193 of file Tree.h.

Referenced by VFS::acquireMount(), DeviceHashTree::add(), PosixSubsystem::PosixThread::addThreadData(), MemoryMapManager::clone(), PosixSubsystem::closeFileDescriptor(), PosixSubsystem::duplicateFileDescriptor(), Ext2Filesystem::encodeFileHandle(), DeviceHashTree::getDevice(), DeviceHashTree::getDevice(), UserManager::getGroup(), MemoryMappedFile::getMapping(), VFS::getMountPath(), PosixSubsystem::PosixThread::getThreadData(), UserManager::getUser(), LwipSocketSyscalls::netconnCallback(), MemoryMapManager::prepareFileResize(), Ext2Filesystem::releaseInode(), VFS::removeDiskFilesystem(), Scheduler::removeThread(), VFS::retireOwnedFilesystem(), VFS::setRootFilesystem(), VFS::syncFilesystem(), Scheduler::threadInSchedule(), and VFS::unregisterFilesystem().

Here is the caller graph for this function:

◆ lookupRef()

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 223 of file Tree.h.

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

Here is the caller graph for this function:

◆ lowerBound()

template<class K , class E >

bool Tree< K, E >::lowerBound	(	const K &	key,
		K &	foundKey,
		E &	foundValue
	)		const

inline

Copies the least key greater than or equal to the query and its value. Copied results let callers resume after mutations without retaining an invalidated iterator. Returns false without changing outputs if absent.

Definition at line 239 of file Tree.h.

Referenced by CacheManager::findNextCache().

Here is the caller graph for this function:

◆ operator=()

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 131 of file Tree.h.

◆ rebalanceNode()

template<class K , class E >

void Tree< K, E >::rebalanceNode ( Node * n )

inlineprivate

Definition at line 519 of file Tree.h.

◆ remove()

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 301 of file Tree.h.

Referenced by LwipSocketSyscalls::lastDescriptorClosed(), Scheduler::removeThread(), PosixSubsystem::PosixThread::removeThreadData(), MappingList< Object >::reserveBack(), and MemoryMappedFile::untrackMapping().

Here is the caller graph for this function:

◆ rotateLeft()

template<class K , class E >

void Tree< K, E >::rotateLeft ( Node * n )

inlineprivate

Definition at line 447 of file Tree.h.

◆ rotateRight()

template<class K , class E >

void Tree< K, E >::rotateRight ( Node * n )

inlineprivate

Definition at line 466 of file Tree.h.

◆ take()

template<class K , class E >

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

inline

Atomically move an element out of the tree and remove its key.

This is useful when releasing the element can run arbitrary teardown: ownership is transferred to the caller before the node is destroyed, so the caller controls where the final release occurs.

Definition at line 363 of file Tree.h.

Referenced by PosixSubsystem::addFileDescriptor(), PosixSubsystem::closeFileDescriptor(), PosixSubsystem::copyDescriptors(), PosixSubsystem::duplicateFileDescriptor(), PosixSubsystem::freeFd(), PosixSubsystem::freeMultipleFds(), VFS::removeDiskFilesystem(), VFS::retireOwnedFilesystem(), and VFS::unregisterFilesystem().

Here is the caller graph for this function:

◆ traverseNode_Insert()

template<class K , class E >

void Tree< K, E >::traverseNode_Insert ( Node * n )

inlineprivate

Definition at line 550 of file Tree.h.

◆ traverseNode_Remove()

template<class K , class E >

void Tree< K, E >::traverseNode_Remove ( Node * n )

inlineprivate

Definition at line 558 of file Tree.h.

◆ tryInsert() [1/2]

template<class K , class E >

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

inline

A failed insertion leaves the tree unchanged; existing keys need no allocation.

Definition at line 169 of file Tree.h.

Referenced by MemoryMapManager::prepareFileResize(), MappingList< Object >::reserveBack(), and MemoryMappedFile::trap().

Here is the caller graph for this function:

◆ tryInsert() [2/2]

template<class K , class E >

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

inline

Definition at line 180 of file Tree.h.

Member Data Documentation

◆ m_Begin

template<class K , class E >

IteratorNode* Tree< K, E >::m_Begin

mutableprivate

Definition at line 620 of file Tree.h.

◆ nItems

template<class K , class E >

size_t Tree< K, E >::nItems

private

Definition at line 618 of file Tree.h.

◆ root

template<class K , class E >

Node* Tree< K, E >::root

private

Definition at line 617 of file Tree.h.

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

Tree.h

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ ConstIterator

◆ Iterator

Constructor & Destructor Documentation

◆ Tree() [1/2]

◆ Tree() [2/2]

◆ ~Tree()

Member Function Documentation

◆ balanceFactor()

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ contains()

◆ copyFrom()

◆ count()

◆ createInsertionNode()

◆ end() [1/2]

◆ end() [2/2]

◆ erase()

◆ find()

◆ floorBound()

◆ height()

◆ insert() [1/2]

◆ insert() [2/2]

◆ lookup()

◆ lookupRef()

◆ lowerBound()

◆ operator=()

◆ rebalanceNode()

◆ remove()

◆ rotateLeft()

◆ rotateRight()

◆ take()

◆ traverseNode_Insert()

◆ traverseNode_Remove()

◆ tryInsert() [1/2]

◆ tryInsert() [2/2]

Member Data Documentation

◆ m_Begin

◆ nItems

◆ root