C++ API - frepple::utils::Tree Class Reference

Classes | Public Types | Public Member Functions | List of all members
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:
Inheritance graph
[legend]

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 ()
 

Additional Inherited Members

- Protected Member Functions inherited from frepple::utils::NonCopyable
 NonCopyable ()
 
 ~NonCopyable ()
 

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 3640 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 3648 of file utils.h.

Constructor & Destructor Documentation

frepple::utils::Tree::Tree ( bool  b = false)
inline

Default constructor.

Definition at line 3745 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 3759 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 3765 of file utils.h.

void frepple::utils::Tree::clear ( )

Remove all elements from the tree.

Definition at line 29 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 3775 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 3771 of file utils.h.

void frepple::utils::Tree::erase ( TreeNode *  x)

Remove a node from the tree.

Definition at line 176 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 3814 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 3831 of file utils.h.

TreeNode* frepple::utils::Tree::insert ( TreeNode *  v)
inline

Insert a new node in the tree.

Definition at line 3851 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 46 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 3778 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 3795 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 362 of file name.cpp.

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