1 /*
2 * Doubly-linked list
3 * Copyright (c) 2009, Jouni Malinen <j@w1.fi>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation.
8 *
9 * Alternatively, this software may be distributed under the terms of BSD
10 * license.
11 *
12 * See README and COPYING for more details.
13 */
14
15 #ifndef DL_LIST_H
16 #define DL_LIST_H
17
18 #include <stddef.h>
19
20 /**
21 * struct dl_list - Doubly-linked list
22 */
23 struct dl_list {
24 struct dl_list *next;
25 struct dl_list *prev;
26 };
27
dl_list_init(struct dl_list * list)28 static inline void dl_list_init(struct dl_list *list)
29 {
30 list->next = list;
31 list->prev = list;
32 }
33
dl_list_add(struct dl_list * list,struct dl_list * item)34 static inline void dl_list_add(struct dl_list *list, struct dl_list *item)
35 {
36 item->next = list->next;
37 item->prev = list;
38 list->next->prev = item;
39 list->next = item;
40 }
41
dl_list_add_tail(struct dl_list * list,struct dl_list * item)42 static inline void dl_list_add_tail(struct dl_list *list, struct dl_list *item)
43 {
44 dl_list_add(list->prev, item);
45 }
46
dl_list_del(struct dl_list * item)47 static inline void dl_list_del(struct dl_list *item)
48 {
49 item->next->prev = item->prev;
50 item->prev->next = item->next;
51 item->next = NULL;
52 item->prev = NULL;
53 }
54
dl_list_empty(struct dl_list * list)55 static inline int dl_list_empty(struct dl_list *list)
56 {
57 return list->next == list;
58 }
59
dl_list_len(struct dl_list * list)60 static inline unsigned int dl_list_len(struct dl_list *list)
61 {
62 struct dl_list *item;
63 int count = 0;
64 for (item = list->next; item != list; item = item->next)
65 count++;
66 return count;
67 }
68
69 #ifndef offsetof
70 #define offsetof(type, member) ((long) &((type *) 0)->member)
71 #endif
72
73 #define dl_list_entry(item, type, member) \
74 ((type *) ((char *) item - offsetof(type, member)))
75
76 #define dl_list_first(list, type, member) \
77 (dl_list_empty((list)) ? NULL : \
78 dl_list_entry((list)->next, type, member))
79
80 #define dl_list_last(list, type, member) \
81 (dl_list_empty((list)) ? NULL : \
82 dl_list_entry((list)->prev, type, member))
83
84 #define dl_list_for_each(item, list, type, member) \
85 for (item = dl_list_entry((list)->next, type, member); \
86 &item->member != (list); \
87 item = dl_list_entry(item->member.next, type, member))
88
89 #define dl_list_for_each_safe(item, n, list, type, member) \
90 for (item = dl_list_entry((list)->next, type, member), \
91 n = dl_list_entry(item->member.next, type, member); \
92 &item->member != (list); \
93 item = n, n = dl_list_entry(n->member.next, type, member))
94
95 #define dl_list_for_each_reverse(item, list, type, member) \
96 for (item = dl_list_entry((list)->prev, type, member); \
97 &item->member != (list); \
98 item = dl_list_entry(item->member.prev, type, member))
99
100 #define DEFINE_DL_LIST(name) \
101 struct dl_list name = { &(name), &(name) }
102
103 #endif /* DL_LIST_H */
104
