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