Commit | Line | Data |
---|---|---|
a00718e7 MD |
1 | /* |
2 | * Copyright (C) 2002 Free Software Foundation, Inc. | |
3 | * (originally part of the GNU C Library) | |
4 | * Contributed by Ulrich Drepper <drepper@redhat.com>, 2002. | |
5 | * | |
6 | * Copyright (C) 2009 Pierre-Marc Fournier | |
7 | * Conversion to RCU list. | |
8 | * Copyright (C) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
9 | * | |
10 | * This library is free software; you can redistribute it and/or | |
11 | * modify it under the terms of the GNU Lesser General Public | |
12 | * License as published by the Free Software Foundation; either | |
13 | * version 2.1 of the License, or (at your option) any later version. | |
14 | * | |
15 | * This library is distributed in the hope that it will be useful, | |
16 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
17 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
18 | * Lesser General Public License for more details. | |
19 | * | |
20 | * You should have received a copy of the GNU Lesser General Public | |
21 | * License along with this library; if not, write to the Free Software | |
22 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
23 | */ | |
7a50dcf7 | 24 | |
34cfb3e3 MD |
25 | #ifndef _CDS_LIST_H |
26 | #define _CDS_LIST_H 1 | |
7a50dcf7 MD |
27 | |
28 | /* The definitions of this file are adopted from those which can be | |
29 | found in the Linux kernel headers to enable people familiar with | |
30 | the latter find their way in these sources as well. */ | |
31 | ||
32 | ||
33 | /* Basic type for the double-link list. */ | |
34cfb3e3 | 34 | struct cds_list_head |
7a50dcf7 | 35 | { |
16aa9ee8 DG |
36 | struct cds_list_head *next; |
37 | struct cds_list_head *prev; | |
34cfb3e3 | 38 | }; |
7a50dcf7 | 39 | |
7a50dcf7 | 40 | /* Define a variable with the head and tail of the list. */ |
16aa9ee8 | 41 | #define CDS_LIST_HEAD(name) \ |
34cfb3e3 | 42 | struct cds_list_head name = { &(name), &(name) } |
7a50dcf7 MD |
43 | |
44 | /* Initialize a new list head. */ | |
16aa9ee8 | 45 | #define CDS_INIT_LIST_HEAD(ptr) \ |
7a50dcf7 MD |
46 | (ptr)->next = (ptr)->prev = (ptr) |
47 | ||
16aa9ee8 | 48 | #define CDS_LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } |
7a50dcf7 MD |
49 | |
50 | /* Add new element at the head of the list. */ | |
51 | static inline void | |
34cfb3e3 | 52 | cds_list_add (struct cds_list_head *newp, struct cds_list_head *head) |
7a50dcf7 MD |
53 | { |
54 | head->next->prev = newp; | |
55 | newp->next = head->next; | |
56 | newp->prev = head; | |
57 | head->next = newp; | |
58 | } | |
59 | ||
60 | ||
61 | /* Add new element at the tail of the list. */ | |
62 | static inline void | |
34cfb3e3 | 63 | cds_list_add_tail (struct cds_list_head *newp, struct cds_list_head *head) |
7a50dcf7 MD |
64 | { |
65 | head->prev->next = newp; | |
66 | newp->next = head; | |
67 | newp->prev = head->prev; | |
68 | head->prev = newp; | |
69 | } | |
70 | ||
71 | ||
63ff4873 MD |
72 | /* Remove element from list. */ |
73 | static inline void | |
34cfb3e3 | 74 | __cds_list_del (struct cds_list_head *prev, struct cds_list_head *next) |
63ff4873 MD |
75 | { |
76 | next->prev = prev; | |
77 | prev->next = next; | |
78 | } | |
79 | ||
7a50dcf7 MD |
80 | /* Remove element from list. */ |
81 | static inline void | |
34cfb3e3 | 82 | cds_list_del (struct cds_list_head *elem) |
7a50dcf7 | 83 | { |
16aa9ee8 | 84 | __cds_list_del (elem->prev, elem->next); |
7a50dcf7 MD |
85 | } |
86 | ||
3ec07d9f PM |
87 | /* Remove element from list, initializing the element's list pointers. */ |
88 | static inline void | |
89 | cds_list_del_init (struct cds_list_head *elem) | |
90 | { | |
91 | cds_list_del(elem); | |
92 | CDS_INIT_LIST_HEAD(elem); | |
93 | } | |
94 | ||
ac956d00 MD |
95 | /* delete from list, add to another list as head */ |
96 | static inline void | |
34cfb3e3 | 97 | cds_list_move (struct cds_list_head *elem, struct cds_list_head *head) |
ac956d00 | 98 | { |
16aa9ee8 DG |
99 | __cds_list_del (elem->prev, elem->next); |
100 | cds_list_add (elem, head); | |
ac956d00 | 101 | } |
7a50dcf7 | 102 | |
5db941e8 MD |
103 | /* replace an old entry. |
104 | */ | |
105 | static inline void | |
34cfb3e3 | 106 | cds_list_replace(struct cds_list_head *old, struct cds_list_head *_new) |
5db941e8 MD |
107 | { |
108 | _new->next = old->next; | |
109 | _new->prev = old->prev; | |
110 | _new->prev->next = _new; | |
111 | _new->next->prev = _new; | |
112 | } | |
113 | ||
7a50dcf7 MD |
114 | /* Join two lists. */ |
115 | static inline void | |
34cfb3e3 | 116 | cds_list_splice (struct cds_list_head *add, struct cds_list_head *head) |
7a50dcf7 MD |
117 | { |
118 | /* Do nothing if the list which gets added is empty. */ | |
119 | if (add != add->next) | |
120 | { | |
121 | add->next->prev = head; | |
122 | add->prev->next = head->next; | |
123 | head->next->prev = add->prev; | |
124 | head->next = add->next; | |
125 | } | |
126 | } | |
127 | ||
4b7cab77 MD |
128 | /* Returns 1 if list is empty, 0 otherwise */ |
129 | static inline | |
130 | int cds_list_empty(struct cds_list_head *head) | |
131 | { | |
132 | return head->next == head->prev; | |
133 | } | |
134 | ||
7a50dcf7 | 135 | /* Get typed element from list at a given position. */ |
16aa9ee8 | 136 | #define cds_list_entry(ptr, type, member) \ |
7a50dcf7 MD |
137 | ((type *) ((char *) (ptr) - (unsigned long) (&((type *) 0)->member))) |
138 | ||
139 | ||
58090b34 | 140 | /* Get first entry from a list. */ |
4b7cab77 MD |
141 | #define cds_list_first_entry(head, type, member) \ |
142 | cds_list_entry((head)->next, type, member) | |
58090b34 | 143 | |
7a50dcf7 MD |
144 | |
145 | /* Iterate forward over the elements of the list. */ | |
16aa9ee8 | 146 | #define cds_list_for_each(pos, head) \ |
7a50dcf7 MD |
147 | for (pos = (head)->next; pos != (head); pos = pos->next) |
148 | ||
149 | ||
150 | /* Iterate forward over the elements of the list. */ | |
16aa9ee8 | 151 | #define cds_list_for_each_prev(pos, head) \ |
7a50dcf7 MD |
152 | for (pos = (head)->prev; pos != (head); pos = pos->prev) |
153 | ||
154 | ||
155 | /* Iterate backwards over the elements list. The list elements can be | |
156 | removed from the list while doing this. */ | |
16aa9ee8 | 157 | #define cds_list_for_each_prev_safe(pos, p, head) \ |
7a50dcf7 MD |
158 | for (pos = (head)->prev, p = pos->prev; \ |
159 | pos != (head); \ | |
160 | pos = p, p = pos->prev) | |
161 | ||
16aa9ee8 DG |
162 | #define cds_list_for_each_entry(pos, head, member) \ |
163 | for (pos = cds_list_entry((head)->next, typeof(*pos), member); \ | |
7a50dcf7 | 164 | &pos->member != (head); \ |
16aa9ee8 | 165 | pos = cds_list_entry(pos->member.next, typeof(*pos), member)) |
7a50dcf7 | 166 | |
16aa9ee8 DG |
167 | #define cds_list_for_each_entry_reverse(pos, head, member) \ |
168 | for (pos = cds_list_entry((head)->prev, typeof(*pos), member); \ | |
7a50dcf7 | 169 | &pos->member != (head); \ |
16aa9ee8 | 170 | pos = cds_list_entry(pos->member.prev, typeof(*pos), member)) |
7a50dcf7 | 171 | |
16aa9ee8 DG |
172 | #define cds_list_for_each_entry_safe(pos, p, head, member) \ |
173 | for (pos = cds_list_entry((head)->next, typeof(*pos), member), \ | |
174 | p = cds_list_entry(pos->member.next,typeof(*pos), member); \ | |
7a50dcf7 | 175 | &pos->member != (head); \ |
16aa9ee8 | 176 | pos = p, p = cds_list_entry(pos->member.next, typeof(*pos), member)) |
7a50dcf7 | 177 | |
34cfb3e3 | 178 | static inline int cds_list_empty(struct cds_list_head *head) |
7a50dcf7 MD |
179 | { |
180 | return head == head->next; | |
181 | } | |
182 | ||
34cfb3e3 MD |
183 | static inline void cds_list_replace_init(struct cds_list_head *old, |
184 | struct cds_list_head *_new) | |
7a50dcf7 | 185 | { |
34cfb3e3 | 186 | struct cds_list_head *head = old->next; |
16aa9ee8 DG |
187 | cds_list_del(old); |
188 | cds_list_add_tail(_new, head); | |
189 | CDS_INIT_LIST_HEAD(old); | |
7a50dcf7 MD |
190 | } |
191 | ||
34cfb3e3 | 192 | #endif /* _CDS_LIST_H */ |