]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
c7ecbf1e | 2 | * Copyright (c) 2008, 2009, 2010, 2011, 2013, 2015 Nicira, Inc. |
064af421 | 3 | * |
a14bc59f BP |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at: | |
064af421 | 7 | * |
a14bc59f BP |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
064af421 BP |
15 | */ |
16 | #ifndef LIST_H | |
17 | #define LIST_H 1 | |
18 | ||
19 | /* Doubly linked list. */ | |
20 | ||
21 | #include <stdbool.h> | |
22 | #include <stddef.h> | |
23 | #include "util.h" | |
55951e15 | 24 | #include "openvswitch/list.h" |
064af421 | 25 | |
ca6ba700 TG |
26 | static inline void list_init(struct ovs_list *); |
27 | static inline void list_poison(struct ovs_list *); | |
064af421 BP |
28 | |
29 | /* List insertion. */ | |
ca6ba700 TG |
30 | static inline void list_insert(struct ovs_list *, struct ovs_list *); |
31 | static inline void list_splice(struct ovs_list *before, struct ovs_list *first, | |
32 | struct ovs_list *last); | |
33 | static inline void list_push_front(struct ovs_list *, struct ovs_list *); | |
34 | static inline void list_push_back(struct ovs_list *, struct ovs_list *); | |
35 | static inline void list_replace(struct ovs_list *, const struct ovs_list *); | |
c7ecbf1e | 36 | static inline void list_moved(struct ovs_list *, const struct ovs_list *orig); |
ca6ba700 | 37 | static inline void list_move(struct ovs_list *dst, struct ovs_list *src); |
064af421 BP |
38 | |
39 | /* List removal. */ | |
ca6ba700 TG |
40 | static inline struct ovs_list *list_remove(struct ovs_list *); |
41 | static inline struct ovs_list *list_pop_front(struct ovs_list *); | |
42 | static inline struct ovs_list *list_pop_back(struct ovs_list *); | |
064af421 BP |
43 | |
44 | /* List elements. */ | |
ca6ba700 TG |
45 | static inline struct ovs_list *list_front(const struct ovs_list *); |
46 | static inline struct ovs_list *list_back(const struct ovs_list *); | |
064af421 BP |
47 | |
48 | /* List properties. */ | |
ca6ba700 TG |
49 | static inline size_t list_size(const struct ovs_list *); |
50 | static inline bool list_is_empty(const struct ovs_list *); | |
51 | static inline bool list_is_singleton(const struct ovs_list *); | |
52 | static inline bool list_is_short(const struct ovs_list *); | |
064af421 | 53 | |
4e8e4213 | 54 | #define LIST_FOR_EACH(ITER, MEMBER, LIST) \ |
f17e8ad6 | 55 | for (INIT_CONTAINER(ITER, (LIST)->next, MEMBER); \ |
4e8e4213 | 56 | &(ITER)->MEMBER != (LIST); \ |
772ec52b | 57 | ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER)) |
1f3c5efc | 58 | #define LIST_FOR_EACH_CONTINUE(ITER, MEMBER, LIST) \ |
f17e8ad6 | 59 | for (INIT_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER); \ |
1f3c5efc JR |
60 | &(ITER)->MEMBER != (LIST); \ |
61 | ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER)) | |
4e8e4213 | 62 | #define LIST_FOR_EACH_REVERSE(ITER, MEMBER, LIST) \ |
f17e8ad6 | 63 | for (INIT_CONTAINER(ITER, (LIST)->prev, MEMBER); \ |
4e8e4213 | 64 | &(ITER)->MEMBER != (LIST); \ |
772ec52b | 65 | ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) |
1f3c5efc JR |
66 | #define LIST_FOR_EACH_REVERSE_CONTINUE(ITER, MEMBER, LIST) \ |
67 | for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER); \ | |
68 | &(ITER)->MEMBER != (LIST); \ | |
69 | ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) | |
33e191a0 | 70 | #define LIST_FOR_EACH_SAFE(ITER, NEXT, MEMBER, LIST) \ |
f17e8ad6 | 71 | for (INIT_CONTAINER(ITER, (LIST)->next, MEMBER); \ |
33e191a0 | 72 | (&(ITER)->MEMBER != (LIST) \ |
f17e8ad6 | 73 | ? INIT_CONTAINER(NEXT, (ITER)->MEMBER.next, MEMBER), 1 \ |
33e191a0 | 74 | : 0); \ |
772ec52b | 75 | (ITER) = (NEXT)) |
5f03c983 JR |
76 | #define LIST_FOR_EACH_POP(ITER, MEMBER, LIST) \ |
77 | while (!list_is_empty(LIST) \ | |
78 | && (INIT_CONTAINER(ITER, list_pop_front(LIST), MEMBER), 1)) | |
5445f508 JR |
79 | \f |
80 | /* Inline implementations. */ | |
81 | ||
82 | /* Initializes 'list' as an empty list. */ | |
83 | static inline void | |
ca6ba700 | 84 | list_init(struct ovs_list *list) |
5445f508 JR |
85 | { |
86 | list->next = list->prev = list; | |
87 | } | |
88 | ||
89 | /* Initializes 'list' with pointers that will (probably) cause segfaults if | |
90 | * dereferenced and, better yet, show up clearly in a debugger. */ | |
91 | static inline void | |
ca6ba700 | 92 | list_poison(struct ovs_list *list) |
5445f508 JR |
93 | { |
94 | memset(list, 0xcc, sizeof *list); | |
95 | } | |
96 | ||
97 | /* Inserts 'elem' just before 'before'. */ | |
98 | static inline void | |
ca6ba700 | 99 | list_insert(struct ovs_list *before, struct ovs_list *elem) |
5445f508 JR |
100 | { |
101 | elem->prev = before->prev; | |
102 | elem->next = before; | |
103 | before->prev->next = elem; | |
104 | before->prev = elem; | |
105 | } | |
106 | ||
107 | /* Removes elements 'first' though 'last' (exclusive) from their current list, | |
108 | then inserts them just before 'before'. */ | |
109 | static inline void | |
ca6ba700 | 110 | list_splice(struct ovs_list *before, struct ovs_list *first, struct ovs_list *last) |
5445f508 JR |
111 | { |
112 | if (first == last) { | |
113 | return; | |
114 | } | |
115 | last = last->prev; | |
116 | ||
117 | /* Cleanly remove 'first'...'last' from its current list. */ | |
118 | first->prev->next = last->next; | |
119 | last->next->prev = first->prev; | |
120 | ||
121 | /* Splice 'first'...'last' into new list. */ | |
122 | first->prev = before->prev; | |
123 | last->next = before; | |
124 | before->prev->next = first; | |
125 | before->prev = last; | |
126 | } | |
127 | ||
128 | /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in | |
129 | 'list'. */ | |
130 | static inline void | |
ca6ba700 | 131 | list_push_front(struct ovs_list *list, struct ovs_list *elem) |
5445f508 JR |
132 | { |
133 | list_insert(list->next, elem); | |
134 | } | |
135 | ||
136 | /* Inserts 'elem' at the end of 'list', so that it becomes the back in | |
137 | * 'list'. */ | |
138 | static inline void | |
ca6ba700 | 139 | list_push_back(struct ovs_list *list, struct ovs_list *elem) |
5445f508 JR |
140 | { |
141 | list_insert(list, elem); | |
142 | } | |
143 | ||
144 | /* Puts 'elem' in the position currently occupied by 'position'. | |
145 | * Afterward, 'position' is not part of a list. */ | |
146 | static inline void | |
ca6ba700 | 147 | list_replace(struct ovs_list *element, const struct ovs_list *position) |
5445f508 JR |
148 | { |
149 | element->next = position->next; | |
150 | element->next->prev = element; | |
151 | element->prev = position->prev; | |
152 | element->prev->next = element; | |
153 | } | |
154 | ||
155 | /* Adjusts pointers around 'list' to compensate for 'list' having been moved | |
c7ecbf1e BP |
156 | * around in memory (e.g. as a consequence of realloc()), with original |
157 | * location 'orig'. | |
5445f508 | 158 | * |
c7ecbf1e BP |
159 | * ('orig' likely points to freed memory, but this function does not |
160 | * dereference 'orig', it only compares it to 'list'. In a very pedantic | |
161 | * language lawyer sense, this still yields undefined behavior, but it works | |
162 | * with actual compilers.) */ | |
5445f508 | 163 | static inline void |
c7ecbf1e | 164 | list_moved(struct ovs_list *list, const struct ovs_list *orig) |
5445f508 | 165 | { |
c7ecbf1e BP |
166 | if (list->next == orig) { |
167 | list_init(list); | |
168 | } else { | |
169 | list->prev->next = list->next->prev = list; | |
170 | } | |
5445f508 JR |
171 | } |
172 | ||
173 | /* Initializes 'dst' with the contents of 'src', compensating for moving it | |
174 | * around in memory. The effect is that, if 'src' was the head of a list, now | |
175 | * 'dst' is the head of a list containing the same elements. */ | |
176 | static inline void | |
ca6ba700 | 177 | list_move(struct ovs_list *dst, struct ovs_list *src) |
5445f508 | 178 | { |
c7ecbf1e BP |
179 | *dst = *src; |
180 | list_moved(dst, src); | |
5445f508 JR |
181 | } |
182 | ||
183 | /* Removes 'elem' from its list and returns the element that followed it. | |
184 | Undefined behavior if 'elem' is not in a list. */ | |
ca6ba700 TG |
185 | static inline struct ovs_list * |
186 | list_remove(struct ovs_list *elem) | |
5445f508 JR |
187 | { |
188 | elem->prev->next = elem->next; | |
189 | elem->next->prev = elem->prev; | |
190 | return elem->next; | |
191 | } | |
192 | ||
193 | /* Removes the front element from 'list' and returns it. Undefined behavior if | |
194 | 'list' is empty before removal. */ | |
ca6ba700 TG |
195 | static inline struct ovs_list * |
196 | list_pop_front(struct ovs_list *list) | |
5445f508 | 197 | { |
ca6ba700 | 198 | struct ovs_list *front = list->next; |
5445f508 JR |
199 | |
200 | list_remove(front); | |
201 | return front; | |
202 | } | |
203 | ||
204 | /* Removes the back element from 'list' and returns it. | |
205 | Undefined behavior if 'list' is empty before removal. */ | |
ca6ba700 TG |
206 | static inline struct ovs_list * |
207 | list_pop_back(struct ovs_list *list) | |
5445f508 | 208 | { |
ca6ba700 | 209 | struct ovs_list *back = list->prev; |
5445f508 JR |
210 | |
211 | list_remove(back); | |
212 | return back; | |
213 | } | |
214 | ||
215 | /* Returns the front element in 'list_'. | |
216 | Undefined behavior if 'list_' is empty. */ | |
ca6ba700 TG |
217 | static inline struct ovs_list * |
218 | list_front(const struct ovs_list *list_) | |
5445f508 | 219 | { |
ca6ba700 | 220 | struct ovs_list *list = CONST_CAST(struct ovs_list *, list_); |
5445f508 JR |
221 | |
222 | ovs_assert(!list_is_empty(list)); | |
223 | ||
224 | return list->next; | |
225 | } | |
226 | ||
227 | /* Returns the back element in 'list_'. | |
228 | Undefined behavior if 'list_' is empty. */ | |
ca6ba700 TG |
229 | static inline struct ovs_list * |
230 | list_back(const struct ovs_list *list_) | |
5445f508 | 231 | { |
ca6ba700 | 232 | struct ovs_list *list = CONST_CAST(struct ovs_list *, list_); |
5445f508 JR |
233 | |
234 | ovs_assert(!list_is_empty(list)); | |
235 | ||
236 | return list->prev; | |
237 | } | |
238 | ||
239 | /* Returns the number of elements in 'list'. | |
240 | Runs in O(n) in the number of elements. */ | |
241 | static inline size_t | |
ca6ba700 | 242 | list_size(const struct ovs_list *list) |
5445f508 | 243 | { |
ca6ba700 | 244 | const struct ovs_list *e; |
5445f508 JR |
245 | size_t cnt = 0; |
246 | ||
247 | for (e = list->next; e != list; e = e->next) { | |
248 | cnt++; | |
249 | } | |
250 | return cnt; | |
251 | } | |
252 | ||
253 | /* Returns true if 'list' is empty, false otherwise. */ | |
254 | static inline bool | |
ca6ba700 | 255 | list_is_empty(const struct ovs_list *list) |
5445f508 JR |
256 | { |
257 | return list->next == list; | |
258 | } | |
259 | ||
260 | /* Returns true if 'list' has exactly 1 element, false otherwise. */ | |
261 | static inline bool | |
ca6ba700 | 262 | list_is_singleton(const struct ovs_list *list) |
5445f508 JR |
263 | { |
264 | return list_is_short(list) && !list_is_empty(list); | |
265 | } | |
266 | ||
267 | /* Returns true if 'list' has 0 or 1 elements, false otherwise. */ | |
268 | static inline bool | |
ca6ba700 | 269 | list_is_short(const struct ovs_list *list) |
5445f508 JR |
270 | { |
271 | return list->next == list->prev; | |
272 | } | |
064af421 BP |
273 | |
274 | #endif /* list.h */ |