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 * Join two lists together.
123 *
124 * @param head_list_1 Pointer to the pointer of a head element of the list.
125 *
126 * @param head_list_2 Pointer to the pointer of a head element of the list
127 * to be appended. After the call, this pointer will be
128 * invalidated (set to NULL).
129 ******************************************************************************/
130 void sl_slist_join(sl_slist_node_t **head_list_1,
131 sl_slist_node_t **head_list_2);
132
133 /*******************************************************************************
134 * Remove an item from the list.
135 *
136 * @param head Pointer to pointer of the head element of list.
137 *
138 * @param item Pointer to the item to remove.
139 ******************************************************************************/
140 void sl_slist_remove(sl_slist_node_t **head,
141 sl_slist_node_t *item);
142
143 /*******************************************************************************
144 * Sort list items.
145 *
146 * @param head Pointer to the pointer of the head element of the list.
147 *
148 * @param cmp_fnct Pointer to function to use for sorting the list.
149 * item_l Pointer to left item.
150 * item_r Pointer to right item.
151 * Returns whether the two items are ordered (true) or not (false).
152 ******************************************************************************/
153 void sl_slist_sort(sl_slist_node_t **head,
154 bool (*cmp_fnct)(sl_slist_node_t *item_l,
155 sl_slist_node_t *item_r));
156
157 /*******************************************************************************
158 * Checks if the list is empty.
159 *
160 * @param head Pointer to the head element of the list.
161 ******************************************************************************/
sl_slist_is_empty(sl_slist_node_t * head)162 static inline bool sl_slist_is_empty(sl_slist_node_t *head)
163 {
164 return head == NULL;
165 }
166
167 /** @} (end addtogroup slist) */
168
169 #ifdef __cplusplus
170 }
171 #endif
172
173 #endif /* SL_SLIST_H */
174
