1/* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements.  See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License.  You may obtain a copy of the License at
7 *
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.
15 */
16
17/*
18 * This code draws heavily from the 4.4BSD <sys/queue.h> macros
19 * and Dean Gaudet's "splim/ring.h".
20 * <http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/queue.h>
21 * <http://www.arctic.org/~dean/splim/>
22 *
23 * We'd use Dean's code directly if we could guarantee the
24 * availability of inline functions.
25 */
26
27#ifndef APR_RING_H
28#define APR_RING_H
29
30/**
31 * @file apr_ring.h
32 * @brief APR Rings
33 */
34
35/*
36 * for offsetof()
37 */
38#include "apr_general.h"
39
40/**
41 * @defgroup apr_ring Ring Macro Implementations
42 * @ingroup APR
43 * A ring is a kind of doubly-linked list that can be manipulated
44 * without knowing where its head is.
45 * @{
46 */
47
48/**
49 * The Ring Element
50 *
51 * A ring element struct is linked to the other elements in the ring
52 * through its ring entry field, e.g.
53 * <pre>
54 *      struct my_element_t {
55 *          APR_RING_ENTRY(my_element_t) link;
56 *          int foo;
57 *          char *bar;
58 *      };
59 * </pre>
60 *
61 * An element struct may be put on more than one ring if it has more
62 * than one APR_RING_ENTRY field. Each APR_RING_ENTRY has a corresponding
63 * APR_RING_HEAD declaration.
64 *
65 * @warning For strict C standards compliance you should put the APR_RING_ENTRY
66 * first in the element struct unless the head is always part of a larger
67 * object with enough earlier fields to accommodate the offsetof() used
68 * to compute the ring sentinel below. You can usually ignore this caveat.
69 */
70#define APR_RING_ENTRY(elem)						\
71    struct {								\
72	struct elem * volatile next;					\
73	struct elem * volatile prev;					\
74    }
75
76/**
77 * The Ring Head
78 *
79 * Each ring is managed via its head, which is a struct declared like this:
80 * <pre>
81 *      APR_RING_HEAD(my_ring_t, my_element_t);
82 *      struct my_ring_t ring, *ringp;
83 * </pre>
84 *
85 * This struct looks just like the element link struct so that we can
86 * be sure that the typecasting games will work as expected.
87 *
88 * The first element in the ring is next after the head, and the last
89 * element is just before the head.
90 */
91#define APR_RING_HEAD(head, elem)					\
92    struct head {							\
93	struct elem * volatile next;					\
94	struct elem * volatile prev;					\
95    }
96
97/**
98 * The Ring Sentinel
99 *
100 * This is the magic pointer value that occurs before the first and
101 * after the last elements in the ring, computed from the address of
102 * the ring's head.  The head itself isn't an element, but in order to
103 * get rid of all the special cases when dealing with the ends of the
104 * ring, we play typecasting games to make it look like one.
105 *
106 * Here is a diagram to illustrate the arrangements of the next and
107 * prev pointers of each element in a single ring. Note that they point
108 * to the start of each element, not to the APR_RING_ENTRY structure.
109 *
110 * <pre>
111 *     +->+------+<-+  +->+------+<-+  +->+------+<-+
112 *     |  |struct|  |  |  |struct|  |  |  |struct|  |
113 *    /   | elem |   \/   | elem |   \/   | elem |  \
114 * ...    |      |   /\   |      |   /\   |      |   ...
115 *        +------+  |  |  +------+  |  |  +------+
116 *   ...--|prev  |  |  +--|ring  |  |  +--|prev  |
117 *        |  next|--+     | entry|--+     |  next|--...
118 *        +------+        +------+        +------+
119 *        | etc. |        | etc. |        | etc. |
120 *        :      :        :      :        :      :
121 * </pre>
122 *
123 * The APR_RING_HEAD is nothing but a bare APR_RING_ENTRY. The prev
124 * and next pointers in the first and last elements don't actually
125 * point to the head, they point to a phantom place called the
126 * sentinel. Its value is such that last->next->next == first because
127 * the offset from the sentinel to the head's next pointer is the same
128 * as the offset from the start of an element to its next pointer.
129 * This also works in the opposite direction.
130 *
131 * <pre>
132 *        last                            first
133 *     +->+------+<-+  +->sentinel<-+  +->+------+<-+
134 *     |  |struct|  |  |            |  |  |struct|  |
135 *    /   | elem |   \/              \/   | elem |  \
136 * ...    |      |   /\              /\   |      |   ...
137 *        +------+  |  |  +------+  |  |  +------+
138 *   ...--|prev  |  |  +--|ring  |  |  +--|prev  |
139 *        |  next|--+     |  head|--+     |  next|--...
140 *        +------+        +------+        +------+
141 *        | etc. |                        | etc. |
142 *        :      :                        :      :
143 * </pre>
144 *
145 * Note that the offset mentioned above is different for each kind of
146 * ring that the element may be on, and each kind of ring has a unique
147 * name for its APR_RING_ENTRY in each element, and has its own type
148 * for its APR_RING_HEAD.
149 *
150 * Note also that if the offset is non-zero (which is required if an
151 * element has more than one APR_RING_ENTRY), the unreality of the
152 * sentinel may have bad implications on very perverse implementations
153 * of C -- see the warning in APR_RING_ENTRY.
154 *
155 * @param hp   The head of the ring
156 * @param elem The name of the element struct
157 * @param link The name of the APR_RING_ENTRY in the element struct
158 */
159#define APR_RING_SENTINEL(hp, elem, link)				\
160    (struct elem *)((char *)(&(hp)->next) - APR_OFFSETOF(struct elem, link))
161
162/**
163 * The first element of the ring
164 * @param hp   The head of the ring
165 */
166#define APR_RING_FIRST(hp)	(hp)->next
167/**
168 * The last element of the ring
169 * @param hp   The head of the ring
170 */
171#define APR_RING_LAST(hp)	(hp)->prev
172/**
173 * The next element in the ring
174 * @param ep   The current element
175 * @param link The name of the APR_RING_ENTRY in the element struct
176 */
177#define APR_RING_NEXT(ep, link)	(ep)->link.next
178/**
179 * The previous element in the ring
180 * @param ep   The current element
181 * @param link The name of the APR_RING_ENTRY in the element struct
182 */
183#define APR_RING_PREV(ep, link)	(ep)->link.prev
184
185
186/**
187 * Initialize a ring
188 * @param hp   The head of the ring
189 * @param elem The name of the element struct
190 * @param link The name of the APR_RING_ENTRY in the element struct
191 */
192#define APR_RING_INIT(hp, elem, link) do {				\
193	APR_RING_FIRST((hp)) = APR_RING_SENTINEL((hp), elem, link);	\
194	APR_RING_LAST((hp))  = APR_RING_SENTINEL((hp), elem, link);	\
195    } while (0)
196
197/**
198 * Determine if a ring is empty
199 * @param hp   The head of the ring
200 * @param elem The name of the element struct
201 * @param link The name of the APR_RING_ENTRY in the element struct
202 * @return true or false
203 */
204#define APR_RING_EMPTY(hp, elem, link)					\
205    (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))
206
207/**
208 * Initialize a singleton element
209 * @param ep   The element
210 * @param link The name of the APR_RING_ENTRY in the element struct
211 */
212#define APR_RING_ELEM_INIT(ep, link) do {				\
213	APR_RING_NEXT((ep), link) = (ep);				\
214	APR_RING_PREV((ep), link) = (ep);				\
215    } while (0)
216
217
218/**
219 * Splice the sequence ep1..epN into the ring before element lep
220 *   (..lep.. becomes ..ep1..epN..lep..)
221 * @warning This doesn't work for splicing before the first element or on
222 *   empty rings... see APR_RING_SPLICE_HEAD for one that does
223 * @param lep  Element in the ring to splice before
224 * @param ep1  First element in the sequence to splice in
225 * @param epN  Last element in the sequence to splice in
226 * @param link The name of the APR_RING_ENTRY in the element struct
227 */
228#define APR_RING_SPLICE_BEFORE(lep, ep1, epN, link) do {		\
229	APR_RING_NEXT((epN), link) = (lep);				\
230	APR_RING_PREV((ep1), link) = APR_RING_PREV((lep), link);	\
231	APR_RING_NEXT(APR_RING_PREV((lep), link), link) = (ep1);	\
232	APR_RING_PREV((lep), link) = (epN);				\
233    } while (0)
234
235/**
236 * Splice the sequence ep1..epN into the ring after element lep
237 *   (..lep.. becomes ..lep..ep1..epN..)
238 * @warning This doesn't work for splicing after the last element or on
239 *   empty rings... see APR_RING_SPLICE_TAIL for one that does
240 * @param lep  Element in the ring to splice after
241 * @param ep1  First element in the sequence to splice in
242 * @param epN  Last element in the sequence to splice in
243 * @param link The name of the APR_RING_ENTRY in the element struct
244 */
245#define APR_RING_SPLICE_AFTER(lep, ep1, epN, link) do {			\
246	APR_RING_PREV((ep1), link) = (lep);				\
247	APR_RING_NEXT((epN), link) = APR_RING_NEXT((lep), link);	\
248	APR_RING_PREV(APR_RING_NEXT((lep), link), link) = (epN);	\
249	APR_RING_NEXT((lep), link) = (ep1);				\
250    } while (0)
251
252/**
253 * Insert the element nep into the ring before element lep
254 *   (..lep.. becomes ..nep..lep..)
255 * @warning This doesn't work for inserting before the first element or on
256 *   empty rings... see APR_RING_INSERT_HEAD for one that does
257 * @param lep  Element in the ring to insert before
258 * @param nep  Element to insert
259 * @param link The name of the APR_RING_ENTRY in the element struct
260 */
261#define APR_RING_INSERT_BEFORE(lep, nep, link)				\
262	APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link)
263
264/**
265 * Insert the element nep into the ring after element lep
266 *   (..lep.. becomes ..lep..nep..)
267 * @warning This doesn't work for inserting after the last element or on
268 *   empty rings... see APR_RING_INSERT_TAIL for one that does
269 * @param lep  Element in the ring to insert after
270 * @param nep  Element to insert
271 * @param link The name of the APR_RING_ENTRY in the element struct
272 */
273#define APR_RING_INSERT_AFTER(lep, nep, link)				\
274	APR_RING_SPLICE_AFTER((lep), (nep), (nep), link)
275
276
277/**
278 * Splice the sequence ep1..epN into the ring before the first element
279 *   (..hp.. becomes ..hp..ep1..epN..)
280 * @param hp   Head of the ring
281 * @param ep1  First element in the sequence to splice in
282 * @param epN  Last element in the sequence to splice in
283 * @param elem The name of the element struct
284 * @param link The name of the APR_RING_ENTRY in the element struct
285 */
286#define APR_RING_SPLICE_HEAD(hp, ep1, epN, elem, link)			\
287	APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((hp), elem, link),	\
288			     (ep1), (epN), link)
289
290/**
291 * Splice the sequence ep1..epN into the ring after the last element
292 *   (..hp.. becomes ..ep1..epN..hp..)
293 * @param hp   Head of the ring
294 * @param ep1  First element in the sequence to splice in
295 * @param epN  Last element in the sequence to splice in
296 * @param elem The name of the element struct
297 * @param link The name of the APR_RING_ENTRY in the element struct
298 */
299#define APR_RING_SPLICE_TAIL(hp, ep1, epN, elem, link)			\
300	APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((hp), elem, link),	\
301			     (ep1), (epN), link)
302
303/**
304 * Insert the element nep into the ring before the first element
305 *   (..hp.. becomes ..hp..nep..)
306 * @param hp   Head of the ring
307 * @param nep  Element to insert
308 * @param elem The name of the element struct
309 * @param link The name of the APR_RING_ENTRY in the element struct
310 */
311#define APR_RING_INSERT_HEAD(hp, nep, elem, link)			\
312	APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link)
313
314/**
315 * Insert the element nep into the ring after the last element
316 *   (..hp.. becomes ..nep..hp..)
317 * @param hp   Head of the ring
318 * @param nep  Element to insert
319 * @param elem The name of the element struct
320 * @param link The name of the APR_RING_ENTRY in the element struct
321 */
322#define APR_RING_INSERT_TAIL(hp, nep, elem, link)			\
323	APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link)
324
325/**
326 * Concatenate ring h2 onto the end of ring h1, leaving h2 empty.
327 * @param h1   Head of the ring to concatenate onto
328 * @param h2   Head of the ring to concatenate
329 * @param elem The name of the element struct
330 * @param link The name of the APR_RING_ENTRY in the element struct
331 */
332#define APR_RING_CONCAT(h1, h2, elem, link) do {			\
333	if (!APR_RING_EMPTY((h2), elem, link)) {			\
334	    APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((h1), elem, link),	\
335				  APR_RING_FIRST((h2)),			\
336				  APR_RING_LAST((h2)), link);		\
337	    APR_RING_INIT((h2), elem, link);				\
338	}								\
339    } while (0)
340
341/**
342 * Prepend ring h2 onto the beginning of ring h1, leaving h2 empty.
343 * @param h1   Head of the ring to prepend onto
344 * @param h2   Head of the ring to prepend
345 * @param elem The name of the element struct
346 * @param link The name of the APR_RING_ENTRY in the element struct
347 */
348#define APR_RING_PREPEND(h1, h2, elem, link) do {			\
349	if (!APR_RING_EMPTY((h2), elem, link)) {			\
350	    APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((h1), elem, link),	\
351				  APR_RING_FIRST((h2)),			\
352				  APR_RING_LAST((h2)), link);		\
353	    APR_RING_INIT((h2), elem, link);				\
354	}								\
355    } while (0)
356
357/**
358 * Unsplice a sequence of elements from a ring
359 * @warning The unspliced sequence is left with dangling pointers at either end
360 * @param ep1  First element in the sequence to unsplice
361 * @param epN  Last element in the sequence to unsplice
362 * @param link The name of the APR_RING_ENTRY in the element struct
363 */
364#define APR_RING_UNSPLICE(ep1, epN, link) do {				\
365	APR_RING_NEXT(APR_RING_PREV((ep1), link), link) =		\
366		     APR_RING_NEXT((epN), link);			\
367	APR_RING_PREV(APR_RING_NEXT((epN), link), link) =		\
368		     APR_RING_PREV((ep1), link);			\
369    } while (0)
370
371/**
372 * Remove a single element from a ring
373 * @warning The unspliced element is left with dangling pointers at either end
374 * @param ep   Element to remove
375 * @param link The name of the APR_RING_ENTRY in the element struct
376 */
377#define APR_RING_REMOVE(ep, link)					\
378    APR_RING_UNSPLICE((ep), (ep), link)
379
380/**
381 * Iterate over a ring
382 * @param ep The current element
383 * @param head The head of the ring
384 * @param elem The name of the element struct
385 * @param link The name of the APR_RING_ENTRY in the element struct
386 */
387#define APR_RING_FOREACH(ep, head, elem, link)                          \
388    for (ep = APR_RING_FIRST(head);                                     \
389         ep != APR_RING_SENTINEL(head, elem, link);                     \
390         ep = APR_RING_NEXT(ep, link))
391
392/**
393 * Iterate over a ring safe against removal of the current element
394 * @param ep1 The current element
395 * @param ep2 Iteration cursor
396 * @param head The head of the ring
397 * @param elem The name of the element struct
398 * @param link The name of the APR_RING_ENTRY in the element struct
399 */
400#define APR_RING_FOREACH_SAFE(ep1, ep2, head, elem, link)               \
401    for (ep1 = APR_RING_FIRST(head), ep2 = APR_RING_NEXT(ep1, link);    \
402         ep1 != APR_RING_SENTINEL(head, elem, link);                    \
403         ep1 = ep2, ep2 = APR_RING_NEXT(ep1, link))
404
405/* Debugging tools: */
406
407#ifdef APR_RING_DEBUG
408#include <stdio.h>
409#include <assert.h>
410
411#define APR_RING_CHECK_ONE(msg, ptr)					\
412	fprintf(stderr, "*** %s %p\n", msg, ptr)
413
414#define APR_RING_CHECK(hp, elem, link, msg)				\
415	APR_RING_CHECK_ELEM(APR_RING_SENTINEL(hp, elem, link), elem, link, msg)
416
417#define APR_RING_CHECK_ELEM(ep, elem, link, msg) do {			\
418	struct elem *start = (ep);					\
419	struct elem *here = start;					\
420	fprintf(stderr, "*** ring check start -- %s\n", msg);		\
421	do {								\
422	    fprintf(stderr, "\telem %p\n", here);			\
423	    fprintf(stderr, "\telem->next %p\n",			\
424		    APR_RING_NEXT(here, link));				\
425	    fprintf(stderr, "\telem->prev %p\n",			\
426		    APR_RING_PREV(here, link));				\
427	    fprintf(stderr, "\telem->next->prev %p\n",			\
428		    APR_RING_PREV(APR_RING_NEXT(here, link), link));	\
429	    fprintf(stderr, "\telem->prev->next %p\n",			\
430		    APR_RING_NEXT(APR_RING_PREV(here, link), link));	\
431	    if (APR_RING_PREV(APR_RING_NEXT(here, link), link) != here) { \
432		fprintf(stderr, "\t*** elem->next->prev != elem\n");	\
433		break;							\
434	    }								\
435	    if (APR_RING_NEXT(APR_RING_PREV(here, link), link) != here) { \
436		fprintf(stderr, "\t*** elem->prev->next != elem\n");	\
437		break;							\
438	    }								\
439	    here = APR_RING_NEXT(here, link);				\
440	} while (here != start);					\
441	fprintf(stderr, "*** ring check end\n");			\
442    } while (0)
443
444#define APR_RING_CHECK_CONSISTENCY(hp, elem, link)			\
445	APR_RING_CHECK_ELEM_CONSISTENCY(APR_RING_SENTINEL(hp, elem, link),\
446					elem, link)
447
448#define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link) do {		\
449	struct elem *start = (ep);					\
450	struct elem *here = start;					\
451	do {								\
452	    assert(APR_RING_PREV(APR_RING_NEXT(here, link), link) == here); \
453	    assert(APR_RING_NEXT(APR_RING_PREV(here, link), link) == here); \
454	    here = APR_RING_NEXT(here, link);				\
455	} while (here != start);					\
456    } while (0)
457
458#else
459/**
460 * Print a single pointer value to STDERR
461 *   (This is a no-op unless APR_RING_DEBUG is defined.)
462 * @param msg Descriptive message
463 * @param ptr Pointer value to print
464 */
465#define APR_RING_CHECK_ONE(msg, ptr)
466/**
467 * Dump all ring pointers to STDERR, starting with the head and looping all
468 * the way around the ring back to the head.  Aborts if an inconsistency
469 * is found.
470 *   (This is a no-op unless APR_RING_DEBUG is defined.)
471 * @param hp   Head of the ring
472 * @param elem The name of the element struct
473 * @param link The name of the APR_RING_ENTRY in the element struct
474 * @param msg  Descriptive message
475 */
476#define APR_RING_CHECK(hp, elem, link, msg)
477/**
478 * Loops around a ring and checks all the pointers for consistency.  Pops
479 * an assertion if any inconsistency is found.  Same idea as APR_RING_CHECK()
480 * except that it's silent if all is well.
481 *   (This is a no-op unless APR_RING_DEBUG is defined.)
482 * @param hp   Head of the ring
483 * @param elem The name of the element struct
484 * @param link The name of the APR_RING_ENTRY in the element struct
485 */
486#define APR_RING_CHECK_CONSISTENCY(hp, elem, link)
487/**
488 * Dump all ring pointers to STDERR, starting with the given element and
489 * looping all the way around the ring back to that element.  Aborts if
490 * an inconsistency is found.
491 *   (This is a no-op unless APR_RING_DEBUG is defined.)
492 * @param ep   The element
493 * @param elem The name of the element struct
494 * @param link The name of the APR_RING_ENTRY in the element struct
495 * @param msg  Descriptive message
496 */
497#define APR_RING_CHECK_ELEM(ep, elem, link, msg)
498/**
499 * Loops around a ring, starting with the given element, and checks all
500 * the pointers for consistency.  Pops an assertion if any inconsistency
501 * is found.  Same idea as APR_RING_CHECK_ELEM() except that it's silent
502 * if all is well.
503 *   (This is a no-op unless APR_RING_DEBUG is defined.)
504 * @param ep   The element
505 * @param elem The name of the element struct
506 * @param link The name of the APR_RING_ENTRY in the element struct
507 */
508#define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link)
509#endif
510
511/** @} */
512
513#endif /* !APR_RING_H */
514