bottleneck testcase based on rubbos
[bottlenecks.git] / rubbos / app / apache2 / include / apr_ring.h
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 *next;                                              \
73         struct elem *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) - 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 /**
382  * Iterate through a ring
383  * @param ep The current element
384  * @param hp The ring to iterate over
385  * @param elem The name of the element struct
386  * @param link The name of the APR_RING_ENTRY in the element struct
387  * @remark This is the same as either:
388  * <pre>
389  *      ep = APR_RING_FIRST(hp);
390  *      while (ep != APR_RING_SENTINEL(hp, elem, link)) {
391  *          ...
392  *          ep = APR_RING_NEXT(ep, link);
393  *      }
394  *   OR
395  *      for (ep = APR_RING_FIRST(hp);
396  *           ep != APR_RING_SENTINEL(hp, elem, link);
397  *           ep = APR_RING_NEXT(ep, link)) {
398  *          ...
399  *      }
400  * </pre>
401  * @warning Be aware that you cannot change the value of ep within
402  * the foreach loop, nor can you destroy the ring element it points to.
403  * Modifying the prev and next pointers of the element is dangerous
404  * but can be done if you're careful.  If you change ep's value or
405  * destroy the element it points to, then APR_RING_FOREACH
406  * will have no way to find out what element to use for its next
407  * iteration.  The reason for this can be seen by looking closely
408  * at the equivalent loops given in the tip above.  So, for example,
409  * if you are writing a loop that empties out a ring one element
410  * at a time, APR_RING_FOREACH just won't work for you.  Do it
411  * by hand, like so:
412  * <pre>
413  *      while (!APR_RING_EMPTY(hp, elem, link)) {
414  *          ep = APR_RING_FIRST(hp);
415  *          ...
416  *          APR_RING_REMOVE(ep, link);
417  *      }
418  * </pre>
419  * @deprecated This macro causes more headaches than it's worth.  Use
420  * one of the alternatives documented here instead; the clarity gained
421  * in what's really going on is well worth the extra line or two of code.
422  * This macro will be removed at some point in the future.
423  */
424 #define APR_RING_FOREACH(ep, hp, elem, link)                            \
425     for ((ep)  = APR_RING_FIRST((hp));                                  \
426          (ep) != APR_RING_SENTINEL((hp), elem, link);                   \
427          (ep)  = APR_RING_NEXT((ep), link))
428
429 /**
430  * Iterate through a ring backwards
431  * @param ep The current element
432  * @param hp The ring to iterate over
433  * @param elem The name of the element struct
434  * @param link The name of the APR_RING_ENTRY in the element struct
435  * @see APR_RING_FOREACH
436  */
437 #define APR_RING_FOREACH_REVERSE(ep, hp, elem, link)                    \
438     for ((ep)  = APR_RING_LAST((hp));                                   \
439          (ep) != APR_RING_SENTINEL((hp), elem, link);                   \
440          (ep)  = APR_RING_PREV((ep), link))
441
442
443 /* Debugging tools: */
444
445 #ifdef APR_RING_DEBUG
446 #include <stdio.h>
447 #include <assert.h>
448
449 #define APR_RING_CHECK_ONE(msg, ptr)                                    \
450         fprintf(stderr, "*** %s %p\n", msg, ptr)
451
452 #define APR_RING_CHECK(hp, elem, link, msg)                             \
453         APR_RING_CHECK_ELEM(APR_RING_SENTINEL(hp, elem, link), elem, link, msg)
454
455 #define APR_RING_CHECK_ELEM(ep, elem, link, msg) do {                   \
456         struct elem *start = (ep);                                      \
457         struct elem *here = start;                                      \
458         fprintf(stderr, "*** ring check start -- %s\n", msg);           \
459         do {                                                            \
460             fprintf(stderr, "\telem %p\n", here);                       \
461             fprintf(stderr, "\telem->next %p\n",                        \
462                     APR_RING_NEXT(here, link));                         \
463             fprintf(stderr, "\telem->prev %p\n",                        \
464                     APR_RING_PREV(here, link));                         \
465             fprintf(stderr, "\telem->next->prev %p\n",                  \
466                     APR_RING_PREV(APR_RING_NEXT(here, link), link));    \
467             fprintf(stderr, "\telem->prev->next %p\n",                  \
468                     APR_RING_NEXT(APR_RING_PREV(here, link), link));    \
469             if (APR_RING_PREV(APR_RING_NEXT(here, link), link) != here) { \
470                 fprintf(stderr, "\t*** elem->next->prev != elem\n");    \
471                 break;                                                  \
472             }                                                           \
473             if (APR_RING_NEXT(APR_RING_PREV(here, link), link) != here) { \
474                 fprintf(stderr, "\t*** elem->prev->next != elem\n");    \
475                 break;                                                  \
476             }                                                           \
477             here = APR_RING_NEXT(here, link);                           \
478         } while (here != start);                                        \
479         fprintf(stderr, "*** ring check end\n");                        \
480     } while (0)
481
482 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)                      \
483         APR_RING_CHECK_ELEM_CONSISTENCY(APR_RING_SENTINEL(hp, elem, link),\
484                                         elem, link)
485
486 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link) do {            \
487         struct elem *start = (ep);                                      \
488         struct elem *here = start;                                      \
489         do {                                                            \
490             assert(APR_RING_PREV(APR_RING_NEXT(here, link), link) == here); \
491             assert(APR_RING_NEXT(APR_RING_PREV(here, link), link) == here); \
492             here = APR_RING_NEXT(here, link);                           \
493         } while (here != start);                                        \
494     } while (0)
495
496 #else
497 /**
498  * Print a single pointer value to STDERR
499  *   (This is a no-op unless APR_RING_DEBUG is defined.)
500  * @param msg Descriptive message
501  * @param ptr Pointer value to print
502  */
503 #define APR_RING_CHECK_ONE(msg, ptr)
504 /**
505  * Dump all ring pointers to STDERR, starting with the head and looping all
506  * the way around the ring back to the head.  Aborts if an inconsistency
507  * is found.
508  *   (This is a no-op unless APR_RING_DEBUG is defined.)
509  * @param hp   Head of the ring
510  * @param elem The name of the element struct
511  * @param link The name of the APR_RING_ENTRY in the element struct
512  * @param msg  Descriptive message
513  */
514 #define APR_RING_CHECK(hp, elem, link, msg)
515 /**
516  * Loops around a ring and checks all the pointers for consistency.  Pops
517  * an assertion if any inconsistency is found.  Same idea as APR_RING_CHECK()
518  * except that it's silent if all is well.
519  *   (This is a no-op unless APR_RING_DEBUG is defined.)
520  * @param hp   Head of the ring
521  * @param elem The name of the element struct
522  * @param link The name of the APR_RING_ENTRY in the element struct
523  */
524 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)
525 /**
526  * Dump all ring pointers to STDERR, starting with the given element and
527  * looping all the way around the ring back to that element.  Aborts if
528  * an inconsistency is found.
529  *   (This is a no-op unless APR_RING_DEBUG is defined.)
530  * @param ep   The element
531  * @param elem The name of the element struct
532  * @param link The name of the APR_RING_ENTRY in the element struct
533  * @param msg  Descriptive message
534  */
535 #define APR_RING_CHECK_ELEM(ep, elem, link, msg)
536 /**
537  * Loops around a ring, starting with the given element, and checks all
538  * the pointers for consistency.  Pops an assertion if any inconsistency
539  * is found.  Same idea as APR_RING_CHECK_ELEM() except that it's silent
540  * if all is well.
541  *   (This is a no-op unless APR_RING_DEBUG is defined.)
542  * @param ep   The element
543  * @param elem The name of the element struct
544  * @param link The name of the APR_RING_ENTRY in the element struct
545  */
546 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link)
547 #endif
548
549 /** @} */ 
550
551 #endif /* !APR_RING_H */