A Red-Black Tree is a data structure representing a self-balancing binary search tree. Tree consists of nodes maintaining links to the parent, left and right nodes. Advantage over a linked-list is faster search based on the key comparison. Advantage over a hashtable is simplified memory management (no additional allocation within the library), better scalability up and down, and possibility to easily iterate the set in ascending/descending order.

Creating and Initializing Red-Black Trees

To create and initialize an RB Tree the user must create an le_rbtree_Tree_t typed object and initialize it using le_rbtree_InitTree() routine. At this time the user has to provide a pointer to the comparator function, that provides a way to perform a comparison between objects. The tree must be initialized before it can be used.

// provide the comparator function
static int compare(const void* a, const void* b)
{
   // return negative, 0, or positive value
}
 
// Create the tree.
le_rbtree_Tree_t MyTree;
 
// Initialize the tree.
le_rbtree_InitTree(&MyTree, compare);

Elements of le_rbtree_Tree_t MUST NOT be accessed directly by the user.

Creating and Accessing Nodes

Nodes can contain any data in any format and is defined and created by the user. The only requirement for nodes is that it must contain an le_rbtree_Node_t link member. The link member must be initialized by calling le_rbtree_InitNode() before it is added to the tree; at this time, pointer to the key of this object must be provided. The node can be added to the tree using the function le_rbtree_Insert().

// The node may be defined like this.
typedef struct
{
     MyKeyType key;
     dataType someUserData;
     ...
     le_rbtree_Node_t myLink;
}
MyNodeClass_t;
 
void foo (void)
{
    // Create the node.  Get the memory from a memory pool previously created.
    MyNodeClass_t* myNodePtr = le_mem_ForceAlloc(MyNodePool);
 
    // Initialize the node's link.
    le_rbtree_InitNode(&MyTree, &myNodePtr->key);
 
    // Add the node to the tree by passing in the node's link.
    le_rbtree_Insert(&MyTree, &myNodePtr->myLink);
}

Finding node in a Tree

To find the node in the tree by the given key, use le_rbtree_Find() function. To obtain the object itself, use the CONTAINER_OF macro defined in le_basics.h. Here's a code sample using CONTAINER_OF to obtain the node:

// declare and initialize the key
MyKeyType key = <...>;
// Assuming MyTree has been created and initialized and is not empty.
le_rbtree_Node_t* linkPtr = le_rbtree_Find(&MyTree, &key);
 
// Now we have the link but still need the node to access user data.
// We use CONTAINER_OF to get a pointer to the node given the node's link.
if (linkPtr != NULL)
{
    MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
}

The user is responsible for creating and freeing memory for all nodes; the RB Tree module only manages the links in the nodes. The node must be removed from all trees before its memory can be freed.

The elements of le_rbtree_Node_t MUST NOT be accessed directly by the user.

Traversing a Tree

Tree can be traversed in an ascending or descending order (in the sense of greater/lesser provided by the comparator function):

// Ascending order
le_rbtree_Node_t* linkPtr;
for (linkPtr = le_rbtree_GetFirst(&MyTree);
     linkPtr != NULL;
     linkPtr = le_rbtree_GetNext(&MyTree, linkPtr))
{
    MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
}
 
// Descending order
le_rbtree_Node_t* linkPtr;
for (linkPtr = le_rbtree_GetLast(&MyTree);
     linkPtr != NULL;
     linkPtr = le_rbtree_GetPrev(&MyTree, linkPtr))
{
    MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
}

Removing node from a Tree

To remove a node from a Tree, use le_rbtree_RemoveByKey() function:

// Remove the node
le_rbtree_RemoveByKey(&MyTree, &(myNodePtr->key));
// Free the object
le_mem_Release(myNodePtr);

or le_rbtree_Remove() function:

// Remove the node
le_rbtree_Remove(&MyTree, &(myNodePtr->myLink));
// Free the object
le_mem_Release(myNodePtr);

Thread Safety and Re-Entrancy

All Red-Black Tree function calls are re-entrant and thread safe themselves, but if the nodes and/or Tree object are shared by multiple threads, explicit steps must be taken to maintain mutual exclusion of access. If you're accessing the same tree from multiple threads, you must use a mutex or some other form of thread synchronization to ensure only one thread accesses the tree at a time.