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