File: | lib/list.h |
Warning: | line 324, column 18 Access to field 'next' results in a dereference of a null pointer (loaded from field 'prev') |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* | |||
2 | * lwan - simple web server | |||
3 | * Copyright (c) 2020 Leandro A. F. Pereira <leandro@hardinfo.org> | |||
4 | * | |||
5 | * This program is free software; you can redistribute it and/or | |||
6 | * modify it under the terms of the GNU General Public License | |||
7 | * as published by the Free Software Foundation; either version 2 | |||
8 | * of the License, or any later version. | |||
9 | * | |||
10 | * This program is distributed in the hope that it will be useful, | |||
11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |||
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |||
13 | * GNU General Public License for more details. | |||
14 | * | |||
15 | * You should have received a copy of the GNU General Public License | |||
16 | * along with this program; if not, write to the Free Software | |||
17 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, | |||
18 | * USA. | |||
19 | */ | |||
20 | ||||
21 | #define _GNU_SOURCE | |||
22 | #include <stdarg.h> | |||
23 | #include <stdio.h> | |||
24 | #include <pthread.h> | |||
25 | ||||
26 | #include "list.h" | |||
27 | #include "ringbuffer.h" | |||
28 | #include "lwan-private.h" | |||
29 | ||||
30 | struct lwan_pubsub_topic { | |||
31 | struct list_head subscribers; | |||
32 | pthread_mutex_t lock; | |||
33 | }; | |||
34 | ||||
35 | struct lwan_pubsub_msg { | |||
36 | struct lwan_value value; | |||
37 | unsigned int refcount; | |||
38 | }; | |||
39 | ||||
40 | DEFINE_RING_BUFFER_TYPE(lwan_pubsub_msg_ref_ring, struct lwan_pubsub_msg *, 16)extern int (*__Static_assert_function (void)) [!!sizeof (struct { int __error_if_negative: ((16) && !((16) & ((16 )-1))) ? 2 : -1; })]; struct lwan_pubsub_msg_ref_ring { uint32_t read, write; struct lwan_pubsub_msg * array[16]; }; __attribute__ ((unused)) static inline uint32_t lwan_pubsub_msg_ref_ring_mask ( uint32_t value) { return value & ((16)-1); } __attribute__ ((unused)) static inline uint32_t lwan_pubsub_msg_ref_ring_size ( const struct lwan_pubsub_msg_ref_ring *rb) { return rb-> write - rb->read; } __attribute__((unused)) static inline _Bool lwan_pubsub_msg_ref_ring_full( const struct lwan_pubsub_msg_ref_ring *rb) { return lwan_pubsub_msg_ref_ring_size(rb) == (16); } __attribute__ ((unused)) static inline _Bool lwan_pubsub_msg_ref_ring_empty ( const struct lwan_pubsub_msg_ref_ring *rb) { return rb-> write == rb->read; } __attribute__((unused)) static inline void lwan_pubsub_msg_ref_ring_init( struct lwan_pubsub_msg_ref_ring *rb) { rb->write = rb->read = 0; } __attribute__((unused )) static inline void lwan_pubsub_msg_ref_ring_put( struct lwan_pubsub_msg_ref_ring *rb, const struct lwan_pubsub_msg * *e) { ((void) sizeof ((! lwan_pubsub_msg_ref_ring_full(rb)) ? 1 : 0), __extension__ ({ if (!lwan_pubsub_msg_ref_ring_full(rb)) ; else __assert_fail ("!lwan_pubsub_msg_ref_ring_full(rb)", "/home/buildbot/lwan-worker/clang-analyze/build/src/lib/lwan-pubsub.c" , 40, __extension__ __PRETTY_FUNCTION__); })); memcpy(&rb ->array[lwan_pubsub_msg_ref_ring_mask(rb->write++)], e, sizeof(*e)); } __attribute__((unused)) static inline _Bool lwan_pubsub_msg_ref_ring_try_put ( struct lwan_pubsub_msg_ref_ring *rb, const struct lwan_pubsub_msg * *e) { if (lwan_pubsub_msg_ref_ring_full(rb)) return 0; memcpy (&rb->array[lwan_pubsub_msg_ref_ring_mask(rb->write ++)], e, sizeof(*e)); return 1; } __attribute__((unused)) static inline struct lwan_pubsub_msg * lwan_pubsub_msg_ref_ring_get ( struct lwan_pubsub_msg_ref_ring *rb) { ((void) sizeof ((!lwan_pubsub_msg_ref_ring_empty (rb)) ? 1 : 0), __extension__ ({ if (!lwan_pubsub_msg_ref_ring_empty (rb)) ; else __assert_fail ("!lwan_pubsub_msg_ref_ring_empty(rb)" , "/home/buildbot/lwan-worker/clang-analyze/build/src/lib/lwan-pubsub.c" , 40, __extension__ __PRETTY_FUNCTION__); })); return rb-> array[lwan_pubsub_msg_ref_ring_mask(rb->read++)]; } __attribute__ ((unused)) static inline struct lwan_pubsub_msg * *lwan_pubsub_msg_ref_ring_get_ptr ( struct lwan_pubsub_msg_ref_ring *rb) { ((void) sizeof ((!lwan_pubsub_msg_ref_ring_empty (rb)) ? 1 : 0), __extension__ ({ if (!lwan_pubsub_msg_ref_ring_empty (rb)) ; else __assert_fail ("!lwan_pubsub_msg_ref_ring_empty(rb)" , "/home/buildbot/lwan-worker/clang-analyze/build/src/lib/lwan-pubsub.c" , 40, __extension__ __PRETTY_FUNCTION__); })); return &rb ->array[lwan_pubsub_msg_ref_ring_mask(rb->read++)]; } __attribute__ ((unused)) static inline struct lwan_pubsub_msg * *lwan_pubsub_msg_ref_ring_get_ptr_or_null (struct lwan_pubsub_msg_ref_ring *rb) { return lwan_pubsub_msg_ref_ring_empty (rb) ? ((void*)0) : &rb->array[lwan_pubsub_msg_ref_ring_mask (rb->read++)]; } | |||
41 | ||||
42 | struct lwan_pubsub_msg_ref { | |||
43 | struct list_node ref; | |||
44 | struct lwan_pubsub_msg_ref_ring ring; | |||
45 | }; | |||
46 | ||||
47 | struct lwan_pubsub_subscriber { | |||
48 | struct list_node subscriber; | |||
49 | ||||
50 | pthread_mutex_t lock; | |||
51 | struct list_head msg_refs; | |||
52 | }; | |||
53 | ||||
54 | static void lwan_pubsub_queue_init(struct lwan_pubsub_subscriber *sub) | |||
55 | { | |||
56 | list_head_init(&sub->msg_refs); | |||
57 | } | |||
58 | ||||
59 | static bool_Bool lwan_pubsub_queue_put(struct lwan_pubsub_subscriber *sub, | |||
60 | const struct lwan_pubsub_msg *msg) | |||
61 | { | |||
62 | struct lwan_pubsub_msg_ref *ref; | |||
63 | ||||
64 | ref = list_tail(&sub->msg_refs, struct lwan_pubsub_msg_ref, ref)((struct lwan_pubsub_msg_ref *)list_tail_((&sub->msg_refs ), (__builtin_offsetof(struct lwan_pubsub_msg_ref, ref) + ((typeof (((struct lwan_pubsub_msg_ref *)0)->ref) *)0 != (struct list_node *)0)))); | |||
65 | if (ref) { | |||
66 | /* Try putting the message in the last ringbuffer in this queue: if it's | |||
67 | * full, will need to allocate a new ring buffer, even if others might | |||
68 | * have space in them: the FIFO order must be preserved, and short of | |||
69 | * compacting the queue at this point -- which will eventually happen | |||
70 | * as it is consumed -- this is the only option. */ | |||
71 | if (lwan_pubsub_msg_ref_ring_try_put(&ref->ring, &msg)) | |||
72 | return true1; | |||
73 | } | |||
74 | ||||
75 | ref = malloc(sizeof(*ref)); | |||
76 | if (!ref) | |||
77 | return false0; | |||
78 | ||||
79 | lwan_pubsub_msg_ref_ring_init(&ref->ring); | |||
80 | lwan_pubsub_msg_ref_ring_put(&ref->ring, &msg); | |||
81 | list_add_tail(&sub->msg_refs, &ref->ref); | |||
82 | ||||
83 | return true1; | |||
84 | } | |||
85 | ||||
86 | static struct lwan_pubsub_msg * | |||
87 | lwan_pubsub_queue_get(struct lwan_pubsub_subscriber *sub) | |||
88 | { | |||
89 | struct lwan_pubsub_msg_ref *ref, *next; | |||
90 | ||||
91 | list_for_each_safe (&sub->msg_refs, ref, next, ref)for (ref = list_node_to_off_(list_check((&sub->msg_refs ), __func__)->n.next, ((__builtin_offsetof(typeof(*ref), ref ) + ((typeof(ref->ref) *)0 != (struct list_node *)0)))), next = list_node_to_off_(list_node_from_off_(ref, ((__builtin_offsetof (typeof(*ref), ref) + ((typeof(ref->ref) *)0 != (struct list_node *)0))))->next, ((__builtin_offsetof(typeof(*ref), ref) + ( (typeof(ref->ref) *)0 != (struct list_node *)0)))); list_node_from_off_ (ref, ((__builtin_offsetof(typeof(*ref), ref) + ((typeof(ref-> ref) *)0 != (struct list_node *)0)))) != &(&sub->msg_refs )->n; ref = next, next = list_node_to_off_(list_node_from_off_ (ref, ((__builtin_offsetof(typeof(*ref), ref) + ((typeof(ref-> ref) *)0 != (struct list_node *)0))))->next, ((__builtin_offsetof (typeof(*ref), ref) + ((typeof(ref->ref) *)0 != (struct list_node *)0))))) { | |||
92 | struct lwan_pubsub_msg *msg; | |||
93 | ||||
94 | if (lwan_pubsub_msg_ref_ring_empty(&ref->ring)) { | |||
95 | list_del(&ref->ref); | |||
96 | free(ref); | |||
97 | continue; | |||
98 | } | |||
99 | ||||
100 | msg = lwan_pubsub_msg_ref_ring_get(&ref->ring); | |||
101 | ||||
102 | if (ref->ref.next != ref->ref.prev) { | |||
103 | /* If this segment isn't the last one, try pulling in just one | |||
104 | * element from the next segment, as there's space in the | |||
105 | * current segment now. | |||
106 | * | |||
107 | * This might lead to an empty ring buffer segment in the middle | |||
108 | * of the linked list. This is by design, to introduce some | |||
109 | * hysteresis and avoid the pathological case where malloc churn | |||
110 | * will happen when subscribers consume at the same rate as | |||
111 | * publishers are able to publish. | |||
112 | * | |||
113 | * The condition above will take care of these empty segments | |||
114 | * once they're dealt with, eventually compacting the queue | |||
115 | * completely (and ultimately reducing it to an empty list | |||
116 | * without any ring buffers). | |||
117 | */ | |||
118 | struct lwan_pubsub_msg_ref *next_ring; | |||
119 | ||||
120 | next_ring = container_of(ref->ref.next, struct lwan_pubsub_msg_ref, ref)((struct lwan_pubsub_msg_ref *) ((char *)(ref->ref.next) - __builtin_offsetof(struct lwan_pubsub_msg_ref, ref)) + ((typeof (*(ref->ref.next)) *)0 != (typeof(((struct lwan_pubsub_msg_ref *)0)->ref) *)0)); | |||
121 | if (!lwan_pubsub_msg_ref_ring_empty(&next_ring->ring)) { | |||
122 | const struct lwan_pubsub_msg *next_msg; | |||
123 | ||||
124 | next_msg = lwan_pubsub_msg_ref_ring_get(&next_ring->ring); | |||
125 | lwan_pubsub_msg_ref_ring_put(&ref->ring, &next_msg); | |||
126 | } | |||
127 | } | |||
128 | ||||
129 | return msg; | |||
130 | } | |||
131 | ||||
132 | return NULL((void*)0); | |||
133 | } | |||
134 | ||||
135 | static void lwan_pubsub_unsubscribe_internal(struct lwan_pubsub_topic *topic, | |||
136 | struct lwan_pubsub_subscriber *sub, | |||
137 | bool_Bool take_topic_lock); | |||
138 | ||||
139 | struct lwan_pubsub_topic *lwan_pubsub_new_topic(void) | |||
140 | { | |||
141 | struct lwan_pubsub_topic *topic = calloc(1, sizeof(*topic)); | |||
142 | ||||
143 | if (!topic) | |||
144 | return NULL((void*)0); | |||
145 | ||||
146 | list_head_init(&topic->subscribers); | |||
147 | pthread_mutex_init(&topic->lock, NULL((void*)0)); | |||
148 | ||||
149 | return topic; | |||
150 | } | |||
151 | ||||
152 | void lwan_pubsub_free_topic(struct lwan_pubsub_topic *topic) | |||
153 | { | |||
154 | struct lwan_pubsub_subscriber *iter, *next; | |||
155 | ||||
156 | pthread_mutex_lock(&topic->lock); | |||
157 | list_for_each_safe (&topic->subscribers, iter, next, subscriber)for (iter = list_node_to_off_(list_check((&topic->subscribers ), __func__)->n.next, ((__builtin_offsetof(typeof(*iter), subscriber ) + ((typeof(iter->subscriber) *)0 != (struct list_node *) 0)))), next = list_node_to_off_(list_node_from_off_(iter, ((__builtin_offsetof (typeof(*iter), subscriber) + ((typeof(iter->subscriber) * )0 != (struct list_node *)0))))->next, ((__builtin_offsetof (typeof(*iter), subscriber) + ((typeof(iter->subscriber) * )0 != (struct list_node *)0)))); list_node_from_off_(iter, (( __builtin_offsetof(typeof(*iter), subscriber) + ((typeof(iter ->subscriber) *)0 != (struct list_node *)0)))) != &(& topic->subscribers)->n; iter = next, next = list_node_to_off_ (list_node_from_off_(iter, ((__builtin_offsetof(typeof(*iter) , subscriber) + ((typeof(iter->subscriber) *)0 != (struct list_node *)0))))->next, ((__builtin_offsetof(typeof(*iter), subscriber ) + ((typeof(iter->subscriber) *)0 != (struct list_node *) 0))))) | |||
158 | lwan_pubsub_unsubscribe_internal(topic, iter, false0); | |||
159 | pthread_mutex_unlock(&topic->lock); | |||
160 | ||||
161 | pthread_mutex_destroy(&topic->lock); | |||
162 | ||||
163 | free(topic); | |||
164 | } | |||
165 | ||||
166 | void lwan_pubsub_msg_done(struct lwan_pubsub_msg *msg) | |||
167 | { | |||
168 | if (!ATOMIC_DEC(msg->refcount)(__sync_sub_and_fetch(((&(msg->refcount))), ((1))))) { | |||
169 | free(msg->value.value); | |||
170 | free(msg); | |||
171 | } | |||
172 | } | |||
173 | ||||
174 | static bool_Bool lwan_pubsub_publish_value(struct lwan_pubsub_topic *topic, | |||
175 | const struct lwan_value value) | |||
176 | { | |||
177 | struct lwan_pubsub_msg *msg = malloc(sizeof(*msg)); | |||
178 | struct lwan_pubsub_subscriber *sub; | |||
179 | ||||
180 | if (!msg) | |||
181 | return false0; | |||
182 | ||||
183 | /* Initialize refcount to 1, so we can drop one ref after publishing to | |||
184 | * all subscribers. If it drops to 0, it means we didn't publish the | |||
185 | * message and we can free it. */ | |||
186 | msg->refcount = 1; | |||
187 | msg->value = value; | |||
188 | ||||
189 | pthread_mutex_lock(&topic->lock); | |||
190 | list_for_each (&topic->subscribers, sub, subscriber)for (sub = list_node_to_off_(list_check((&topic->subscribers ), __func__)->n.next, ((__builtin_offsetof(typeof(*sub), subscriber ) + ((typeof(sub->subscriber) *)0 != (struct list_node *)0 )))); list_node_from_off_((void *)sub, ((__builtin_offsetof(typeof (*sub), subscriber) + ((typeof(sub->subscriber) *)0 != (struct list_node *)0)))) != &(&topic->subscribers)->n ; sub = list_node_to_off_(list_node_from_off_((void *)sub, (( __builtin_offsetof(typeof(*sub), subscriber) + ((typeof(sub-> subscriber) *)0 != (struct list_node *)0))))->next, ((__builtin_offsetof (typeof(*sub), subscriber) + ((typeof(sub->subscriber) *)0 != (struct list_node *)0))))) { | |||
191 | ATOMIC_INC(msg->refcount)(__sync_add_and_fetch(((&(msg->refcount))), ((1)))); | |||
192 | ||||
193 | pthread_mutex_lock(&sub->lock); | |||
194 | if (!lwan_pubsub_queue_put(sub, msg)) { | |||
195 | lwan_status_warning("Couldn't enqueue message, dropping")lwan_status_warning_debug("/home/buildbot/lwan-worker/clang-analyze/build/src/lib/lwan-pubsub.c" , 195, __FUNCTION__, "Couldn't enqueue message, dropping"); | |||
196 | ATOMIC_DEC(msg->refcount)(__sync_sub_and_fetch(((&(msg->refcount))), ((1)))); | |||
197 | } | |||
198 | pthread_mutex_unlock(&sub->lock); | |||
199 | } | |||
200 | pthread_mutex_unlock(&topic->lock); | |||
201 | ||||
202 | lwan_pubsub_msg_done(msg); | |||
203 | ||||
204 | return true1; | |||
205 | } | |||
206 | ||||
207 | static void *my_memdup(const void *src, size_t len) | |||
208 | { | |||
209 | void *dup = malloc(len); | |||
210 | ||||
211 | return dup ? memcpy(dup, src, len) : NULL((void*)0); | |||
212 | } | |||
213 | ||||
214 | bool_Bool lwan_pubsub_publish(struct lwan_pubsub_topic *topic, | |||
215 | const void *contents, | |||
216 | size_t len) | |||
217 | { | |||
218 | const struct lwan_value value = { .value = my_memdup(contents, len), .len = len }; | |||
219 | ||||
220 | if (!value.value) | |||
221 | return false0; | |||
222 | ||||
223 | return lwan_pubsub_publish_value(topic, value); | |||
224 | } | |||
225 | ||||
226 | bool_Bool lwan_pubsub_publishf(struct lwan_pubsub_topic *topic, | |||
227 | const char *format, | |||
228 | ...) | |||
229 | { | |||
230 | char *msg; | |||
231 | int len; | |||
232 | va_list ap; | |||
233 | ||||
234 | va_start(ap, format)__builtin_va_start(ap, format); | |||
235 | len = vasprintf(&msg, format, ap); | |||
236 | va_end(ap)__builtin_va_end(ap); | |||
237 | ||||
238 | if (len < 0) | |||
| ||||
239 | return false0; | |||
240 | ||||
241 | const struct lwan_value value = { .value = msg, .len = (size_t)len }; | |||
242 | return lwan_pubsub_publish_value(topic, value); | |||
243 | } | |||
244 | ||||
245 | struct lwan_pubsub_subscriber * | |||
246 | lwan_pubsub_subscribe(struct lwan_pubsub_topic *topic) | |||
247 | { | |||
248 | struct lwan_pubsub_subscriber *sub = calloc(1, sizeof(*sub)); | |||
249 | ||||
250 | if (!sub) | |||
251 | return NULL((void*)0); | |||
252 | ||||
253 | pthread_mutex_init(&sub->lock, NULL((void*)0)); | |||
254 | lwan_pubsub_queue_init(sub); | |||
255 | ||||
256 | pthread_mutex_lock(&topic->lock); | |||
257 | list_add(&topic->subscribers, &sub->subscriber); | |||
258 | pthread_mutex_unlock(&topic->lock); | |||
259 | ||||
260 | return sub; | |||
261 | } | |||
262 | ||||
263 | struct lwan_pubsub_msg *lwan_pubsub_consume(struct lwan_pubsub_subscriber *sub) | |||
264 | { | |||
265 | struct lwan_pubsub_msg *msg; | |||
266 | ||||
267 | pthread_mutex_lock(&sub->lock); | |||
268 | msg = lwan_pubsub_queue_get(sub); | |||
269 | pthread_mutex_unlock(&sub->lock); | |||
270 | ||||
271 | return msg; | |||
272 | } | |||
273 | ||||
274 | static void lwan_pubsub_unsubscribe_internal(struct lwan_pubsub_topic *topic, | |||
275 | struct lwan_pubsub_subscriber *sub, | |||
276 | bool_Bool take_topic_lock) | |||
277 | { | |||
278 | struct lwan_pubsub_msg *iter; | |||
279 | ||||
280 | if (take_topic_lock) | |||
281 | pthread_mutex_lock(&topic->lock); | |||
282 | list_del(&sub->subscriber); | |||
283 | if (take_topic_lock) | |||
284 | pthread_mutex_unlock(&topic->lock); | |||
285 | ||||
286 | pthread_mutex_lock(&sub->lock); | |||
287 | while ((iter = lwan_pubsub_queue_get(sub))) | |||
288 | lwan_pubsub_msg_done(iter); | |||
289 | pthread_mutex_unlock(&sub->lock); | |||
290 | ||||
291 | pthread_mutex_destroy(&sub->lock); | |||
292 | free(sub); | |||
293 | } | |||
294 | ||||
295 | void lwan_pubsub_unsubscribe(struct lwan_pubsub_topic *topic, | |||
296 | struct lwan_pubsub_subscriber *sub) | |||
297 | { | |||
298 | return (void)lwan_pubsub_unsubscribe_internal(topic, sub, true1); | |||
299 | } | |||
300 | ||||
301 | const struct lwan_value *lwan_pubsub_msg_value(const struct lwan_pubsub_msg *msg) | |||
302 | { | |||
303 | return &msg->value; | |||
304 | } |
1 | /* | |||
2 | * list - double linked list routines | |||
3 | * Author: Rusty Russell <rusty@rustcorp.com.au> | |||
4 | * | |||
5 | * The list header contains routines for manipulating double linked lists. | |||
6 | * It defines two types: struct list_head used for anchoring lists, and | |||
7 | * struct list_node which is usually embedded in the structure which is placed | |||
8 | * in the list. | |||
9 | * | |||
10 | * Permission is hereby granted, free of charge, to any person obtaining a | |||
11 | * copy of this software and associated documentation files (the | |||
12 | * "Software"), to deal in the Software without restriction, including | |||
13 | * without limitation the rights to use, copy, modify, merge, publish, | |||
14 | * distribute, sublicense, and/or sell copies of the Software, and to permit | |||
15 | * persons to whom the Software is furnished to do so, subject to the | |||
16 | * following conditions: | |||
17 | * | |||
18 | * The above copyright notice and this permission notice shall be included | |||
19 | * in all copies or substantial portions of the Software. | |||
20 | * | |||
21 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS | |||
22 | * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF | |||
23 | * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. | |||
24 | * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY | |||
25 | * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT | |||
26 | * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR | |||
27 | * THE USE OR OTHER DEALINGS IN THE SOFTWARE. | |||
28 | */ | |||
29 | ||||
30 | #pragma once | |||
31 | #include <stdbool.h> | |||
32 | #include <stddef.h> | |||
33 | #include <assert.h> | |||
34 | ||||
35 | /** | |||
36 | * check_type - issue a warning or build failure if type is not correct. | |||
37 | * @expr: the expression whose type we should check (not evaluated). | |||
38 | * @type: the exact type we expect the expression to be. | |||
39 | * | |||
40 | * This macro is usually used within other macros to try to ensure that a macro | |||
41 | * argument is of the expected type. No type promotion of the expression is | |||
42 | * done: an unsigned int is not the same as an int! | |||
43 | * | |||
44 | * check_type() always evaluates to 0. | |||
45 | * | |||
46 | * If your compiler does not support typeof, then the best we can do is fail | |||
47 | * to compile if the sizes of the types are unequal (a less complete check). | |||
48 | * | |||
49 | * Example: | |||
50 | * // They should always pass a 64-bit value to _set_some_value! | |||
51 | * #define set_some_value(expr) \ | |||
52 | * _set_some_value((check_type((expr), uint64_t), (expr))) | |||
53 | */ | |||
54 | #define check_type(expr, type)((typeof(expr) *)0 != (type *)0) \ | |||
55 | ((typeof(expr) *)0 != (type *)0) | |||
56 | ||||
57 | /** | |||
58 | * check_types_match - issue a warning or build failure if types are not same. | |||
59 | * @expr1: the first expression (not evaluated). | |||
60 | * @expr2: the second expression (not evaluated). | |||
61 | * | |||
62 | * This macro is usually used within other macros to try to ensure that | |||
63 | * arguments are of identical types. No type promotion of the expressions is | |||
64 | * done: an unsigned int is not the same as an int! | |||
65 | * | |||
66 | * check_types_match() always evaluates to 0. | |||
67 | * | |||
68 | * If your compiler does not support typeof, then the best we can do is fail | |||
69 | * to compile if the sizes of the types are unequal (a less complete check). | |||
70 | * | |||
71 | * Example: | |||
72 | * // Do subtraction to get to enclosing type, but make sure that | |||
73 | * // pointer is of correct type for that member. | |||
74 | * #define container_of(mbr_ptr, encl_type, mbr) \ | |||
75 | * (check_types_match((mbr_ptr), &((encl_type *)0)->mbr), \ | |||
76 | * ((encl_type *) \ | |||
77 | * ((char *)(mbr_ptr) - offsetof(enclosing_type, mbr)))) | |||
78 | */ | |||
79 | ||||
80 | #define check_types_match(expr1, expr2)((typeof(expr1) *)0 != (typeof(expr2) *)0) \ | |||
81 | ((typeof(expr1) *)0 != (typeof(expr2) *)0) | |||
82 | ||||
83 | /** | |||
84 | * container_of - get pointer to enclosing structure | |||
85 | * @member_ptr: pointer to the structure member | |||
86 | * @containing_type: the type this member is within | |||
87 | * @member: the name of this member within the structure. | |||
88 | * | |||
89 | * Given a pointer to a member of a structure, this macro does pointer | |||
90 | * subtraction to return the pointer to the enclosing type. | |||
91 | * | |||
92 | * Example: | |||
93 | * struct foo { | |||
94 | * int fielda, fieldb; | |||
95 | * // ... | |||
96 | * }; | |||
97 | * struct info { | |||
98 | * int some_other_field; | |||
99 | * struct foo my_foo; | |||
100 | * }; | |||
101 | * | |||
102 | * static struct info *foo_to_info(struct foo *foo) | |||
103 | * { | |||
104 | * return container_of(foo, struct info, my_foo); | |||
105 | * } | |||
106 | */ | |||
107 | #define container_of(member_ptr, containing_type, member)((containing_type *) ((char *)(member_ptr) - __builtin_offsetof (containing_type, member)) + ((typeof(*(member_ptr)) *)0 != ( typeof(((containing_type *)0)->member) *)0)) \ | |||
108 | ((containing_type *) \ | |||
109 | ((char *)(member_ptr) \ | |||
110 | - container_off(containing_type, member)__builtin_offsetof(containing_type, member)) \ | |||
111 | + check_types_match(*(member_ptr), ((containing_type *)0)->member)((typeof(*(member_ptr)) *)0 != (typeof(((containing_type *)0) ->member) *)0)) | |||
112 | ||||
113 | /** | |||
114 | * container_of_var - get pointer to enclosing structure using a variable | |||
115 | * @member_ptr: pointer to the structure member | |||
116 | * @container_var: a pointer of same type as this member's container | |||
117 | * @member: the name of this member within the structure. | |||
118 | * | |||
119 | * Given a pointer to a member of a structure, this macro does pointer | |||
120 | * subtraction to return the pointer to the enclosing type. | |||
121 | * | |||
122 | * Example: | |||
123 | * static struct info *foo_to_i(struct foo *foo) | |||
124 | * { | |||
125 | * struct info *i = container_of_var(foo, i, my_foo); | |||
126 | * return i; | |||
127 | * } | |||
128 | */ | |||
129 | #if HAVE_TYPEOF | |||
130 | #define container_of_var(member_ptr, container_var, member)((void *)((char *)(member_ptr) - __builtin_offsetof(typeof(*container_var ), member))) \ | |||
131 | container_of(member_ptr, typeof(*container_var), member)((typeof(*container_var) *) ((char *)(member_ptr) - __builtin_offsetof (typeof(*container_var), member)) + ((typeof(*(member_ptr)) * )0 != (typeof(((typeof(*container_var) *)0)->member) *)0)) | |||
132 | #else | |||
133 | #define container_of_var(member_ptr, container_var, member)((void *)((char *)(member_ptr) - __builtin_offsetof(typeof(*container_var ), member))) \ | |||
134 | ((void *)((char *)(member_ptr) - \ | |||
135 | container_off_var(container_var, member)__builtin_offsetof(typeof(*container_var), member))) | |||
136 | #endif | |||
137 | ||||
138 | /** | |||
139 | * container_off - get offset to enclosing structure | |||
140 | * @containing_type: the type this member is within | |||
141 | * @member: the name of this member within the structure. | |||
142 | * | |||
143 | * Given a pointer to a member of a structure, this macro does | |||
144 | * typechecking and figures out the offset to the enclosing type. | |||
145 | * | |||
146 | * Example: | |||
147 | * struct foo { | |||
148 | * int fielda, fieldb; | |||
149 | * // ... | |||
150 | * }; | |||
151 | * struct info { | |||
152 | * int some_other_field; | |||
153 | * struct foo my_foo; | |||
154 | * }; | |||
155 | * | |||
156 | * static struct info *foo_to_info(struct foo *foo) | |||
157 | * { | |||
158 | * size_t off = container_off(struct info, my_foo); | |||
159 | * return (void *)((char *)foo - off); | |||
160 | * } | |||
161 | */ | |||
162 | #define container_off(containing_type, member)__builtin_offsetof(containing_type, member) \ | |||
163 | offsetof(containing_type, member)__builtin_offsetof(containing_type, member) | |||
164 | ||||
165 | /** | |||
166 | * container_off_var - get offset of a field in enclosing structure | |||
167 | * @container_var: a pointer to a container structure | |||
168 | * @member: the name of a member within the structure. | |||
169 | * | |||
170 | * Given (any) pointer to a structure and a its member name, this | |||
171 | * macro does pointer subtraction to return offset of member in a | |||
172 | * structure memory layout. | |||
173 | * | |||
174 | */ | |||
175 | #define container_off_var(var, member)__builtin_offsetof(typeof(*var), member) \ | |||
176 | container_off(typeof(*var), member)__builtin_offsetof(typeof(*var), member) | |||
177 | ||||
178 | /** | |||
179 | * struct list_node - an entry in a doubly-linked list | |||
180 | * @next: next entry (self if empty) | |||
181 | * @prev: previous entry (self if empty) | |||
182 | * | |||
183 | * This is used as an entry in a linked list. | |||
184 | * Example: | |||
185 | * struct child { | |||
186 | * const char *name; | |||
187 | * // Linked list of all us children. | |||
188 | * struct list_node list; | |||
189 | * }; | |||
190 | */ | |||
191 | struct list_node | |||
192 | { | |||
193 | struct list_node *next, *prev; | |||
194 | }; | |||
195 | ||||
196 | /** | |||
197 | * struct list_head - the head of a doubly-linked list | |||
198 | * @h: the list_head (containing next and prev pointers) | |||
199 | * | |||
200 | * This is used as the head of a linked list. | |||
201 | * Example: | |||
202 | * struct parent { | |||
203 | * const char *name; | |||
204 | * struct list_head children; | |||
205 | * unsigned int num_children; | |||
206 | * }; | |||
207 | */ | |||
208 | struct list_head | |||
209 | { | |||
210 | struct list_node n; | |||
211 | }; | |||
212 | ||||
213 | /** | |||
214 | * list_check - check head of a list for consistency | |||
215 | * @h: the list_head | |||
216 | * @abortstr: the location to print on aborting, or NULL. | |||
217 | * | |||
218 | * Because list_nodes have redundant information, consistency checking between | |||
219 | * the back and forward links can be done. This is useful as a debugging check. | |||
220 | * If @abortstr is non-NULL, that will be printed in a diagnostic if the list | |||
221 | * is inconsistent, and the function will abort. | |||
222 | * | |||
223 | * Returns the list head if the list is consistent, NULL if not (it | |||
224 | * can never return NULL if @abortstr is set). | |||
225 | * | |||
226 | * See also: list_check_node() | |||
227 | * | |||
228 | * Example: | |||
229 | * static void dump_parent(struct parent *p) | |||
230 | * { | |||
231 | * struct child *c; | |||
232 | * | |||
233 | * printf("%s (%u children):\n", p->name, p->num_children); | |||
234 | * list_check(&p->children, "bad child list"); | |||
235 | * list_for_each(&p->children, c, list) | |||
236 | * printf(" -> %s\n", c->name); | |||
237 | * } | |||
238 | */ | |||
239 | struct list_head *list_check(const struct list_head *h, const char *abortstr); | |||
240 | ||||
241 | /** | |||
242 | * list_check_node - check node of a list for consistency | |||
243 | * @n: the list_node | |||
244 | * @abortstr: the location to print on aborting, or NULL. | |||
245 | * | |||
246 | * Check consistency of the list node is in (it must be in one). | |||
247 | * | |||
248 | * See also: list_check() | |||
249 | * | |||
250 | * Example: | |||
251 | * static void dump_child(const struct child *c) | |||
252 | * { | |||
253 | * list_check_node(&c->list, "bad child list"); | |||
254 | * printf("%s\n", c->name); | |||
255 | * } | |||
256 | */ | |||
257 | struct list_node *list_check_node(const struct list_node *n, | |||
258 | const char *abortstr); | |||
259 | ||||
260 | #ifndef NDEBUG | |||
261 | void list_poison_node(struct list_node *node); | |||
262 | ||||
263 | #define list_poison(n)list_poison_node(n) list_poison_node(n) | |||
264 | #define list_debug(h)list_check((h), __func__) list_check((h), __func__) | |||
265 | #define list_debug_node(n)list_check_node((n), __func__) list_check_node((n), __func__) | |||
266 | #else | |||
267 | #define list_poison(n)list_poison_node(n) | |||
268 | #define list_debug(h)list_check((h), __func__) (h) | |||
269 | #define list_debug_node(n)list_check_node((n), __func__) (n) | |||
270 | #endif | |||
271 | ||||
272 | /** | |||
273 | * list_head_init - initialize a list_head | |||
274 | * @h: the list_head to set to the empty list | |||
275 | * | |||
276 | * Example: | |||
277 | * ... | |||
278 | * struct parent *parent = malloc(sizeof(*parent)); | |||
279 | * | |||
280 | * list_head_init(&parent->children); | |||
281 | * parent->num_children = 0; | |||
282 | */ | |||
283 | static inline void list_head_init(struct list_head *h) | |||
284 | { | |||
285 | h->n.next = h->n.prev = &h->n; | |||
286 | } | |||
287 | ||||
288 | /** | |||
289 | * list_add - add an entry at the start of a linked list. | |||
290 | * @h: the list_head to add the node to | |||
291 | * @n: the list_node to add to the list. | |||
292 | * | |||
293 | * The list_node does not need to be initialized; it will be overwritten. | |||
294 | * Example: | |||
295 | * struct child *child = malloc(sizeof(*child)); | |||
296 | * | |||
297 | * child->name = "marvin"; | |||
298 | * list_add(&parent->children, &child->list); | |||
299 | * parent->num_children++; | |||
300 | */ | |||
301 | static inline void list_add(struct list_head *h, struct list_node *n) | |||
302 | { | |||
303 | n->next = h->n.next; | |||
304 | n->prev = &h->n; | |||
305 | h->n.next->prev = n; | |||
306 | h->n.next = n; | |||
307 | (void)list_debug(h)list_check((h), __func__); | |||
308 | } | |||
309 | ||||
310 | /** | |||
311 | * list_add_tail - add an entry at the end of a linked list. | |||
312 | * @h: the list_head to add the node to | |||
313 | * @n: the list_node to add to the list. | |||
314 | * | |||
315 | * The list_node does not need to be initialized; it will be overwritten. | |||
316 | * Example: | |||
317 | * list_add_tail(&parent->children, &child->list); | |||
318 | * parent->num_children++; | |||
319 | */ | |||
320 | static inline void list_add_tail(struct list_head *h, struct list_node *n) | |||
321 | { | |||
322 | n->next = &h->n; | |||
323 | n->prev = h->n.prev; | |||
324 | h->n.prev->next = n; | |||
| ||||
325 | h->n.prev = n; | |||
326 | (void)list_debug(h)list_check((h), __func__); | |||
327 | } | |||
328 | ||||
329 | /** | |||
330 | * list_empty - is a list empty? | |||
331 | * @h: the list_head | |||
332 | * | |||
333 | * If the list is empty, returns true. | |||
334 | * | |||
335 | * Example: | |||
336 | * assert(list_empty(&parent->children) == (parent->num_children == 0)); | |||
337 | */ | |||
338 | static inline bool_Bool list_empty(const struct list_head *h) | |||
339 | { | |||
340 | (void)list_debug(h)list_check((h), __func__); | |||
341 | return h->n.next == &h->n; | |||
342 | } | |||
343 | ||||
344 | /** | |||
345 | * list_del - delete an entry from an (unknown) linked list. | |||
346 | * @n: the list_node to delete from the list. | |||
347 | * | |||
348 | * Note that this leaves @n in an undefined state; it can be added to | |||
349 | * another list, but not deleted again. | |||
350 | * | |||
351 | * See also: | |||
352 | * list_del_from() | |||
353 | * | |||
354 | * Example: | |||
355 | * list_del(&child->list); | |||
356 | * parent->num_children--; | |||
357 | */ | |||
358 | static inline void list_del(struct list_node *n) | |||
359 | { | |||
360 | (void)list_debug_node(n)list_check_node((n), __func__); | |||
361 | n->next->prev = n->prev; | |||
362 | n->prev->next = n->next; | |||
363 | ||||
364 | /* Catch use-after-del. */ | |||
365 | list_poison(n)list_poison_node(n); | |||
366 | } | |||
367 | ||||
368 | /** | |||
369 | * list_del_from - delete an entry from a known linked list. | |||
370 | * @h: the list_head the node is in. | |||
371 | * @n: the list_node to delete from the list. | |||
372 | * | |||
373 | * This explicitly indicates which list a node is expected to be in, | |||
374 | * which is better documentation and can catch more bugs. | |||
375 | * | |||
376 | * See also: list_del() | |||
377 | * | |||
378 | * Example: | |||
379 | * list_del_from(&parent->children, &child->list); | |||
380 | * parent->num_children--; | |||
381 | */ | |||
382 | static inline void list_del_from(struct list_head *h, struct list_node *n) | |||
383 | { | |||
384 | #ifndef NDEBUG | |||
385 | { | |||
386 | /* Thorough check: make sure it was in list! */ | |||
387 | struct list_node *i; | |||
388 | for (i = h->n.next; i != n; i = i->next) | |||
389 | assert(i != &h->n)((void) sizeof ((i != &h->n) ? 1 : 0), __extension__ ( { if (i != &h->n) ; else __assert_fail ("i != &h->n" , "/home/buildbot/lwan-worker/clang-analyze/build/src/lib/list.h" , 389, __extension__ __PRETTY_FUNCTION__); })); | |||
390 | } | |||
391 | #else | |||
392 | (void)h; | |||
393 | #endif /* NDEBUG */ | |||
394 | ||||
395 | /* Quick test that catches a surprising number of bugs. */ | |||
396 | assert(!list_empty(h))((void) sizeof ((!list_empty(h)) ? 1 : 0), __extension__ ({ if (!list_empty(h)) ; else __assert_fail ("!list_empty(h)", "/home/buildbot/lwan-worker/clang-analyze/build/src/lib/list.h" , 396, __extension__ __PRETTY_FUNCTION__); })); | |||
397 | list_del(n); | |||
398 | } | |||
399 | ||||
400 | /** | |||
401 | * list_entry - convert a list_node back into the structure containing it. | |||
402 | * @n: the list_node | |||
403 | * @type: the type of the entry | |||
404 | * @member: the list_node member of the type | |||
405 | * | |||
406 | * Example: | |||
407 | * // First list entry is children.next; convert back to child. | |||
408 | * child = list_entry(parent->children.n.next, struct child, list); | |||
409 | * | |||
410 | * See Also: | |||
411 | * list_top(), list_for_each() | |||
412 | */ | |||
413 | #define list_entry(n, type, member)((type *) ((char *)(n) - __builtin_offsetof(type, member)) + ( (typeof(*(n)) *)0 != (typeof(((type *)0)->member) *)0)) container_of(n, type, member)((type *) ((char *)(n) - __builtin_offsetof(type, member)) + ( (typeof(*(n)) *)0 != (typeof(((type *)0)->member) *)0)) | |||
414 | ||||
415 | /** | |||
416 | * list_top - get the first entry in a list | |||
417 | * @h: the list_head | |||
418 | * @type: the type of the entry | |||
419 | * @member: the list_node member of the type | |||
420 | * | |||
421 | * If the list is empty, returns NULL. | |||
422 | * | |||
423 | * Example: | |||
424 | * struct child *first; | |||
425 | * first = list_top(&parent->children, struct child, list); | |||
426 | * if (!first) | |||
427 | * printf("Empty list!\n"); | |||
428 | */ | |||
429 | #define list_top(h, type, member)((type *)list_top_((h), (__builtin_offsetof(type, member) + ( (typeof(((type *)0)->member) *)0 != (struct list_node *)0) ))) \ | |||
430 | ((type *)list_top_((h), list_off_(type, member)(__builtin_offsetof(type, member) + ((typeof(((type *)0)-> member) *)0 != (struct list_node *)0)))) | |||
431 | ||||
432 | static inline const void *list_top_(const struct list_head *h, size_t off) | |||
433 | { | |||
434 | if (list_empty(h)) | |||
435 | return NULL((void*)0); | |||
436 | return (const char *)h->n.next - off; | |||
437 | } | |||
438 | ||||
439 | /** | |||
440 | * list_pop - remove the first entry in a list | |||
441 | * @h: the list_head | |||
442 | * @type: the type of the entry | |||
443 | * @member: the list_node member of the type | |||
444 | * | |||
445 | * If the list is empty, returns NULL. | |||
446 | * | |||
447 | * Example: | |||
448 | * struct child *one; | |||
449 | * one = list_pop(&parent->children, struct child, list); | |||
450 | * if (!one) | |||
451 | * printf("Empty list!\n"); | |||
452 | */ | |||
453 | #define list_pop(h, type, member)((type *)list_pop_((h), (__builtin_offsetof(type, member) + ( (typeof(((type *)0)->member) *)0 != (struct list_node *)0) ))) \ | |||
454 | ((type *)list_pop_((h), list_off_(type, member)(__builtin_offsetof(type, member) + ((typeof(((type *)0)-> member) *)0 != (struct list_node *)0)))) | |||
455 | ||||
456 | static inline const void *list_pop_(const struct list_head *h, size_t off) | |||
457 | { | |||
458 | struct list_node *n; | |||
459 | ||||
460 | if (list_empty(h)) | |||
461 | return NULL((void*)0); | |||
462 | n = h->n.next; | |||
463 | list_del(n); | |||
464 | return (const char *)n - off; | |||
465 | } | |||
466 | ||||
467 | /** | |||
468 | * list_tail - get the last entry in a list | |||
469 | * @h: the list_head | |||
470 | * @type: the type of the entry | |||
471 | * @member: the list_node member of the type | |||
472 | * | |||
473 | * If the list is empty, returns NULL. | |||
474 | * | |||
475 | * Example: | |||
476 | * struct child *last; | |||
477 | * last = list_tail(&parent->children, struct child, list); | |||
478 | * if (!last) | |||
479 | * printf("Empty list!\n"); | |||
480 | */ | |||
481 | #define list_tail(h, type, member)((type *)list_tail_((h), (__builtin_offsetof(type, member) + ( (typeof(((type *)0)->member) *)0 != (struct list_node *)0) ))) \ | |||
482 | ((type *)list_tail_((h), list_off_(type, member)(__builtin_offsetof(type, member) + ((typeof(((type *)0)-> member) *)0 != (struct list_node *)0)))) | |||
483 | ||||
484 | static inline const void *list_tail_(const struct list_head *h, size_t off) | |||
485 | { | |||
486 | if (list_empty(h)) | |||
487 | return NULL((void*)0); | |||
488 | return (const char *)h->n.prev - off; | |||
489 | } | |||
490 | ||||
491 | /** | |||
492 | * list_for_each - iterate through a list. | |||
493 | * @h: the list_head (warning: evaluated multiple times!) | |||
494 | * @i: the structure containing the list_node | |||
495 | * @member: the list_node member of the structure | |||
496 | * | |||
497 | * This is a convenient wrapper to iterate @i over the entire list. It's | |||
498 | * a for loop, so you can break and continue as normal. | |||
499 | * | |||
500 | * Example: | |||
501 | * list_for_each(&parent->children, child, list) | |||
502 | * printf("Name: %s\n", child->name); | |||
503 | */ | |||
504 | #define list_for_each(h, i, member)for (i = list_node_to_off_(list_check((h), __func__)->n.next , ((__builtin_offsetof(typeof(*i), member) + ((typeof(i->member ) *)0 != (struct list_node *)0)))); list_node_from_off_((void *)i, ((__builtin_offsetof(typeof(*i), member) + ((typeof(i-> member) *)0 != (struct list_node *)0)))) != &(h)->n; i = list_node_to_off_(list_node_from_off_((void *)i, ((__builtin_offsetof (typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node *)0))))->next, ((__builtin_offsetof(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node *)0))))) \ | |||
505 | list_for_each_off(h, i, list_off_var_(i, member))for (i = list_node_to_off_(list_check((h), __func__)->n.next , ((__builtin_offsetof(typeof(*i), member) + ((typeof(i->member ) *)0 != (struct list_node *)0)))); list_node_from_off_((void *)i, ((__builtin_offsetof(typeof(*i), member) + ((typeof(i-> member) *)0 != (struct list_node *)0)))) != &(h)->n; i = list_node_to_off_(list_node_from_off_((void *)i, ((__builtin_offsetof (typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node *)0))))->next, ((__builtin_offsetof(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node *)0))))) | |||
506 | ||||
507 | /** | |||
508 | * list_for_each_rev - iterate through a list backwards. | |||
509 | * @h: the list_head | |||
510 | * @i: the structure containing the list_node | |||
511 | * @member: the list_node member of the structure | |||
512 | * | |||
513 | * This is a convenient wrapper to iterate @i over the entire list. It's | |||
514 | * a for loop, so you can break and continue as normal. | |||
515 | * | |||
516 | * Example: | |||
517 | * list_for_each_rev(&parent->children, child, list) | |||
518 | * printf("Name: %s\n", child->name); | |||
519 | */ | |||
520 | #define list_for_each_rev(h, i, member)for (i = ((void *)((char *)(list_check((h), __func__)->n.prev ) - __builtin_offsetof(typeof(*i), member))); &i->member != &(h)->n; i = ((void *)((char *)(i->member.prev) - __builtin_offsetof(typeof(*i), member)))) \ | |||
521 | for (i = container_of_var(list_debug(h)->n.prev, i, member)((void *)((char *)(list_check((h), __func__)->n.prev) - __builtin_offsetof (typeof(*i), member))); \ | |||
522 | &i->member != &(h)->n; \ | |||
523 | i = container_of_var(i->member.prev, i, member)((void *)((char *)(i->member.prev) - __builtin_offsetof(typeof (*i), member)))) | |||
524 | ||||
525 | /** | |||
526 | * list_for_each_safe - iterate through a list, maybe during deletion | |||
527 | * @h: the list_head | |||
528 | * @i: the structure containing the list_node | |||
529 | * @nxt: the structure containing the list_node | |||
530 | * @member: the list_node member of the structure | |||
531 | * | |||
532 | * This is a convenient wrapper to iterate @i over the entire list. It's | |||
533 | * a for loop, so you can break and continue as normal. The extra variable | |||
534 | * @nxt is used to hold the next element, so you can delete @i from the list. | |||
535 | * | |||
536 | * Example: | |||
537 | * struct child *next; | |||
538 | * list_for_each_safe(&parent->children, child, next, list) { | |||
539 | * list_del(&child->list); | |||
540 | * parent->num_children--; | |||
541 | * } | |||
542 | */ | |||
543 | #define list_for_each_safe(h, i, nxt, member)for (i = list_node_to_off_(list_check((h), __func__)->n.next , ((__builtin_offsetof(typeof(*i), member) + ((typeof(i->member ) *)0 != (struct list_node *)0)))), nxt = list_node_to_off_(list_node_from_off_ (i, ((__builtin_offsetof(typeof(*i), member) + ((typeof(i-> member) *)0 != (struct list_node *)0))))->next, ((__builtin_offsetof (typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node *)0)))); list_node_from_off_(i, ((__builtin_offsetof(typeof( *i), member) + ((typeof(i->member) *)0 != (struct list_node *)0)))) != &(h)->n; i = nxt, nxt = list_node_to_off_( list_node_from_off_(i, ((__builtin_offsetof(typeof(*i), member ) + ((typeof(i->member) *)0 != (struct list_node *)0))))-> next, ((__builtin_offsetof(typeof(*i), member) + ((typeof(i-> member) *)0 != (struct list_node *)0))))) \ | |||
544 | list_for_each_safe_off(h, i, nxt, list_off_var_(i, member))for (i = list_node_to_off_(list_check((h), __func__)->n.next , ((__builtin_offsetof(typeof(*i), member) + ((typeof(i->member ) *)0 != (struct list_node *)0)))), nxt = list_node_to_off_(list_node_from_off_ (i, ((__builtin_offsetof(typeof(*i), member) + ((typeof(i-> member) *)0 != (struct list_node *)0))))->next, ((__builtin_offsetof (typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node *)0)))); list_node_from_off_(i, ((__builtin_offsetof(typeof( *i), member) + ((typeof(i->member) *)0 != (struct list_node *)0)))) != &(h)->n; i = nxt, nxt = list_node_to_off_( list_node_from_off_(i, ((__builtin_offsetof(typeof(*i), member ) + ((typeof(i->member) *)0 != (struct list_node *)0))))-> next, ((__builtin_offsetof(typeof(*i), member) + ((typeof(i-> member) *)0 != (struct list_node *)0))))) | |||
545 | ||||
546 | /** | |||
547 | * list_append_list - empty one list onto the end of another. | |||
548 | * @to: the list to append into | |||
549 | * @from: the list to empty. | |||
550 | * | |||
551 | * This takes the entire contents of @from and moves it to the end of | |||
552 | * @to. After this @from will be empty. | |||
553 | * | |||
554 | * Example: | |||
555 | * struct list_head adopter; | |||
556 | * | |||
557 | * list_append_list(&adopter, &parent->children); | |||
558 | * assert(list_empty(&parent->children)); | |||
559 | * parent->num_children = 0; | |||
560 | */ | |||
561 | static inline void list_append_list(struct list_head *to, | |||
562 | struct list_head *from) | |||
563 | { | |||
564 | struct list_node *from_tail = list_debug(from)list_check((from), __func__)->n.prev; | |||
565 | struct list_node *to_tail = list_debug(to)list_check((to), __func__)->n.prev; | |||
566 | ||||
567 | /* Sew in head and entire list. */ | |||
568 | to->n.prev = from_tail; | |||
569 | from_tail->next = &to->n; | |||
570 | to_tail->next = &from->n; | |||
571 | from->n.prev = to_tail; | |||
572 | ||||
573 | /* Now remove head. */ | |||
574 | list_del(&from->n); | |||
575 | list_head_init(from); | |||
576 | } | |||
577 | ||||
578 | /** | |||
579 | * list_prepend_list - empty one list into the start of another. | |||
580 | * @to: the list to prepend into | |||
581 | * @from: the list to empty. | |||
582 | * | |||
583 | * This takes the entire contents of @from and moves it to the start | |||
584 | * of @to. After this @from will be empty. | |||
585 | * | |||
586 | * Example: | |||
587 | * list_prepend_list(&adopter, &parent->children); | |||
588 | * assert(list_empty(&parent->children)); | |||
589 | * parent->num_children = 0; | |||
590 | */ | |||
591 | static inline void list_prepend_list(struct list_head *to, | |||
592 | struct list_head *from) | |||
593 | { | |||
594 | struct list_node *from_tail = list_debug(from)list_check((from), __func__)->n.prev; | |||
595 | struct list_node *to_head = list_debug(to)list_check((to), __func__)->n.next; | |||
596 | ||||
597 | /* Sew in head and entire list. */ | |||
598 | to->n.next = &from->n; | |||
599 | from->n.prev = &to->n; | |||
600 | to_head->prev = from_tail; | |||
601 | from_tail->next = to_head; | |||
602 | ||||
603 | /* Now remove head. */ | |||
604 | list_del(&from->n); | |||
605 | list_head_init(from); | |||
606 | } | |||
607 | ||||
608 | /** | |||
609 | * list_for_each_off - iterate through a list of memory regions. | |||
610 | * @h: the list_head | |||
611 | * @i: the pointer to a memory region which contains list node data. | |||
612 | * @off: offset(relative to @i) at which list node data resides. | |||
613 | * | |||
614 | * This is a low-level wrapper to iterate @i over the entire list, used to | |||
615 | * implement all oher, more high-level, for-each constructs. It's a for loop, | |||
616 | * so you can break and continue as normal. | |||
617 | * | |||
618 | * WARNING! Being the low-level macro that it is, this wrapper doesn't know | |||
619 | * nor care about the type of @i. The only assumtion made is that @i points | |||
620 | * to a chunk of memory that at some @offset, relative to @i, contains a | |||
621 | * properly filled `struct node_list' which in turn contains pointers to | |||
622 | * memory chunks and it's turtles all the way down. Whith all that in mind | |||
623 | * remember that given the wrong pointer/offset couple this macro will | |||
624 | * happilly churn all you memory untill SEGFAULT stops it, in other words | |||
625 | * caveat emptor. | |||
626 | * | |||
627 | * It is worth mentioning that one of legitimate use-cases for that wrapper | |||
628 | * is operation on opaque types with known offset for `struct list_node' | |||
629 | * member(preferably 0), because it allows you not to disclose the type of | |||
630 | * @i. | |||
631 | * | |||
632 | * Example: | |||
633 | * list_for_each_off(&parent->children, child, | |||
634 | * offsetof(struct child, list)) | |||
635 | * printf("Name: %s\n", child->name); | |||
636 | */ | |||
637 | #define list_for_each_off(h, i, off)for (i = list_node_to_off_(list_check((h), __func__)->n.next , (off)); list_node_from_off_((void *)i, (off)) != &(h)-> n; i = list_node_to_off_(list_node_from_off_((void *)i, (off) )->next, (off))) \ | |||
638 | for (i = list_node_to_off_(list_debug(h)list_check((h), __func__)->n.next, (off)); \ | |||
639 | list_node_from_off_((void *)i, (off)) != &(h)->n; \ | |||
640 | i = list_node_to_off_(list_node_from_off_((void *)i, (off))->next, \ | |||
641 | (off))) | |||
642 | ||||
643 | /** | |||
644 | * list_for_each_safe_off - iterate through a list of memory regions, maybe | |||
645 | * during deletion | |||
646 | * @h: the list_head | |||
647 | * @i: the pointer to a memory region which contains list node data. | |||
648 | * @nxt: the structure containing the list_node | |||
649 | * @off: offset(relative to @i) at which list node data resides. | |||
650 | * | |||
651 | * For details see `list_for_each_off' and `list_for_each_safe' | |||
652 | * descriptions. | |||
653 | * | |||
654 | * Example: | |||
655 | * list_for_each_safe_off(&parent->children, child, | |||
656 | * next, offsetof(struct child, list)) | |||
657 | * printf("Name: %s\n", child->name); | |||
658 | */ | |||
659 | #define list_for_each_safe_off(h, i, nxt, off)for (i = list_node_to_off_(list_check((h), __func__)->n.next , (off)), nxt = list_node_to_off_(list_node_from_off_(i, (off ))->next, (off)); list_node_from_off_(i, (off)) != &(h )->n; i = nxt, nxt = list_node_to_off_(list_node_from_off_ (i, (off))->next, (off))) \ | |||
660 | for (i = list_node_to_off_(list_debug(h)list_check((h), __func__)->n.next, (off)), \ | |||
661 | nxt = list_node_to_off_(list_node_from_off_(i, (off))->next, \ | |||
662 | (off)); \ | |||
663 | list_node_from_off_(i, (off)) != &(h)->n; \ | |||
664 | i = nxt, \ | |||
665 | nxt = list_node_to_off_(list_node_from_off_(i, (off))->next, \ | |||
666 | (off))) | |||
667 | ||||
668 | ||||
669 | /* Other -off variants. */ | |||
670 | #define list_entry_off(n, type, off)((type *)list_node_from_off_((n), (off))) \ | |||
671 | ((type *)list_node_from_off_((n), (off))) | |||
672 | ||||
673 | #define list_head_off(h, type, off)((type *)list_head_off((h), (off))) \ | |||
674 | ((type *)list_head_off((h), (off))) | |||
675 | ||||
676 | #define list_tail_off(h, type, off)((type *)list_tail_((h), (off))) \ | |||
677 | ((type *)list_tail_((h), (off))) | |||
678 | ||||
679 | #define list_add_off(h, n, off)list_add((h), list_node_from_off_((n), (off))) \ | |||
680 | list_add((h), list_node_from_off_((n), (off))) | |||
681 | ||||
682 | #define list_del_off(n, off)list_del(list_node_from_off_((n), (off))) \ | |||
683 | list_del(list_node_from_off_((n), (off))) | |||
684 | ||||
685 | #define list_del_from_off(h, n, off)list_del_from(h, list_node_from_off_((n), (off))) \ | |||
686 | list_del_from(h, list_node_from_off_((n), (off))) | |||
687 | ||||
688 | /* Offset helper functions so we only single-evaluate. */ | |||
689 | static inline void *list_node_to_off_(struct list_node *node, size_t off) | |||
690 | { | |||
691 | return (void *)((char *)node - off); | |||
692 | } | |||
693 | static inline struct list_node *list_node_from_off_(void *ptr, size_t off) | |||
694 | { | |||
695 | return (struct list_node *)((char *)ptr + off); | |||
696 | } | |||
697 | ||||
698 | /* Get the offset of the member, but make sure it's a list_node. */ | |||
699 | #define list_off_(type, member)(__builtin_offsetof(type, member) + ((typeof(((type *)0)-> member) *)0 != (struct list_node *)0)) \ | |||
700 | (container_off(type, member)__builtin_offsetof(type, member) + \ | |||
701 | check_type(((type *)0)->member, struct list_node)((typeof(((type *)0)->member) *)0 != (struct list_node *)0 )) | |||
702 | ||||
703 | #define list_off_var_(var, member)(__builtin_offsetof(typeof(*var), member) + ((typeof(var-> member) *)0 != (struct list_node *)0)) \ | |||
704 | (container_off_var(var, member)__builtin_offsetof(typeof(*var), member) + \ | |||
705 | check_type(var->member, struct list_node)((typeof(var->member) *)0 != (struct list_node *)0)) |