1 /*
2 * Copyright (c) 2020 HiSilicon (Shanghai) Technologies CO., LIMITED.
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 * @defgroup list List
17 * @ingroup linux
18 */
19
20 #ifndef _LINUX_LIST_H
21 #define _LINUX_LIST_H
22
23 #include "stddef.h"
24 #include "linux/wait.h"
25
26 #ifdef __cplusplus
27 extern "C" {
28 #endif /* __cplusplus */
29
30 typedef struct list_head {
31 struct list_head *next;
32 struct list_head *prev;
33 } list_head_t;
34
35 struct hlist_head {
36 struct hlist_node *first;
37 };
38
39 typedef struct hlist_node {
40 struct hlist_node *next, **pprev;
41 } hlist_node_t;
42
43 #define LIST_HEAD_INIT(name) { &(name), &(name) }
44
45 /**
46 * @ingroup list
47 * @brief Declares variables and initializes the linked list header.
48 *
49 * @par Description:
50 * This API is used to declares variables and initializes the linked list header.
51 * @attention
52 * None.
53 *
54 * @param name [IN] A node in a doubly linked list.
55 *
56 * @retval None.
57 * @par Dependency:
58 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
59 * @see INIT_LIST_HEAD
60 */
61 #define LIST_HEAD(name) list_head_t name = LIST_HEAD_INIT(name)
62
63 /**
64 * @ingroup list
65 * @brief Initialize the input node to a doubly linked list.
66 *
67 * @par Description:
68 * This API is used to initialize the input node (the first parameter list) to a doubly linked list.
69 * @attention
70 * <ul>
71 * <li> The parameter passed in should be a legal pointer. </li>
72 * </ul>
73 *
74 * @param list [IN] A node in a doubly linked list.
75 *
76 * @retval None.
77 * @par Dependency:
78 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
79 * @see LIST_HEAD
80 */
INIT_LIST_HEAD(list_head_t * list)81 static __inline__ void INIT_LIST_HEAD(list_head_t *list)
82 {
83 list->next = list;
84 list->prev = list;
85 }
86
87 /**
88 * @ingroup list
89 * @brief Identify whether a specified doubly linked list is empty or not.
90 *
91 * @par Description:
92 * This API is used to judge whether a doubly linked list is empty or not.
93 * @attention
94 * <ul>
95 * <li> The parameter passed in should be a legal pointer. </li>
96 * </ul>
97 *
98 * @param list [IN] Doubly linked list.
99 *
100 * @retval #1 The doubly linked list is empty.
101 * @retval #0 The doubly linked list is not empty.
102 * @par Dependency:
103 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
104 * @see None.
105 */
list_empty(const list_head_t * list)106 static __inline__ int list_empty(const list_head_t *list)
107 {
108 return list->next == list;
109 }
110
111 /**
112 * @ingroup list
113 * @brief Insert an entry after the specified entry.
114 *
115 * @par Description:
116 * This API is used to insert an entry after the specified entry.
117 * @attention
118 * <ul>
119 * <li> The parameters passed in should be legal pointers. </li>
120 * </ul>
121 *
122 * @param newNode [IN] The new node to be inserted.
123 * @param afterNode [IN] Point to where the node is inserted.
124 *
125 * @retval None
126 * @par Dependency:
127 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
128 * @see list_del | list_add_tail
129 */
list_add(list_head_t * newNode,list_head_t * afterNode)130 static __inline__ void list_add(list_head_t *newNode, list_head_t *afterNode)
131 {
132 list_head_t *nextNode = afterNode->next;
133 newNode->prev = afterNode;
134 newNode->next = nextNode;
135 nextNode->prev = newNode;
136 afterNode->next = newNode;
137 }
138
139 /**
140 * @ingroup list
141 * @brief Insert an entry before the specified entry.
142 *
143 * @par Description:
144 * This API is used to insert an entry before the specified entry.
145 * @attention
146 * <ul>
147 * <li> The parameters passed in should be legal pointers. </li>
148 * </ul>
149 *
150 * @param newNode [IN] The new node to be inserted.
151 * @param beforeNode [IN] Point to where the node is inserted.
152 *
153 * @retval None.
154 * @par Dependency:
155 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
156 * @see list_add
157 */
list_add_tail(list_head_t * newNode,list_head_t * beforeNode)158 static __inline__ void list_add_tail(list_head_t *newNode, list_head_t *beforeNode)
159 {
160 list_head_t *pstprev = beforeNode->prev;
161 newNode->next = beforeNode;
162 newNode->prev = pstprev;
163 pstprev->next = newNode;
164 beforeNode->prev = newNode;
165 }
166
167 /**
168 * @ingroup list
169 * @brief Gets the address of the container structure.
170 *
171 * @par Description:
172 * This API gets the address of the structure where the list #ptr is located based on the address of the #ptr.
173 * @attention
174 * None.
175 *
176 * @param ptr [IN] Type #list_head_t * The node of the doubly linked list.
177 * @param type [IN] The type of structure.
178 * @param member [IN] The doubly linked list name in the structure.
179 *
180 * @retval The pointer to the address of the container structure.
181 * @par Dependency:
182 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
183 * @see list_for_each_entry
184 */
185 #define list_entry(ptr, type, member) LOS_DL_LIST_ENTRY(ptr, type, member)
186
187 /**
188 * @ingroup list
189 * @brief Traverse a doubly linked list.
190 *
191 * @par Description:
192 * This API is used to traverse a doubly linked list. The API is a loop. The start node of the
193 * doubly linked list is the second parameter list. And in each loop, the obtained pointer to
194 * the next node of the doubly linked list is outputted in the first parameter item.
195 * @attention
196 * None.
197 *
198 * @param node [IN/OUT] Type #list_head_t * The pointer to the next node in the doubly linked list.
199 * @param list [IN] Type #list_head_t * The pointer to the node of the doubly linked list to be traversed.
200 *
201 * @retval None.
202 * @par Dependency:
203 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
204 * @see list_for_each_safe | list_for_each_entry
205 */
206 #define list_for_each(node, list) for ((node) = (list)->next; (node) != (list); (node) = (node)->next)
207
208 /**
209 * @ingroup list
210 * @brief Traverse a doubly linked list and obtain the address of the structure containing the linked list node.
211 *
212 * @par Description:
213 * Traverse a doubly linked list and obtain the address of the structure containing the linked list node.
214 * @attention
215 * None.
216 *
217 * @param list [IN/OUT] The pointer to the structure that contains the doubly linked list node.
218 * @param head [IN] Type #list_head_t * The start node of the doubly linked list to be traversed.
219 * @param item [IN] The doubly linked list name in the structure.
220 *
221 * @retval None.
222 * @par Dependency:
223 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
224 * @see list_entry | list_for_each_entry_safe | list_for_each
225 */
226 #define list_for_each_entry(list, head, item) \
227 for ((list) = list_entry((head)->next, __typeof__(*list), item); \
228 &((list)->item) != (head); \
229 (list) = list_entry((list)->item.next, __typeof__(*list), item))
230
231 /**
232 * @ingroup list
233 * @brief Traverse a doubly linked list safe against removal of list entry.
234 *
235 * @par Description:
236 * This API is used to traverse a doubly linked list safe against removal of list entry.
237 * @attention
238 * None.
239 *
240 * @param pos [IN/OUT] Type #list_head_t * Cursor for looping.
241 * @param n [IN/OUT] Type #list_head_t * The pointer to the next node of the first parameter #pos.
242 * @param head [IN] Type #list_head_t * The pointer to the node of the doubly linked list to be traversed.
243 *
244 * @retval None.
245 * @par Dependency:
246 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
247 * @see list_for_each | list_for_each_entry_safe
248 */
249 #define list_for_each_safe(pos, n, head) \
250 for ((pos) = (head)->next, (n) = (pos)->next; (pos) != (head); (pos) = (n), (n) = (pos)->next)
251
252 /**
253 * @ingroup list
254 * @brief Obtains the address of the structure containing the head node of the doubly linked list.
255 *
256 * @par Description:
257 * This API is used to obtain the address of the structure containing the head node of the doubly linked list.
258 * @attention
259 * None.
260 *
261 * @param ptr [IN] Type #list_head_t * The kead node of the doubly linked list.
262 * @param type [IN] Structure name.
263 * @param member [IN] The doubly linked list name in the structure.
264 *
265 * @retval The pointer to the structure that contains the head node of the doubly linked list.
266 * @par Dependency:
267 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
268 * @see list_entry
269 */
270 #define list_first_entry(ptr, type, member) list_entry((ptr)->next, type, member)
271
272 /* ist_is_last - tests whether @list is the last entry in list @head */
273 /**
274 * @ingroup list
275 * @brief Check whether the node #list is the tail node of the doubly linked list.
276 *
277 * @par Description:
278 * This API is used to check whether the node #list is the tail node of the doubly linked list.
279 * @attention
280 * <ul>
281 * <li> The parameter passed in should be a legal pointer. </li>
282 * </ul>
283 *
284 * @param list [IN] Type #list_head_t * The node to be checked.
285 * @param head [IN] The head node of the doubly linked list.
286 *
287 * @retval #1 The node #list is the tail node of the doubly linked list.
288 @retval #0 The node #list is not the tail node of the doubly linked list.
289 * @par Dependency:
290 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
291 * @see None.
292 */
list_is_last(const list_head_t * list,const list_head_t * head)293 static inline int list_is_last(const list_head_t *list, const list_head_t *head)
294 {
295 return list->next == head;
296 }
297
298 /**
299 * @ingroup list
300 * @brief Traverses the structure containing double linked list nodes, and it is safe against removal of list entry.
301 *
302 * @par Description:
303 * This API is used to traverses the structure containing double linked list nodes.
304 * @attention
305 * None.
306 *
307 * @param pos [IN/OUT] The pointer to the structure that contains the doubly linked list node.
308 * @param n [IN/OUT] Type #list_head_t * The pointer to the next node of the first parameter #pos.
309 * @param head [IN] Type #list_head_t * The start node of the doubly linked list to be traversed.
310 * @param member [IN] The doubly linked list name in the structure.
311 *
312 * @retval None.
313 * @par Dependency:
314 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
315 * @see list_entry | list_for_each_entry | list_for_each_safe
316 */
317 #define list_for_each_entry_safe(pos, n, head, member) \
318 for ((pos) = list_entry((head)->next, __typeof__(*(pos)), member), \
319 (n) = list_entry((pos)->member.next, __typeof__(*(pos)), member); \
320 &(pos)->member != (head); \
321 (pos) = (n), (n) = list_entry((n)->member.next, __typeof__(*n), member))
322
323 /**
324 * @ingroup list
325 * @brief Reversely traverses a structure containing double linked list nodes.
326 *
327 * @par Description:
328 * Reversely traverses a structure containing double linked list nodes.
329 * @attention
330 * None.
331 *
332 * @param pos [IN/OUT] The pointer to the structure that contains the doubly linked list node.
333 * @param head [IN] Type #list_head_t * The start node of the doubly linked list to be traversed.
334 * @param member [IN] The doubly linked list name in the structure.
335 *
336 * @retval None.
337 * @par Dependency:
338 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
339 * @see list_entry | list_for_each_entry | list_for_each
340 */
341 #define list_for_each_entry_reverse(pos, head, member) \
342 for ((pos) = list_entry((head)->prev, __typeof__(*(pos)), member); \
343 &(pos)->member != (head); \
344 (pos) = list_entry((pos)->member.prev, __typeof__(*(pos)), member))
345
346 /**
347 * @ingroup list
348 * @brief Delete a specified node from a doubly linked list.
349 *
350 * @par Description:
351 * This API is used to delete a specified node from a doubly linked list.
352 * @attention
353 * <ul>
354 * <li> The parameter passed in should be a legal pointer. </li>
355 * </ul>
356 *
357 * @param node [IN] Node to be deleted.
358 *
359 * @retval None.
360 * @par Dependency:
361 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
362 * @see list_add
363 */
list_del(list_head_t * node)364 static __inline__ void list_del(list_head_t *node)
365 {
366 node->next->prev = node->prev;
367 node->prev->next = node->next;
368 }
369
370 /**
371 * @ingroup list
372 * @brief Delete a node from the linked list by using the previous node and next node.
373 *
374 * @par Description:
375 * This API is used to delete a node from the linked list by using the previous node and next node.
376 * @attention
377 * <ul>
378 * <li> The parameter passed in should be a legal pointer. </li>
379 * </ul>
380 *
381 * @param prev [IN] The previous node of the target delete node.
382 * @param next [IN] The next node of the target delete node.
383 *
384 * @retval None.
385 * @par Dependency:
386 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
387 * @see None.
388 */
__list_del(list_head_t * prev,list_head_t * next)389 static inline void __list_del(list_head_t *prev, list_head_t *next)
390 {
391 next->prev = prev;
392 prev->next = next;
393 }
394
395 /**
396 * @ingroup list
397 * @brief Delete a specified node from a doubly linked list.
398 *
399 * @par Description:
400 * This API is used to delete a specified node from a doubly linked list.
401 * @attention
402 * <ul>
403 * <li> The parameter passed in should be a legal pointer. </li>
404 * <li> list_del is an external interface, and __list_del_entry、__list_del are internal kernel interfaces. </li>
405 * </ul>
406 *
407 * @param entry [IN] Node to be deleted.
408 *
409 * @retval None.
410 * @par Dependency:
411 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
412 * @see __list_del | list_del
413 */
__list_del_entry(list_head_t * entry)414 static inline void __list_del_entry(list_head_t *entry)
415 {
416 __list_del(entry->prev, entry->next);
417 }
418
419 /**
420 * @ingroup list
421 * @brief Delete the #list from the original double linked list,
422 * and insert it as the head node into another double linked list.
423 *
424 * @par Description:
425 * This API is used to deletes the #list from the original double linked list,
426 * and insert it as the head node into another double linked list.
427 * @attention
428 * <ul>
429 * <li> The parameter passed in should be a legal pointer. </li>
430 * </ul>
431 *
432 * @param list [IN] Node to be deleted.
433 * @param head [IN] Head of the inserted double linked list.
434 *
435 * @retval None.
436 * @par Dependency:
437 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
438 * @see __list_del_entry | list_add
439 */
list_move(list_head_t * list,list_head_t * head)440 static inline void list_move(list_head_t *list, list_head_t *head)
441 {
442 __list_del_entry(list);
443 list_add(list, head);
444 }
445
446 /**
447 * @ingroup list
448 * @brief Deletes the node #entry from the double linked list and reinitialize it.
449 *
450 * @par Description:
451 * This API is used to deletes the node #entry from the double linked list and reinitialize it.
452 * @attention
453 * <ul>
454 * <li> The parameter passed in should be a legal pointer. </li>
455 * </ul>
456 *
457 * @param entry [IN] Node to be deleted.
458 *
459 * @retval None.
460 * @par Dependency:
461 * <ul><li>list.h: the header file that contains the API declaration.</li></ul>
462 * @see __list_del | INIT_LIST_HEAD
463 */
list_del_init(list_head_t * entry)464 static inline void list_del_init(list_head_t *entry)
465 {
466 __list_del(entry->prev, entry->next);
467 INIT_LIST_HEAD(entry);
468 }
469
470 #ifdef __cplusplus
471 }
472 #endif /* __cplusplus */
473
474 #endif /* _LINUX_LIST_H */
475