Apache Portable Runtime
apr_ring.h
Go to the documentation of this file.
00001 /* Licensed to the Apache Software Foundation (ASF) under one or more
00002  * contributor license agreements.  See the NOTICE file distributed with
00003  * this work for additional information regarding copyright ownership.
00004  * The ASF licenses this file to You under the Apache License, Version 2.0
00005  * (the "License"); you may not use this file except in compliance with
00006  * the License.  You may obtain a copy of the License at
00007  *
00008  *     http://www.apache.org/licenses/LICENSE-2.0
00009  *
00010  * Unless required by applicable law or agreed to in writing, software
00011  * distributed under the License is distributed on an "AS IS" BASIS,
00012  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00013  * See the License for the specific language governing permissions and
00014  * limitations under the License.
00015  */
00016 
00017 /*
00018  * This code draws heavily from the 4.4BSD <sys/queue.h> macros
00019  * and Dean Gaudet's "splim/ring.h".
00020  * <http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/queue.h>
00021  * <http://www.arctic.org/~dean/splim/>
00022  *
00023  * We'd use Dean's code directly if we could guarantee the
00024  * availability of inline functions.
00025  */
00026 
00027 #ifndef APR_RING_H
00028 #define APR_RING_H
00029 
00030 /**
00031  * @file apr_ring.h
00032  * @brief APR Rings
00033  */
00034 
00035 /*
00036  * for offsetof()
00037  */
00038 #include "apr_general.h"
00039 
00040 /**
00041  * @defgroup apr_ring Ring Macro Implementations
00042  * @ingroup APR 
00043  * A ring is a kind of doubly-linked list that can be manipulated
00044  * without knowing where its head is.
00045  * @{
00046  */
00047 
00048 /**
00049  * The Ring Element
00050  *
00051  * A ring element struct is linked to the other elements in the ring
00052  * through its ring entry field, e.g.
00053  * <pre>
00054  *      struct my_element_t {
00055  *          APR_RING_ENTRY(my_element_t) link;
00056  *          int foo;
00057  *          char *bar;
00058  *      };
00059  * </pre>
00060  *
00061  * An element struct may be put on more than one ring if it has more
00062  * than one APR_RING_ENTRY field. Each APR_RING_ENTRY has a corresponding
00063  * APR_RING_HEAD declaration.
00064  *
00065  * @warning For strict C standards compliance you should put the APR_RING_ENTRY
00066  * first in the element struct unless the head is always part of a larger
00067  * object with enough earlier fields to accommodate the offsetof() used
00068  * to compute the ring sentinel below. You can usually ignore this caveat.
00069  */
00070 #define APR_RING_ENTRY(elem)                                            \
00071     struct {                                                            \
00072         struct elem * volatile next;                                    \
00073         struct elem * volatile prev;                                    \
00074     }
00075 
00076 /**
00077  * The Ring Head
00078  *
00079  * Each ring is managed via its head, which is a struct declared like this:
00080  * <pre>
00081  *      APR_RING_HEAD(my_ring_t, my_element_t);
00082  *      struct my_ring_t ring, *ringp;
00083  * </pre>
00084  *
00085  * This struct looks just like the element link struct so that we can
00086  * be sure that the typecasting games will work as expected.
00087  *
00088  * The first element in the ring is next after the head, and the last
00089  * element is just before the head.
00090  */
00091 #define APR_RING_HEAD(head, elem)                                       \
00092     struct head {                                                       \
00093         struct elem * volatile next;                                    \
00094         struct elem * volatile prev;                                    \
00095     }
00096 
00097 /**
00098  * The Ring Sentinel
00099  *
00100  * This is the magic pointer value that occurs before the first and
00101  * after the last elements in the ring, computed from the address of
00102  * the ring's head.  The head itself isn't an element, but in order to
00103  * get rid of all the special cases when dealing with the ends of the
00104  * ring, we play typecasting games to make it look like one.
00105  *
00106  * Here is a diagram to illustrate the arrangements of the next and
00107  * prev pointers of each element in a single ring. Note that they point
00108  * to the start of each element, not to the APR_RING_ENTRY structure.
00109  *
00110  * <pre>
00111  *     +->+------+<-+  +->+------+<-+  +->+------+<-+
00112  *     |  |struct|  |  |  |struct|  |  |  |struct|  |
00113  *    /   | elem |   \/   | elem |   \/   | elem |  \
00114  * ...    |      |   /\   |      |   /\   |      |   ...
00115  *        +------+  |  |  +------+  |  |  +------+
00116  *   ...--|prev  |  |  +--|ring  |  |  +--|prev  |
00117  *        |  next|--+     | entry|--+     |  next|--...
00118  *        +------+        +------+        +------+
00119  *        | etc. |        | etc. |        | etc. |
00120  *        :      :        :      :        :      :
00121  * </pre>
00122  *
00123  * The APR_RING_HEAD is nothing but a bare APR_RING_ENTRY. The prev
00124  * and next pointers in the first and last elements don't actually
00125  * point to the head, they point to a phantom place called the
00126  * sentinel. Its value is such that last->next->next == first because
00127  * the offset from the sentinel to the head's next pointer is the same
00128  * as the offset from the start of an element to its next pointer.
00129  * This also works in the opposite direction.
00130  *
00131  * <pre>
00132  *        last                            first
00133  *     +->+------+<-+  +->sentinel<-+  +->+------+<-+
00134  *     |  |struct|  |  |            |  |  |struct|  |
00135  *    /   | elem |   \/              \/   | elem |  \
00136  * ...    |      |   /\              /\   |      |   ...
00137  *        +------+  |  |  +------+  |  |  +------+
00138  *   ...--|prev  |  |  +--|ring  |  |  +--|prev  |
00139  *        |  next|--+     |  head|--+     |  next|--...
00140  *        +------+        +------+        +------+
00141  *        | etc. |                        | etc. |
00142  *        :      :                        :      :
00143  * </pre>
00144  *
00145  * Note that the offset mentioned above is different for each kind of
00146  * ring that the element may be on, and each kind of ring has a unique
00147  * name for its APR_RING_ENTRY in each element, and has its own type
00148  * for its APR_RING_HEAD.
00149  *
00150  * Note also that if the offset is non-zero (which is required if an
00151  * element has more than one APR_RING_ENTRY), the unreality of the
00152  * sentinel may have bad implications on very perverse implementations
00153  * of C -- see the warning in APR_RING_ENTRY.
00154  *
00155  * @param hp   The head of the ring
00156  * @param elem The name of the element struct
00157  * @param link The name of the APR_RING_ENTRY in the element struct
00158  */
00159 #define APR_RING_SENTINEL(hp, elem, link)                               \
00160     (struct elem *)((char *)(&(hp)->next) - APR_OFFSETOF(struct elem, link))
00161 
00162 /**
00163  * The first element of the ring
00164  * @param hp   The head of the ring
00165  */
00166 #define APR_RING_FIRST(hp)      (hp)->next
00167 /**
00168  * The last element of the ring
00169  * @param hp   The head of the ring
00170  */
00171 #define APR_RING_LAST(hp)       (hp)->prev
00172 /**
00173  * The next element in the ring
00174  * @param ep   The current element
00175  * @param link The name of the APR_RING_ENTRY in the element struct
00176  */
00177 #define APR_RING_NEXT(ep, link) (ep)->link.next
00178 /**
00179  * The previous element in the ring
00180  * @param ep   The current element
00181  * @param link The name of the APR_RING_ENTRY in the element struct
00182  */
00183 #define APR_RING_PREV(ep, link) (ep)->link.prev
00184 
00185 
00186 /**
00187  * Initialize a ring
00188  * @param hp   The head of the ring
00189  * @param elem The name of the element struct
00190  * @param link The name of the APR_RING_ENTRY in the element struct
00191  */
00192 #define APR_RING_INIT(hp, elem, link) do {                              \
00193         APR_RING_FIRST((hp)) = APR_RING_SENTINEL((hp), elem, link);     \
00194         APR_RING_LAST((hp))  = APR_RING_SENTINEL((hp), elem, link);     \
00195     } while (0)
00196 
00197 /**
00198  * Determine if a ring is empty
00199  * @param hp   The head of the ring
00200  * @param elem The name of the element struct
00201  * @param link The name of the APR_RING_ENTRY in the element struct
00202  * @return true or false
00203  */
00204 #define APR_RING_EMPTY(hp, elem, link)                                  \
00205     (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))
00206 
00207 /**
00208  * Initialize a singleton element
00209  * @param ep   The element
00210  * @param link The name of the APR_RING_ENTRY in the element struct
00211  */
00212 #define APR_RING_ELEM_INIT(ep, link) do {                               \
00213         APR_RING_NEXT((ep), link) = (ep);                               \
00214         APR_RING_PREV((ep), link) = (ep);                               \
00215     } while (0)
00216 
00217 
00218 /**
00219  * Splice the sequence ep1..epN into the ring before element lep
00220  *   (..lep.. becomes ..ep1..epN..lep..)
00221  * @warning This doesn't work for splicing before the first element or on
00222  *   empty rings... see APR_RING_SPLICE_HEAD for one that does
00223  * @param lep  Element in the ring to splice before
00224  * @param ep1  First element in the sequence to splice in
00225  * @param epN  Last element in the sequence to splice in
00226  * @param link The name of the APR_RING_ENTRY in the element struct
00227  */
00228 #define APR_RING_SPLICE_BEFORE(lep, ep1, epN, link) do {                \
00229         APR_RING_NEXT((epN), link) = (lep);                             \
00230         APR_RING_PREV((ep1), link) = APR_RING_PREV((lep), link);        \
00231         APR_RING_NEXT(APR_RING_PREV((lep), link), link) = (ep1);        \
00232         APR_RING_PREV((lep), link) = (epN);                             \
00233     } while (0)
00234 
00235 /**
00236  * Splice the sequence ep1..epN into the ring after element lep
00237  *   (..lep.. becomes ..lep..ep1..epN..)
00238  * @warning This doesn't work for splicing after the last element or on
00239  *   empty rings... see APR_RING_SPLICE_TAIL for one that does
00240  * @param lep  Element in the ring to splice after
00241  * @param ep1  First element in the sequence to splice in
00242  * @param epN  Last element in the sequence to splice in
00243  * @param link The name of the APR_RING_ENTRY in the element struct
00244  */
00245 #define APR_RING_SPLICE_AFTER(lep, ep1, epN, link) do {                 \
00246         APR_RING_PREV((ep1), link) = (lep);                             \
00247         APR_RING_NEXT((epN), link) = APR_RING_NEXT((lep), link);        \
00248         APR_RING_PREV(APR_RING_NEXT((lep), link), link) = (epN);        \
00249         APR_RING_NEXT((lep), link) = (ep1);                             \
00250     } while (0)
00251 
00252 /**
00253  * Insert the element nep into the ring before element lep
00254  *   (..lep.. becomes ..nep..lep..)
00255  * @warning This doesn't work for inserting before the first element or on
00256  *   empty rings... see APR_RING_INSERT_HEAD for one that does
00257  * @param lep  Element in the ring to insert before
00258  * @param nep  Element to insert
00259  * @param link The name of the APR_RING_ENTRY in the element struct
00260  */
00261 #define APR_RING_INSERT_BEFORE(lep, nep, link)                          \
00262         APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link)
00263 
00264 /**
00265  * Insert the element nep into the ring after element lep
00266  *   (..lep.. becomes ..lep..nep..)
00267  * @warning This doesn't work for inserting after the last element or on
00268  *   empty rings... see APR_RING_INSERT_TAIL for one that does
00269  * @param lep  Element in the ring to insert after
00270  * @param nep  Element to insert
00271  * @param link The name of the APR_RING_ENTRY in the element struct
00272  */
00273 #define APR_RING_INSERT_AFTER(lep, nep, link)                           \
00274         APR_RING_SPLICE_AFTER((lep), (nep), (nep), link)
00275 
00276 
00277 /**
00278  * Splice the sequence ep1..epN into the ring before the first element
00279  *   (..hp.. becomes ..hp..ep1..epN..)
00280  * @param hp   Head of the ring
00281  * @param ep1  First element in the sequence to splice in
00282  * @param epN  Last element in the sequence to splice in
00283  * @param elem The name of the element struct
00284  * @param link The name of the APR_RING_ENTRY in the element struct
00285  */
00286 #define APR_RING_SPLICE_HEAD(hp, ep1, epN, elem, link)                  \
00287         APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((hp), elem, link),      \
00288                              (ep1), (epN), link)
00289 
00290 /**
00291  * Splice the sequence ep1..epN into the ring after the last element
00292  *   (..hp.. becomes ..ep1..epN..hp..)
00293  * @param hp   Head of the ring
00294  * @param ep1  First element in the sequence to splice in
00295  * @param epN  Last element in the sequence to splice in
00296  * @param elem The name of the element struct
00297  * @param link The name of the APR_RING_ENTRY in the element struct
00298  */
00299 #define APR_RING_SPLICE_TAIL(hp, ep1, epN, elem, link)                  \
00300         APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((hp), elem, link),     \
00301                              (ep1), (epN), link)
00302 
00303 /**
00304  * Insert the element nep into the ring before the first element
00305  *   (..hp.. becomes ..hp..nep..)
00306  * @param hp   Head of the ring
00307  * @param nep  Element to insert
00308  * @param elem The name of the element struct
00309  * @param link The name of the APR_RING_ENTRY in the element struct
00310  */
00311 #define APR_RING_INSERT_HEAD(hp, nep, elem, link)                       \
00312         APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link)
00313 
00314 /**
00315  * Insert the element nep into the ring after the last element
00316  *   (..hp.. becomes ..nep..hp..)
00317  * @param hp   Head of the ring
00318  * @param nep  Element to insert
00319  * @param elem The name of the element struct
00320  * @param link The name of the APR_RING_ENTRY in the element struct
00321  */
00322 #define APR_RING_INSERT_TAIL(hp, nep, elem, link)                       \
00323         APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link)
00324 
00325 /**
00326  * Concatenate ring h2 onto the end of ring h1, leaving h2 empty.
00327  * @param h1   Head of the ring to concatenate onto
00328  * @param h2   Head of the ring to concatenate
00329  * @param elem The name of the element struct
00330  * @param link The name of the APR_RING_ENTRY in the element struct
00331  */
00332 #define APR_RING_CONCAT(h1, h2, elem, link) do {                        \
00333         if (!APR_RING_EMPTY((h2), elem, link)) {                        \
00334             APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((h1), elem, link), \
00335                                   APR_RING_FIRST((h2)),                 \
00336                                   APR_RING_LAST((h2)), link);           \
00337             APR_RING_INIT((h2), elem, link);                            \
00338         }                                                               \
00339     } while (0)
00340 
00341 /**
00342  * Prepend ring h2 onto the beginning of ring h1, leaving h2 empty.
00343  * @param h1   Head of the ring to prepend onto
00344  * @param h2   Head of the ring to prepend
00345  * @param elem The name of the element struct
00346  * @param link The name of the APR_RING_ENTRY in the element struct
00347  */
00348 #define APR_RING_PREPEND(h1, h2, elem, link) do {                       \
00349         if (!APR_RING_EMPTY((h2), elem, link)) {                        \
00350             APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((h1), elem, link),  \
00351                                   APR_RING_FIRST((h2)),                 \
00352                                   APR_RING_LAST((h2)), link);           \
00353             APR_RING_INIT((h2), elem, link);                            \
00354         }                                                               \
00355     } while (0)
00356 
00357 /**
00358  * Unsplice a sequence of elements from a ring
00359  * @warning The unspliced sequence is left with dangling pointers at either end
00360  * @param ep1  First element in the sequence to unsplice
00361  * @param epN  Last element in the sequence to unsplice
00362  * @param link The name of the APR_RING_ENTRY in the element struct
00363  */
00364 #define APR_RING_UNSPLICE(ep1, epN, link) do {                          \
00365         APR_RING_NEXT(APR_RING_PREV((ep1), link), link) =               \
00366                      APR_RING_NEXT((epN), link);                        \
00367         APR_RING_PREV(APR_RING_NEXT((epN), link), link) =               \
00368                      APR_RING_PREV((ep1), link);                        \
00369     } while (0)
00370 
00371 /**
00372  * Remove a single element from a ring
00373  * @warning The unspliced element is left with dangling pointers at either end
00374  * @param ep   Element to remove
00375  * @param link The name of the APR_RING_ENTRY in the element struct
00376  */
00377 #define APR_RING_REMOVE(ep, link)                                       \
00378     APR_RING_UNSPLICE((ep), (ep), link)
00379 
00380 /**
00381  * Iterate over a ring
00382  * @param ep The current element
00383  * @param head The head of the ring
00384  * @param elem The name of the element struct
00385  * @param link The name of the APR_RING_ENTRY in the element struct
00386  */
00387 #define APR_RING_FOREACH(ep, head, elem, link)                          \
00388     for (ep = APR_RING_FIRST(head);                                     \
00389          ep != APR_RING_SENTINEL(head, elem, link);                     \
00390          ep = APR_RING_NEXT(ep, link))
00391 
00392 /**
00393  * Iterate over a ring safe against removal of the current element
00394  * @param ep1 The current element
00395  * @param ep2 Iteration cursor
00396  * @param head The head of the ring
00397  * @param elem The name of the element struct
00398  * @param link The name of the APR_RING_ENTRY in the element struct
00399  */
00400 #define APR_RING_FOREACH_SAFE(ep1, ep2, head, elem, link)               \
00401     for (ep1 = APR_RING_FIRST(head), ep2 = APR_RING_NEXT(ep1, link);    \
00402          ep1 != APR_RING_SENTINEL(head, elem, link);                    \
00403          ep1 = ep2, ep2 = APR_RING_NEXT(ep1, link))
00404 
00405 /* Debugging tools: */
00406 
00407 #ifdef APR_RING_DEBUG
00408 #include <stdio.h>
00409 #include <assert.h>
00410 
00411 #define APR_RING_CHECK_ONE(msg, ptr)                                    \
00412         fprintf(stderr, "*** %s %p\n", msg, ptr)
00413 
00414 #define APR_RING_CHECK(hp, elem, link, msg)                             \
00415         APR_RING_CHECK_ELEM(APR_RING_SENTINEL(hp, elem, link), elem, link, msg)
00416 
00417 #define APR_RING_CHECK_ELEM(ep, elem, link, msg) do {                   \
00418         struct elem *start = (ep);                                      \
00419         struct elem *here = start;                                      \
00420         fprintf(stderr, "*** ring check start -- %s\n", msg);           \
00421         do {                                                            \
00422             fprintf(stderr, "\telem %p\n", here);                       \
00423             fprintf(stderr, "\telem->next %p\n",                        \
00424                     APR_RING_NEXT(here, link));                         \
00425             fprintf(stderr, "\telem->prev %p\n",                        \
00426                     APR_RING_PREV(here, link));                         \
00427             fprintf(stderr, "\telem->next->prev %p\n",                  \
00428                     APR_RING_PREV(APR_RING_NEXT(here, link), link));    \
00429             fprintf(stderr, "\telem->prev->next %p\n",                  \
00430                     APR_RING_NEXT(APR_RING_PREV(here, link), link));    \
00431             if (APR_RING_PREV(APR_RING_NEXT(here, link), link) != here) { \
00432                 fprintf(stderr, "\t*** elem->next->prev != elem\n");    \
00433                 break;                                                  \
00434             }                                                           \
00435             if (APR_RING_NEXT(APR_RING_PREV(here, link), link) != here) { \
00436                 fprintf(stderr, "\t*** elem->prev->next != elem\n");    \
00437                 break;                                                  \
00438             }                                                           \
00439             here = APR_RING_NEXT(here, link);                           \
00440         } while (here != start);                                        \
00441         fprintf(stderr, "*** ring check end\n");                        \
00442     } while (0)
00443 
00444 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)                      \
00445         APR_RING_CHECK_ELEM_CONSISTENCY(APR_RING_SENTINEL(hp, elem, link),\
00446                                         elem, link)
00447 
00448 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link) do {            \
00449         struct elem *start = (ep);                                      \
00450         struct elem *here = start;                                      \
00451         do {                                                            \
00452             assert(APR_RING_PREV(APR_RING_NEXT(here, link), link) == here); \
00453             assert(APR_RING_NEXT(APR_RING_PREV(here, link), link) == here); \
00454             here = APR_RING_NEXT(here, link);                           \
00455         } while (here != start);                                        \
00456     } while (0)
00457 
00458 #else
00459 /**
00460  * Print a single pointer value to STDERR
00461  *   (This is a no-op unless APR_RING_DEBUG is defined.)
00462  * @param msg Descriptive message
00463  * @param ptr Pointer value to print
00464  */
00465 #define APR_RING_CHECK_ONE(msg, ptr)
00466 /**
00467  * Dump all ring pointers to STDERR, starting with the head and looping all
00468  * the way around the ring back to the head.  Aborts if an inconsistency
00469  * is found.
00470  *   (This is a no-op unless APR_RING_DEBUG is defined.)
00471  * @param hp   Head of the ring
00472  * @param elem The name of the element struct
00473  * @param link The name of the APR_RING_ENTRY in the element struct
00474  * @param msg  Descriptive message
00475  */
00476 #define APR_RING_CHECK(hp, elem, link, msg)
00477 /**
00478  * Loops around a ring and checks all the pointers for consistency.  Pops
00479  * an assertion if any inconsistency is found.  Same idea as APR_RING_CHECK()
00480  * except that it's silent if all is well.
00481  *   (This is a no-op unless APR_RING_DEBUG is defined.)
00482  * @param hp   Head of the ring
00483  * @param elem The name of the element struct
00484  * @param link The name of the APR_RING_ENTRY in the element struct
00485  */
00486 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)
00487 /**
00488  * Dump all ring pointers to STDERR, starting with the given element and
00489  * looping all the way around the ring back to that element.  Aborts if
00490  * an inconsistency is found.
00491  *   (This is a no-op unless APR_RING_DEBUG is defined.)
00492  * @param ep   The element
00493  * @param elem The name of the element struct
00494  * @param link The name of the APR_RING_ENTRY in the element struct
00495  * @param msg  Descriptive message
00496  */
00497 #define APR_RING_CHECK_ELEM(ep, elem, link, msg)
00498 /**
00499  * Loops around a ring, starting with the given element, and checks all
00500  * the pointers for consistency.  Pops an assertion if any inconsistency
00501  * is found.  Same idea as APR_RING_CHECK_ELEM() except that it's silent
00502  * if all is well.
00503  *   (This is a no-op unless APR_RING_DEBUG is defined.)
00504  * @param ep   The element
00505  * @param elem The name of the element struct
00506  * @param link The name of the APR_RING_ENTRY in the element struct
00507  */
00508 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link)
00509 #endif
00510 
00511 /** @} */ 
00512 
00513 #endif /* !APR_RING_H */
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines