frepple::utils::Tree Class Reference

This class implements a binary tree data structure. It is used as a container for entities keyed by their name. More...

#include <utils.h>

Inheritance diagram for frepple::utils::Tree:

List of all members.

Classes
class	TreeNode
	This class represents a node in the tree. More...
Public Types
enum	NodeColor { red, black, none }
Public Member Functions
TreeNode *	begin () const
void	clear ()
bool	empty () const
TreeNode *	end () const
void	erase (TreeNode *x)
TreeNode *	find (const string &k) const
TreeNode *	findLowerBound (const string &k, bool *f) const
TreeNode *	insert (TreeNode *v)
TreeNode *	insert (TreeNode *v, TreeNode *hint)
void	rename (TreeNode *obj, string newname)
size_t	size () const
	Tree (bool b=false)
void	verify () const
	~Tree ()

---

Detailed Description

This class implements a binary tree data structure. It is used as a container for entities keyed by their name.

Technically, the data structure can be described as a red-black tree with intrusive tree nodes.

See also:

HasName

Definition at line 3409 of file utils.h.

---

Member Enumeration Documentation

enum frepple::utils::Tree::NodeColor

The algorithm assigns a color to each node in the tree. The color is used to keep the tree balanced.
A node with color 'none' is a node that hasn't been inserted yet in the tree.

Enumerator:

red
black
none

Definition at line 3417 of file utils.h.

---

Constructor & Destructor Documentation

frepple::utils::Tree::Tree

(

bool

b = false

)

[inline]

Default constructor.

Definition at line 3514 of file utils.h.

frepple::utils::Tree::~Tree

(

)

[inline]

Destructor.
By default, the objects in the tree are not deleted when the tree is deleted. This is done for performance reasons: the program can shut down faster.

Definition at line 3528 of file utils.h.

---

Member Function Documentation

TreeNode* frepple::utils::Tree::begin

(

)

const [inline]

Returns an iterator to the start of the list.
The user will need to take care of properly acquiring a read lock on on the tree object.

Definition at line 3534 of file utils.h.

void frepple::utils::Tree::clear

(

)

Remove all elements from the tree.

Definition at line 36 of file name.cpp.

bool frepple::utils::Tree::empty

(

)

const [inline]

Returns true if the list is empty.
Its complexity is O(1).

Definition at line 3544 of file utils.h.

TreeNode* frepple::utils::Tree::end

(

)

const [inline]

Returns an iterator pointing beyond the last element in the list.
The user will need to take care of properly acquiring a read lock on on the tree object.

Definition at line 3540 of file utils.h.

void frepple::utils::Tree::erase

(

TreeNode *

x

)

Remove a node from the tree.

Definition at line 190 of file name.cpp.

TreeNode* frepple::utils::Tree::find

(

const string &

k

)

const [inline]

Search for an element in the tree.
Profiling shows this function has a significant impact on the CPU time (mainly because of the string comparisons), and has been optimized as much as possible.

Definition at line 3591 of file utils.h.

TreeNode* frepple::utils::Tree::findLowerBound	(	const string &	k,
		bool *	f
	)		const [inline]

Find the element with this given key or the element immediately preceding it.
The second argument is a boolean that is set to true when the element is found in the list.

Definition at line 3609 of file utils.h.

TreeNode* frepple::utils::Tree::insert

(

TreeNode *

v

)

[inline]

Insert a new node in the tree.

Definition at line 3630 of file utils.h.

Tree::TreeNode * frepple::utils::Tree::insert	(	TreeNode *	v,
		TreeNode *	hint
	)

Insert a new node in the tree. The second argument is a hint on the proper location in the tree.
Profiling shows this function has a significant impact on the cpu time (mainly because of the string comparisons), and has been optimized as much as possible.

Definition at line 57 of file name.cpp.

void frepple::utils::Tree::rename	(	TreeNode *	obj,
		string	newname
	)		[inline]

Renames an existing node, and adjusts its position in the tree.

Definition at line 3551 of file utils.h.

size_t frepple::utils::Tree::size

(

)

const [inline]

This method returns the number of nodes inserted in this tree.
Its complexity is O(1), so it can be called on large trees without any performance impact.

Definition at line 3568 of file utils.h.

void frepple::utils::Tree::verify

(

)

const

Verifies the integrity of the tree and returns true if everything is correct.
The tree should be locked before calling this function.

Definition at line 379 of file name.cpp.

---

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

• utils.h
• name.cpp