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 #ifndef OFFSET_OF_FIELD
381 #define OFFSET_OF_FIELD(type, field) ((unsigned int)&((type *)0)->field)
382 #endif
383
384 /*
385 * @ingroup utils_list
386 * @brief Obtain the pointer to a doubly linked list in a structure.
387 *
388 * @par Description:
389 * This API is used to obtain the pointer to a doubly linked list in a structure.
390 * @attention
391 * <ul>
392 * <li>None.</li>
393 * </ul>
394 *
395 * @param type [IN] Structure name.
396 * @param member [IN] Member name of the doubly linked list in the structure.
397 *
398 * @retval Pointer to the doubly linked list in the structure.
399 * @par Dependency:
400 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
401 * @see
402 */
403 #define UTILS_OFF_SET_OF(type, member) ((unsigned int)&((type *)0)->member)
404
405 /*
406 * @ingroup utils_list
407 * @brief Obtain the pointer to a structure that contains a doubly linked list.
408 *
409 * @par Description:
410 * This API is used to obtain the pointer to a structure that contains a doubly linked list.
411 * <ul>
412 * <li>None.</li>
413 * </ul>
414 * @attention
415 * <ul>
416 * <li>None.</li>
417 * </ul>
418 *
419 * @param item [IN] Current node's pointer to the next node.
420 * @param type [IN] Structure name.
421 * @param member [IN] Member name of the doubly linked list in the structure.
422 *
423 * @retval Pointer to the structure that contains the doubly linked list.
424 * @par Dependency:
425 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
426 * @see
427 */
428 #define UTILS_DL_LIST_ENTRY(item, type, member) \
429 ((type *)(void *)((char *)(item) - UTILS_OFF_SET_OF(type, member)))
430
431 /*
432 * @ingroup utils_list
433 * @brief Iterate over a doubly linked list of given type.
434 *
435 * @par Description:
436 * This API is used to iterate over a doubly linked list of given type.
437 * @attention
438 * <ul>
439 * <li>None.</li>
440 * </ul>
441 *
442 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
443 * @param list [IN] Pointer to the doubly linked list to be traversed.
444 * @param type [IN] Structure name.
445 * @param member [IN] Member name of the doubly linked list in the structure.
446 *
447 * @retval None.
448 * @par Dependency:
449 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
450 * @see
451 */
452 #define UTILS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member) \
453 for (item = UTILS_DL_LIST_ENTRY((list)->pstNext, type, member); \
454 &(item)->member != (list); \
455 item = UTILS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
456
457 /*
458 * @ingroup utils_list
459 * @brief iterate over a doubly linked list safe against removal of list entry.
460 *
461 * @par Description:
462 * This API is used to iterate over a doubly linked list safe against removal of list entry.
463 * @attention
464 * <ul>
465 * <li>None.</li>
466 * </ul>
467 *
468 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
469 * @param next [IN] Save the next node.
470 * @param list [IN] Pointer to the doubly linked list to be traversed.
471 * @param type [IN] Structure name.
472 * @param member [IN] Member name of the doubly linked list in the structure.
473 *
474 * @retval None.
475 * @par Dependency:
476 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
477 * @see
478 */
479 #define UTILS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member) \
480 for (item = UTILS_DL_LIST_ENTRY((list)->pstNext, type, member), \
481 next = UTILS_DL_LIST_ENTRY((item)->member.pstNext, type, member); \
482 &(item)->member != (list); \
483 item = next, next = UTILS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
484
485 /*
486 * @ingroup utils_list
487 * @brief Delete initialize a doubly linked list.
488 *
489 * @par Description:
490 * This API is used to delete initialize a doubly linked list.
491 * @attention
492 * <ul>
493 * <li>The parameter passed in should be ensured to be s legal pointer.</li>
494 * </ul>
495 *
496 * @param list [IN] Doubly linked list.
497 *
498 * @retval None.
499 * @par Dependency:
500 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
501 * @see
502 */
UtilsListDelInit(UTILS_DL_LIST * list)503 static inline void UtilsListDelInit(UTILS_DL_LIST *list)
504 {
505 list->pstNext->pstPrev = list->pstPrev;
506 list->pstPrev->pstNext = list->pstNext;
507 UtilsListInit(list);
508 }
509
510 /*
511 * @ingroup utils_list
512 * @brief iterate over a doubly linked list.
513 *
514 * @par Description:
515 * This API is used to iterate over a doubly linked list.
516 * @attention
517 * <ul>
518 * <li>None.</li>
519 * </ul>
520 *
521 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
522 * @param list [IN] Pointer to the doubly linked list to be traversed.
523 *
524 * @retval None.
525 * @par Dependency:
526 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
527 * @see
528 */
529 #define UTILS_DL_LIST_FOR_EACH(item, list) \
530 for (item = (list)->pstNext; \
531 (item) != (list); \
532 item = (item)->pstNext)
533
534 /*
535 * @ingroup utils_list
536 * @brief Iterate over a doubly linked list safe against removal of list entry.
537 *
538 * @par Description:
539 * This API is used to iterate over a doubly linked list safe against removal of list entry.
540 * @attention
541 * <ul>
542 * <li>None.</li>
543 * </ul>
544 *
545 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
546 * @param next [IN] Save the next node.
547 * @param list [IN] Pointer to the doubly linked list to be traversed.
548 *
549 * @retval None.
550 * @par Dependency:
551 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
552 * @see
553 */
554 #define UTILS_DL_LIST_FOR_EACH_SAFE(item, next, list) \
555 for (item = (list)->pstNext, next = (item)->pstNext; \
556 (item) != (list); \
557 item = next, next = (item)->pstNext)
558
559 /*
560 * @ingroup utils_list
561 * @brief Initialize a double linked list.
562 *
563 * @par Description:
564 * This API is used to initialize a double linked list.
565 * @attention
566 * <ul>
567 * <li>None.</li>
568 * </ul>
569 *
570 * @param list [IN] Pointer to the doubly linked list to be traversed.
571 *
572 * @retval None.
573 * @par Dependency:
574 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
575 * @see
576 */
577 #define UTILS_DL_LIST_HEAD(list) UTILS_DL_LIST list = { &(list), &(list) }
578
579 #define UTILS_ListPeekHeadType(list, type, element) \
580 do { \
581 type *__t; \
582 if ((list)->pstNext == list) { \
583 __t = NULL; \
584 } else { \
585 __t = UTILS_DL_LIST_ENTRY((list)->pstNext, type, element); \
586 } \
587 __t; \
588 } while (0)
589
590 #define UTILS_ListRemoveHeadType(list, type, element) \
591 do { \
592 type *__t; \
593 if ((list)->pstNext == list) { \
594 __t = NULL; \
595 } else { \
596 __t = UTILS_DL_LIST_ENTRY((list)->pstNext, type, element); \
597 UtilsListDelete((list)->pstNext); \
598 } \
599 __t; \
600 } while (0)
601
602 #define UTILS_ListNextType(list, item, type, element) \
603 do { \
604 type *__t; \
605 if ((item)->pstNext == list) { \
606 __t = NULL; \
607 } else { \
608 __t = UTILS_DL_LIST_ENTRY((item)->pstNext, type, element); \
609 } \
610 __t; \
611 } while (0)
612
613 #ifdef __cplusplus
614 #if __cplusplus
615 }
616 #endif /* __cplusplus */
617 #endif /* __cplusplus */
618
619 #endif /* _UTILS_LIST_H */