1 /*
2 * Copyright (c) 2020 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 /*
17 * @defgroup utils_list Doubly linked list
18 * @ingroup utils
19 * @attention
20 * <ul>
21 * <li>All of the APIs provided in this module are not thread-safe.</li>
22 * </ul>
23 */
24
25 #ifndef _UTILS_LIST_H
26 #define _UTILS_LIST_H
27
28 #include <stdbool.h>
29 #include "ohos_types.h"
30
31 #ifdef __cplusplus
32 #if __cplusplus
33 extern "C" {
34 #endif /* __cplusplus */
35 #endif /* __cplusplus */
36
37 typedef struct UTILS_DL_LIST {
38 struct UTILS_DL_LIST *pstPrev; /* < Current node's pointer to the previous node */
39 struct UTILS_DL_LIST *pstNext; /* < Current node's pointer to the next node */
40 } UTILS_DL_LIST;
41
42 /*
43 * @ingroup utils_list
44 *
45 * @par Description:
46 * This API is used to initialize a doubly linked list.
47 * @attention
48 * <ul>
49 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
50 * </ul>
51 *
52 * @param list [IN] Node in a doubly linked list.
53 *
54 * @retval None.
55 * @par Dependency:
56 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
57 * @see
58 */
UtilsListInit(UTILS_DL_LIST * list)59 static inline void UtilsListInit(UTILS_DL_LIST *list)
60 {
61 list->pstNext = list;
62 list->pstPrev = list;
63 }
64
65 /*
66 * @ingroup utils_list
67 * @brief Point to the next node pointed to by the current node.
68 *
69 * @par Description:
70 * <ul>
71 * <li>This API is used to point to the next node pointed to by the current node.</li>
72 * </ul>
73 * @attention
74 * <ul>
75 * <li>None.</li>
76 * </ul>
77 *
78 * @param object [IN] Node in the doubly linked list.
79 *
80 * @retval None.
81 * @par Dependency:
82 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
83 * @see
84 */
85 #define UTILS_DL_LIST_FIRST(object) ((object)->pstNext)
86
87 /*
88 * @ingroup utils_list
89 * @brief Node is the end of the list.
90 *
91 * @par Description:
92 * <ul>
93 * <li>This API is used to test node is the end of the list.</li>
94 * </ul>
95 * @attention
96 * <ul>
97 * <li>None.</li>
98 * </ul>
99 *
100 * @param object [IN] Node in the doubly linked list.
101 *
102 * @retval None.
103 * @par Dependency:
104 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
105 * @see
106 */
107 #define UTILS_DL_LIST_IS_END(list, node) ((list) == (node) ? TRUE : FALSE)
108
109 /*
110 * @ingroup utils_list
111 * @brief Node is on the list.
112 *
113 * @par Description:
114 * <ul>
115 * <li>This API is used to test node is on the list.</li>
116 * </ul>
117 * @attention
118 * <ul>
119 * <li>None.</li>
120 * </ul>
121 *
122 * @param object [IN] Node in the doubly linked list.
123 *
124 * @retval None.
125 * @par Dependency:
126 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
127 * @see
128 */
129 #define UTILS_DL_LIST_IS_ON_QUEUE(node) ((node)->pstPrev != NULL && (node)->pstNext != NULL)
130
131 /*
132 * @ingroup utils_list
133 * @brief Point to the previous node pointed to by the current node.
134 *
135 * @par Description:
136 * <ul>
137 * <li>This API is used to point to the previous node pointed to by the current node.</li>
138 * </ul>
139 * @attention
140 * <ul>
141 * <li>None.</li>
142 * </ul>
143 *
144 * @param object [IN] Node in the doubly linked list.
145 *
146 * @retval None.
147 * @par Dependency:
148 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
149 * @see
150 */
151 #define UTILS_DL_LIST_LAST(object) ((object)->pstPrev)
152
153 /*
154 * @ingroup utils_list
155 * @brief Insert a new node to a doubly linked list.
156 *
157 * @par Description:
158 * This API is used to insert a new node to a doubly linked list.
159 * @attention
160 * <ul>
161 * <li>The parameters passed in should be ensured to be legal pointers.</li>
162 * </ul>
163 *
164 * @param list [IN] Doubly linked list where the new node is inserted.
165 * @param node [IN] New node to be inserted.
166 *
167 * @retval None
168 * @par Dependency:
169 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
170 * @see UtilsListDelete
171 */
UtilsListAdd(UTILS_DL_LIST * list,UTILS_DL_LIST * node)172 static inline void UtilsListAdd(UTILS_DL_LIST *list, UTILS_DL_LIST *node)
173 {
174 node->pstNext = list->pstNext;
175 node->pstPrev = list;
176 list->pstNext->pstPrev = node;
177 list->pstNext = node;
178 }
179
180 /*
181 * @ingroup utils_list
182 * @brief Insert a node to the tail of a doubly linked list.
183 *
184 * @par Description:
185 * This API is used to insert a new node to the tail of a doubly linked list.
186 * @attention
187 * <ul>
188 * <li>The parameters passed in should be ensured to be legal pointers.</li>
189 * </ul>
190 *
191 * @param list [IN] Doubly linked list where the new node is inserted.
192 * @param node [IN] New node to be inserted.
193 *
194 * @retval None.
195 * @par Dependency:
196 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
197 * @see UtilsListAdd | UtilsListHeadInsert
198 */
UtilsListTailInsert(UTILS_DL_LIST * list,UTILS_DL_LIST * node)199 static inline void UtilsListTailInsert(UTILS_DL_LIST *list, UTILS_DL_LIST *node)
200 {
201 UtilsListAdd(list->pstPrev, node);
202 }
203
204 /*
205 * @ingroup utils_list
206 * @brief Insert a node to the head of a doubly linked list.
207 *
208 * @par Description:
209 * This API is used to insert a new node to the head of a doubly linked list.
210 * @attention
211 * <ul>
212 * <li>The parameters passed in should be ensured to be legal pointers.</li>
213 * </ul>
214 *
215 * @param list [IN] Doubly linked list where the new node is inserted.
216 * @param node [IN] New node to be inserted.
217 *
218 * @retval None.
219 * @par Dependency:
220 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
221 * @see UtilsListAdd | UtilsListTailInsert
222 */
UtilsListHeadInsert(UTILS_DL_LIST * list,UTILS_DL_LIST * node)223 static inline void UtilsListHeadInsert(UTILS_DL_LIST *list, UTILS_DL_LIST *node)
224 {
225 UtilsListAdd(list, node);
226 }
227
228 /*
229 * @ingroup utils_list
230 *
231 * @par Description:
232 * <ul>
233 * <li>This API is used to delete a specified node from a doubly linked list.</li>
234 * </ul>
235 * @attention
236 * <ul>
237 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
238 * </ul>
239 *
240 * @param node [IN] Node to be deleted.
241 *
242 * @retval None.
243 * @par Dependency:
244 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
245 * @see UtilsListAdd
246 */
UtilsListDelete(UTILS_DL_LIST * node)247 static inline void UtilsListDelete(UTILS_DL_LIST *node)
248 {
249 node->pstNext->pstPrev = node->pstPrev;
250 node->pstPrev->pstNext = node->pstNext;
251 node->pstNext = NULL;
252 node->pstPrev = NULL;
253 }
254
255 /*
256 * @ingroup utils_list
257 * @brief Identify whether a specified doubly linked list is empty.
258 *
259 * @par Description:
260 * <ul>
261 * <li>This API is used to return whether a doubly linked list is empty.</li>
262 * </ul>
263 * @attention
264 * <ul>
265 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
266 * </ul>
267 *
268 * @param list [IN] Doubly linked list.
269 *
270 * @retval TRUE The doubly linked list is empty.
271 * @retval FALSE The doubly linked list is not empty.
272 * @par Dependency:
273 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
274 * @see
275 */
UtilsListEmpty(UTILS_DL_LIST * list)276 static inline bool UtilsListEmpty(UTILS_DL_LIST *list)
277 {
278 return (bool)(list->pstNext == list);
279 }
280
281 /*
282 * @ingroup utils_list
283 * @brief Insert a new list to a doubly linked list.
284 *
285 * @par Description:
286 * This API is used to insert a new list to a doubly linked list.
287 * @attention
288 * <ul>
289 * <li>The parameters passed in should be ensured to be legal pointers.</li>
290 * </ul>
291 *
292 * @param oldList [IN] Doubly linked list where the new list is inserted.
293 * @param newList [IN] New list to be inserted.
294 *
295 * @retval None
296 * @par Dependency:
297 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
298 * @see UtilsListDelete
299 */
UtilsListAddList(UTILS_DL_LIST * oldList,UTILS_DL_LIST * newList)300 static inline void UtilsListAddList(UTILS_DL_LIST *oldList, UTILS_DL_LIST *newList)
301 {
302 UTILS_DL_LIST *oldListHead = oldList->pstNext;
303 UTILS_DL_LIST *oldListTail = oldList;
304 UTILS_DL_LIST *newListHead = newList;
305 UTILS_DL_LIST *newListTail = newList->pstPrev;
306
307 oldListTail->pstNext = newListHead;
308 newListHead->pstPrev = oldListTail;
309 oldListHead->pstPrev = newListTail;
310 newListTail->pstNext = oldListHead;
311 }
312
313 /*
314 * @ingroup utils_list
315 * @brief Insert a doubly list to the tail of a doubly linked list.
316 *
317 * @par Description:
318 * This API is used to insert a new doubly list to the tail of a doubly linked list.
319 * @attention
320 * <ul>
321 * <li>The parameters passed in should be ensured to be legal pointers.</li>
322 * </ul>
323 *
324 * @param oldList [IN] Doubly linked list where the new list is inserted.
325 * @param newList [IN] New list to be inserted.
326 *
327 * @retval None.
328 * @par Dependency:
329 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
330 * @see UtilsListAddList | UtilsListHeadInsertList
331 */
UtilsListTailInsertList(UTILS_DL_LIST * oldList,UTILS_DL_LIST * newList)332 static inline void UtilsListTailInsertList(UTILS_DL_LIST *oldList, UTILS_DL_LIST *newList)
333 {
334 UtilsListAddList(oldList->pstPrev, newList);
335 }
336
337 /*
338 * @ingroup utils_list
339 * @brief Insert a doubly list to the head of a doubly linked list.
340 *
341 * @par Description:
342 * This API is used to insert a new doubly list to the head of a doubly linked list.
343 * @attention
344 * <ul>
345 * <li>The parameters passed in should be ensured to be legal pointers.</li>
346 * </ul>
347 *
348 * @param oldList [IN] Doubly linked list where the new list is inserted.
349 * @param newList [IN] New list to be inserted.
350 *
351 * @retval None.
352 * @par Dependency:
353 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
354 * @see UtilsListAddList | UtilsListTailInsertList
355 */
UtilsListHeadInsertList(UTILS_DL_LIST * oldList,UTILS_DL_LIST * newList)356 static inline void UtilsListHeadInsertList(UTILS_DL_LIST *oldList, UTILS_DL_LIST *newList)
357 {
358 UtilsListAddList(oldList, newList);
359 }
360
361 /*
362 * @ingroup utils_list
363 * @brief Obtain the offset of a field to a structure address.
364 *
365 * @par Description:
366 * This API is used to obtain the offset of a field to a structure address.
367 * @attention
368 * <ul>
369 * <li>None.</li>
370 * </ul>
371 *
372 * @param type [IN] Structure name.
373 * @param field [IN] Name of the field of which the offset is to be measured.
374 *
375 * @retval Offset of the field to the structure address.
376 * @par Dependency:
377 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
378 * @see
379 */
380 #define OFFSET_OF_FIELD(type, field) ((unsigned int)&((type *)0)->field)
381
382 /*
383 * @ingroup utils_list
384 * @brief Obtain the pointer to a doubly linked list in a structure.
385 *
386 * @par Description:
387 * This API is used to obtain the pointer to a doubly linked list in a structure.
388 * @attention
389 * <ul>
390 * <li>None.</li>
391 * </ul>
392 *
393 * @param type [IN] Structure name.
394 * @param member [IN] Member name of the doubly linked list in the structure.
395 *
396 * @retval Pointer to the doubly linked list in the structure.
397 * @par Dependency:
398 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
399 * @see
400 */
401 #define UTILS_OFF_SET_OF(type, member) ((unsigned int)&((type *)0)->member)
402
403 /*
404 * @ingroup utils_list
405 * @brief Obtain the pointer to a structure that contains a doubly linked list.
406 *
407 * @par Description:
408 * This API is used to obtain the pointer to a structure that contains a doubly linked list.
409 * <ul>
410 * <li>None.</li>
411 * </ul>
412 * @attention
413 * <ul>
414 * <li>None.</li>
415 * </ul>
416 *
417 * @param item [IN] Current node's pointer to the next node.
418 * @param type [IN] Structure name.
419 * @param member [IN] Member name of the doubly linked list in the structure.
420 *
421 * @retval Pointer to the structure that contains the doubly linked list.
422 * @par Dependency:
423 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
424 * @see
425 */
426 #define UTILS_DL_LIST_ENTRY(item, type, member) \
427 ((type *)(void *)((char *)(item) - UTILS_OFF_SET_OF(type, member)))
428
429 /*
430 * @ingroup utils_list
431 * @brief Iterate over a doubly linked list of given type.
432 *
433 * @par Description:
434 * This API is used to iterate over a doubly linked list of given type.
435 * @attention
436 * <ul>
437 * <li>None.</li>
438 * </ul>
439 *
440 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
441 * @param list [IN] Pointer to the doubly linked list to be traversed.
442 * @param type [IN] Structure name.
443 * @param member [IN] Member name of the doubly linked list in the structure.
444 *
445 * @retval None.
446 * @par Dependency:
447 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
448 * @see
449 */
450 #define UTILS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member) \
451 for (item = UTILS_DL_LIST_ENTRY((list)->pstNext, type, member); \
452 &(item)->member != (list); \
453 item = UTILS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
454
455 /*
456 * @ingroup utils_list
457 * @brief iterate over a doubly linked list safe against removal of list entry.
458 *
459 * @par Description:
460 * This API is used to iterate over a doubly linked list safe against removal of list entry.
461 * @attention
462 * <ul>
463 * <li>None.</li>
464 * </ul>
465 *
466 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
467 * @param next [IN] Save the next node.
468 * @param list [IN] Pointer to the doubly linked list to be traversed.
469 * @param type [IN] Structure name.
470 * @param member [IN] Member name of the doubly linked list in the structure.
471 *
472 * @retval None.
473 * @par Dependency:
474 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
475 * @see
476 */
477 #define UTILS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member) \
478 for (item = UTILS_DL_LIST_ENTRY((list)->pstNext, type, member), \
479 next = UTILS_DL_LIST_ENTRY((item)->member.pstNext, type, member); \
480 &(item)->member != (list); \
481 item = next, next = UTILS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
482
483 /*
484 * @ingroup utils_list
485 * @brief Delete initialize a doubly linked list.
486 *
487 * @par Description:
488 * This API is used to delete initialize a doubly linked list.
489 * @attention
490 * <ul>
491 * <li>The parameter passed in should be ensured to be s legal pointer.</li>
492 * </ul>
493 *
494 * @param list [IN] Doubly linked list.
495 *
496 * @retval None.
497 * @par Dependency:
498 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
499 * @see
500 */
UtilsListDelInit(UTILS_DL_LIST * list)501 static inline void UtilsListDelInit(UTILS_DL_LIST *list)
502 {
503 list->pstNext->pstPrev = list->pstPrev;
504 list->pstPrev->pstNext = list->pstNext;
505 UtilsListInit(list);
506 }
507
508 /*
509 * @ingroup utils_list
510 * @brief iterate over a doubly linked list.
511 *
512 * @par Description:
513 * This API is used to iterate over a doubly linked list.
514 * @attention
515 * <ul>
516 * <li>None.</li>
517 * </ul>
518 *
519 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
520 * @param list [IN] Pointer to the doubly linked list to be traversed.
521 *
522 * @retval None.
523 * @par Dependency:
524 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
525 * @see
526 */
527 #define UTILS_DL_LIST_FOR_EACH(item, list) \
528 for (item = (list)->pstNext; \
529 (item) != (list); \
530 item = (item)->pstNext)
531
532 /*
533 * @ingroup utils_list
534 * @brief Iterate over a doubly linked list safe against removal of list entry.
535 *
536 * @par Description:
537 * This API is used to iterate over a doubly linked list safe against removal of list entry.
538 * @attention
539 * <ul>
540 * <li>None.</li>
541 * </ul>
542 *
543 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
544 * @param next [IN] Save the next node.
545 * @param list [IN] Pointer to the doubly linked list to be traversed.
546 *
547 * @retval None.
548 * @par Dependency:
549 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
550 * @see
551 */
552 #define UTILS_DL_LIST_FOR_EACH_SAFE(item, next, list) \
553 for (item = (list)->pstNext, next = (item)->pstNext; \
554 (item) != (list); \
555 item = next, next = (item)->pstNext)
556
557 /*
558 * @ingroup utils_list
559 * @brief Initialize a double linked list.
560 *
561 * @par Description:
562 * This API is used to initialize a double linked list.
563 * @attention
564 * <ul>
565 * <li>None.</li>
566 * </ul>
567 *
568 * @param list [IN] Pointer to the doubly linked list to be traversed.
569 *
570 * @retval None.
571 * @par Dependency:
572 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
573 * @see
574 */
575 #define UTILS_DL_LIST_HEAD(list) UTILS_DL_LIST list = { &(list), &(list) }
576
577 #define UTILS_ListPeekHeadType(list, type, element) \
578 do { \
579 type *__t; \
580 if ((list)->pstNext == list) { \
581 __t = NULL; \
582 } else { \
583 __t = UTILS_DL_LIST_ENTRY((list)->pstNext, type, element); \
584 } \
585 __t; \
586 } while (0)
587
588 #define UTILS_ListRemoveHeadType(list, type, element) \
589 do { \
590 type *__t; \
591 if ((list)->pstNext == list) { \
592 __t = NULL; \
593 } else { \
594 __t = UTILS_DL_LIST_ENTRY((list)->pstNext, type, element); \
595 UtilsListDelete((list)->pstNext); \
596 } \
597 __t; \
598 } while (0)
599
600 #define UTILS_ListNextType(list, item, type, element) \
601 do { \
602 type *__t; \
603 if ((item)->pstNext == list) { \
604 __t = NULL; \
605 } else { \
606 __t = UTILS_DL_LIST_ENTRY((item)->pstNext, type, element); \
607 } \
608 __t; \
609 } while (0)
610
611 #ifdef __cplusplus
612 #if __cplusplus
613 }
614 #endif /* __cplusplus */
615 #endif /* __cplusplus */
616
617 #endif /* _UTILS_LIST_H */