le_redBlackTree.h

    1 /**
    2  * @page c_redBlackTree Red/Black Tree API
    3  *
    4  * @ref le_redBlackTree.h "API Reference"
    5  *
    6  * <HR>
    7  *
    8  * A Red-Black Tree is a data structure representing a self-balancing binary search tree.
    9  * Tree consists of nodes maintaining links to the parent, left and right nodes. Advantage over a
   10  * linked-list is faster search based on the key comparison. Advantage over a hashtable is
   11  * simplified memory management (no additional allocation within the library), better
   12  * scalability up and down, and possibility to easily iterate the set in ascending/descending order.
   13  *
   14  * @section rbtree_createTree Creating and Initializing Red-Black Trees
   15  *
   16  * To create and initialize an RB Tree the user must create an le_rbtree_Tree_t typed object and
   17  * initialize it using le_rbtree_InitTree() routine. At this time the user has to provide a pointer
   18  * to the comparator function, that provides a way to perform a comparison between objects.
   19  * The tree <b>must</b> be initialized before it can be used.
   20  *
   21  * @code
   22  * // provide the comparator function
   23  * static int compare(const void* a, const void* b)
   24  * {
   25  *    // return negative, 0, or positive value
   26  * }
   27  *
   28  * // Create the tree.
   29  * le_rbtree_Tree_t MyTree;
   30  *
   31  * // Initialize the tree.
   32  * le_rbtree_InitTree(&MyTree, compare);
   33  * @endcode
   34  *
   35  * <b> Elements of @c le_rbtree_Tree_t MUST NOT be accessed directly by the user. </b>
   36  *
   37  *
   38  * @section rbtree_createNode Creating and Accessing Nodes
   39  *
   40  * Nodes can contain any data in any format and is defined and created by the user. The only
   41  * requirement for nodes is that it must contain an @c le_rbtree_Node_t link member. The link member
   42  * must be initialized by calling @c le_rbtree_InitNode() before it is added to the tree; at this
   43  * time, pointer to the key of this object must be provided.
   44  * The node can be added to the tree using the function @c le_rbtree_Insert().
   45  *
   46  * @code
   47  * // The node may be defined like this.
   48  * typedef struct
   49  * {
   50  *      MyKeyType key;
   51  *      dataType someUserData;
   52  *      ...
   53  *      le_rbtree_Node_t myLink;
   54  * }
   55  * MyNodeClass_t;
   56  *
   57  * void foo (void)
   58  * {
   59  *     // Create the node.  Get the memory from a memory pool previously created.
   60  *     MyNodeClass_t* myNodePtr = le_mem_ForceAlloc(MyNodePool);
   61  *
   62  *     // Initialize the node's link.
   63  *     le_rbtree_InitNode(&MyTree, &myNodePtr->key);
   64  *
   65  *     // Add the node to the tree by passing in the node's link.
   66  *     le_rbtree_Insert(&MyTree, &myNodePtr->myLink);
   67  * }
   68  * @endcode
   69  *
   70  * @section rbtree_find Finding node in a Tree
   71  *
   72  * To find the node in the tree by the given key, use @c le_rbtree_Find() function.
   73  * To obtain the object itself, use the @c CONTAINER_OF macro defined in
   74  * le_basics.h. Here's a code sample using @c CONTAINER_OF to obtain the node:
   75  *
   76  * @code
   77  * // declare and initialize the key
   78  * MyKeyType key = <...>;
   79  * // Assuming MyTree has been created and initialized and is not empty.
   80  * le_rbtree_Node_t* linkPtr = le_rbtree_Find(&MyTree, &key);
   81  *
   82  * // Now we have the link but still need the node to access user data.
   83  * // We use CONTAINER_OF to get a pointer to the node given the node's link.
   84  * if (linkPtr != NULL)
   85  * {
   86  *     MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
   87  * }
   88  * @endcode
   89  *
   90  * The user is responsible for creating and freeing memory for all nodes; the RB Tree module
   91  * only manages the links in the nodes. The node must be removed from all trees before its
   92  * memory can be freed.
   93  *
   94  * <b>The elements of @c le_rbtree_Node_t MUST NOT be accessed directly by the user.</b>
   95  *
   96  * @section rbtree_traverse Traversing a Tree
   97  *
   98  * Tree can be traversed in an ascending or descending order (in the sense of greater/lesser
   99  * provided by the comparator function):
  100  *
  101  * @code
  102  * // Ascending order
  103  * le_rbtree_Node_t* linkPtr;
  104  * for (linkPtr = le_rbtree_GetFirst(&MyTree);
  105  *      linkPtr != NULL;
  106  *      linkPtr = le_rbtree_GetNext(&MyTree, linkPtr))
  107  * {
  108  *     MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
  109  * }
  110  *
  111  * // Descending order
  112  * le_rbtree_Node_t* linkPtr;
  113  * for (linkPtr = le_rbtree_GetLast(&MyTree);
  114  *      linkPtr != NULL;
  115  *      linkPtr = le_rbtree_GetPrev(&MyTree, linkPtr))
  116  * {
  117  *     MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
  118  * }
  119  * @endcode
  120  *
  121  * @section rbtree_remove Removing node from a Tree
  122  *
  123  * To remove a node from a Tree, use le_rbtree_RemoveByKey() function:
  124  * @code
  125  *     // Remove the node
  126  *     le_rbtree_RemoveByKey(&MyTree, &(myNodePtr->key));
  127  *     // Free the object
  128  *     le_mem_Release(myNodePtr);
  129  * @endcode
  130  *
  131  * or le_rbtree_Remove() function:
  132  * @code
  133  *     // Remove the node
  134  *     le_rbtree_Remove(&MyTree, &(myNodePtr->myLink));
  135  *     // Free the object
  136  *     le_mem_Release(myNodePtr);
  137  * @endcode
  138  *
  139  * @section rbtree_synch Thread Safety and Re-Entrancy
  140  *
  141  * All Red-Black Tree function calls are re-entrant and thread safe themselves, but if the nodes
  142  * and/or Tree object are shared by multiple threads, explicit steps must be taken to maintain
  143  * mutual exclusion of access. If you're accessing the same tree from multiple threads, you @e must
  144  * use a @ref c_mutex "mutex" or some other form of thread synchronization to ensure only one thread
  145  * accesses the tree at a time.
  146  *
  147  * <HR>
  148  *
  149  * Copyright (C) Sierra Wireless Inc.
  150  */
  151 
  152 /** @file le_redBlackTree.h
  153  *
  154  * Legato @ref c_redBlackTree include file.
  155  *
  156  * Copyright (C) Sierra Wireless Inc.
  157  */
  158 
  159 #ifndef LEGATO_RED_BLACK_TREE_INCLUDE_GUARD
  160 #define LEGATO_RED_BLACK_TREE_INCLUDE_GUARD
  161 
  162 /**
  163  * Color type for Red-Black tree.
  164  */
  165 typedef enum
  166 {
  167     LE_RBTREE_NO_COLOR,
  168     LE_RBTREE_BLACK,
  169     LE_RBTREE_RED
  170 }
  171 le_rbtree_Color_t;
  172 
  173 /**
  174  * The type of the node of the Red-Black Tree.
  175  */
  176 typedef struct le_rbtree_Node
  177 {
  178     void *key;                      ///< Key pointer.
  179     struct le_rbtree_Node *parent;  ///< Parent link pointer.
  180     struct le_rbtree_Node *left;    ///< Left node link pointer.
  181     struct le_rbtree_Node *right;   ///< Right node link pointer.
  182     le_rbtree_Color_t color;        ///< Color
  183 }
  184 le_rbtree_Node_t;
  185 
  186 //--------------------------------------------------------------------------------------------------
  187 /**
  188  * This is a comparator function to compare objects in a tree.
  189  *
  190  *  @return negative, 0, positive number if the first key is less, equal, or greater than
  191  *          the second one.
  192  */
  193 //--------------------------------------------------------------------------------------------------
  194 typedef int (*le_rbtree_CompareFunc_t)
  195 (
  196     const void *key1Ptr,   ///< [IN] Pointer to the key of the first object
  197     const void *key2Ptr    ///< [IN] Pointer to the key of the second object
  198 );
  199 
  200 
  201 //--------------------------------------------------------------------------------------------------
  202 /**
  203  * This is the RBTree object. User must initialize it by calling le_rbtree_InitTree.
  204  *
  205  * @warning User MUST NOT access the contents of this structure directly.
  206  */
  207 //--------------------------------------------------------------------------------------------------
  208 typedef struct le_rbtree_Tree
  209 {
  210     le_rbtree_Node_t *root;         ///< Root tree node.
  211     size_t size;                    ///< Number of elements in the tree.
  212     le_rbtree_CompareFunc_t compFn; ///< Key comparison function.
  213 }
  214 le_rbtree_Tree_t;
  215 
  216 
  217 //--------------------------------------------------------------------------------------------------
  218 /**
  219  * Initialize the Red-Black Tree.
  220  */
  221 //--------------------------------------------------------------------------------------------------
  222 void le_rbtree_InitTree
  223 (
  224     le_rbtree_Tree_t *treePtr,      ///< [IN] Pointer to the tree object.
  225     le_rbtree_CompareFunc_t compFn  ///< [IN] Pointer to the comparator function.
  226 );
  227 
  228 //--------------------------------------------------------------------------------------------------
  229 /**
  230  * Initialize the Node Link.
  231  */
  232 //--------------------------------------------------------------------------------------------------
  233 void le_rbtree_InitNode
  234 (
  235     le_rbtree_Node_t *linkPtr,      ///< [INOUT] Node link pointer.
  236     void *keyPtr                    ///< [IN] Key pointer.
  237 );
  238 
  239 //--------------------------------------------------------------------------------------------------
  240 /**
  241  * Insert a new node in the tree. If Node with matching key is already in the tree, does nothing
  242  * (no update).
  243  *
  244  * @return Pointer to the Node inserted in the tree.
  245  *         NULL if the node already exists in the tree (duplicate).
  246  */
  247 //--------------------------------------------------------------------------------------------------
  248 le_rbtree_Node_t* le_rbtree_Insert
  249 (
  250     le_rbtree_Tree_t *treePtr,            ///< [IN] Tree to insert into.
  251     le_rbtree_Node_t *newLinkPtr          ///< [IN] New link to add.
  252 );
  253 
  254 //--------------------------------------------------------------------------------------------------
  255 /**
  256  * Find object in the tree for the given key.
  257  *
  258  * @return Pointer to the Node found in the tree.
  259  *         NULL if not found.
  260  */
  261 //--------------------------------------------------------------------------------------------------
  262 le_rbtree_Node_t* le_rbtree_Find
  263 (
  264     le_rbtree_Tree_t *treePtr,    ///< [IN] Tree to get the object from.
  265     void *keyPtr                  ///< [IN] Pointer to the key to be retrieved
  266 );
  267 
  268 //--------------------------------------------------------------------------------------------------
  269 /**
  270  * Removes the specified node from the tree.
  271  *
  272  * @return Pointer to the node removed from the tree.
  273  *         NULL if not found.
  274  */
  275 //--------------------------------------------------------------------------------------------------
  276 le_rbtree_Node_t* le_rbtree_Remove
  277 (
  278     le_rbtree_Tree_t *treePtr,    ///< [IN] Tree to remove from.
  279     le_rbtree_Node_t *linkPtr     ///< [IN] Link to remove.
  280 );
  281 
  282 //--------------------------------------------------------------------------------------------------
  283 /**
  284  * Removes the specified node from the tree by the specified key.
  285  *
  286  * @return Pointer to the node removed from the tree.
  287  *         NULL if not found.
  288  */
  289 //--------------------------------------------------------------------------------------------------
  290 le_rbtree_Node_t* le_rbtree_RemoveByKey
  291 (
  292     le_rbtree_Tree_t *treePtr,    ///< [IN] Tree to remove from.
  293     void *keyPtr                  ///< [IN] Pointer to the key to be removed
  294 );
  295 
  296 //--------------------------------------------------------------------------------------------------
  297 /**
  298  * Get the first (smallest) node in the tree.
  299  *
  300  * @return Pointer to the node if successful.
  301  *         NULL if the tree is empty.
  302  */
  303 //--------------------------------------------------------------------------------------------------
  304 le_rbtree_Node_t* le_rbtree_GetFirst
  305 (
  306     const le_rbtree_Tree_t *treePtr    ///< [IN] Tree to get the object from.
  307 );
  308 
  309 //--------------------------------------------------------------------------------------------------
  310 /**
  311  * Get the last (greatest) node in the tree.
  312  *
  313  * @return Pointer to the Node if successful.
  314  *         NULL if the tree is empty.
  315  */
  316 //--------------------------------------------------------------------------------------------------
  317 le_rbtree_Node_t* le_rbtree_GetLast
  318 (
  319     const le_rbtree_Tree_t *treePtr    ///< [IN] Tree to get the object from.
  320 );
  321 
  322 //--------------------------------------------------------------------------------------------------
  323 /**
  324  * Returns the node next to currentLinkPtr without removing it from the tree.
  325  * User must ensure that currentLinkPtr is in the tree.
  326  *
  327  * @return
  328  *      Pointer to the next link if successful.
  329  *      NULL if there is no node greater than the currentLinkPtr.
  330  */
  331 //--------------------------------------------------------------------------------------------------
  332 le_rbtree_Node_t* le_rbtree_GetNext
  333 (
  334     const le_rbtree_Tree_t *treePtr,   ///< [IN] Tree to get the object from.
  335     le_rbtree_Node_t *currentLinkPtr   ///< [IN] Current node pointer.
  336 );
  337 
  338 //--------------------------------------------------------------------------------------------------
  339 /**
  340  * Returns the node previous to currentLinkPtr without removing it from the tree.
  341  * User must ensure that currentLinkPtr is in the tree.
  342  *
  343  * @return
  344  *      Pointer to the previous link if successful.
  345  *      NULL if there is no node smaller than the currentLinkPtr.
  346  */
  347 //--------------------------------------------------------------------------------------------------
  348 le_rbtree_Node_t* le_rbtree_GetPrev
  349 (
  350     const le_rbtree_Tree_t *treePtr,        ///< [IN] Tree containing currentLinkPtr.
  351     le_rbtree_Node_t *currentLinkPtr        ///< [IN] Get the link that is relative to this link.
  352 );
  353 
  354 //--------------------------------------------------------------------------------------------------
  355 /**
  356  * Tests if the Tree is empty.
  357  *
  358  * @return  Returns true if empty, false otherwise.
  359  */
  360 //--------------------------------------------------------------------------------------------------
  361 bool le_rbtree_IsEmpty
  362 (
  363     const le_rbtree_Tree_t *treePtr         ///< [IN] Tree containing currentLinkPtr.
  364 );
  365 
  366 //--------------------------------------------------------------------------------------------------
  367 /**
  368  * Calculates size of the Tree.
  369  *
  370  * @return  The number of elementskeys in the Tree.
  371  */
  372 //--------------------------------------------------------------------------------------------------
  373 size_t le_rbtree_Size
  374 (
  375     const le_rbtree_Tree_t *treePtr         ///< [IN] Tree containing currentLinkPtr.
  376 );
  377 
  378 #endif  // LEGATO_RED_BLACK_TREE_INCLUDE_GUARD
