Apache Portable Runtime: apr_ring.h Source 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 *next;                                              \
00073         struct elem *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) - 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 
00380 
00424 #define APR_RING_FOREACH(ep, hp, elem, link)                            \
00425     for ((ep)  = APR_RING_FIRST((hp));                                  \
00426          (ep) != APR_RING_SENTINEL((hp), elem, link);                   \
00427          (ep)  = APR_RING_NEXT((ep), link))
00428 
00437 #define APR_RING_FOREACH_REVERSE(ep, hp, elem, link)                    \
00438     for ((ep)  = APR_RING_LAST((hp));                                   \
00439          (ep) != APR_RING_SENTINEL((hp), elem, link);                   \
00440          (ep)  = APR_RING_PREV((ep), link))
00441 
00442 
00443 /* Debugging tools: */
00444 
00445 #ifdef APR_RING_DEBUG
00446 #include <stdio.h>
00447 #include <assert.h>
00448 
00449 #define APR_RING_CHECK_ONE(msg, ptr)                                    \
00450         fprintf(stderr, "*** %s %p\n", msg, ptr)
00451 
00452 #define APR_RING_CHECK(hp, elem, link, msg)                             \
00453         APR_RING_CHECK_ELEM(APR_RING_SENTINEL(hp, elem, link), elem, link, msg)
00454 
00455 #define APR_RING_CHECK_ELEM(ep, elem, link, msg) do {                   \
00456         struct elem *start = (ep);                                      \
00457         struct elem *here = start;                                      \
00458         fprintf(stderr, "*** ring check start -- %s\n", msg);           \
00459         do {                                                            \
00460             fprintf(stderr, "\telem %p\n", here);                       \
00461             fprintf(stderr, "\telem->next %p\n",                        \
00462                     APR_RING_NEXT(here, link));                         \
00463             fprintf(stderr, "\telem->prev %p\n",                        \
00464                     APR_RING_PREV(here, link));                         \
00465             fprintf(stderr, "\telem->next->prev %p\n",                  \
00466                     APR_RING_PREV(APR_RING_NEXT(here, link), link));    \
00467             fprintf(stderr, "\telem->prev->next %p\n",                  \
00468                     APR_RING_NEXT(APR_RING_PREV(here, link), link));    \
00469             if (APR_RING_PREV(APR_RING_NEXT(here, link), link) != here) { \
00470                 fprintf(stderr, "\t*** elem->next->prev != elem\n");    \
00471                 break;                                                  \
00472             }                                                           \
00473             if (APR_RING_NEXT(APR_RING_PREV(here, link), link) != here) { \
00474                 fprintf(stderr, "\t*** elem->prev->next != elem\n");    \
00475                 break;                                                  \
00476             }                                                           \
00477             here = APR_RING_NEXT(here, link);                           \
00478         } while (here != start);                                        \
00479         fprintf(stderr, "*** ring check end\n");                        \
00480     } while (0)
00481 
00482 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)                      \
00483         APR_RING_CHECK_ELEM_CONSISTENCY(APR_RING_SENTINEL(hp, elem, link),\
00484                                         elem, link)
00485 
00486 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link) do {            \
00487         struct elem *start = (ep);                                      \
00488         struct elem *here = start;                                      \
00489         do {                                                            \
00490             assert(APR_RING_PREV(APR_RING_NEXT(here, link), link) == here); \
00491             assert(APR_RING_NEXT(APR_RING_PREV(here, link), link) == here); \
00492             here = APR_RING_NEXT(here, link);                           \
00493         } while (here != start);                                        \
00494     } while (0)
00495 
00496 #else
00497 
00503 #define APR_RING_CHECK_ONE(msg, ptr)
00504 
00514 #define APR_RING_CHECK(hp, elem, link, msg)
00515 
00524 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)
00525 
00535 #define APR_RING_CHECK_ELEM(ep, elem, link, msg)
00536 
00546 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link)
00547 #endif
00548 
00551 #endif /* !APR_RING_H */