le_doublyLinkedList.h

Go to the documentation of this file.
1 /**
2  * @page c_doublyLinkedList Doubly Linked List API
3  *
4  * @subpage le_doublyLinkedList.h "API Reference"
5  *
6  * <HR>
7  *
8  * A doubly linked list is a data structure consisting of a group of nodes linked together linearly.
9  * Each node consists of data elements with links to the next node and previous nodes. The main
10  * advantage of linked lists (over simple arrays) is the nodes can be inserted and removed
11  * anywhere in the list without reallocating the entire array. Linked list nodes don't
12  * need to be stored contiguously in memory, but nodes then you can't access by
13  * index, you have to be access by traversing the list.
14  *
15  * @section dls_createList Creating and Initializing Lists
16  *
17  * To create and initialize a linked list the user must create a le_dls_List_t typed list and assign
18  * LE_DLS_LIST_INIT to it. The assignment of LE_DLS_LIST_INIT can be done either when the list is
19  * declared or after its declared. The list <b>must</b> be initialized before it can be
20  * used.
21  *
22  * @code
23  * // Create and initialized the list in the declaration.
24  * le_dls_List_t MyList = LE_DLS_LIST_INIT;
25  * @endcode
26  *
27  * Or
28  *
29  * @code
30  * // Create list.
31  * le_dls_List_t MyList;
32  *
33  * // Initialize the list.
34  * MyList = LE_DLS_LIST_INIT;
35  * @endcode
36  *
37  * <b> Elements of le_dls_List_t MUST NOT be accessed directly by the user. </b>
38  *
39  *
40  * @section dls_createNode Creating and Accessing Nodes
41  *
42  * Nodes can contain any data in any format and is defined and created by the user. The only
43  * requirement for nodes is that it must contain a @c le_dls_Link_t link member. The link member must
44  * be initialized by assigning LE_DLS_LINK_INIT to it before it can be used. Nodes can then be
45  * added to the list by passing their links to the add functions (le_dls_Stack(), le_dls_Queue(),
46  * etc.). For example:
47  *
48  * @code
49  * // The node may be defined like this.
50  * typedef struct
51  * {
52  * dataType someUserData;
53  * ...
54  * le_dls_Link_t myLink;
55  *
56  * }
57  * MyNodeClass_t;
58  *
59  * // Create and initialize the list.
60  * le_dls_List_t MyList = LE_DLS_LIST_INIT;
61  *
62  * void foo (void)
63  * {
64  * // Create the node. Get the memory from a memory pool previously created.
65  * MyNodeClass_t* myNodePtr = le_mem_ForceAlloc(MyNodePool);
66  *
67  * // Initialize the node's link.
68  * myNodePtr->myLink = LE_DLS_LINK_INIT;
69  *
70  * // Add the node to the head of the list by passing in the node's link.
71  * le_dls_Stack(&MyList, &(myNodePtr->myLink));
72  * }
73  * @endcode
74  *
75  * The links in the nodes are actually added to the list and not the nodes themselves. This
76  * allows a node to be included on multiple lists through links
77  * added to different lists. It also allows linking different type nodes in a list.
78  *
79  * To obtain the node itself, use the @c CONTAINER_OF macro defined in
80  * le_basics.h. Here's a code sample using CONTAINER_OF to obtain the node:
81  *
82  * @code
83  * // Assuming mylist has been created and initialized and is not empty.
84  * le_dls_Link_t* linkPtr = le_dls_Peek(&MyList);
85  *
86  * // Now we have the link but still need the node to access user data.
87  * // We use CONTAINER_OF to get a pointer to the node given the node's link.
88  * if (linkPtr != NULL)
89  * {
90  * MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
91  * }
92  * @endcode
93  *
94  * The user is responsible for creating and freeing memory for all nodes; the linked list module
95  * only manages the links in the nodes. The node must be removed from all lists before its
96  * memory can be freed.
97  *
98  * <b>The elements of @c le_dls_Link_t MUST NOT be accessed directly by the user.</b>
99  *
100  *
101  * @section dls_add Adding Links to a List
102  *
103  * To add nodes to a list, pass the node's link to one of these functions:
104  *
105  * - @c le_dls_Stack() - Adds the link to the head of the list.
106  * - @c le_dls_Queue() - Adds the link to the tail of the list.
107  * - @c le_dls_AddAfter() - Adds the link to a list after another specified link.
108  * - @c le_dls_AddBefore() - Adds the link to a list before another specified link.
109  *
110  *
111  * @section dls_remove Removing Links from a List
112  *
113  * To remove nodes from a list, use one of these functions:
114  *
115  * - @c le_dls_Pop() - Removes and returns the link at the head of the list.
116  * - @c le_dls_PopTail() - Removes and returns the link at the tail of the list.
117  * - @c le_dls_Remove() - Remove a specified link from the list.
118  *
119  *
120  * @section dls_peek Accessing Links in a List
121  *
122  * To access a link in a list without removing the link, use one of these functions:
123  *
124  * - @c le_dls_Peek() - Returns the link at the head of the list without removing it.
125  * - @c le_dls_PeekTail() - Returns the link at the tail of the list without removing it.
126  * - @c le_dls_PeekNext() - Returns the link next to a specified link without removing it.
127  * - @c le_dls_PeekPrev() - Returns the link previous to a specified link without removing it.
128  *
129  *
130  * @section dls_swap Swapping Links
131  *
132  * To swap two links, use:
133  *
134  * - @c le_dls_Swap() - Swaps the position of two links in a list.
135  *
136  * @section dls_sort Sorting Lists
137  *
138  * To sort a list use:
139  *
140  * @c le_dls_Sort() - Sorts a list
141  *
142  * @section dls_query Querying List Status
143  *
144  * These functions can be used to query a list's current status:
145  *
146  * - @c le_dls_IsEmpty() - Checks if a given list is empty.
147  * - @c le_dls_IsInList() - Checks if a specified link is in the list.
148  * - @c le_dls_IsHead() - Checks if a specified link is at the head of the list.
149  * - @c le_dls_IsTail() - Checks if a specified link is at the tail of the list.
150  * - @c le_dls_NumLinks() - Checks the number of links currently in the list.
151  * - @c le_dls_IsListCorrupted() - Checks if the list is corrupted.
152  *
153  *
154  * @section dls_fifo Queues and Stacks
155  *
156  * This implementation of linked lists can be used for either queues or stacks.
157  *
158  * To use the list as a queue, restrict additions to the list to @c le_dls_Queue() and removals
159  * from the list to @c le_dls_Pop().
160  *
161  * To use the list as a stack, restrict additions to the list to @c le_dls_Stack() and removals
162  * from the list to @c le_dls_Pop().
163  *
164  *
165  * @section dls_synch Thread Safety and Re-Entrancy
166  *
167  * All linked list function calls are re-entrant and thread safe themselves, but if the nodes and/or
168  * list object are shared by multiple threads, explicit steps must be taken to maintain mutual
169  * exclusion of access. If you're accessing the same list from multiple threads, you @e must use a
170  * @ref c_mutex "mutex" or some other form of thread synchronization to ensure only one thread
171  * accesses the list at a time.
172  *
173  * <HR>
174  *
175  * Copyright (C) Sierra Wireless Inc.
176  */
177 
178 
179 /** @file le_doublyLinkedList.h
180  *
181  * Legato @ref c_doublyLinkedList include file.
182  *
183  * Copyright (C) Sierra Wireless Inc.
184  */
185 
186 #ifndef LEGATO_DOUBLY_LINKED_LIST_INCLUDE_GUARD
187 #define LEGATO_DOUBLY_LINKED_LIST_INCLUDE_GUARD
188 
189 
190 //--------------------------------------------------------------------------------------------------
191 /**
192  * This link object must be included in each user node. The node's link object is used to add the
193  * node to a list. A node may have multiple link objects which would allow the node to be part of
194  * multiple lists simultaneously. This link object must be initialized by assigning
195  * LE_DLS_LINK_INIT to it.
196  *
197  * @warning The structure's content MUST NOT be accessed directly.
198  */
199 //--------------------------------------------------------------------------------------------------
200 typedef struct le_dls_Link
201 {
202  struct le_dls_Link* nextPtr; ///< Next link pointer.
203  struct le_dls_Link* prevPtr; ///< Previous link pointer.
204 }
206 
207 
208 //--------------------------------------------------------------------------------------------------
209 /**
210  * This is the list object. User must create this list object and initialize it by assigning
211  * LE_DLS_LIST_INIT to it.
212  *
213  * @warning User MUST NOT access the contents of this structure directly.
214  */
215 //--------------------------------------------------------------------------------------------------
216 typedef struct
217 {
218  le_dls_Link_t* headLinkPtr; ///< Link to list head.
219 }
221 
222 
223 //--------------------------------------------------------------------------------------------------
224 /**
225  * This is a comparator function for sorting a list.
226  *
227  * This must return true if @c a goes before @c b in the list.
228  */
229 //--------------------------------------------------------------------------------------------------
231 
232 
233 //--------------------------------------------------------------------------------------------------
234 /**
235  * When a list is created it must be initialized to this macro in the declaration,
236  * or have @c LE_DLS_LIST_INIT assigned to it, before being used
237  */
238 //--------------------------------------------------------------------------------------------------
239 #define LE_DLS_LIST_DECL_INIT {NULL}
240 
241 //--------------------------------------------------------------------------------------------------
242 /**
243  * When a list is created it must be initialized by assigning this macro to the list, or
244  * initializing to @c LE_DLS_LIST_DECL_INIT in the declaration, before the list can be used.
245  */
246 //--------------------------------------------------------------------------------------------------
247 #define LE_DLS_LIST_INIT (le_dls_List_t)LE_DLS_LIST_DECL_INIT
248 
249 
250 //--------------------------------------------------------------------------------------------------
251 /**
252  * When a link is created it must be initialized by assigning this macro to the link before it can
253  * be used.
254  */
255 //--------------------------------------------------------------------------------------------------
256 #define LE_DLS_LINK_INIT (le_dls_Link_t){NULL, NULL}
257 
258 
259 //--------------------------------------------------------------------------------------------------
260 /**
261  * Adds a link at the head of the list.
262  */
263 //--------------------------------------------------------------------------------------------------
264 void le_dls_Stack
265 (
266  le_dls_List_t* listPtr, ///< [IN] List to add to.
267  le_dls_Link_t* newLinkPtr ///< [IN] New link to add.
268 );
269 
270 
271 //--------------------------------------------------------------------------------------------------
272 /**
273  * Adds a link to the tail of the list.
274  */
275 //--------------------------------------------------------------------------------------------------
276 void le_dls_Queue
277 (
278  le_dls_List_t* listPtr, ///< [IN] List to add to.
279  le_dls_Link_t* newLinkPtr ///< [IN] New link to add.
280 );
281 
282 
283 //--------------------------------------------------------------------------------------------------
284 /**
285  * Adds a link after currentLinkPtr. User must ensure that currentLinkPtr is in the list
286  * otherwise the behaviour of this function is undefined.
287  */
288 //--------------------------------------------------------------------------------------------------
289 void le_dls_AddAfter
290 (
291  le_dls_List_t* listPtr, ///< [IN] List to add to.
292  le_dls_Link_t* currentLinkPtr, ///< [IN] New link will be inserted after this link.
293  le_dls_Link_t* newLinkPtr ///< [IN] New link to add.
294 );
295 
296 
297 //--------------------------------------------------------------------------------------------------
298 /**
299  * Adds a link after currentLinkPtr. User must ensure that currentLinkPtr is in the list
300  * otherwise the behaviour of this function is undefined.
301  */
302 //--------------------------------------------------------------------------------------------------
303 void le_dls_AddBefore
304 (
305  le_dls_List_t* listPtr, ///< [IN] List to add to.
306  le_dls_Link_t* currentLinkPtr, ///< [IN] New link will be inserted before this link.
307  le_dls_Link_t* newLinkPtr ///< [IN] New link to add.
308 );
309 
310 
311 //--------------------------------------------------------------------------------------------------
312 /**
313  * Removes and returns the link at the head of the list.
314  *
315  * @return
316  * Removed link.
317  * NULL if the link is not available because the list is empty.
318  */
319 //--------------------------------------------------------------------------------------------------
321 (
322  le_dls_List_t* listPtr ///< [IN] List to remove from.
323 );
324 
325 
326 //--------------------------------------------------------------------------------------------------
327 /**
328  * Removes and returns the link at the tail of the list.
329  *
330  * @return
331  * The removed link.
332  * NULL if the link is not available because the list is empty.
333  */
334 //--------------------------------------------------------------------------------------------------
336 (
337  le_dls_List_t* listPtr ///< [IN] List to remove from.
338 );
339 
340 
341 //--------------------------------------------------------------------------------------------------
342 /**
343  * Removes the specified link from the list. Ensure the link is in the list
344  * otherwise the behaviour of this function is undefined.
345  */
346 //--------------------------------------------------------------------------------------------------
347 void le_dls_Remove
348 (
349  le_dls_List_t* listPtr, ///< [IN] List to remove from.
350  le_dls_Link_t* linkToRemovePtr ///< [IN] Link to remove.
351 );
352 
353 
354 //--------------------------------------------------------------------------------------------------
355 /**
356  * Returns the link at the head of the list without removing it from the list.
357  *
358  * @return
359  * Pointer to the head link if successful.
360  * NULL if the list is empty.
361  */
362 //--------------------------------------------------------------------------------------------------
364 (
365  const le_dls_List_t* listPtr ///< [IN] The list.
366 );
367 
368 
369 //--------------------------------------------------------------------------------------------------
370 /**
371  * Returns the link at the tail of the list without removing it from the list.
372  *
373  * @return
374  * A pointer to the tail link if successful.
375  * NULL if the list is empty.
376  */
377 //--------------------------------------------------------------------------------------------------
379 (
380  const le_dls_List_t* listPtr ///< [IN] The list.
381 );
382 
383 
384 //--------------------------------------------------------------------------------------------------
385 /**
386  * Checks if a list is empty.
387  *
388  * @return
389  * true if empty, false if not empty.
390  */
391 //--------------------------------------------------------------------------------------------------
393 (
394  const le_dls_List_t* listPtr ///< [IN] The list.
395 )
396 //--------------------------------------------------------------------------------------------------
397 {
398  return (le_dls_Peek(listPtr) == NULL);
399 }
400 
401 
402 //--------------------------------------------------------------------------------------------------
403 /**
404  * Returns the link next to currentLinkPtr (i.e., the link beside currentLinkPtr that is closer to the
405  * tail) without removing it from the list. User must ensure that currentLinkPtr is in the list
406  * otherwise the behaviour of this function is undefined.
407  *
408  * @return
409  * Pointer to the next link if successful.
410  * NULL if there is no link next to the currentLinkPtr (currentLinkPtr is at the tail of the
411  * list).
412  */
413 //--------------------------------------------------------------------------------------------------
415 (
416  const le_dls_List_t* listPtr, ///< [IN] List containing currentLinkPtr.
417  const le_dls_Link_t* currentLinkPtr ///< [IN] Get the link that is relative to this link.
418 );
419 
420 
421 //--------------------------------------------------------------------------------------------------
422 /**
423  * Returns the link previous to currentLinkPtr without removing it from the list. User must
424  * ensure that currentLinkPtr is in the list otherwise the behaviour of this function is undefined.
425  *
426  * @return
427  * Pointer to the previous link if successful.
428  * NULL if there is no link previous to the currentLinkPtr (currentLinkPtr is at the head of
429  * the list).
430  */
431 //--------------------------------------------------------------------------------------------------
433 (
434  const le_dls_List_t* listPtr, ///< [IN] List containing currentLinkPtr.
435  const le_dls_Link_t* currentLinkPtr ///< [IN] Get the link that is relative to this link.
436 );
437 
438 
439 //--------------------------------------------------------------------------------------------------
440 /**
441  * Swaps the position of two links in the list. User must ensure that both links are in the
442  * list otherwise the behaviour of this function is undefined.
443  */
444 //--------------------------------------------------------------------------------------------------
445 void le_dls_Swap
446 (
447  le_dls_List_t* listPtr, ///< [IN] List containing the links to swap.
448  le_dls_Link_t* linkPtr, ///< [IN] One of the two link pointers to swap.
449  le_dls_Link_t* otherLinkPtr ///< [IN] Other link pointer to swap.
450 );
451 
452 
453 //--------------------------------------------------------------------------------------------------
454 /**
455  * Sort a list in ascending order.
456  */
457 //--------------------------------------------------------------------------------------------------
458 void le_dls_Sort
459 (
460  le_dls_List_t* listPtr, ///< [IN] List to sort
461  le_dls_LessThanFunc_t comparatorPtr ///< [IN] Comparator function for sorting
462 );
463 
464 
465 //--------------------------------------------------------------------------------------------------
466 /**
467  * Checks if a link is in the list.
468  *
469  * @return
470  * true if the link is in the list.
471  * false if the link is not in the list.
472  */
473 //--------------------------------------------------------------------------------------------------
474 bool le_dls_IsInList
475 (
476  const le_dls_List_t* listPtr, ///< [IN] List to check.
477  const le_dls_Link_t* linkPtr ///< [IN] Check if this link is in the list.
478 );
479 
480 
481 //--------------------------------------------------------------------------------------------------
482 /**
483  * Checks if a link is at the head of the list (next to be popped).
484  *
485  * @return
486  * - true if the link is at the head of the list.
487  * - false if not.
488  */
489 //--------------------------------------------------------------------------------------------------
491 (
492  const le_dls_List_t* listPtr, ///< [IN] List to check.
493  const le_dls_Link_t* linkPtr ///< [IN] Check if this link is at the head of the list.
494 )
495 {
496  return (le_dls_Peek(listPtr) == linkPtr);
497 }
498 
499 
500 //--------------------------------------------------------------------------------------------------
501 /**
502  * Checks if a link is at the tail of the list (last to be popped).
503  *
504  * @return
505  * - true if the link is at the tail of the list.
506  * - false if not.
507  */
508 //--------------------------------------------------------------------------------------------------
510 (
511  const le_dls_List_t* listPtr, ///< [IN] List to check.
512  const le_dls_Link_t* linkPtr ///< [IN] Check if this link is at the tail of the list.
513 )
514 {
515  return (le_dls_PeekTail(listPtr) == linkPtr);
516 }
517 
518 
519 //--------------------------------------------------------------------------------------------------
520 /**
521  * Returns the number of links in a list.
522  *
523  * @return
524  * Number of links.
525  */
526 //--------------------------------------------------------------------------------------------------
527 size_t le_dls_NumLinks
528 (
529  const le_dls_List_t* listPtr ///< [IN] List to count.
530 );
531 
532 
533 //--------------------------------------------------------------------------------------------------
534 /**
535  * Checks if the list is corrupted.
536  *
537  * @return
538  * true if the list is corrupted.
539  * false if the list is not corrupted.
540  */
541 //--------------------------------------------------------------------------------------------------
543 (
544  const le_dls_List_t* listPtr ///< [IN] List to check.
545 );
546 
547 //--------------------------------------------------------------------------------------------------
548 /**
549  * Simple iteration through a doubly linked list
550  */
551 //--------------------------------------------------------------------------------------------------
552 #define LE_DLS_FOREACH(listPtr, iteratorPtr, type, member) \
553  for ((iteratorPtr) = CONTAINER_OF(le_dls_Peek(listPtr), type, member); \
554  &((iteratorPtr)->member); \
555  (iteratorPtr) = CONTAINER_OF(le_dls_PeekNext((listPtr),&((iteratorPtr)->member)), \
556  type, member))
557 
558 
559 #endif // LEGATO_DOUBLY_LINKED_LIST_INCLUDE_GUARD
le_dls_Link_t * le_dls_PeekPrev(const le_dls_List_t *listPtr, const le_dls_Link_t *currentLinkPtr)
le_dls_Link_t * le_dls_PeekTail(const le_dls_List_t *listPtr)
LE_DECLARE_INLINE bool le_dls_IsEmpty(const le_dls_List_t *listPtr)
Definition: le_doublyLinkedList.h:393
void le_dls_AddBefore(le_dls_List_t *listPtr, le_dls_Link_t *currentLinkPtr, le_dls_Link_t *newLinkPtr)
void le_dls_Queue(le_dls_List_t *listPtr, le_dls_Link_t *newLinkPtr)
bool(* le_dls_LessThanFunc_t)(le_dls_Link_t *a, le_dls_Link_t *b)
Definition: le_doublyLinkedList.h:230
bool le_dls_IsListCorrupted(const le_dls_List_t *listPtr)
le_dls_Link_t * headLinkPtr
Link to list head.
Definition: le_doublyLinkedList.h:218
void le_dls_AddAfter(le_dls_List_t *listPtr, le_dls_Link_t *currentLinkPtr, le_dls_Link_t *newLinkPtr)
void le_dls_Remove(le_dls_List_t *listPtr, le_dls_Link_t *linkToRemovePtr)
le_dls_Link_t * le_dls_PeekNext(const le_dls_List_t *listPtr, const le_dls_Link_t *currentLinkPtr)
le_dls_Link_t * le_dls_Pop(le_dls_List_t *listPtr)
void le_dls_Stack(le_dls_List_t *listPtr, le_dls_Link_t *newLinkPtr)
size_t le_dls_NumLinks(const le_dls_List_t *listPtr)
void le_dls_Swap(le_dls_List_t *listPtr, le_dls_Link_t *linkPtr, le_dls_Link_t *otherLinkPtr)
le_dls_Link_t * le_dls_PopTail(le_dls_List_t *listPtr)
LE_DECLARE_INLINE bool le_dls_IsHead(const le_dls_List_t *listPtr, const le_dls_Link_t *linkPtr)
Definition: le_doublyLinkedList.h:491
Definition: le_doublyLinkedList.h:216
void le_dls_Sort(le_dls_List_t *listPtr, le_dls_LessThanFunc_t comparatorPtr)
#define LE_DECLARE_INLINE
Definition: le_basics.h:333
le_dls_Link_t * le_dls_Peek(const le_dls_List_t *listPtr)
bool le_dls_IsInList(const le_dls_List_t *listPtr, const le_dls_Link_t *linkPtr)
LE_DECLARE_INLINE bool le_dls_IsTail(const le_dls_List_t *listPtr, const le_dls_Link_t *linkPtr)
Definition: le_doublyLinkedList.h:510