| /* ==================================================================== |
| * The Apache Software License, Version 1.1 |
| * |
| * Copyright (c) 2000-2001 The Apache Software Foundation. All rights |
| * reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in |
| * the documentation and/or other materials provided with the |
| * distribution. |
| * |
| * 3. The end-user documentation included with the redistribution, |
| * if any, must include the following acknowledgment: |
| * "This product includes software developed by the |
| * Apache Software Foundation (http://www.apache.org/)." |
| * Alternately, this acknowledgment may appear in the software itself, |
| * if and wherever such third-party acknowledgments normally appear. |
| * |
| * 4. The names "Apache" and "Apache Software Foundation" must |
| * not be used to endorse or promote products derived from this |
| * software without prior written permission. For written |
| * permission, please contact apache@apache.org. |
| * |
| * 5. Products derived from this software may not be called "Apache", |
| * nor may "Apache" appear in their name, without prior written |
| * permission of the Apache Software Foundation. |
| * |
| * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED |
| * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
| * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR |
| * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF |
| * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
| * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, |
| * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT |
| * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| * SUCH DAMAGE. |
| * ==================================================================== |
| * |
| * This software consists of voluntary contributions made by many |
| * individuals on behalf of the Apache Software Foundation. For more |
| * information on the Apache Software Foundation, please see |
| * <http://www.apache.org/>. |
| */ |
| |
| /* |
| * This code draws heavily from the 4.4BSD <sys/queue.h> macros |
| * and Dean Gaudet's "splim/ring.h". |
| * <http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/queue.h> |
| * <http://www.arctic.org/~dean/splim/> |
| * |
| * We'd use Dean's code directly if we could guarantee the |
| * availability of inline functions. |
| */ |
| |
| #ifndef APR_RING_H |
| #define APR_RING_H |
| |
| /* |
| * for offsetof() |
| */ |
| #include <stddef.h> |
| |
| /** |
| * @package Rings |
| */ |
| /* |
| * A ring is a kind of doubly-linked list that can be manipulated |
| * without knowing where its head is. |
| */ |
| |
| /** |
| * <p>The Ring Element</p> |
| * |
| * A ring element struct is linked to the other elements in the ring |
| * through its ring entry field, e.g. |
| * <pre> |
| * struct my_element_t { |
| * APR_RING_ENTRY(my_element_t) link; |
| * int foo; |
| * char *bar; |
| * }; |
| * </pre> |
| * An element struct may be put on more than one ring if it has |
| * more than one APR_RING_ENTRY field. |
| * |
| * @warning For strict C standards compliance you should put the APR_RING_ENTRY |
| * first in the element struct unless the head is always part of a larger |
| * object with enough earlier fields to accommodate the offsetof() used |
| * to compute the ring sentinel below. You can usually ignore this caveat. |
| * @defvar APR_RING_ENTRY |
| */ |
| #define APR_RING_ENTRY(elem) \ |
| struct { \ |
| struct elem *next; \ |
| struct elem *prev; \ |
| } |
| |
| /** |
| * <p>The Ring Head</p> |
| * |
| * Each ring is managed via its head, which is a struct declared like this: |
| * <pre> |
| * APR_RING_HEAD(my_ring_t, my_element_t); |
| * struct my_ring_t ring, *ringp; |
| * </pre> |
| * |
| * This struct looks just like the element link struct so that we can |
| * be sure that the typecasting games will work as expected. |
| * |
| * The first element in the ring is next after the head, and the last |
| * element is just before the head. |
| * @defvar APR_RING_HEAD |
| */ |
| #define APR_RING_HEAD(head, elem) \ |
| struct head { \ |
| struct elem *next; \ |
| struct elem *prev; \ |
| } |
| |
| /** |
| * <p>The Ring Sentinel</p> |
| * |
| * This is the magic pointer value that occurs before the first and |
| * after the last elements in the ring, computed from the address of |
| * the ring's head. The head itself isn't an element, but in order to |
| * get rid of all the special cases when dealing with the ends of the |
| * ring, we play typecasting games to make it look like one. |
| * |
| * @param hp The head of the ring |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc elem *APR_RING_SENTINEL(head *hp, struct elem, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_SENTINEL(hp, elem, link) \ |
| (struct elem *)((char *)(hp) - offsetof(struct elem, link)) |
| |
| /** |
| * The first element of the ring |
| * @param hp The head of the ring |
| * @deffunc elem *APR_RING_FIRST(head *hp) |
| */ |
| #define APR_RING_FIRST(hp) (hp)->next |
| /** |
| * The last element of the ring |
| * @param hp The head of the ring |
| * @deffunc elem *APR_RING_LAST(head *hp) |
| */ |
| #define APR_RING_LAST(hp) (hp)->prev |
| /** |
| * The next element in the ring |
| * @param ep The current element |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc elem *APR_RING_NEXT(elem *ep, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_NEXT(ep, link) (ep)->link.next |
| /** |
| * The previous element in the ring |
| * @param ep The current element |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc elem *APR_RING_PREV(elem *ep, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_PREV(ep, link) (ep)->link.prev |
| |
| |
| /** |
| * Initialize a ring |
| * @param hp The head of the ring |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_INIT(head *hp, struct elem, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_INIT(hp, elem, link) do { \ |
| APR_RING_FIRST((hp)) = APR_RING_SENTINEL((hp), elem, link); \ |
| APR_RING_LAST((hp)) = APR_RING_SENTINEL((hp), elem, link); \ |
| } while (0) |
| |
| /** |
| * Determine if a ring is empty |
| * @param hp The head of the ring |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @return true or false |
| * @deffunc int APR_RING_EMPTY(head *hp, struct elem, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_EMPTY(hp, elem, link) \ |
| (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link)) |
| |
| /** |
| * Initialize a singleton element |
| * @param ep The element |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_ELEM_INIT(elem *ep, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_ELEM_INIT(ep, link) do { \ |
| APR_RING_NEXT((ep), link) = (ep); \ |
| APR_RING_PREV((ep), link) = (ep); \ |
| } while (0) |
| |
| |
| /** |
| * Splice the sequence ep1..epN into the ring before element lep |
| * (..lep.. becomes ..ep1..epN..lep..) |
| * @warning This doesn't work for splicing before the first element or on |
| * empty rings... see APR_RING_SPLICE_HEAD for one that does |
| * @param lep Element in the ring to splice before |
| * @param ep1 First element in the sequence to splice in |
| * @param epN Last element in the sequence to splice in |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_SPLICE_BEFORE(elem *lep, elem *ep1, elem *epN, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_SPLICE_BEFORE(lep, ep1, epN, link) do { \ |
| APR_RING_NEXT((epN), link) = (lep); \ |
| APR_RING_PREV((ep1), link) = APR_RING_PREV((lep), link); \ |
| APR_RING_NEXT(APR_RING_PREV((lep), link), link) = (ep1); \ |
| APR_RING_PREV((lep), link) = (epN); \ |
| } while (0) |
| |
| /** |
| * Splice the sequence ep1..epN into the ring after element lep |
| * (..lep.. becomes ..lep..ep1..epN..) |
| * @warning This doesn't work for splicing after the last element or on |
| * empty rings... see APR_RING_SPLICE_TAIL for one that does |
| * @param lep Element in the ring to splice after |
| * @param ep1 First element in the sequence to splice in |
| * @param epN Last element in the sequence to splice in |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_SPLICE_AFTER(elem *lep, elem *ep1, elem *epN, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_SPLICE_AFTER(lep, ep1, epN, link) do { \ |
| APR_RING_PREV((ep1), link) = (lep); \ |
| APR_RING_NEXT((epN), link) = APR_RING_NEXT((lep), link); \ |
| APR_RING_PREV(APR_RING_NEXT((lep), link), link) = (epN); \ |
| APR_RING_NEXT((lep), link) = (ep1); \ |
| } while (0) |
| |
| /** |
| * Insert the element nep into the ring before element lep |
| * (..lep.. becomes ..nep..lep..) |
| * @warning This doesn't work for inserting before the first element or on |
| * empty rings... see APR_RING_INSERT_HEAD for one that does |
| * @param lep Element in the ring to insert before |
| * @param nep Element to insert |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_INSERT_BEFORE(elem *lep, elem *nep, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_INSERT_BEFORE(lep, nep, link) \ |
| APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link) |
| |
| /** |
| * Insert the element nep into the ring after element lep |
| * (..lep.. becomes ..lep..nep..) |
| * @warning This doesn't work for inserting after the last element or on |
| * empty rings... see APR_RING_INSERT_TAIL for one that does |
| * @param lep Element in the ring to insert after |
| * @param nep Element to insert |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_INSERT_AFTER(elem *lep, elem *nep, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_INSERT_AFTER(lep, nep, link) \ |
| APR_RING_SPLICE_AFTER((lep), (nep), (nep), link) |
| |
| |
| /** |
| * Splice the sequence ep1..epN into the ring before the first element |
| * (..hp.. becomes ..hp..ep1..epN..) |
| * @param hp Head of the ring |
| * @param ep1 First element in the sequence to splice in |
| * @param epN Last element in the sequence to splice in |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_SPLICE_HEAD(head *hp, elem *ep1, elem *epN, struct elem, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_SPLICE_HEAD(hp, ep1, epN, elem, link) \ |
| APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((hp), elem, link), \ |
| (ep1), (epN), link) |
| |
| /** |
| * Splice the sequence ep1..epN into the ring after the last element |
| * (..hp.. becomes ..ep1..epN..hp..) |
| * @param hp Head of the ring |
| * @param ep1 First element in the sequence to splice in |
| * @param epN Last element in the sequence to splice in |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_SPLICE_TAIL(head *hp, elem *ep1, elem *epN, struct elem, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_SPLICE_TAIL(hp, ep1, epN, elem, link) \ |
| APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((hp), elem, link), \ |
| (ep1), (epN), link) |
| |
| /** |
| * Insert the element nep into the ring before the first element |
| * (..hp.. becomes ..hp..nep..) |
| * @param hp Head of the ring |
| * @param nep Element to insert |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_INSERT_HEAD(head *hp, elem *nep, struct elem, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_INSERT_HEAD(hp, nep, elem, link) \ |
| APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link) |
| |
| /** |
| * Insert the element nep into the ring after the last element |
| * (..hp.. becomes ..nep..hp..) |
| * @param hp Head of the ring |
| * @param nep Element to insert |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_INSERT_TAIL(head *hp, elem *nep, struct elem, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_INSERT_TAIL(hp, nep, elem, link) \ |
| APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link) |
| |
| /** |
| * Concatenate ring h2 onto the end of ring h1, leaving h2 empty. |
| * @param h1 Head of the ring to concatenate onto |
| * @param h2 Head of the ring to concatenate |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_CONCAT(head *h1, head *h2, struct elem, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_CONCAT(h1, h2, elem, link) do { \ |
| if (!APR_RING_EMPTY((h2), elem, link)) { \ |
| APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((h1), elem, link), \ |
| APR_RING_FIRST((h2)), \ |
| APR_RING_LAST((h2)), link); \ |
| APR_RING_INIT((h2), elem, link); \ |
| } \ |
| } while (0) |
| |
| |
| /** |
| * Unsplice a sequence of elements from a ring |
| * @warning The unspliced sequence is left with dangling pointers at either end |
| * @param ep1 First element in the sequence to unsplice |
| * @param epN Last element in the sequence to unsplice |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_UNSPLICE(elem *ep1, elem *epN, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_UNSPLICE(ep1, epN, link) do { \ |
| APR_RING_NEXT(APR_RING_PREV((ep1), link), link) = \ |
| APR_RING_NEXT((epN), link); \ |
| APR_RING_PREV(APR_RING_NEXT((epN), link), link) = \ |
| APR_RING_PREV((ep1), link); \ |
| } while (0) |
| |
| /** |
| * Remove a single element from a ring |
| * @warning The unspliced element is left with dangling pointers at either end |
| * @param ep Element to remove |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @deffunc void APR_RING_REMOVE(elem *ep, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_REMOVE(ep, link) \ |
| APR_RING_UNSPLICE((ep), (ep), link) |
| |
| |
| /** |
| * Iterate through a ring |
| * @param ep The current element |
| * @param hp The ring to iterate over |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @tip This is the same as either: |
| * <pre> |
| * ep = APR_RING_FIRST(hp); |
| * while (ep != APR_RING_SENTINEL(hp, elem, link)) { |
| * ... |
| * ep = APR_RING_NEXT(ep, link); |
| * } |
| * OR |
| * for (ep = APR_RING_FIRST(hp); |
| * ep != APR_RING_SENTINEL(hp, elem, link); |
| * ep = APR_RING_NEXT(ep, link)) { |
| * ... |
| * } |
| * </pre> |
| * @deffunc void APR_RING_FOREACH(elem *ep, head *hp, struct elem, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_FOREACH(ep, hp, elem, link) \ |
| for ((ep) = APR_RING_FIRST((hp)); \ |
| (ep) != APR_RING_SENTINEL((hp), elem, link); \ |
| (ep) = APR_RING_NEXT((ep), link)) |
| |
| /** |
| * Iterate through a ring backwards |
| * @param ep The current element |
| * @param hp The ring to iterate over |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @see APR_RING_FOREACH |
| * @deffunc void APR_RING_FOREACH_REVERSE(elem *ep, head *hp, struct elem, APR_RING_ENTRY link) |
| */ |
| #define APR_RING_FOREACH_REVERSE(ep, hp, elem, link) \ |
| for ((ep) = APR_RING_LAST((hp)); \ |
| (ep) != APR_RING_SENTINEL((hp), elem, link); \ |
| (ep) = APR_RING_PREV((ep), link)) |
| |
| |
| /* Debugging tools: */ |
| |
| /** |
| * Print a single pointer value to STDERR |
| * (This is a no-op unless APR_RING_DEBUG is defined.) |
| * @param msg Descriptive message |
| * @param ptr Pointer value to print |
| * @deffunc void APR_RING_CHECK_ONE(char *msg, void *ptr) |
| */ |
| /** |
| * Dump all ring pointers to STDERR, starting with the head and looping all |
| * the way around the ring back to the head. Aborts if an inconsistency |
| * is found. |
| * (This is a no-op unless APR_RING_DEBUG is defined.) |
| * @param hp Head of the ring |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @param msg Descriptive message |
| * @deffunc void APR_RING_CHECK(head *hp, struct elem, APR_RING_ENTRY link, char *msg) |
| */ |
| /** |
| * Dump all ring pointers to STDERR, starting with the given element and |
| * looping all the way around the ring back to that element. Aborts if |
| * an inconsistency is found. |
| * (This is a no-op unless APR_RING_DEBUG is defined.) |
| * @param ep The element |
| * @param elem The name of the element struct |
| * @param link The name of the APR_RING_ENTRY in the element struct |
| * @param msg Descriptive message |
| * @deffunc void APR_RING_CHECK_ELEM(elem *ep, struct elem, APR_RING_ENTRY link, char *msg) |
| */ |
| #ifdef APR_RING_DEBUG |
| #include <stdio.h> |
| #define APR_RING_CHECK_ONE(msg, ptr) \ |
| fprintf(stderr, "*** %s %p\n", msg, ptr) |
| #define APR_RING_CHECK(hp, elem, link, msg) \ |
| APR_RING_CHECK_ELEM(APR_RING_SENTINEL(hp, elem, link), elem, link, msg) |
| #define APR_RING_CHECK_ELEM(ep, elem, link, msg) do { \ |
| struct elem *start = (ep); \ |
| struct elem *this = start; \ |
| fprintf(stderr, "*** ring check start -- %s\n", msg); \ |
| do { \ |
| fprintf(stderr, "\telem %p\n", this); \ |
| fprintf(stderr, "\telem->next %p\n", \ |
| APR_RING_NEXT(this, link)); \ |
| fprintf(stderr, "\telem->prev %p\n", \ |
| APR_RING_PREV(this, link)); \ |
| fprintf(stderr, "\telem->next->prev %p\n", \ |
| APR_RING_PREV(APR_RING_NEXT(this, link), link)); \ |
| fprintf(stderr, "\telem->prev->next %p\n", \ |
| APR_RING_NEXT(APR_RING_PREV(this, link), link)); \ |
| if (APR_RING_PREV(APR_RING_NEXT(this, link), link) != this) { \ |
| fprintf(stderr, "\t*** this->next->prev != this\n"); \ |
| break; \ |
| } \ |
| if (APR_RING_NEXT(APR_RING_PREV(this, link), link) != this) { \ |
| fprintf(stderr, "\t*** this->prev->next != this\n"); \ |
| break; \ |
| } \ |
| this = APR_RING_NEXT(this, link); \ |
| } while (this != start); \ |
| fprintf(stderr, "*** ring check end\n"); \ |
| } while (0) |
| #else |
| #define APR_RING_CHECK_ONE(msg, ptr) |
| #define APR_RING_CHECK(hp, elem, link, msg) |
| #define APR_RING_CHECK_ELEM(ep, elem, link, msg) |
| #endif |
| |
| #endif /* !APR_RING_H */ |