le_singlyLinkedList.h

Go to the documentation of this file.
1 /**
2  * @page c_singlyLinkedList Singly Linked List API
3  *
4  * @ref 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. Use of this work is subject to license.
162  */
163 
164 
165  /** @file le_singlyLinkedList.h
166  *
167  * Legato @ref c_singlyLinkedList include file.
168  *
169  * Copyright (C) Sierra Wireless Inc. Use of this work is subject to license.
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  * When a list is created, it must be initialized by assigning this macro to the list before the list
211  * can be used.
212  */
213 //--------------------------------------------------------------------------------------------------
214 #define LE_SLS_LIST_INIT (le_sls_List_t){NULL}
215 
216 
217 //--------------------------------------------------------------------------------------------------
218 /**
219  * When a link is created, it must be initialized by assigning this macro to the link before it can
220  * be used.
221  */
222 //--------------------------------------------------------------------------------------------------
223 #define LE_SLS_LINK_INIT (le_sls_Link_t){NULL}
224 
225 
226 //--------------------------------------------------------------------------------------------------
227 /**
228  * Adds a link at the head of the list.
229  */
230 //--------------------------------------------------------------------------------------------------
231 void le_sls_Stack
232 (
233  le_sls_List_t* listPtr, ///< [IN] List to add to.
234  le_sls_Link_t* newLinkPtr ///< [IN] New link to add.
235 );
236 
237 
238 //--------------------------------------------------------------------------------------------------
239 /**
240  * Adds a link to the tail of the list.
241  */
242 //--------------------------------------------------------------------------------------------------
243 void le_sls_Queue
244 (
245  le_sls_List_t* listPtr, ///< [IN] List to add to.
246  le_sls_Link_t* newLinkPtr ///< [IN] New link to add.
247 );
248 
249 
250 //--------------------------------------------------------------------------------------------------
251 /**
252  * Adds a link after currentLinkPtr. Ensure that currentLinkPtr is in the list
253  * otherwise the behaviour of this function is undefined.
254  */
255 //--------------------------------------------------------------------------------------------------
256 void le_sls_AddAfter
257 (
258  le_sls_List_t* listPtr, ///< [IN] List to add to.
259  le_sls_Link_t* currentLinkPtr, ///< [IN] New link will be inserted after this link.
260  le_sls_Link_t* newLinkPtr ///< [IN] New link to add.
261 );
262 
263 
264 //--------------------------------------------------------------------------------------------------
265 /**
266  * Removes the link found after currentLinkPtr. The user must ensure that currentLinkPtr is in the
267  * list otherwise the behaviour of this function is undefined.
268  *
269  * @return
270  * Pointer to the removed link.
271  * NULL if there are no more links in the list after currentLinkPtr.
272  */
273 //--------------------------------------------------------------------------------------------------
275 (
276  le_sls_List_t* listPtr, ///< [IN] The list to remove from.
277  le_sls_Link_t* currentLinkPtr ///< [IN] The link after this one will be removed from the
278  ///< list.
279 );
280 
281 
282 //--------------------------------------------------------------------------------------------------
283 /**
284  * Removes and returns the link at the head of the list.
285  *
286  * @return
287  * Removed link.
288  * NULL if the link is not available because the list is empty.
289  */
290 //--------------------------------------------------------------------------------------------------
292 (
293  le_sls_List_t* listPtr ///< [IN] List to remove from.
294 );
295 
296 
297 //--------------------------------------------------------------------------------------------------
298 /**
299  * Returns the link at the head of the list without removing it from the list.
300  *
301  * @return
302  * Pointer to the head link if successful.
303  * NULL if the list is empty.
304  */
305 //--------------------------------------------------------------------------------------------------
307 (
308  const le_sls_List_t* listPtr ///< [IN] The list.
309 );
310 
311 
312 //------------------------------------------------------------------------------------------------------------
313 /**
314  * Returns the link at the tail of the list without removing it from the list.
315  *
316  * @return
317  * A pointer to the tail link if successful.
318  * NULL if the list is empty.
319  */
320 //------------------------------------------------------------------------------------------------------------
322 (
323  const le_sls_List_t* listPtr ///< [IN] The list.
324 );
325 
326 
327 //--------------------------------------------------------------------------------------------------
328 /**
329  * Returns the link next to currentLinkPtr (i.e., the link beside currentLinkPtr that's closer to the
330  * tail) without removing it from the list. Ensure currentLinkPtr is in the list
331  * otherwise the behaviour of this function is undefined.
332  *
333  * @return
334  * Pointer to the next link if successful.
335  * NULL if there is no link next to the currentLinkPtr (currentLinkPtr is at the tail of the
336  * list).
337  */
338 //--------------------------------------------------------------------------------------------------
340 (
341  const le_sls_List_t* listPtr, ///< [IN] List containing currentLinkPtr.
342  const le_sls_Link_t* currentLinkPtr ///< [IN] Get the link that is relative to this link.
343 );
344 
345 
346 //--------------------------------------------------------------------------------------------------
347 /**
348  * Checks if a list is empty.
349  *
350  * @return
351  * true if empty, false if not empty.
352  */
353 //--------------------------------------------------------------------------------------------------
354 static inline bool le_sls_IsEmpty
355 (
356  const le_sls_List_t* listPtr ///< [IN] The list.
357 )
358 //--------------------------------------------------------------------------------------------------
359 {
360  return (le_sls_Peek(listPtr) == NULL);
361 }
362 
363 
364 //--------------------------------------------------------------------------------------------------
365 /**
366  * Checks if a link is in the list.
367  *
368  * @return
369  * - true if the link is in the list.
370  * - false if the link is not in the list.
371  */
372 //--------------------------------------------------------------------------------------------------
373 bool le_sls_IsInList
374 (
375  const le_sls_List_t* listPtr, ///< [IN] List to check.
376  const le_sls_Link_t* linkPtr ///< [IN] Check if this link is in the list.
377 );
378 
379 
380 //--------------------------------------------------------------------------------------------------
381 /**
382  * Checks if a link is at the head of the list (next to be popped).
383  *
384  * @return
385  * - true if the link is at the head of the list.
386  * - false if not.
387  */
388 //--------------------------------------------------------------------------------------------------
389 static inline bool le_sls_IsHead
390 (
391  const le_sls_List_t* listPtr, ///< [IN] List to check.
392  const le_sls_Link_t* linkPtr ///< [IN] Check if this link is at the head of the list.
393 )
394 {
395  return (le_sls_Peek(listPtr) == linkPtr);
396 }
397 
398 
399 //--------------------------------------------------------------------------------------------------
400 /**
401  * Checks if a link is at the tail of the list (last to be popped).
402  *
403  * @return
404  * - true if the link is at the tail of the list.
405  * - false if not.
406  */
407 //--------------------------------------------------------------------------------------------------
408 static inline bool le_sls_IsTail
409 (
410  const le_sls_List_t* listPtr, ///< [IN] List to check.
411  const le_sls_Link_t* linkPtr ///< [IN] Check if this link is at the tail of the list.
412 )
413 {
414  return (le_sls_PeekTail(listPtr) == linkPtr);
415 }
416 
417 
418 //--------------------------------------------------------------------------------------------------
419 /**
420  * Returns the number of links in a list.
421  *
422  * @return
423  * Number of links.
424  */
425 //--------------------------------------------------------------------------------------------------
426 size_t le_sls_NumLinks
427 (
428  const le_sls_List_t* listPtr ///< [IN] List to count.
429 );
430 
431 
432 //--------------------------------------------------------------------------------------------------
433 /**
434  * Checks if the list is corrupted.
435  *
436  * @return
437  * true if the list is corrupted.
438  * false if the list is not corrupted.
439  */
440 //--------------------------------------------------------------------------------------------------
442 (
443  const le_sls_List_t* listPtr ///< [IN] List to check.
444 );
445 
446 
447 #endif // LEGATO_SINGLY_LINKED_LIST_INCLUDE_GUARD
448 
static bool le_sls_IsHead(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
Definition: le_singlyLinkedList.h:390
void le_sls_Queue(le_sls_List_t *listPtr, le_sls_Link_t *newLinkPtr)
static bool le_sls_IsEmpty(const le_sls_List_t *listPtr)
Definition: le_singlyLinkedList.h:355
bool le_sls_IsInList(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
static bool le_sls_IsTail(const le_sls_List_t *listPtr, const le_sls_Link_t *linkPtr)
Definition: le_singlyLinkedList.h:409
le_sls_Link_t * le_sls_RemoveAfter(le_sls_List_t *listPtr, le_sls_Link_t *currentLinkPtr)
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_Peek(const le_sls_List_t *listPtr)
le_sls_Link_t * le_sls_Pop(le_sls_List_t *listPtr)
void le_sls_AddAfter(le_sls_List_t *listPtr, le_sls_Link_t *currentLinkPtr, le_sls_Link_t *newLinkPtr)
bool le_sls_IsListCorrupted(const le_sls_List_t *listPtr)
le_sls_Link_t * tailLinkPtr
Tail link pointer.
Definition: le_singlyLinkedList.h:203
le_sls_Link_t * le_sls_PeekTail(const le_sls_List_t *listPtr)
size_t le_sls_NumLinks(const le_sls_List_t *listPtr)
Definition: le_singlyLinkedList.h:201
void le_sls_Stack(le_sls_List_t *listPtr, le_sls_Link_t *newLinkPtr)