le_singlyLinkedList.h

Go to the documentation of this file.
1 /**
2  * @page c_singlyLinkedList Singly Linked List API
3  *
4  * @subpage le_singlyLinkedList.h "API Reference"
5  *
6  * <HR>
7  *
8  * A singly linked list is a data structure consisting of a group of nodes linked together linearly.
9  * Each node consists of data elements and a link to the next node. The main advantage of linked
10  * lists over simple arrays is that the nodes can be inserted anywhere in the list without
11  * reallocating the entire array because the nodes in a linked list do not need to be stored
12  * contiguously in memory. However, nodes in the list cannot be accessed by index but must be
13  * accessed by traversing the list.
14  *
15  *
16  * @section sls_createList Creating and Initializing Lists
17  *
18  * To create and initialize a linked list, @c create a le_sls_List_t typed list and assign
19  * LE_SLS_LIST_INIT to it. The assignment of LE_SLS_LIST_INIT can be done either when the list is
20  * declared or after it's declared. The list <b>must</b> be initialized before it can be
21  * used.
22  *
23  * @code
24  * // Create and initialized the list in the declaration.
25  * le_sls_List_t MyList = LE_SLS_LIST_INIT;
26  * @endcode
27  *
28  * Or
29  *
30  * @code
31  * // Create list.
32  * le_sls_List_t MyList;
33  *
34  * // Initialize the list.
35  * MyList = LE_SLS_LIST_INIT;
36  * @endcode
37  *
38  * <b> The elements of le_sls_List_t MUST NOT be accessed directly by the user. </b>
39  *
40  *
41  * @section sls_createNode Creating and Accessing Nodes
42  *
43  * Nodes can contain any data in any format and is defined and created by the user. The only
44  * requirement for nodes is that it must contain a le_sls_Link_t link member. The link member must
45  * be initialized by assigning LE_SLS_LINK_INIT to it before it can be used. Nodes can then be
46  * added to the list by passing their links to the add functions (le_sls_Stack(), le_sls_Queue(),
47  * etc.). For example:
48  *
49  * @code
50  * // The node may be defined like this.
51  * typedef struct
52  * {
53  * dataType someUserData;
54  * ...
55  * le_sls_Link_t myLink;
56  *
57  * }
58  * MyNodeClass_t;
59  *
60  * // Create and initialize the list.
61  * le_sls_List_t MyList = LE_SLS_LIST_INIT;
62  *
63  * void foo (void)
64  * {
65  * // Create the node. Get the memory from a memory pool previously created.
66  * MyNodeClass_t* myNodePtr = le_mem_ForceAlloc(MyNodePool);
67  *
68  * // Initialize the node's link.
69  * myNodePtr->myLink = LE_SLS_LINK_INIT;
70  *
71  * // Add the node to the head of the list by passing in the node's link.
72  * le_sls_Stack(&MyList, &(myNodePtr->myLink));
73  * }
74  * @endcode
75  *
76  * The links in the nodes are added to the list and not the nodes themselves. This
77  * allows a node to be simultaneously part of multiple lists simply by having multiple links and
78  * adding the links into differently lists. This also means that nodes in a list can be of
79  * different types.
80  *
81  * Because the links and not the nodes are in the list, the user must have a way to obtain
82  * the node itself from the link. This is achieved using the @c CONTAINER_OF macro defined in
83  * le_basics.h. This code sample shows using CONTAINER_OF to obtain the node:
84  *
85  * @code
86  * // Assuming mylist has been created and initialized and is not empty.
87  * le_sls_Link_t* linkPtr = le_sls_Peek(&MyList);
88  *
89  * // Now we have the link but we want the node so we can access the user data.
90  * // We use CONTAINER_OF to get a pointer to the node given the node's link.
91  * if (linkPtr != NULL)
92  * {
93  * MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
94  * }
95  * @endcode
96  *
97  * The user is responsible for creating and freeing memory for all nodes, the linked list module
98  * simply manages the links in the nodes. The node must first be removed from all lists before its
99  * memory is freed.
100  *
101  * <b>The elements of le_sls_Link_t MUST NOT be accessed directly by the user.</b>
102  *
103  *
104  * @section sls_add Adding Links to a List
105  *
106  * To add nodes to a list pass the node's link to one of the following functions:
107  *
108  * - le_sls_Stack() - Adds the link to the head of the list.
109  * - le_sls_Queue() - Adds the link to the tail of the list.
110  * - le_sls_AddAfter() - Adds the link to a list after another specified link.
111  *
112  *
113  * @section sls_remove Removing Links from a List
114  *
115  * To remove nodes from a list, use @c le_sls_Pop() to remove and return the link at the head of
116  * the list.
117  *
118  *
119  * @section sls_peek Accessing Links in a List
120  *
121  * To access a link in a list without removing the link, use one of the following functions:
122  *
123  * - @c le_sls_Peek() - Returns the link at the head of the list without removing it.
124  * - @c le_sls_PeekNext() - Returns the link next to a specified link without removing it.
125  * - @c le_sls_PeekTail() - Returns the link at the tail of the list without removing it.
126  *
127  *
128  * @section sls_query Querying List Status
129  *
130  * The following functions can be used to query a list's current status:
131  *
132  * - @c le_sls_IsEmpty() - Checks if a given list is empty or not.
133  * - @c le_sls_IsInList() - Checks if a specified link is in the list.
134  * - @c le_sls_IsHead() - Checks if a specified link is at the head of the list.
135  * - @c le_sls_IsTail() - Checks if a specified link is at the tail of the list.
136  * - @c le_sls_NumLinks() - Checks the number of links currently in the list.
137  * - @c le_sls_IsListCorrupted() - Checks if the list is corrupted.
138  *
139  *
140  * @section sls_fifo Queues and Stacks
141  *
142  * This implementation of linked lists can easily be used as either queues or stacks.
143  *
144  * To use the list as a queue, restrict additions to the list to @c le_sls_Queue() and removals
145  * from the list to @c le_sls_Pop().
146  *
147  * To use the list as a stack, restrict additions to the list to @c le_sls_Stack() and removals
148  * from the list to @c le_sls_Pop().
149  *
150  *
151  * @section sls_synch Thread Safety and Re-Entrancy
152  *
153  * All linked list function calls are re-entrant and thread safe themselves, but if the nodes and/or
154  * list object are shared by multiple threads, then explicit steps must be taken to maintain mutual
155  * exclusion of access. If you're accessing the same list from multiple threads, you @e must use a
156  * @ref c_mutex "mutex" or some other form of thread synchronization to ensure only one thread
157  * accesses the list at a time.
158  *
159  * <HR>
160  *
161  * Copyright (C) Sierra Wireless Inc.
162  */
163 
164 
165 /** @file le_singlyLinkedList.h
166  *
167  * Legato @ref c_singlyLinkedList include file.
168  *
169  * Copyright (C) Sierra Wireless Inc.
170  */
171 
172 #ifndef LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
173 #define LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
174 
175 
176 //--------------------------------------------------------------------------------------------------
177 /**
178  * This link object must be included in each user node. The node's link object is used to add the
179  * node to a list. A node may have multiple link objects which would allow the node to be part of
180  * multiple lists simultaneously. This link object must be initialized by assigning
181  * LE_SLS_LINK_INIT to it.
182  *
183  * @warning The user MUST NOT access the contents of this structure directly.
184  */
185 //--------------------------------------------------------------------------------------------------
186 typedef struct le_sls_Link
187 {
188  struct le_sls_Link* nextPtr; ///< Next link pointer.
189 }
191 
192 
193 //--------------------------------------------------------------------------------------------------
194 /**
195  * This is the list object. Create this list object and initialize it by assigning
196  * LE_SLS_LIST_INIT to it.
197  *
198  * @warning DON'T access the contents of this structure directly.
199  */
200 //--------------------------------------------------------------------------------------------------
201 typedef struct
202 {
203  le_sls_Link_t* tailLinkPtr; ///< Tail link pointer.
204 }
206 
207 
208 //--------------------------------------------------------------------------------------------------
209 /**
210  * This is a comparator function for sorting a list.
211  *
212  * This must return true if @c a goes before @c b in the list.
213  */
214 //--------------------------------------------------------------------------------------------------
216 
217 
218 //--------------------------------------------------------------------------------------------------
219 /**
220  * When a list is created it must be initialized to this macro in the declaration,
221  * or have @c LE_SLS_LIST_INIT assigned to it, before being used
222  */
223 //--------------------------------------------------------------------------------------------------
224 #define LE_SLS_LIST_DECL_INIT {NULL}
225 
226 //--------------------------------------------------------------------------------------------------
227 /**
228  * When a list is created it must be initialized by assigning this macro to the list, or
229  * initializing to @c LE_SLS_LIST_DECL_INIT in the declaration, before the list can be used.
230  */
231 //--------------------------------------------------------------------------------------------------
232 #define LE_SLS_LIST_INIT (le_sls_List_t)LE_SLS_LIST_DECL_INIT
233 
234 
235 //--------------------------------------------------------------------------------------------------
236 /**
237  * When a link is created it must be initialized by assigning this macro to the link before it can
238  * be used.
239  */
240 //--------------------------------------------------------------------------------------------------
241 #define LE_SLS_LINK_INIT (le_sls_Link_t){NULL}
242 
243 
244 //--------------------------------------------------------------------------------------------------
245 /**
246  * Adds a link at the head of the list.
247  */
248 //--------------------------------------------------------------------------------------------------
249 void le_sls_Stack
250 (
251  le_sls_List_t* listPtr, ///< [IN] List to add to.
252  le_sls_Link_t* newLinkPtr ///< [IN] New link to add.
253 );
254 
255 
256 //--------------------------------------------------------------------------------------------------
257 /**
258  * Adds a link to the tail of the list.
259  */
260 //--------------------------------------------------------------------------------------------------
261 void le_sls_Queue
262 (
263  le_sls_List_t* listPtr, ///< [IN] List to add to.
264  le_sls_Link_t* newLinkPtr ///< [IN] New link to add.
265 );
266 
267 
268 //--------------------------------------------------------------------------------------------------
269 /**
270  * Adds a link after currentLinkPtr, or to the beginning of the list if currentLinkPtr is NULL.
271  * Ensure that currentLinkPtr is in the list (or NULL) otherwise the behaviour of this function is
272  * undefined.
273  */
274 //--------------------------------------------------------------------------------------------------
275 void le_sls_AddAfter
276 (
277  le_sls_List_t* listPtr, ///< [IN] List to add to.
278  le_sls_Link_t* currentLinkPtr, ///< [IN] New link will be inserted after this link.
279  le_sls_Link_t* newLinkPtr ///< [IN] New link to add.
280 );
281 
282 
283 //--------------------------------------------------------------------------------------------------
284 /**
285  * Removes the link found after currentLinkPtr. The user must ensure that currentLinkPtr is in the
286  * list otherwise the behaviour of this function is undefined.
287  *
288  * @return
289  * Pointer to the removed link.
290  * NULL if there are no more links in the list after currentLinkPtr.
291  */
292 //--------------------------------------------------------------------------------------------------
294 (
295  le_sls_List_t* listPtr, ///< [IN] The list to remove from.
296  le_sls_Link_t* currentLinkPtr ///< [IN] The link after this one will be removed from the
297  ///< list.
298 );
299 
300 
301 //--------------------------------------------------------------------------------------------------
302 /**
303  * Removes and returns the link at the head of the list.
304  *
305  * @return
306  * Removed link.
307  * NULL if the link is not available because the list is empty.
308  */
309 //--------------------------------------------------------------------------------------------------
311 (
312  le_sls_List_t* listPtr ///< [IN] List to remove from.
313 );
314 
315 
316 //--------------------------------------------------------------------------------------------------
317 /**
318  * Returns the link at the head of the list without removing it from the list.
319  *
320  * @return
321  * Pointer to the head link if successful.
322  * NULL if the list is empty.
323  */
324 //--------------------------------------------------------------------------------------------------
326 (
327  const le_sls_List_t* listPtr ///< [IN] The list.
328 );
329 
330 
331 //------------------------------------------------------------------------------------------------------------
332 /**
333  * Returns the link at the tail of the list without removing it from the list.
334  *
335  * @return
336  * A pointer to the tail link if successful.
337  * NULL if the list is empty.
338  */
339 //------------------------------------------------------------------------------------------------------------
341 (
342  const le_sls_List_t* listPtr ///< [IN] The list.
343 );
344 
345 
346 //--------------------------------------------------------------------------------------------------
347 /**
348  * Returns the link next to currentLinkPtr (i.e., the link beside currentLinkPtr that's closer to the
349  * tail) without removing it from the list. Ensure currentLinkPtr is in the list
350  * otherwise the behaviour of this function is undefined.
351  *
352  * @return
353  * Pointer to the next link if successful.
354  * NULL if there is no link next to the currentLinkPtr (currentLinkPtr is at the tail of the
355  * list).
356  */
357 //--------------------------------------------------------------------------------------------------
359 (
360  const le_sls_List_t* listPtr, ///< [IN] List containing currentLinkPtr.
361  const le_sls_Link_t* currentLinkPtr ///< [IN] Get the link that is relative to this link.
362 );
363 
364 
365 //--------------------------------------------------------------------------------------------------
366 /**
367  * Checks if a list is empty.
368  *
369  * @return
370  * true if empty, false if not empty.
371  */
372 //--------------------------------------------------------------------------------------------------
374 (
375  const le_sls_List_t* listPtr ///< [IN] The list.
376 )
377 //--------------------------------------------------------------------------------------------------
378 {
379  return (le_sls_Peek(listPtr) == NULL);
380 }
381 
382 
383 //--------------------------------------------------------------------------------------------------
384 /**
385  * Sort a list in ascending order.
386  */
387 //--------------------------------------------------------------------------------------------------
388 void le_sls_Sort
389 (
390  le_sls_List_t* listPtr, ///< [IN] List to sort
391  le_sls_LessThanFunc_t comparatorPtr ///< [IN] Comparator function for sorting
392 );
393 
394 //--------------------------------------------------------------------------------------------------
395 /**
396  * Checks if a link is in the list.
397  *
398  * @return
399  * - true if the link is in the list.
400  * - false if the link is not in the list.
401  */
402 //--------------------------------------------------------------------------------------------------
403 bool le_sls_IsInList
404 (
405  const le_sls_List_t* listPtr, ///< [IN] List to check.
406  const le_sls_Link_t* linkPtr ///< [IN] Check if this link is in the list.
407 );
408 
409 
410 //--------------------------------------------------------------------------------------------------
411 /**
412  * Checks if a link is at the head of the list (next to be popped).
413  *
414  * @return
415  * - true if the link is at the head of the list.
416  * - false if not.
417  */
418 //--------------------------------------------------------------------------------------------------
420 (
421  const le_sls_List_t* listPtr, ///< [IN] List to check.
422  const le_sls_Link_t* linkPtr ///< [IN] Check if this link is at the head of the list.
423 )
424 {
425  return (le_sls_Peek(listPtr) == linkPtr);
426 }
427 
428 
429 //--------------------------------------------------------------------------------------------------
430 /**
431  * Checks if a link is at the tail of the list (last to be popped).
432  *
433  * @return
434  * - true if the link is at the tail of the list.
435  * - false if not.
436  */
437 //--------------------------------------------------------------------------------------------------
439 (
440  const le_sls_List_t* listPtr, ///< [IN] List to check.
441  const le_sls_Link_t* linkPtr ///< [IN] Check if this link is at the tail of the list.
442 )
443 {
444  return (le_sls_PeekTail(listPtr) == linkPtr);
445 }
446 
447 
448 //--------------------------------------------------------------------------------------------------
449 /**
450  * Returns the number of links in a list.
451  *
452  * @return
453  * Number of links.
454  */
455 //--------------------------------------------------------------------------------------------------
456 size_t le_sls_NumLinks
457 (
458  const le_sls_List_t* listPtr ///< [IN] List to count.
459 );
460 
461 
462 //--------------------------------------------------------------------------------------------------
463 /**
464  * Checks if the list is corrupted.
465  *
466  * @return
467  * true if the list is corrupted.
468  * false if the list is not corrupted.
469  */
470 //--------------------------------------------------------------------------------------------------
472 (
473  const le_sls_List_t* listPtr ///< [IN] List to check.
474 );
475 
476 //--------------------------------------------------------------------------------------------------
477 /**
478  * Simple iteration through a singly linked list
479  */
480 //--------------------------------------------------------------------------------------------------
481 #define LE_SLS_FOREACH(listPtr, iteratorPtr, type, member) \
482  for ((iteratorPtr) = CONTAINER_OF(le_sls_Peek(listPtr), type, member); \
483  &((iteratorPtr)->member); \
484  (iteratorPtr) = CONTAINER_OF(le_sls_PeekNext((listPtr),&((iteratorPtr)->member)), \
485  type, member))
486 
487 
488 
489 #endif // LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
size_t le_sls_NumLinks(const le_sls_List_t *listPtr)
bool(* le_sls_LessThanFunc_t)(le_sls_Link_t *a, le_sls_Link_t *b)
Definition: le_singlyLinkedList.h:215
LE_DECLARE_INLINE bool le_sls_IsTail(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
Definition: le_singlyLinkedList.h:439
le_sls_Link_t * le_sls_PeekNext(const le_sls_List_t *listPtr, const le_sls_Link_t *currentLinkPtr)
le_sls_Link_t * le_sls_PeekTail(const le_sls_List_t *listPtr)
LE_DECLARE_INLINE bool le_sls_IsHead(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
Definition: le_singlyLinkedList.h:420
le_sls_Link_t * le_sls_Peek(const le_sls_List_t *listPtr)
void le_sls_Stack(le_sls_List_t *listPtr, le_sls_Link_t *newLinkPtr)
void le_sls_Queue(le_sls_List_t *listPtr, le_sls_Link_t *newLinkPtr)
void le_sls_Sort(le_sls_List_t *listPtr, le_sls_LessThanFunc_t comparatorPtr)
bool le_sls_IsListCorrupted(const le_sls_List_t *listPtr)
bool le_sls_IsInList(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
LE_DECLARE_INLINE bool le_sls_IsEmpty(const le_sls_List_t *listPtr)
Definition: le_singlyLinkedList.h:374
Definition: le_singlyLinkedList.h:201
le_sls_Link_t * le_sls_Pop(le_sls_List_t *listPtr)
le_sls_Link_t * tailLinkPtr
Tail link pointer.
Definition: le_singlyLinkedList.h:203
void le_sls_AddAfter(le_sls_List_t *listPtr, le_sls_Link_t *currentLinkPtr, le_sls_Link_t *newLinkPtr)
#define LE_DECLARE_INLINE
Definition: le_basics.h:320
le_sls_Link_t * le_sls_RemoveAfter(le_sls_List_t *listPtr, le_sls_Link_t *currentLinkPtr)