1 /**
2 * @file list.h
3 * @copyright Copyright (C) 2015-2018 Alibaba Group Holding Limited
4 */
5
6 #ifndef AOS_LIST_H
7 #define AOS_LIST_H
8
9 #ifdef __cplusplus
10 extern "C" {
11 #endif
12
13 /** @addtogroup aos_list LIST
14 * list data structure manage.
15 *
16 * @{
17 */
18
19 /*
20 * Get offset of a member variable.
21 *
22 * @param[in] type the type of the struct this is embedded in.
23 * @param[in] member the name of the variable within the struct.
24 */
25 #define aos_offsetof(type, member) ((size_t)&(((type *)0)->member))
26
27 /*
28 * Get the struct for this entry.
29 *
30 * @param[in] ptr the list head to take the element from.
31 * @param[in] type the type of the struct this is embedded in.
32 * @param[in] member the name of the variable within the struct.
33 */
34 #define aos_container_of(ptr, type, member) \
35 ((type *)((char *)(ptr) - aos_offsetof(type, member)))
36
37 /* for double link list */
38 typedef struct dlist_s {
39 struct dlist_s *prev;
40 struct dlist_s *next;
41 } dlist_t;
42
43 /*
44 * add one node into data list.
45 *
46 * @param[in] node the data node to be inserted.
47 * @param[in] prev previous data node address.
48 * @param[in] next next data node address.
49 */
__dlist_add(dlist_t * node,dlist_t * prev,dlist_t * next)50 static inline void __dlist_add(dlist_t *node, dlist_t *prev, dlist_t *next)
51 {
52 node->next = next;
53 node->prev = prev;
54
55 prev->next = node;
56 next->prev = node;
57 }
58
59 /*
60 * Get the struct for this entry.
61 *
62 * @param[in] addr the list head to take the element from.
63 * @param[in] type the type of the struct this is embedded in.
64 * @param[in] member the name of the dlist_t within the struct.
65 */
66 #define dlist_entry(addr, type, member) \
67 ((type *)((long)addr - aos_offsetof(type, member)))
68
69 /*
70 * add one node just behind specified node.
71 *
72 * @param[in] node the data node to be inserted.
73 * @param[in] queue the specified last node.
74 */
dlist_add(dlist_t * node,dlist_t * queue)75 static inline void dlist_add(dlist_t *node, dlist_t *queue)
76 {
77 __dlist_add(node, queue, queue->next);
78 }
79
80 /*
81 * add one node just before specified node.
82 *
83 * @param[in] node the data node to be inserted.
84 * @param[in] queue the specified next node before which new node should be inserted.
85 */
dlist_add_tail(dlist_t * node,dlist_t * queue)86 static inline void dlist_add_tail(dlist_t *node, dlist_t *queue)
87 {
88 __dlist_add(node, queue->prev, queue);
89 }
90
91 /*
92 * delete one node from the data list.
93 *
94 * @param[in] node the data node to be deleted.
95 */
dlist_del(dlist_t * node)96 static inline void dlist_del(dlist_t *node)
97 {
98 dlist_t *prev = node->prev;
99 dlist_t *next = node->next;
100
101 prev->next = next;
102 next->prev = prev;
103 }
104
105 /*
106 * initialize one node.
107 *
108 * @param[in] node the data node to be initialized.
109 */
dlist_init(dlist_t * node)110 static inline void dlist_init(dlist_t *node)
111 {
112 node->next = node->prev = node;
113 }
114
115 /*
116 * initialize one node.
117 *
118 * @param[in] list the data node to be initialized.
119 */
INIT_AOS_DLIST_HEAD(dlist_t * list)120 static inline void INIT_AOS_DLIST_HEAD(dlist_t *list)
121 {
122 list->next = list;
123 list->prev = list;
124 }
125
126 /*
127 * Judge whether data list is empty.
128 *
129 * @param[in] head the head node of data list.
130 *
131 * @return 1 on empty, 0 FALSE.
132 */
dlist_empty(const dlist_t * head)133 static inline int dlist_empty(const dlist_t *head)
134 {
135 return head->next == head;
136 }
137
138 /*
139 * Initialise the list.
140 *
141 * @param[in] list the list to be inited.
142 */
143 #define AOS_DLIST_INIT(list) {&(list), &(list)}
144
145 /*
146 * Get the first element from a list
147 *
148 * @param[in] ptr the list head to take the element from.
149 * @param[in] type the type of the struct this is embedded in.
150 * @param[in] member the name of the dlist_t within the struct.
151 */
152 #define dlist_first_entry(ptr, type, member) dlist_entry((ptr)->next, type, member)
153
154 /*
155 * Iterate over a list.
156 *
157 * @param[in] pos the &struct dlist_t to use as a loop cursor.
158 * @param[in] head he head for your list.
159 */
160 #define dlist_for_each(pos, head) for (pos = (head)->next; pos != (head); pos = pos->next)
161
162 /*
163 * Iterate over a list safe against removal of list entry.
164 *
165 * @param[in] pos the &struct dlist_t to use as a loop cursor.
166 * @param[in] n another &struct dlist_t to use as temporary storage.
167 * @param[in] head he head for your list.
168 */
169 #define dlist_for_each_safe(pos, n, head) \
170 for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
171
172 /*
173 * Iterate over list of given type.
174 *
175 * @param[in] queue he head for your list.
176 * @param[in] node the &struct dlist_t to use as a loop cursor.
177 * @param[in] type the type of the struct this is embedded in.
178 * @param[in] member the name of the dlist_t within the struct.
179 */
180 #define dlist_for_each_entry(queue, node, type, member) \
181 for (node = aos_container_of((queue)->next, type, member); \
182 &node->member != (queue); \
183 node = aos_container_of(node->member.next, type, member))
184
185 /*
186 * Iterate over list of given type safe against removal of list entry.
187 *
188 * @param[in] queue the head for your list.
189 * @param[in] n the type * to use as a temp.
190 * @param[in] node the type * to use as a loop cursor.
191 * @param[in] type the type of the struct this is embedded in.
192 * @param[in] member the name of the dlist_t within the struct.
193 */
194 #define dlist_for_each_entry_safe(queue, n, node, type, member) \
195 for (node = aos_container_of((queue)->next, type, member), \
196 n = (queue)->next ? (queue)->next->next : NULL; \
197 &node->member != (queue); \
198 node = aos_container_of(n, type, member), n = n ? n->next : NULL)
199
200 /*
201 * Get the struct for this entry.
202 * @param[in] ptr the list head to take the element from.
203 * @param[in] type the type of the struct this is embedded in.
204 * @param[in] member the name of the variable within the struct.
205 */
206 #define aos_list_entry(ptr, type, member) aos_container_of(ptr, type, member)
207
208 /*
209 * Iterate backwards over list of given type.
210 *
211 * @param[in] pos the type * to use as a loop cursor.
212 * @param[in] head he head for your list.
213 * @param[in] member the name of the dlist_t within the struct.
214 * @param[in] type the type of the struct this is embedded in.
215 */
216 #define dlist_for_each_entry_reverse(pos, head, member, type) \
217 for (pos = aos_list_entry((head)->prev, type, member); \
218 &pos->member != (head); \
219 pos = aos_list_entry(pos->member.prev, type, member))
220
221 /*
222 * Get the list length.
223 *
224 * @param[in] queue the head for your list.
225 *
226 * @return list length.
227 */
dlist_entry_number(dlist_t * queue)228 static inline int dlist_entry_number(dlist_t *queue)
229 {
230 int num;
231
232 dlist_t *cur = queue;
233
234 for (num = 0; cur->next != queue; cur = cur->next, num++)
235 ;
236
237 return num;
238 }
239
240 /*
241 * Initialise the list.
242 *
243 * @param[in] name the list to be initialized.
244 */
245 #define AOS_DLIST_HEAD_INIT(name) {&(name), &(name)}
246
247 /*
248 * Initialise the list.
249 *
250 * @param[in] name the list to be initialized.
251 */
252 #define AOS_DLIST_HEAD(name) dlist_t name = AOS_DLIST_HEAD_INIT(name)
253
254 /* for single link list */
255 typedef struct slist_s {
256 struct slist_s *next;
257 } slist_t;
258
259 /*
260 * add one node into a signle link list at head.
261 *
262 * @param[in] node the data node to be inserted.
263 * @param[in] head the specified head node.
264 */
slist_add(slist_t * node,slist_t * head)265 static inline void slist_add(slist_t *node, slist_t *head)
266 {
267 node->next = head->next;
268 head->next = node;
269 }
270
271 /*
272 * add one node into a signle link list at tail.
273 *
274 * @param[in] node the data node to be inserted.
275 * @param[in] head the specified head node.
276 */
slist_add_tail(slist_t * node,slist_t * head)277 static inline void slist_add_tail(slist_t *node, slist_t *head)
278 {
279 while (head->next) {
280 head = head->next;
281 }
282
283 slist_add(node, head);
284 }
285
286 /*
287 * delete one node from the head list.
288 *
289 * @param[in] node the data node to be deleted.
290 * @param[in] head the specified head node.
291 */
slist_del(slist_t * node,slist_t * head)292 static inline void slist_del(slist_t *node, slist_t *head)
293 {
294 while (head->next) {
295 if (head->next == node) {
296 head->next = node->next;
297 break;
298 }
299
300 head = head->next;
301 }
302 }
303
304 /*
305 * Judge whether data list is empty.
306 *
307 * @param[in] head the head node of data list.
308 *
309 * @return 1 on empty, 0 FALSE.
310 */
slist_empty(const slist_t * head)311 static inline int slist_empty(const slist_t *head)
312 {
313 return !head->next;
314 }
315
316 /*
317 * initialize one node.
318 *
319 * @param[in] head the data node to be initialized.
320 */
slist_init(slist_t * head)321 static inline void slist_init(slist_t *head)
322 {
323 head->next = 0;
324 }
325
326 /*
327 * Iterate over list of given type.
328 *
329 * @param[in] queue he head for your list.
330 * @param[in] node the type * to use as a loop cursor.
331 * @param[in] type the type of the struct this is embedded in.
332 * @param[in] member the name of the slist_t within the struct.
333 */
334 #define slist_for_each_entry(queue, node, type, member) \
335 for (node = aos_container_of((queue)->next, type, member); \
336 (uintptr_t)node + aos_offsetof(type, member) != 0; \
337 node = aos_container_of(node->member.next, type, member))
338
339 /*
340 * Iterate over list of given type safe against removal of list entry.
341 *
342 * @param[in] queue the head for your list.
343 * @param[in] tmp the type * to use as a temp.
344 * @param[in] node the type * to use as a loop cursor.
345 * @param[in] type the type of the struct this is embedded in.
346 * @param[in] member the name of the slist_t within the struct.
347 */
348 #define slist_for_each_entry_safe(queue, tmp, node, type, member) \
349 for (node = aos_container_of((queue)->next, type, member), \
350 tmp = (queue)->next ? (queue)->next->next : NULL; \
351 (uintptr_t)node + aos_offsetof(type, member) != 0; \
352 node = aos_container_of(tmp, type, member), tmp = tmp ? tmp->next : tmp)
353
354 /*
355 * Initialise the list.
356 *
357 * @param[in] name the list to be initialized.
358 */
359 #define AOS_SLIST_HEAD_INIT(name) {0}
360
361 /*
362 * Initialise the list.
363 *
364 * @param[in] name the list to be initialized.
365 */
366 #define AOS_SLIST_HEAD(name) slist_t name = AOS_SLIST_HEAD_INIT(name)
367
368 /*
369 * Get the struct for this entry.
370 *
371 * @param[in] addr the list head to take the element from.
372 * @param[in] type the type of the struct this is embedded in.
373 * @param[in] member the name of the slist_t within the struct.
374 */
375 #define slist_entry(addr, type, member) \
376 (addr ? (type *)((long)addr - aos_offsetof(type, member)) : (type *)addr)
377
378 /*
379 * Get the first element from a list.
380 *
381 * @param[in] ptr the list head to take the element from.
382 * @param[in] type the type of the struct this is embedded in.
383 * @param[in] member the name of the slist_t within the struct.
384 */
385 #define slist_first_entry(ptr, type, member) slist_entry((ptr)->next, type, member)
386
387 /*
388 * Get the list length.
389 *
390 * @param[in] queue the head for your list.
391 *
392 * @return list length.
393 */
slist_entry_number(slist_t * queue)394 static inline int slist_entry_number(slist_t *queue)
395 {
396 int num;
397
398 slist_t *cur = queue;
399
400 for (num = 0; cur->next; cur = cur->next, num++)
401 ;
402
403 return num;
404 }
405
406 /** @} */
407
408 #ifdef __cplusplus
409 }
410 #endif
411
412 #endif /* AOS_LIST_H */
413
414