le_redBlackTree.h File Reference

Go to the source code of this file.

Data Structures

struct  le_rbtree_Node_t
 
struct  le_rbtree_Tree_t
 

Typedefs

typedef int(* le_rbtree_CompareFunc_t) (const void *key1Ptr, const void *key2Ptr)
 

Enumerations

enum  le_rbtree_Color_t { LE_RBTREE_NO_COLOR, LE_RBTREE_BLACK, LE_RBTREE_RED }
 

Functions

void le_rbtree_InitTree (le_rbtree_Tree_t *treePtr, le_rbtree_CompareFunc_t compFn)
 
void le_rbtree_InitNode (le_rbtree_Node_t *linkPtr, void *keyPtr)
 
le_rbtree_Node_tle_rbtree_Insert (le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *newLinkPtr)
 
le_rbtree_Node_tle_rbtree_Find (le_rbtree_Tree_t *treePtr, void *keyPtr)
 
le_rbtree_Node_tle_rbtree_Remove (le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *linkPtr)
 
le_rbtree_Node_tle_rbtree_RemoveByKey (le_rbtree_Tree_t *treePtr, void *keyPtr)
 
le_rbtree_Node_tle_rbtree_GetFirst (const le_rbtree_Tree_t *treePtr)
 
le_rbtree_Node_tle_rbtree_GetLast (const le_rbtree_Tree_t *treePtr)
 
le_rbtree_Node_tle_rbtree_GetNext (const le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *currentLinkPtr)
 
le_rbtree_Node_tle_rbtree_GetPrev (const le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *currentLinkPtr)
 
bool le_rbtree_IsEmpty (const le_rbtree_Tree_t *treePtr)
 
size_t le_rbtree_Size (const le_rbtree_Tree_t *treePtr)
 

Detailed Description

Legato Red/Black Tree API include file.

Typedef Documentation

◆ le_rbtree_CompareFunc_t

typedef int(* le_rbtree_CompareFunc_t) (const void *key1Ptr, const void *key2Ptr)

This is a comparator function to compare objects in a tree.

Returns
negative, 0, positive number if the first key is less, equal, or greater than the second one.

Enumeration Type Documentation

◆ le_rbtree_Color_t

Color type for Red-Black tree.

Function Documentation

◆ le_rbtree_Find()

le_rbtree_Node_t* le_rbtree_Find ( le_rbtree_Tree_t treePtr,
void *  keyPtr 
)

Find object in the tree for the given key.

Returns
Pointer to the Node found in the tree. NULL if not found.
Parameters
[in]treePtrTree to get the object from.
[in]keyPtrPointer to the key to be retrieved

◆ le_rbtree_GetFirst()

le_rbtree_Node_t* le_rbtree_GetFirst ( const le_rbtree_Tree_t treePtr)

Get the first (smallest) node in the tree.

Returns
Pointer to the node if successful. NULL if the tree is empty.
Parameters
[in]treePtrTree to get the object from.

◆ le_rbtree_GetLast()

le_rbtree_Node_t* le_rbtree_GetLast ( const le_rbtree_Tree_t treePtr)

Get the last (greatest) node in the tree.

Returns
Pointer to the Node if successful. NULL if the tree is empty.
Parameters
[in]treePtrTree to get the object from.

◆ le_rbtree_GetNext()

le_rbtree_Node_t* le_rbtree_GetNext ( const le_rbtree_Tree_t treePtr,
le_rbtree_Node_t currentLinkPtr 
)

Returns the node next to currentLinkPtr without removing it from the tree. User must ensure that currentLinkPtr is in the tree.

Returns
Pointer to the next link if successful. NULL if there is no node greater than the currentLinkPtr.
Parameters
[in]treePtrTree to get the object from.
[in]currentLinkPtrCurrent node pointer.

◆ le_rbtree_GetPrev()

le_rbtree_Node_t* le_rbtree_GetPrev ( const le_rbtree_Tree_t treePtr,
le_rbtree_Node_t currentLinkPtr 
)

Returns the node previous to currentLinkPtr without removing it from the tree. User must ensure that currentLinkPtr is in the tree.

Returns
Pointer to the previous link if successful. NULL if there is no node smaller than the currentLinkPtr.
Parameters
[in]treePtrTree containing currentLinkPtr.
[in]currentLinkPtrGet the link that is relative to this link.

◆ le_rbtree_InitNode()

void le_rbtree_InitNode ( le_rbtree_Node_t linkPtr,
void *  keyPtr 
)

Initialize the Node Link.

Parameters
[in,out]linkPtrNode link pointer.
[in]keyPtrKey pointer.

◆ le_rbtree_InitTree()

void le_rbtree_InitTree ( le_rbtree_Tree_t treePtr,
le_rbtree_CompareFunc_t  compFn 
)

Initialize the Red-Black Tree.

Parameters
[in]treePtrPointer to the tree object.
[in]compFnPointer to the comparator function.

◆ le_rbtree_Insert()

le_rbtree_Node_t* le_rbtree_Insert ( le_rbtree_Tree_t treePtr,
le_rbtree_Node_t newLinkPtr 
)

Insert a new node in the tree. If Node with matching key is already in the tree, does nothing (no update).

Returns
Pointer to the Node inserted in the tree. NULL if the node already exists in the tree (duplicate).
Parameters
[in]treePtrTree to insert into.
[in]newLinkPtrNew link to add.

◆ le_rbtree_IsEmpty()

bool le_rbtree_IsEmpty ( const le_rbtree_Tree_t treePtr)

Tests if the Tree is empty.

Returns
Returns true if empty, false otherwise.
Parameters
[in]treePtrTree containing currentLinkPtr.

◆ le_rbtree_Remove()

le_rbtree_Node_t* le_rbtree_Remove ( le_rbtree_Tree_t treePtr,
le_rbtree_Node_t linkPtr 
)

Removes the specified node from the tree.

Returns
Pointer to the node removed from the tree. NULL if not found.
Parameters
[in]treePtrTree to remove from.
[in]linkPtrLink to remove.

◆ le_rbtree_RemoveByKey()

le_rbtree_Node_t* le_rbtree_RemoveByKey ( le_rbtree_Tree_t treePtr,
void *  keyPtr 
)

Removes the specified node from the tree by the specified key.

Returns
Pointer to the node removed from the tree. NULL if not found.
Parameters
[in]treePtrTree to remove from.
[in]keyPtrPointer to the key to be removed

◆ le_rbtree_Size()

size_t le_rbtree_Size ( const le_rbtree_Tree_t treePtr)

Calculates size of the Tree.

Returns
The number of elementskeys in the Tree.
Parameters
[in]treePtrTree containing currentLinkPtr.