xref: /kernel/liteos_m/utils/los_list.h (revision 3d8536b4) 
1/*
2 * Copyright (c) 2013-2019 Huawei Technologies Co., Ltd. All rights reserved.
3 * Copyright (c) 2020-2021 Huawei Device Co., Ltd. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this list of
9 *    conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
12 *    of conditions and the following disclaimer in the documentation and/or other materials
13 *    provided with the distribution.
14 *
15 * 3. Neither the name of the copyright holder nor the names of its contributors may be used
16 *    to endorse or promote products derived from this software without specific prior written
17 *    permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32/**
33 * @defgroup los_list Doubly linked list
34 * @ingroup kernel
35 */
36
37#ifndef _LOS_LIST_H
38#define _LOS_LIST_H
39
40#include "los_compiler.h"
41
42#ifdef __cplusplus
43#if __cplusplus
44extern "C" {
45#endif /* __cplusplus */
46#endif /* __cplusplus */
47
48/**
49 * @ingroup los_list
50 * Structure of a node in a doubly linked list.
51 */
52typedef struct LOS_DL_LIST {
53    struct LOS_DL_LIST *pstPrev; /**< Current node's pointer to the previous node */
54    struct LOS_DL_LIST *pstNext; /**< Current node's pointer to the next node */
55} LOS_DL_LIST;
56
57/**
58 * @ingroup los_list
59 * @brief Initialize a doubly linked list.
60 *
61 * @par Description:
62 * This API is used to initialize a doubly linked list.
63 * @attention
64 * <ul>
65 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
66 * </ul>
67 *
68 * @param list    [IN] Node in a doubly linked list.
69 *
70 * @retval None.
71 * @par Dependency:
72 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
73 * @see
74 */
75LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListInit(LOS_DL_LIST *list)
76{
77    list->pstNext = list;
78    list->pstPrev = list;
79}
80
81/**
82 * @ingroup los_list
83 * @brief Point to the next node pointed to by the current node.
84 *
85 * @par Description:
86 * <ul>
87 * <li>This API is used to point to the next node pointed to by the current node.</li>
88 * </ul>
89 * @attention
90 * <ul>
91 * <li>None.</li>
92 * </ul>
93 *
94 * @param object  [IN] Node in the doubly linked list.
95 *
96 * @retval None.
97 * @par Dependency:
98 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
99 * @see
100 */
101#define LOS_DL_LIST_FIRST(object) ((object)->pstNext)
102
103/**
104 * @ingroup los_list
105 * @brief Insert a new node to a doubly linked list.
106 *
107 * @par Description:
108 * This API is used to insert a new node to a doubly linked list.
109 * @attention
110 * <ul>
111 * <li>The parameters passed in should be ensured to be legal pointers.</li>
112 * </ul>
113 *
114 * @param list    [IN]   Doubly linked list where the new node is inserted.
115 * @param node    [IN]   New node to be inserted.
116 *
117 * @retval None
118 * @par Dependency:
119 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
120 * @see LOS_ListDelete
121 */
122LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST *node)
123{
124    node->pstNext = list->pstNext;
125    node->pstPrev = list;
126    list->pstNext->pstPrev = node;
127    list->pstNext = node;
128}
129
130/**
131 * @ingroup los_list
132 * @brief Insert a node to the tail of a doubly linked list.
133 *
134 * @par Description:
135 * This API is used to insert a new node to the tail of a doubly linked list.
136 * @attention
137 * <ul>
138 * <li>The parameters passed in should be ensured to be legal pointers.</li>
139 * </ul>
140 *
141 * @param list     [IN] Doubly linked list where the new node is inserted.
142 * @param node     [IN] New node to be inserted.
143 *
144 * @retval None.
145 * @par Dependency:
146 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
147 * @see LOS_ListAdd | LOS_ListHeadInsert
148 */
149LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
150{
151    LOS_ListAdd(list->pstPrev, node);
152}
153
154/**
155 * @ingroup los_list
156 * @brief Insert a node to the head of a doubly linked list.
157 *
158 * @par Description:
159 * This API is used to insert a new node to the head of a doubly linked list.
160 * @attention
161 * <ul>
162 * <li>The parameters passed in should be ensured to be legal pointers.</li>
163 * </ul>
164 *
165 * @param list     [IN] Doubly linked list where the new node is inserted.
166 * @param node     [IN] New node to be inserted.
167 *
168 * @retval None.
169 * @par Dependency:
170 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
171 * @see LOS_ListAdd | LOS_ListTailInsert
172 */
173LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListHeadInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
174{
175    LOS_ListAdd(list, node);
176}
177
178/**
179 * @ingroup los_list
180 * @brief Delete a specified node from a doubly linked list.
181 *
182 * @par Description:
183 * <ul>
184 * <li>This API is used to delete a specified node from a doubly linked list.</li>
185 * </ul>
186 * @attention
187 * <ul>
188 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
189 * </ul>
190 *
191 * @param node    [IN] Node to be deleted.
192 *
193 * @retval None.
194 * @par Dependency:
195 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
196 * @see LOS_ListAdd
197 */
198LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListDelete(LOS_DL_LIST *node)
199{
200    node->pstNext->pstPrev = node->pstPrev;
201    node->pstPrev->pstNext = node->pstNext;
202    node->pstNext = (LOS_DL_LIST *)NULL;
203    node->pstPrev = (LOS_DL_LIST *)NULL;
204}
205
206/**
207 * @ingroup los_list
208 * @brief Identify whether a specified doubly linked list is empty.
209 *
210 * @par Description:
211 * <ul>
212 * <li>This API is used to return whether a doubly linked list is empty.</li>
213 * </ul>
214 * @attention
215 * <ul>
216 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
217 * </ul>
218 *
219 * @param list  [IN] Doubly linked node.
220 *
221 * @retval TRUE The doubly linked list is empty.
222 * @retval FALSE The doubly linked list is not empty.
223 * @par Dependency:
224 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
225 * @see
226 */
227LITE_OS_SEC_ALW_INLINE STATIC_INLINE BOOL LOS_ListEmpty(LOS_DL_LIST *node)
228{
229    return (BOOL)(node->pstNext == node);
230}
231
232/**
233 * @ingroup los_list
234 * @brief Obtain the pointer to a doubly linked list in a structure.
235 *
236 * @par Description:
237 * This API is used to obtain the pointer to a doubly linked list in a structure.
238 * @attention
239 * <ul>
240 * <li>None.</li>
241 * </ul>
242 *
243 * @param type    [IN] Structure name.
244 * @param member  [IN] Member name of the doubly linked list in the structure.
245 *
246 * @retval Pointer to the doubly linked list in the structure.
247 * @par Dependency:
248 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
249 * @see
250 */
251#define LOS_OFF_SET_OF(type, member) ((UINT32)&(((type *)0)->member))
252
253/**
254 * @ingroup los_list
255 * @brief Obtain the pointer to a structure that contains a doubly linked list.
256 *
257 * @par Description:
258 * This API is used to obtain the pointer to a structure that contains a doubly linked list.
259 * <ul>
260 * <li>None.</li>
261 * </ul>
262 * @attention
263 * <ul>
264 * <li>None.</li>
265 * </ul>
266 *
267 * @param item    [IN] Current node's pointer to the next node.
268 * @param type    [IN] Structure name.
269 * @param member  [IN] Member name of the doubly linked list in the structure.
270 *
271 * @retval Pointer to the structure that contains the doubly linked list.
272 * @par Dependency:
273 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
274 * @see
275 */
276#define LOS_DL_LIST_ENTRY(item, type, member) \
277    ((type *)(VOID *)((CHAR *)(item) - LOS_OFF_SET_OF(type, member))) \
278
279/**
280 * @ingroup los_list
281 * @brief Iterate over a doubly linked list of given type.
282 *
283 * @par Description:
284 * This API is used to iterate over a doubly linked list of given type.
285 * @attention
286 * <ul>
287 * <li>None.</li>
288 * </ul>
289 *
290 * @param item           [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
291 * @param list           [IN] Pointer to the doubly linked list to be traversed.
292 * @param type           [IN] Structure name.
293 * @param member         [IN] Member name of the doubly linked list in the structure.
294 *
295 * @retval None.
296 * @par Dependency:
297 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
298 * @see
299 */
300#define LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member) \
301    for ((item) = LOS_DL_LIST_ENTRY((list)->pstNext, type, member); \
302            &(item)->member != (list); \
303            (item) = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
304
305/**
306 * @ingroup los_list
307 * @brief iterate over a doubly linked list safe against removal of list entry.
308 *
309 * @par Description:
310 * This API is used to iterate over a doubly linked list safe against removal of list entry.
311 * @attention
312 * <ul>
313 * <li>None.</li>
314 * </ul>
315 *
316 * @param item           [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
317 * @param next           [IN] Save the next node.
318 * @param list           [IN] Pointer to the doubly linked list to be traversed.
319 * @param type           [IN] Structure name.
320 * @param member         [IN] Member name of the doubly linked list in the structure.
321 *
322 * @retval None.
323 * @par Dependency:
324 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
325 * @see
326 */
327#define LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member) \
328    for ((item) = LOS_DL_LIST_ENTRY((list)->pstNext, type, member), \
329            (next) = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member); \
330            &((item)->member) != (list); \
331            (item) = (next), (next) = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
332
333/**
334 * @ingroup los_list
335 * @brief Delete initialize a doubly linked list.
336 *
337 * @par Description:
338 * This API is used to delete initialize a doubly linked list.
339 * @attention
340 * <ul>
341 * <li>The parameter passed in should be ensured to be s legal pointer.</li>
342 * </ul>
343 *
344 * @param list    [IN] Doubly linked list.
345 *
346 * @retval None.
347 * @par Dependency:
348 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
349 * @see
350 */
351LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListDelInit(LOS_DL_LIST *list)
352{
353    list->pstNext->pstPrev = list->pstPrev;
354    list->pstPrev->pstNext = list->pstNext;
355    LOS_ListInit(list);
356}
357
358/**
359 * @ingroup los_list
360 * @brief iterate over a doubly linked list.
361 *
362 * @par Description:
363 * This API is used to iterate over a doubly linked list.
364 * @attention
365 * <ul>
366 * <li>None.</li>
367 * </ul>
368 *
369 * @param item           [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
370 * @param list           [IN] Pointer to the doubly linked list to be traversed.
371 *
372 * @retval None.
373 * @par Dependency:
374 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
375 * @see
376 */
377#define LOS_DL_LIST_FOR_EACH(item, list) \
378    for ((item) = (list)->pstNext; (item) != (list); (item) = (item)->pstNext)
379
380/**
381 * @ingroup los_list
382 * @brief Iterate over a doubly linked list safe against removal of list entry.
383 *
384 * @par Description:
385 * This API is used to iterate over a doubly linked list safe against removal of list entry.
386 * @attention
387 * <ul>
388 * <li>None.</li>
389 * </ul>
390 *
391 * @param item           [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
392 * @param next           [IN] Save the next node.
393 * @param list           [IN] Pointer to the doubly linked list to be traversed.
394 *
395 * @retval None.
396 * @par Dependency:
397 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
398 * @see
399 */
400#define LOS_DL_LIST_FOR_EACH_SAFE(item, next, list) \
401    for ((item) = (list)->pstNext, (next) = (item)->pstNext; (item) != (list); \
402            (item) = (next), (next) = (item)->pstNext)
403
404/**
405 * @ingroup los_list
406 * @brief Initialize a double linked list.
407 *
408 * @par Description:
409 * This API is used to initialize a double linked list.
410 * @attention
411 * <ul>
412 * <li>None.</li>
413 * </ul>
414 *
415 * @param list           [IN] Pointer to the doubly linked list to be traversed.
416 *
417 * @retval None.
418 * @par Dependency:
419 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
420 * @see
421 */
422#define LOS_DL_LIST_HEAD(list) \
423    LOS_DL_LIST list = { &(list), &(list) }
424
425#ifdef __cplusplus
426#if __cplusplus
427}
428#endif /* __cplusplus */
429#endif /* __cplusplus */
430
431#endif /* _LOS_LIST_H */
432