le_rbtree_GetNext
le_rbtree_Node_t * le_rbtree_GetNext(const le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *currentLinkPtr)
le_rbtree_Color_t
le_rbtree_Color_t
Definition: le_redBlackTree.h:165
le_rbtree_Node_t::parent
struct le_rbtree_Node * parent
Parent link pointer. 
Definition: le_redBlackTree.h:179
le_rbtree_Node_t::left
struct le_rbtree_Node * left
Left node link pointer. 
Definition: le_redBlackTree.h:180
le_rbtree_Tree_t::size
size_t size
Number of elements in the tree. 
Definition: le_redBlackTree.h:211
le_rbtree_Insert
le_rbtree_Node_t * le_rbtree_Insert(le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *newLinkPtr)
le_rbtree_Tree_t::root
le_rbtree_Node_t * root
Root tree node. 
Definition: le_redBlackTree.h:210
le_rbtree_GetLast
le_rbtree_Node_t * le_rbtree_GetLast(const le_rbtree_Tree_t *treePtr)
le_rbtree_Size
size_t le_rbtree_Size(const le_rbtree_Tree_t *treePtr)
le_rbtree_GetFirst
le_rbtree_Node_t * le_rbtree_GetFirst(const le_rbtree_Tree_t *treePtr)
le_rbtree_InitTree
void le_rbtree_InitTree(le_rbtree_Tree_t *treePtr, le_rbtree_CompareFunc_t compFn)
le_rbtree_Node_t::color
le_rbtree_Color_t color
Color. 
Definition: le_redBlackTree.h:182
le_rbtree_GetPrev
le_rbtree_Node_t * le_rbtree_GetPrev(const le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *currentLinkPtr)
le_rbtree_Node_t::key
void * key
Key pointer. 
Definition: le_redBlackTree.h:178
le_rbtree_Node_t::right
struct le_rbtree_Node * right
Right node link pointer. 
Definition: le_redBlackTree.h:181
le_rbtree_Remove
le_rbtree_Node_t * le_rbtree_Remove(le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *linkPtr)
le_rbtree_InitNode
void le_rbtree_InitNode(le_rbtree_Node_t *linkPtr, void *keyPtr)
le_rbtree_Tree_t::compFn
le_rbtree_CompareFunc_t compFn
Key comparison function. 
Definition: le_redBlackTree.h:212
le_rbtree_IsEmpty
bool le_rbtree_IsEmpty(const le_rbtree_Tree_t *treePtr)
le_rbtree_Find
le_rbtree_Node_t * le_rbtree_Find(le_rbtree_Tree_t *treePtr, void *keyPtr)
le_rbtree_Tree_t
Definition: le_redBlackTree.h:208
le_rbtree_Node_t
Definition: le_redBlackTree.h:176
le_rbtree_CompareFunc_t
int(* le_rbtree_CompareFunc_t)(const void *key1Ptr, const void *key2Ptr)
Definition: le_redBlackTree.h:195
le_rbtree_RemoveByKey
le_rbtree_Node_t * le_rbtree_RemoveByKey(le_rbtree_Tree_t *treePtr, void *keyPtr)