Annotation of win32/apache22/srclib/apr/include/apr_ring.h, revision 1.1
1.1 ! moko 1: /* Licensed to the Apache Software Foundation (ASF) under one or more
! 2: * contributor license agreements. See the NOTICE file distributed with
! 3: * this work for additional information regarding copyright ownership.
! 4: * The ASF licenses this file to You under the Apache License, Version 2.0
! 5: * (the "License"); you may not use this file except in compliance with
! 6: * the License. You may obtain a copy of the License at
! 7: *
! 8: * http://www.apache.org/licenses/LICENSE-2.0
! 9: *
! 10: * Unless required by applicable law or agreed to in writing, software
! 11: * distributed under the License is distributed on an "AS IS" BASIS,
! 12: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
! 13: * See the License for the specific language governing permissions and
! 14: * limitations under the License.
! 15: */
! 16:
! 17: /*
! 18: * This code draws heavily from the 4.4BSD <sys/queue.h> macros
! 19: * and Dean Gaudet's "splim/ring.h".
! 20: * <http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/queue.h>
! 21: * <http://www.arctic.org/~dean/splim/>
! 22: *
! 23: * We'd use Dean's code directly if we could guarantee the
! 24: * availability of inline functions.
! 25: */
! 26:
! 27: #ifndef APR_RING_H
! 28: #define APR_RING_H
! 29:
! 30: /**
! 31: * @file apr_ring.h
! 32: * @brief APR Rings
! 33: */
! 34:
! 35: /*
! 36: * for offsetof()
! 37: */
! 38: #include "apr_general.h"
! 39:
! 40: /**
! 41: * @defgroup apr_ring Ring Macro Implementations
! 42: * @ingroup APR
! 43: * A ring is a kind of doubly-linked list that can be manipulated
! 44: * without knowing where its head is.
! 45: * @{
! 46: */
! 47:
! 48: /**
! 49: * The Ring Element
! 50: *
! 51: * A ring element struct is linked to the other elements in the ring
! 52: * through its ring entry field, e.g.
! 53: * <pre>
! 54: * struct my_element_t {
! 55: * APR_RING_ENTRY(my_element_t) link;
! 56: * int foo;
! 57: * char *bar;
! 58: * };
! 59: * </pre>
! 60: *
! 61: * An element struct may be put on more than one ring if it has more
! 62: * than one APR_RING_ENTRY field. Each APR_RING_ENTRY has a corresponding
! 63: * APR_RING_HEAD declaration.
! 64: *
! 65: * @warning For strict C standards compliance you should put the APR_RING_ENTRY
! 66: * first in the element struct unless the head is always part of a larger
! 67: * object with enough earlier fields to accommodate the offsetof() used
! 68: * to compute the ring sentinel below. You can usually ignore this caveat.
! 69: */
! 70: #define APR_RING_ENTRY(elem) \
! 71: struct { \
! 72: struct elem * volatile next; \
! 73: struct elem * volatile prev; \
! 74: }
! 75:
! 76: /**
! 77: * The Ring Head
! 78: *
! 79: * Each ring is managed via its head, which is a struct declared like this:
! 80: * <pre>
! 81: * APR_RING_HEAD(my_ring_t, my_element_t);
! 82: * struct my_ring_t ring, *ringp;
! 83: * </pre>
! 84: *
! 85: * This struct looks just like the element link struct so that we can
! 86: * be sure that the typecasting games will work as expected.
! 87: *
! 88: * The first element in the ring is next after the head, and the last
! 89: * element is just before the head.
! 90: */
! 91: #define APR_RING_HEAD(head, elem) \
! 92: struct head { \
! 93: struct elem * volatile next; \
! 94: struct elem * volatile prev; \
! 95: }
! 96:
! 97: /**
! 98: * The Ring Sentinel
! 99: *
! 100: * This is the magic pointer value that occurs before the first and
! 101: * after the last elements in the ring, computed from the address of
! 102: * the ring's head. The head itself isn't an element, but in order to
! 103: * get rid of all the special cases when dealing with the ends of the
! 104: * ring, we play typecasting games to make it look like one.
! 105: *
! 106: * Here is a diagram to illustrate the arrangements of the next and
! 107: * prev pointers of each element in a single ring. Note that they point
! 108: * to the start of each element, not to the APR_RING_ENTRY structure.
! 109: *
! 110: * <pre>
! 111: * +->+------+<-+ +->+------+<-+ +->+------+<-+
! 112: * | |struct| | | |struct| | | |struct| |
! 113: * / | elem | \/ | elem | \/ | elem | \
! 114: * ... | | /\ | | /\ | | ...
! 115: * +------+ | | +------+ | | +------+
! 116: * ...--|prev | | +--|ring | | +--|prev |
! 117: * | next|--+ | entry|--+ | next|--...
! 118: * +------+ +------+ +------+
! 119: * | etc. | | etc. | | etc. |
! 120: * : : : : : :
! 121: * </pre>
! 122: *
! 123: * The APR_RING_HEAD is nothing but a bare APR_RING_ENTRY. The prev
! 124: * and next pointers in the first and last elements don't actually
! 125: * point to the head, they point to a phantom place called the
! 126: * sentinel. Its value is such that last->next->next == first because
! 127: * the offset from the sentinel to the head's next pointer is the same
! 128: * as the offset from the start of an element to its next pointer.
! 129: * This also works in the opposite direction.
! 130: *
! 131: * <pre>
! 132: * last first
! 133: * +->+------+<-+ +->sentinel<-+ +->+------+<-+
! 134: * | |struct| | | | | |struct| |
! 135: * / | elem | \/ \/ | elem | \
! 136: * ... | | /\ /\ | | ...
! 137: * +------+ | | +------+ | | +------+
! 138: * ...--|prev | | +--|ring | | +--|prev |
! 139: * | next|--+ | head|--+ | next|--...
! 140: * +------+ +------+ +------+
! 141: * | etc. | | etc. |
! 142: * : : : :
! 143: * </pre>
! 144: *
! 145: * Note that the offset mentioned above is different for each kind of
! 146: * ring that the element may be on, and each kind of ring has a unique
! 147: * name for its APR_RING_ENTRY in each element, and has its own type
! 148: * for its APR_RING_HEAD.
! 149: *
! 150: * Note also that if the offset is non-zero (which is required if an
! 151: * element has more than one APR_RING_ENTRY), the unreality of the
! 152: * sentinel may have bad implications on very perverse implementations
! 153: * of C -- see the warning in APR_RING_ENTRY.
! 154: *
! 155: * @param hp The head of the ring
! 156: * @param elem The name of the element struct
! 157: * @param link The name of the APR_RING_ENTRY in the element struct
! 158: */
! 159: #define APR_RING_SENTINEL(hp, elem, link) \
! 160: (struct elem *)((char *)(&(hp)->next) - APR_OFFSETOF(struct elem, link))
! 161:
! 162: /**
! 163: * The first element of the ring
! 164: * @param hp The head of the ring
! 165: */
! 166: #define APR_RING_FIRST(hp) (hp)->next
! 167: /**
! 168: * The last element of the ring
! 169: * @param hp The head of the ring
! 170: */
! 171: #define APR_RING_LAST(hp) (hp)->prev
! 172: /**
! 173: * The next element in the ring
! 174: * @param ep The current element
! 175: * @param link The name of the APR_RING_ENTRY in the element struct
! 176: */
! 177: #define APR_RING_NEXT(ep, link) (ep)->link.next
! 178: /**
! 179: * The previous element in the ring
! 180: * @param ep The current element
! 181: * @param link The name of the APR_RING_ENTRY in the element struct
! 182: */
! 183: #define APR_RING_PREV(ep, link) (ep)->link.prev
! 184:
! 185:
! 186: /**
! 187: * Initialize a ring
! 188: * @param hp The head of the ring
! 189: * @param elem The name of the element struct
! 190: * @param link The name of the APR_RING_ENTRY in the element struct
! 191: */
! 192: #define APR_RING_INIT(hp, elem, link) do { \
! 193: APR_RING_FIRST((hp)) = APR_RING_SENTINEL((hp), elem, link); \
! 194: APR_RING_LAST((hp)) = APR_RING_SENTINEL((hp), elem, link); \
! 195: } while (0)
! 196:
! 197: /**
! 198: * Determine if a ring is empty
! 199: * @param hp The head of the ring
! 200: * @param elem The name of the element struct
! 201: * @param link The name of the APR_RING_ENTRY in the element struct
! 202: * @return true or false
! 203: */
! 204: #define APR_RING_EMPTY(hp, elem, link) \
! 205: (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))
! 206:
! 207: /**
! 208: * Initialize a singleton element
! 209: * @param ep The element
! 210: * @param link The name of the APR_RING_ENTRY in the element struct
! 211: */
! 212: #define APR_RING_ELEM_INIT(ep, link) do { \
! 213: APR_RING_NEXT((ep), link) = (ep); \
! 214: APR_RING_PREV((ep), link) = (ep); \
! 215: } while (0)
! 216:
! 217:
! 218: /**
! 219: * Splice the sequence ep1..epN into the ring before element lep
! 220: * (..lep.. becomes ..ep1..epN..lep..)
! 221: * @warning This doesn't work for splicing before the first element or on
! 222: * empty rings... see APR_RING_SPLICE_HEAD for one that does
! 223: * @param lep Element in the ring to splice before
! 224: * @param ep1 First element in the sequence to splice in
! 225: * @param epN Last element in the sequence to splice in
! 226: * @param link The name of the APR_RING_ENTRY in the element struct
! 227: */
! 228: #define APR_RING_SPLICE_BEFORE(lep, ep1, epN, link) do { \
! 229: APR_RING_NEXT((epN), link) = (lep); \
! 230: APR_RING_PREV((ep1), link) = APR_RING_PREV((lep), link); \
! 231: APR_RING_NEXT(APR_RING_PREV((lep), link), link) = (ep1); \
! 232: APR_RING_PREV((lep), link) = (epN); \
! 233: } while (0)
! 234:
! 235: /**
! 236: * Splice the sequence ep1..epN into the ring after element lep
! 237: * (..lep.. becomes ..lep..ep1..epN..)
! 238: * @warning This doesn't work for splicing after the last element or on
! 239: * empty rings... see APR_RING_SPLICE_TAIL for one that does
! 240: * @param lep Element in the ring to splice after
! 241: * @param ep1 First element in the sequence to splice in
! 242: * @param epN Last element in the sequence to splice in
! 243: * @param link The name of the APR_RING_ENTRY in the element struct
! 244: */
! 245: #define APR_RING_SPLICE_AFTER(lep, ep1, epN, link) do { \
! 246: APR_RING_PREV((ep1), link) = (lep); \
! 247: APR_RING_NEXT((epN), link) = APR_RING_NEXT((lep), link); \
! 248: APR_RING_PREV(APR_RING_NEXT((lep), link), link) = (epN); \
! 249: APR_RING_NEXT((lep), link) = (ep1); \
! 250: } while (0)
! 251:
! 252: /**
! 253: * Insert the element nep into the ring before element lep
! 254: * (..lep.. becomes ..nep..lep..)
! 255: * @warning This doesn't work for inserting before the first element or on
! 256: * empty rings... see APR_RING_INSERT_HEAD for one that does
! 257: * @param lep Element in the ring to insert before
! 258: * @param nep Element to insert
! 259: * @param link The name of the APR_RING_ENTRY in the element struct
! 260: */
! 261: #define APR_RING_INSERT_BEFORE(lep, nep, link) \
! 262: APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link)
! 263:
! 264: /**
! 265: * Insert the element nep into the ring after element lep
! 266: * (..lep.. becomes ..lep..nep..)
! 267: * @warning This doesn't work for inserting after the last element or on
! 268: * empty rings... see APR_RING_INSERT_TAIL for one that does
! 269: * @param lep Element in the ring to insert after
! 270: * @param nep Element to insert
! 271: * @param link The name of the APR_RING_ENTRY in the element struct
! 272: */
! 273: #define APR_RING_INSERT_AFTER(lep, nep, link) \
! 274: APR_RING_SPLICE_AFTER((lep), (nep), (nep), link)
! 275:
! 276:
! 277: /**
! 278: * Splice the sequence ep1..epN into the ring before the first element
! 279: * (..hp.. becomes ..hp..ep1..epN..)
! 280: * @param hp Head of the ring
! 281: * @param ep1 First element in the sequence to splice in
! 282: * @param epN Last element in the sequence to splice in
! 283: * @param elem The name of the element struct
! 284: * @param link The name of the APR_RING_ENTRY in the element struct
! 285: */
! 286: #define APR_RING_SPLICE_HEAD(hp, ep1, epN, elem, link) \
! 287: APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((hp), elem, link), \
! 288: (ep1), (epN), link)
! 289:
! 290: /**
! 291: * Splice the sequence ep1..epN into the ring after the last element
! 292: * (..hp.. becomes ..ep1..epN..hp..)
! 293: * @param hp Head of the ring
! 294: * @param ep1 First element in the sequence to splice in
! 295: * @param epN Last element in the sequence to splice in
! 296: * @param elem The name of the element struct
! 297: * @param link The name of the APR_RING_ENTRY in the element struct
! 298: */
! 299: #define APR_RING_SPLICE_TAIL(hp, ep1, epN, elem, link) \
! 300: APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((hp), elem, link), \
! 301: (ep1), (epN), link)
! 302:
! 303: /**
! 304: * Insert the element nep into the ring before the first element
! 305: * (..hp.. becomes ..hp..nep..)
! 306: * @param hp Head of the ring
! 307: * @param nep Element to insert
! 308: * @param elem The name of the element struct
! 309: * @param link The name of the APR_RING_ENTRY in the element struct
! 310: */
! 311: #define APR_RING_INSERT_HEAD(hp, nep, elem, link) \
! 312: APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link)
! 313:
! 314: /**
! 315: * Insert the element nep into the ring after the last element
! 316: * (..hp.. becomes ..nep..hp..)
! 317: * @param hp Head of the ring
! 318: * @param nep Element to insert
! 319: * @param elem The name of the element struct
! 320: * @param link The name of the APR_RING_ENTRY in the element struct
! 321: */
! 322: #define APR_RING_INSERT_TAIL(hp, nep, elem, link) \
! 323: APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link)
! 324:
! 325: /**
! 326: * Concatenate ring h2 onto the end of ring h1, leaving h2 empty.
! 327: * @param h1 Head of the ring to concatenate onto
! 328: * @param h2 Head of the ring to concatenate
! 329: * @param elem The name of the element struct
! 330: * @param link The name of the APR_RING_ENTRY in the element struct
! 331: */
! 332: #define APR_RING_CONCAT(h1, h2, elem, link) do { \
! 333: if (!APR_RING_EMPTY((h2), elem, link)) { \
! 334: APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((h1), elem, link), \
! 335: APR_RING_FIRST((h2)), \
! 336: APR_RING_LAST((h2)), link); \
! 337: APR_RING_INIT((h2), elem, link); \
! 338: } \
! 339: } while (0)
! 340:
! 341: /**
! 342: * Prepend ring h2 onto the beginning of ring h1, leaving h2 empty.
! 343: * @param h1 Head of the ring to prepend onto
! 344: * @param h2 Head of the ring to prepend
! 345: * @param elem The name of the element struct
! 346: * @param link The name of the APR_RING_ENTRY in the element struct
! 347: */
! 348: #define APR_RING_PREPEND(h1, h2, elem, link) do { \
! 349: if (!APR_RING_EMPTY((h2), elem, link)) { \
! 350: APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((h1), elem, link), \
! 351: APR_RING_FIRST((h2)), \
! 352: APR_RING_LAST((h2)), link); \
! 353: APR_RING_INIT((h2), elem, link); \
! 354: } \
! 355: } while (0)
! 356:
! 357: /**
! 358: * Unsplice a sequence of elements from a ring
! 359: * @warning The unspliced sequence is left with dangling pointers at either end
! 360: * @param ep1 First element in the sequence to unsplice
! 361: * @param epN Last element in the sequence to unsplice
! 362: * @param link The name of the APR_RING_ENTRY in the element struct
! 363: */
! 364: #define APR_RING_UNSPLICE(ep1, epN, link) do { \
! 365: APR_RING_NEXT(APR_RING_PREV((ep1), link), link) = \
! 366: APR_RING_NEXT((epN), link); \
! 367: APR_RING_PREV(APR_RING_NEXT((epN), link), link) = \
! 368: APR_RING_PREV((ep1), link); \
! 369: } while (0)
! 370:
! 371: /**
! 372: * Remove a single element from a ring
! 373: * @warning The unspliced element is left with dangling pointers at either end
! 374: * @param ep Element to remove
! 375: * @param link The name of the APR_RING_ENTRY in the element struct
! 376: */
! 377: #define APR_RING_REMOVE(ep, link) \
! 378: APR_RING_UNSPLICE((ep), (ep), link)
! 379:
! 380: /**
! 381: * Iterate over a ring
! 382: * @param ep The current element
! 383: * @param head The head of the ring
! 384: * @param elem The name of the element struct
! 385: * @param link The name of the APR_RING_ENTRY in the element struct
! 386: */
! 387: #define APR_RING_FOREACH(ep, head, elem, link) \
! 388: for (ep = APR_RING_FIRST(head); \
! 389: ep != APR_RING_SENTINEL(head, elem, link); \
! 390: ep = APR_RING_NEXT(ep, link))
! 391:
! 392: /**
! 393: * Iterate over a ring safe against removal of the current element
! 394: * @param ep1 The current element
! 395: * @param ep2 Iteration cursor
! 396: * @param head The head of the ring
! 397: * @param elem The name of the element struct
! 398: * @param link The name of the APR_RING_ENTRY in the element struct
! 399: */
! 400: #define APR_RING_FOREACH_SAFE(ep1, ep2, head, elem, link) \
! 401: for (ep1 = APR_RING_FIRST(head), ep2 = APR_RING_NEXT(ep1, link); \
! 402: ep1 != APR_RING_SENTINEL(head, elem, link); \
! 403: ep1 = ep2, ep2 = APR_RING_NEXT(ep1, link))
! 404:
! 405: /* Debugging tools: */
! 406:
! 407: #ifdef APR_RING_DEBUG
! 408: #include <stdio.h>
! 409: #include <assert.h>
! 410:
! 411: #define APR_RING_CHECK_ONE(msg, ptr) \
! 412: fprintf(stderr, "*** %s %p\n", msg, ptr)
! 413:
! 414: #define APR_RING_CHECK(hp, elem, link, msg) \
! 415: APR_RING_CHECK_ELEM(APR_RING_SENTINEL(hp, elem, link), elem, link, msg)
! 416:
! 417: #define APR_RING_CHECK_ELEM(ep, elem, link, msg) do { \
! 418: struct elem *start = (ep); \
! 419: struct elem *here = start; \
! 420: fprintf(stderr, "*** ring check start -- %s\n", msg); \
! 421: do { \
! 422: fprintf(stderr, "\telem %p\n", here); \
! 423: fprintf(stderr, "\telem->next %p\n", \
! 424: APR_RING_NEXT(here, link)); \
! 425: fprintf(stderr, "\telem->prev %p\n", \
! 426: APR_RING_PREV(here, link)); \
! 427: fprintf(stderr, "\telem->next->prev %p\n", \
! 428: APR_RING_PREV(APR_RING_NEXT(here, link), link)); \
! 429: fprintf(stderr, "\telem->prev->next %p\n", \
! 430: APR_RING_NEXT(APR_RING_PREV(here, link), link)); \
! 431: if (APR_RING_PREV(APR_RING_NEXT(here, link), link) != here) { \
! 432: fprintf(stderr, "\t*** elem->next->prev != elem\n"); \
! 433: break; \
! 434: } \
! 435: if (APR_RING_NEXT(APR_RING_PREV(here, link), link) != here) { \
! 436: fprintf(stderr, "\t*** elem->prev->next != elem\n"); \
! 437: break; \
! 438: } \
! 439: here = APR_RING_NEXT(here, link); \
! 440: } while (here != start); \
! 441: fprintf(stderr, "*** ring check end\n"); \
! 442: } while (0)
! 443:
! 444: #define APR_RING_CHECK_CONSISTENCY(hp, elem, link) \
! 445: APR_RING_CHECK_ELEM_CONSISTENCY(APR_RING_SENTINEL(hp, elem, link),\
! 446: elem, link)
! 447:
! 448: #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link) do { \
! 449: struct elem *start = (ep); \
! 450: struct elem *here = start; \
! 451: do { \
! 452: assert(APR_RING_PREV(APR_RING_NEXT(here, link), link) == here); \
! 453: assert(APR_RING_NEXT(APR_RING_PREV(here, link), link) == here); \
! 454: here = APR_RING_NEXT(here, link); \
! 455: } while (here != start); \
! 456: } while (0)
! 457:
! 458: #else
! 459: /**
! 460: * Print a single pointer value to STDERR
! 461: * (This is a no-op unless APR_RING_DEBUG is defined.)
! 462: * @param msg Descriptive message
! 463: * @param ptr Pointer value to print
! 464: */
! 465: #define APR_RING_CHECK_ONE(msg, ptr)
! 466: /**
! 467: * Dump all ring pointers to STDERR, starting with the head and looping all
! 468: * the way around the ring back to the head. Aborts if an inconsistency
! 469: * is found.
! 470: * (This is a no-op unless APR_RING_DEBUG is defined.)
! 471: * @param hp Head of the ring
! 472: * @param elem The name of the element struct
! 473: * @param link The name of the APR_RING_ENTRY in the element struct
! 474: * @param msg Descriptive message
! 475: */
! 476: #define APR_RING_CHECK(hp, elem, link, msg)
! 477: /**
! 478: * Loops around a ring and checks all the pointers for consistency. Pops
! 479: * an assertion if any inconsistency is found. Same idea as APR_RING_CHECK()
! 480: * except that it's silent if all is well.
! 481: * (This is a no-op unless APR_RING_DEBUG is defined.)
! 482: * @param hp Head of the ring
! 483: * @param elem The name of the element struct
! 484: * @param link The name of the APR_RING_ENTRY in the element struct
! 485: */
! 486: #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)
! 487: /**
! 488: * Dump all ring pointers to STDERR, starting with the given element and
! 489: * looping all the way around the ring back to that element. Aborts if
! 490: * an inconsistency is found.
! 491: * (This is a no-op unless APR_RING_DEBUG is defined.)
! 492: * @param ep The element
! 493: * @param elem The name of the element struct
! 494: * @param link The name of the APR_RING_ENTRY in the element struct
! 495: * @param msg Descriptive message
! 496: */
! 497: #define APR_RING_CHECK_ELEM(ep, elem, link, msg)
! 498: /**
! 499: * Loops around a ring, starting with the given element, and checks all
! 500: * the pointers for consistency. Pops an assertion if any inconsistency
! 501: * is found. Same idea as APR_RING_CHECK_ELEM() except that it's silent
! 502: * if all is well.
! 503: * (This is a no-op unless APR_RING_DEBUG is defined.)
! 504: * @param ep The element
! 505: * @param elem The name of the element struct
! 506: * @param link The name of the APR_RING_ENTRY in the element struct
! 507: */
! 508: #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link)
! 509: #endif
! 510:
! 511: /** @} */
! 512:
! 513: #endif /* !APR_RING_H */
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to apr_ring.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / win32 / apache22 / srclib / apr / include