GME  13
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 
00035 /*
00036  * for offsetof()
00037  */
00038 #include "apr_general.h"
00039 
00070 #define APR_RING_ENTRY(elem)                                            \
00071     struct {                                                            \
00072         struct elem * volatile next;                                    \
00073         struct elem * volatile prev;                                    \
00074     }
00075 
00091 #define APR_RING_HEAD(head, elem)                                       \
00092     struct head {                                                       \
00093         struct elem * volatile next;                                    \
00094         struct elem * volatile prev;                                    \
00095     }
00096 
00159 #define APR_RING_SENTINEL(hp, elem, link)                               \
00160     (struct elem *)((char *)(&(hp)->next) - APR_OFFSETOF(struct elem, link))
00161 
00166 #define APR_RING_FIRST(hp)      (hp)->next
00167 
00171 #define APR_RING_LAST(hp)       (hp)->prev
00172 
00177 #define APR_RING_NEXT(ep, link) (ep)->link.next
00178 
00183 #define APR_RING_PREV(ep, link) (ep)->link.prev
00184 
00185 
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 
00204 #define APR_RING_EMPTY(hp, elem, link)                                  \
00205     (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))
00206 
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 
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 
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 
00261 #define APR_RING_INSERT_BEFORE(lep, nep, link)                          \
00262         APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link)
00263 
00273 #define APR_RING_INSERT_AFTER(lep, nep, link)                           \
00274         APR_RING_SPLICE_AFTER((lep), (nep), (nep), link)
00275 
00276 
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 
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 
00311 #define APR_RING_INSERT_HEAD(hp, nep, elem, link)                       \
00312         APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link)
00313 
00322 #define APR_RING_INSERT_TAIL(hp, nep, elem, link)                       \
00323         APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link)
00324 
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 
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 
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 
00377 #define APR_RING_REMOVE(ep, link)                                       \
00378     APR_RING_UNSPLICE((ep), (ep), link)
00379 
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 
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 
00465 #define APR_RING_CHECK_ONE(msg, ptr)
00466 
00476 #define APR_RING_CHECK(hp, elem, link, msg)
00477 
00486 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)
00487 
00497 #define APR_RING_CHECK_ELEM(ep, elem, link, msg)
00498 
00508 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link)
00509 #endif
00510 
00513 #endif /* !APR_RING_H */