le_redBlackTree.h

Go to the documentation of this file.
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 }
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.
183 }
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 }
215 
216 
217 //--------------------------------------------------------------------------------------------------
218 /**
219  * Initialize the Red-Black Tree.
220  */
221 //--------------------------------------------------------------------------------------------------
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 //--------------------------------------------------------------------------------------------------
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 //--------------------------------------------------------------------------------------------------
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 //--------------------------------------------------------------------------------------------------
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 //--------------------------------------------------------------------------------------------------
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 //--------------------------------------------------------------------------------------------------
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 //--------------------------------------------------------------------------------------------------
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 //--------------------------------------------------------------------------------------------------
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 //--------------------------------------------------------------------------------------------------
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 //--------------------------------------------------------------------------------------------------
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 //--------------------------------------------------------------------------------------------------
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_Node_t * le_rbtree_GetNext(const le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *currentLinkPtr)
le_rbtree_Color_t
Definition: le_redBlackTree.h:165
struct le_rbtree_Node * parent
Parent link pointer.
Definition: le_redBlackTree.h:179
struct le_rbtree_Node * left
Left node link pointer.
Definition: le_redBlackTree.h:180
size_t size
Number of elements in the tree.
Definition: le_redBlackTree.h:211
le_rbtree_Node_t * le_rbtree_Insert(le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *newLinkPtr)
le_rbtree_Node_t * root
Root tree node.
Definition: le_redBlackTree.h:210
le_rbtree_Node_t * le_rbtree_GetLast(const le_rbtree_Tree_t *treePtr)
size_t le_rbtree_Size(const le_rbtree_Tree_t *treePtr)
le_rbtree_Node_t * le_rbtree_GetFirst(const le_rbtree_Tree_t *treePtr)
void le_rbtree_InitTree(le_rbtree_Tree_t *treePtr, le_rbtree_CompareFunc_t compFn)
le_rbtree_Color_t color
Color.
Definition: le_redBlackTree.h:182
le_rbtree_Node_t * le_rbtree_GetPrev(const le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *currentLinkPtr)
void * key
Key pointer.
Definition: le_redBlackTree.h:178
struct le_rbtree_Node * right
Right node link pointer.
Definition: le_redBlackTree.h:181
le_rbtree_Node_t * le_rbtree_Remove(le_rbtree_Tree_t *treePtr, le_rbtree_Node_t *linkPtr)
void le_rbtree_InitNode(le_rbtree_Node_t *linkPtr, void *keyPtr)
le_rbtree_CompareFunc_t compFn
Key comparison function.
Definition: le_redBlackTree.h:212
bool le_rbtree_IsEmpty(const le_rbtree_Tree_t *treePtr)
le_rbtree_Node_t * le_rbtree_Find(le_rbtree_Tree_t *treePtr, void *keyPtr)
Definition: le_redBlackTree.h:208
Definition: le_redBlackTree.h:176
int(* le_rbtree_CompareFunc_t)(const void *key1Ptr, const void *key2Ptr)
Definition: le_redBlackTree.h:195
le_rbtree_Node_t * le_rbtree_RemoveByKey(le_rbtree_Tree_t *treePtr, void *keyPtr)