Data Structures | Typedefs | Enumerations | Functions

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_t * le_rbtree_Insert (le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *newLinkPtr)
 
le_rbtree_Node_t * le_rbtree_Find (le_rbtree_Tree_t *treePtr, void *keyPtr)
 
le_rbtree_Node_t * le_rbtree_Remove (le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *linkPtr)
 
le_rbtree_Node_t * le_rbtree_RemoveByKey (le_rbtree_Tree_t *treePtr, void *keyPtr)
 
le_rbtree_Node_t * le_rbtree_GetFirst (const le_rbtree_Tree_t *treePtr)
 
le_rbtree_Node_t * le_rbtree_GetLast (const le_rbtree_Tree_t *treePtr)
 
le_rbtree_Node_t * le_rbtree_GetNext (const le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *currentLinkPtr)
 
le_rbtree_Node_t * le_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.

Copyright (C) Sierra Wireless Inc.

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

enum 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.