1 /*******************************************************************************
2  * @file
3  * @brief Single Link List.
4  *******************************************************************************
5  * # License
6  * <b>Copyright 2019 Silicon Laboratories Inc. www.silabs.com</b>
7  *******************************************************************************
8  *
9  * SPDX-License-Identifier: Zlib
10  *
11  * The licensor of this software is Silicon Laboratories Inc.
12  *
13  * This software is provided 'as-is', without any express or implied
14  * warranty. In no event will the authors be held liable for any damages
15  * arising from the use of this software.
16  *
17  * Permission is granted to anyone to use this software for any purpose,
18  * including commercial applications, and to alter it and redistribute it
19  * freely, subject to the following restrictions:
20  *
21  * 1. The origin of this software must not be misrepresented; you must not
22  *    claim that you wrote the original software. If you use this software
23  *    in a product, an acknowledgment in the product documentation would be
24  *    appreciated but is not required.
25  * 2. Altered source versions must be plainly marked as such, and must not be
26  *    misrepresented as being the original software.
27  * 3. This notice may not be removed or altered from any source distribution.
28  *
29  ******************************************************************************/
30 
31 #ifndef SL_SLIST_H
32 #define SL_SLIST_H
33 
34 #include <stdbool.h>
35 #include <stdlib.h>
36 #include <stdint.h>
37 
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41 
42 /*******************************************************************************
43  * @addtogroup slist Singly-Linked List
44  * @brief Singly-linked List module provides APIs to handle singly-linked list
45  *        operations such as insert, push, pop, push back, sort and remove.
46  *
47  * @note The pop operation follows FIFO method.
48  * @n @section slist_usage Singly-Linked List module Usage
49  * @{
50  ******************************************************************************/
51 
52 /// List node type
53 typedef struct sl_slist_node sl_slist_node_t;
54 
55 /// List node
56 struct sl_slist_node {
57   sl_slist_node_t *node; ///< List node
58 };
59 
60 #ifndef DOXYGEN
61 #define  container_of(ptr, type, member)  (type *)((uintptr_t)(ptr) - ((uintptr_t)(&((type *)0)->member)))
62 
63 #define  SL_SLIST_ENTRY                               container_of
64 
65 #define  SL_SLIST_FOR_EACH(list_head, iterator)       for ((iterator) = (list_head); (iterator) != NULL; (iterator) = (iterator)->node)
66 
67 #define  SL_SLIST_FOR_EACH_ENTRY(list_head, entry, type, member) for (  (entry) = SL_SLIST_ENTRY(list_head, type, member);     \
68                                                                         (type *)(entry) != SL_SLIST_ENTRY(NULL, type, member); \
69                                                                         (entry) = SL_SLIST_ENTRY((entry)->member.node, type, member))
70 #endif
71 
72 // -----------------------------------------------------------------------------
73 // Prototypes
74 
75 /*******************************************************************************
76  * Initialize a singly-linked list.
77  *
78  * @param    head  Pointer to pointer of head element of list.
79  ******************************************************************************/
80 void sl_slist_init(sl_slist_node_t **head);
81 
82 /*******************************************************************************
83  * Add given item at beginning of the list.
84  *
85  * @param    head  Pointer to pointer of head element of the list.
86  *
87  * @param    item  Pointer to an item to add.
88  ******************************************************************************/
89 void sl_slist_push(sl_slist_node_t **head,
90                    sl_slist_node_t *item);
91 
92 /*******************************************************************************
93  * Add item at the end of the list.
94  *
95  * @param    head  Pointer to the pointer of a head element of the list.
96  *
97  * @param    item  Pointer to the item to add.
98  ******************************************************************************/
99 void sl_slist_push_back(sl_slist_node_t **head,
100                         sl_slist_node_t *item);
101 
102 /*******************************************************************************
103  * Remove and return the first element of the list.
104  *
105  * @param    head  Pointer to he pointer of the head element of the list.
106  *
107  * @return   Pointer to item that was at top of the list.
108  ******************************************************************************/
109 sl_slist_node_t *sl_slist_pop(sl_slist_node_t **head);
110 
111 /*******************************************************************************
112  * Insert an item after the given item.
113  *
114  * @param    item  Pointer to an item to add.
115  *
116  * @param    pos   Pointer to an item after which the item to add will be inserted.
117  ******************************************************************************/
118 void sl_slist_insert(sl_slist_node_t *item,
119                      sl_slist_node_t *pos);
120 
121 /*******************************************************************************
122  * Remove an item from the list.
123  *
124  * @param    head  Pointer to pointer of the head element of list.
125  *
126  * @param    item  Pointer to the item to remove.
127  *
128  * @note     (1) An EFM_ASSERT is thrown if the item is not found within the list.
129  ******************************************************************************/
130 void sl_slist_remove(sl_slist_node_t **head,
131                      sl_slist_node_t *item);
132 
133 /*******************************************************************************
134  * Sort list items.
135  *
136  * @param    head      Pointer to the pointer of the head element of the list.
137  *
138  * @param    cmp_fnct  Pointer to function to use for sorting the list.
139  *                     item_l    Pointer to left  item.
140  *                     item_r    Pointer to right item.
141  *                     Returns whether the two items are ordered (true) or not (false).
142  ******************************************************************************/
143 void sl_slist_sort(sl_slist_node_t **head,
144                    bool (*cmp_fnct)(sl_slist_node_t *item_l,
145                                     sl_slist_node_t *item_r));
146 
147 /** @} (end addtogroup slist) */
148 
149 #ifdef __cplusplus
150 }
151 #endif
152 
153 #endif /* SL_SLIST_H */
154