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 by assigning this macro to the list before the list
221  * can be used.
222  */
223 //--------------------------------------------------------------------------------------------------
224 #define LE_SLS_LIST_INIT (le_sls_List_t){NULL}
225 
226 
227 //--------------------------------------------------------------------------------------------------
228 /**
229  * When a link is created, it must be initialized by assigning this macro to the link before it can
230  * be used.
231  */
232 //--------------------------------------------------------------------------------------------------
233 #define LE_SLS_LINK_INIT (le_sls_Link_t){NULL}
234 
235 
236 //--------------------------------------------------------------------------------------------------
237 /**
238  * Adds a link at the head of the list.
239  */
240 //--------------------------------------------------------------------------------------------------
241 void le_sls_Stack
242 (
243  le_sls_List_t* listPtr, ///< [IN] List to add to.
244  le_sls_Link_t* newLinkPtr ///< [IN] New link to add.
245 );
246 
247 
248 //--------------------------------------------------------------------------------------------------
249 /**
250  * Adds a link to the tail of the list.
251  */
252 //--------------------------------------------------------------------------------------------------
253 void le_sls_Queue
254 (
255  le_sls_List_t* listPtr, ///< [IN] List to add to.
256  le_sls_Link_t* newLinkPtr ///< [IN] New link to add.
257 );
258 
259 
260 //--------------------------------------------------------------------------------------------------
261 /**
262  * Adds a link after currentLinkPtr, or to the beginning of the list if currentLinkPtr is NULL.
263  * Ensure that currentLinkPtr is in the list (or NULL) otherwise the behaviour of this function is
264  * undefined.
265  */
266 //--------------------------------------------------------------------------------------------------
267 void le_sls_AddAfter
268 (
269  le_sls_List_t* listPtr, ///< [IN] List to add to.
270  le_sls_Link_t* currentLinkPtr, ///< [IN] New link will be inserted after this link.
271  le_sls_Link_t* newLinkPtr ///< [IN] New link to add.
272 );
273 
274 
275 //--------------------------------------------------------------------------------------------------
276 /**
277  * Removes the link found after currentLinkPtr. The user must ensure that currentLinkPtr is in the
278  * list otherwise the behaviour of this function is undefined.
279  *
280  * @return
281  * Pointer to the removed link.
282  * NULL if there are no more links in the list after currentLinkPtr.
283  */
284 //--------------------------------------------------------------------------------------------------
286 (
287  le_sls_List_t* listPtr, ///< [IN] The list to remove from.
288  le_sls_Link_t* currentLinkPtr ///< [IN] The link after this one will be removed from the
289  ///< list.
290 );
291 
292 
293 //--------------------------------------------------------------------------------------------------
294 /**
295  * Removes and returns the link at the head of the list.
296  *
297  * @return
298  * Removed link.
299  * NULL if the link is not available because the list is empty.
300  */
301 //--------------------------------------------------------------------------------------------------
303 (
304  le_sls_List_t* listPtr ///< [IN] List to remove from.
305 );
306 
307 
308 //--------------------------------------------------------------------------------------------------
309 /**
310  * Returns the link at the head of the list without removing it from the list.
311  *
312  * @return
313  * Pointer to the head link if successful.
314  * NULL if the list is empty.
315  */
316 //--------------------------------------------------------------------------------------------------
318 (
319  const le_sls_List_t* listPtr ///< [IN] The list.
320 );
321 
322 
323 //------------------------------------------------------------------------------------------------------------
324 /**
325  * Returns the link at the tail of the list without removing it from the list.
326  *
327  * @return
328  * A pointer to the tail link if successful.
329  * NULL if the list is empty.
330  */
331 //------------------------------------------------------------------------------------------------------------
333 (
334  const le_sls_List_t* listPtr ///< [IN] The list.
335 );
336 
337 
338 //--------------------------------------------------------------------------------------------------
339 /**
340  * Returns the link next to currentLinkPtr (i.e., the link beside currentLinkPtr that's closer to the
341  * tail) without removing it from the list. Ensure currentLinkPtr is in the list
342  * otherwise the behaviour of this function is undefined.
343  *
344  * @return
345  * Pointer to the next link if successful.
346  * NULL if there is no link next to the currentLinkPtr (currentLinkPtr is at the tail of the
347  * list).
348  */
349 //--------------------------------------------------------------------------------------------------
351 (
352  const le_sls_List_t* listPtr, ///< [IN] List containing currentLinkPtr.
353  const le_sls_Link_t* currentLinkPtr ///< [IN] Get the link that is relative to this link.
354 );
355 
356 
357 //--------------------------------------------------------------------------------------------------
358 /**
359  * Checks if a list is empty.
360  *
361  * @return
362  * true if empty, false if not empty.
363  */
364 //--------------------------------------------------------------------------------------------------
366 (
367  const le_sls_List_t* listPtr ///< [IN] The list.
368 )
369 //--------------------------------------------------------------------------------------------------
370 {
371  return (le_sls_Peek(listPtr) == NULL);
372 }
373 
374 
375 //--------------------------------------------------------------------------------------------------
376 /**
377  * Sort a list in ascending order.
378  */
379 //--------------------------------------------------------------------------------------------------
380 void le_sls_Sort
381 (
382  le_sls_List_t* listPtr, ///< [IN] List to sort
383  le_sls_LessThanFunc_t comparatorPtr ///< [IN] Comparator function for sorting
384 );
385 
386 //--------------------------------------------------------------------------------------------------
387 /**
388  * Checks if a link is in the list.
389  *
390  * @return
391  * - true if the link is in the list.
392  * - false if the link is not in the list.
393  */
394 //--------------------------------------------------------------------------------------------------
395 bool le_sls_IsInList
396 (
397  const le_sls_List_t* listPtr, ///< [IN] List to check.
398  const le_sls_Link_t* linkPtr ///< [IN] Check if this link is in the list.
399 );
400 
401 
402 //--------------------------------------------------------------------------------------------------
403 /**
404  * Checks if a link is at the head of the list (next to be popped).
405  *
406  * @return
407  * - true if the link is at the head of the list.
408  * - false if not.
409  */
410 //--------------------------------------------------------------------------------------------------
412 (
413  const le_sls_List_t* listPtr, ///< [IN] List to check.
414  const le_sls_Link_t* linkPtr ///< [IN] Check if this link is at the head of the list.
415 )
416 {
417  return (le_sls_Peek(listPtr) == linkPtr);
418 }
419 
420 
421 //--------------------------------------------------------------------------------------------------
422 /**
423  * Checks if a link is at the tail of the list (last to be popped).
424  *
425  * @return
426  * - true if the link is at the tail of the list.
427  * - false if not.
428  */
429 //--------------------------------------------------------------------------------------------------
431 (
432  const le_sls_List_t* listPtr, ///< [IN] List to check.
433  const le_sls_Link_t* linkPtr ///< [IN] Check if this link is at the tail of the list.
434 )
435 {
436  return (le_sls_PeekTail(listPtr) == linkPtr);
437 }
438 
439 
440 //--------------------------------------------------------------------------------------------------
441 /**
442  * Returns the number of links in a list.
443  *
444  * @return
445  * Number of links.
446  */
447 //--------------------------------------------------------------------------------------------------
448 size_t le_sls_NumLinks
449 (
450  const le_sls_List_t* listPtr ///< [IN] List to count.
451 );
452 
453 
454 //--------------------------------------------------------------------------------------------------
455 /**
456  * Checks if the list is corrupted.
457  *
458  * @return
459  * true if the list is corrupted.
460  * false if the list is not corrupted.
461  */
462 //--------------------------------------------------------------------------------------------------
464 (
465  const le_sls_List_t* listPtr ///< [IN] List to check.
466 );
467 
468 //--------------------------------------------------------------------------------------------------
469 /**
470  * Simple iteration through a singly linked list
471  */
472 //--------------------------------------------------------------------------------------------------
473 #define LE_SLS_FOREACH(listPtr, iteratorPtr, type, member) \
474  for ((iteratorPtr) = CONTAINER_OF(le_sls_Peek(listPtr), type, member); \
475  &((iteratorPtr)->member); \
476  (iteratorPtr) = CONTAINER_OF(le_sls_PeekNext((listPtr),&((iteratorPtr)->member)), \
477  type, member))
478 
479 
480 
481 #endif // LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
482 
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:431
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:412
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:366
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:274
le_sls_Link_t * le_sls_RemoveAfter(le_sls_List_t *listPtr, le_sls_Link_t *currentLinkPtr)