Main Page | Modules | Data Structures | File List | Data Fields | Globals | Related Pages

apr_ring.h

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

Generated on Tue May 10 04:19:07 2005 for Apache Portable Runtime by  doxygen 1.3.9.1