1 /*
2 * Copyright (c) 2022, sakumisu
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6 #ifndef USB_LIST_H
7 #define USB_LIST_H
8
9 #include <string.h>
10 #include <stdint.h>
11
12 #ifdef __cplusplus
13 extern "C" {
14 #endif
15
16 /**
17 * usb_container_of - return the member address of ptr, if the type of ptr is the
18 * struct type.
19 */
20 #define usb_container_of(ptr, type, member) \
21 ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
22
23 /**
24 * Single List structure
25 */
26 struct usb_slist_node {
27 struct usb_slist_node *next; /**< point to next node. */
28 };
29 typedef struct usb_slist_node usb_slist_t; /**< Type for single list. */
30
31 /**
32 * @brief initialize a single list
33 *
34 * @param l the single list to be initialized
35 */
usb_slist_init(usb_slist_t * l)36 static inline void usb_slist_init(usb_slist_t *l)
37 {
38 l->next = NULL;
39 }
40
usb_slist_add_head(usb_slist_t * l,usb_slist_t * n)41 static inline void usb_slist_add_head(usb_slist_t *l, usb_slist_t *n)
42 {
43 n->next = l->next;
44 l->next = n;
45 }
46
usb_slist_add_tail(usb_slist_t * l,usb_slist_t * n)47 static inline void usb_slist_add_tail(usb_slist_t *l, usb_slist_t *n)
48 {
49 usb_slist_t *tmp = l;
50
51 while (tmp->next) {
52 tmp = tmp->next;
53 }
54
55 /* append the node to the tail */
56 tmp->next = n;
57 n->next = NULL;
58 }
59
usb_slist_insert(usb_slist_t * l,usb_slist_t * next,usb_slist_t * n)60 static inline void usb_slist_insert(usb_slist_t *l, usb_slist_t *next, usb_slist_t *n)
61 {
62 if (!next) {
63 usb_slist_add_tail(next, l);
64 return;
65 }
66
67 while (l->next) {
68 if (l->next == next) {
69 l->next = n;
70 n->next = next;
71 }
72
73 l = l->next;
74 }
75 }
76
usb_slist_remove(usb_slist_t * l,usb_slist_t * n)77 static inline usb_slist_t *usb_slist_remove(usb_slist_t *l, usb_slist_t *n)
78 {
79 usb_slist_t *tmp = l;
80 /* remove slist head */
81 while (tmp->next && tmp->next != n) {
82 tmp = tmp->next;
83 }
84
85 /* remove node */
86 if (tmp->next != (usb_slist_t *)0) {
87 tmp->next = tmp->next->next;
88 }
89
90 return l;
91 }
92
usb_slist_len(const usb_slist_t * l)93 static inline unsigned int usb_slist_len(const usb_slist_t *l)
94 {
95 unsigned int len = 0;
96 const usb_slist_t *list = l->next;
97
98 while (list != NULL) {
99 list = list->next;
100 len++;
101 }
102
103 return len;
104 }
105
usb_slist_contains(usb_slist_t * l,usb_slist_t * n)106 static inline unsigned int usb_slist_contains(usb_slist_t *l, usb_slist_t *n)
107 {
108 while (l->next) {
109 if (l->next == n) {
110 return 0;
111 }
112
113 l = l->next;
114 }
115
116 return 1;
117 }
118
usb_slist_head(usb_slist_t * l)119 static inline usb_slist_t *usb_slist_head(usb_slist_t *l)
120 {
121 return l->next;
122 }
123
usb_slist_tail(usb_slist_t * l)124 static inline usb_slist_t *usb_slist_tail(usb_slist_t *l)
125 {
126 while (l->next) {
127 l = l->next;
128 }
129
130 return l;
131 }
132
usb_slist_next(usb_slist_t * n)133 static inline usb_slist_t *usb_slist_next(usb_slist_t *n)
134 {
135 return n->next;
136 }
137
usb_slist_isempty(usb_slist_t * l)138 static inline int usb_slist_isempty(usb_slist_t *l)
139 {
140 return l->next == NULL;
141 }
142
143 /**
144 * @brief initialize a slist object
145 */
146 #define USB_SLIST_OBJECT_INIT(object) \
147 { \
148 NULL \
149 }
150
151 /**
152 * @brief initialize a slist object
153 */
154 #define USB_SLIST_DEFINE(slist) \
155 usb_slist_t slist = { NULL }
156
157 /**
158 * @brief get the struct for this single list node
159 * @param node the entry point
160 * @param type the type of structure
161 * @param member the name of list in structure
162 */
163 #define usb_slist_entry(node, type, member) \
164 usb_container_of(node, type, member)
165
166 /**
167 * usb_slist_first_entry - get the first element from a slist
168 * @ptr: the slist head to take the element from.
169 * @type: the type of the struct this is embedded in.
170 * @member: the name of the slist_struct within the struct.
171 *
172 * Note, that slist is expected to be not empty.
173 */
174 #define usb_slist_first_entry(ptr, type, member) \
175 usb_slist_entry((ptr)->next, type, member)
176
177 /**
178 * usb_slist_tail_entry - get the tail element from a slist
179 * @ptr: the slist head to take the element from.
180 * @type: the type of the struct this is embedded in.
181 * @member: the name of the slist_struct within the struct.
182 *
183 * Note, that slist is expected to be not empty.
184 */
185 #define usb_slist_tail_entry(ptr, type, member) \
186 usb_slist_entry(usb_slist_tail(ptr), type, member)
187
188 /**
189 * usb_slist_first_entry_or_null - get the first element from a slist
190 * @ptr: the slist head to take the element from.
191 * @type: the type of the struct this is embedded in.
192 * @member: the name of the slist_struct within the struct.
193 *
194 * Note, that slist is expected to be not empty.
195 */
196 #define usb_slist_first_entry_or_null(ptr, type, member) \
197 (usb_slist_isempty(ptr) ? NULL : usb_slist_first_entry(ptr, type, member))
198
199 /**
200 * usb_slist_for_each - iterate over a single list
201 * @pos: the usb_slist_t * to use as a loop cursor.
202 * @head: the head for your single list.
203 */
204 #define usb_slist_for_each(pos, head) \
205 for (pos = (head)->next; pos != NULL; pos = pos->next)
206
207 #define usb_slist_for_each_safe(pos, next, head) \
208 for (pos = (head)->next, next = pos->next; pos; \
209 pos = next, next = pos->next)
210
211 /**
212 * usb_slist_for_each_entry - iterate over single list of given type
213 * @pos: the type * to use as a loop cursor.
214 * @head: the head for your single list.
215 * @member: the name of the list_struct within the struct.
216 */
217 #define usb_slist_for_each_entry(pos, head, member) \
218 for (pos = usb_slist_entry((head)->next, typeof(*pos), member); \
219 &pos->member != (NULL); \
220 pos = usb_slist_entry(pos->member.next, typeof(*pos), member))
221
222 #define usb_slist_for_each_entry_safe(pos, n, head, member) \
223 for (pos = usb_slist_entry((head)->next, typeof(*pos), member), \
224 n = usb_slist_entry(pos->member.next, typeof(*pos), member); \
225 &pos->member != (NULL); \
226 pos = n, n = usb_slist_entry(pos->member.next, typeof(*pos), member))
227
228 /**
229 * Double List structure
230 */
231 struct usb_dlist_node {
232 struct usb_dlist_node *next; /**< point to next node. */
233 struct usb_dlist_node *prev; /**< point to prev node. */
234 };
235 typedef struct usb_dlist_node usb_dlist_t; /**< Type for lists. */
236
237 /**
238 * @brief initialize a list
239 *
240 * @param l list to be initialized
241 */
usb_dlist_init(usb_dlist_t * l)242 static inline void usb_dlist_init(usb_dlist_t *l)
243 {
244 l->next = l->prev = l;
245 }
246
247 /**
248 * @brief insert a node after a list
249 *
250 * @param l list to insert it
251 * @param n new node to be inserted
252 */
usb_dlist_insert_after(usb_dlist_t * l,usb_dlist_t * n)253 static inline void usb_dlist_insert_after(usb_dlist_t *l, usb_dlist_t *n)
254 {
255 l->next->prev = n;
256 n->next = l->next;
257
258 l->next = n;
259 n->prev = l;
260 }
261
262 /**
263 * @brief insert a node before a list
264 *
265 * @param n new node to be inserted
266 * @param l list to insert it
267 */
usb_dlist_insert_before(usb_dlist_t * l,usb_dlist_t * n)268 static inline void usb_dlist_insert_before(usb_dlist_t *l, usb_dlist_t *n)
269 {
270 l->prev->next = n;
271 n->prev = l->prev;
272
273 l->prev = n;
274 n->next = l;
275 }
276
277 /**
278 * @brief remove node from list.
279 * @param n the node to remove from the list.
280 */
usb_dlist_remove(usb_dlist_t * n)281 static inline void usb_dlist_remove(usb_dlist_t *n)
282 {
283 n->next->prev = n->prev;
284 n->prev->next = n->next;
285
286 n->next = n->prev = n;
287 }
288
289 /**
290 * @brief move node from list.
291 * @param n the node to remove from the list.
292 */
usb_dlist_move_head(usb_dlist_t * l,usb_dlist_t * n)293 static inline void usb_dlist_move_head(usb_dlist_t *l, usb_dlist_t *n)
294 {
295 usb_dlist_remove(n);
296 usb_dlist_insert_after(l, n);
297 }
298
299 /**
300 * @brief move node from list.
301 * @param n the node to remove from the list.
302 */
usb_dlist_move_tail(usb_dlist_t * l,usb_dlist_t * n)303 static inline void usb_dlist_move_tail(usb_dlist_t *l, usb_dlist_t *n)
304 {
305 usb_dlist_remove(n);
306 usb_dlist_insert_before(l, n);
307 }
308
309 /**
310 * @brief tests whether a list is empty
311 * @param l the list to test.
312 */
usb_dlist_isempty(const usb_dlist_t * l)313 static inline int usb_dlist_isempty(const usb_dlist_t *l)
314 {
315 return l->next == l;
316 }
317
318 /**
319 * @brief get the list length
320 * @param l the list to get.
321 */
usb_dlist_len(const usb_dlist_t * l)322 static inline unsigned int usb_dlist_len(const usb_dlist_t *l)
323 {
324 unsigned int len = 0;
325 const usb_dlist_t *p = l;
326
327 while (p->next != l) {
328 p = p->next;
329 len++;
330 }
331
332 return len;
333 }
334
335 /**
336 * @brief initialize a dlist object
337 */
338 #define USB_DLIST_OBJECT_INIT(object) \
339 { \
340 &(object), &(object) \
341 }
342 /**
343 * @brief initialize a dlist object
344 */
345 #define USB_DLIST_DEFINE(list) \
346 usb_dlist_t list = { &(list), &(list) }
347
348 /**
349 * @brief get the struct for this entry
350 * @param node the entry point
351 * @param type the type of structure
352 * @param member the name of list in structure
353 */
354 #define usb_dlist_entry(node, type, member) \
355 usb_container_of(node, type, member)
356
357 /**
358 * dlist_first_entry - get the first element from a list
359 * @ptr: the list head to take the element from.
360 * @type: the type of the struct this is embedded in.
361 * @member: the name of the list_struct within the struct.
362 *
363 * Note, that list is expected to be not empty.
364 */
365 #define usb_dlist_first_entry(ptr, type, member) \
366 usb_dlist_entry((ptr)->next, type, member)
367 /**
368 * dlist_first_entry_or_null - get the first element from a list
369 * @ptr: the list head to take the element from.
370 * @type: the type of the struct this is embedded in.
371 * @member: the name of the list_struct within the struct.
372 *
373 * Note, that list is expected to be not empty.
374 */
375 #define usb_dlist_first_entry_or_null(ptr, type, member) \
376 (usb_dlist_isempty(ptr) ? NULL : usb_dlist_first_entry(ptr, type, member))
377
378 /**
379 * usb_dlist_for_each - iterate over a list
380 * @pos: the usb_dlist_t * to use as a loop cursor.
381 * @head: the head for your list.
382 */
383 #define usb_dlist_for_each(pos, head) \
384 for (pos = (head)->next; pos != (head); pos = pos->next)
385
386 /**
387 * usb_dlist_for_each_prev - iterate over a list
388 * @pos: the dlist_t * to use as a loop cursor.
389 * @head: the head for your list.
390 */
391 #define usb_dlist_for_each_prev(pos, head) \
392 for (pos = (head)->prev; pos != (head); pos = pos->prev)
393
394 /**
395 * usb_dlist_for_each_safe - iterate over a list safe against removal of list entry
396 * @pos: the dlist_t * to use as a loop cursor.
397 * @n: another dlist_t * to use as temporary storage
398 * @head: the head for your list.
399 */
400 #define usb_dlist_for_each_safe(pos, n, head) \
401 for (pos = (head)->next, n = pos->next; pos != (head); \
402 pos = n, n = pos->next)
403
404 #define usb_dlist_for_each_prev_safe(pos, n, head) \
405 for (pos = (head)->prev, n = pos->prev; pos != (head); \
406 pos = n, n = pos->prev)
407 /**
408 * usb_dlist_for_each_entry - iterate over list of given type
409 * @pos: the type * to use as a loop cursor.
410 * @head: the head for your list.
411 * @member: the name of the list_struct within the struct.
412 */
413 #define usb_dlist_for_each_entry(pos, head, member) \
414 for (pos = usb_dlist_entry((head)->next, typeof(*pos), member); \
415 &pos->member != (head); \
416 pos = usb_dlist_entry(pos->member.next, typeof(*pos), member))
417
418 /**
419 * usb_usb_dlist_for_each_entry_reverse - iterate over list of given type
420 * @pos: the type * to use as a loop cursor.
421 * @head: the head for your list.
422 * @member: the name of the list_struct within the struct.
423 */
424 #define usb_dlist_for_each_entry_reverse(pos, head, member) \
425 for (pos = usb_dlist_entry((head)->prev, typeof(*pos), member); \
426 &pos->member != (head); \
427 pos = usb_dlist_entry(pos->member.prev, typeof(*pos), member))
428
429 /**
430 * usb_usb_dlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
431 * @pos: the type * to use as a loop cursor.
432 * @n: another type * to use as temporary storage
433 * @head: the head for your list.
434 * @member: the name of the list_struct within the struct.
435 */
436 #define usb_dlist_for_each_entry_safe(pos, n, head, member) \
437 for (pos = usb_dlist_entry((head)->next, typeof(*pos), member), \
438 n = usb_dlist_entry(pos->member.next, typeof(*pos), member); \
439 &pos->member != (head); \
440 pos = n, n = usb_dlist_entry(n->member.next, typeof(*n), member))
441
442 /**
443 * usb_usb_dlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
444 * @pos: the type * to use as a loop cursor.
445 * @n: another type * to use as temporary storage
446 * @head: the head for your list.
447 * @member: the name of the list_struct within the struct.
448 */
449 #define usb_dlist_for_each_entry_safe_reverse(pos, n, head, member) \
450 for (pos = usb_dlist_entry((head)->prev, typeof(*pos), field), \
451 n = usb_dlist_entry(pos->member.prev, typeof(*pos), member); \
452 &pos->member != (head); \
453 pos = n, n = usb_dlist_entry(pos->member.prev, typeof(*pos), member))
454
455 #ifdef __cplusplus
456 }
457 #endif
458
459 #endif /* USB_LIST_H */
460