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 00030 /** 00031 * @file apr_ring.h 00032 * @brief APR Rings 00033 */ 00034 00035 /* 00036 * for offsetof() 00037 */ 00038 #include "apr_general.h" 00039 00040 /** 00041 * @defgroup apr_ring Ring Macro Implementations 00042 * @ingroup APR 00043 * A ring is a kind of doubly-linked list that can be manipulated 00044 * without knowing where its head is. 00045 * @{ 00046 */ 00047 00048 /** 00049 * The Ring Element 00050 * 00051 * A ring element struct is linked to the other elements in the ring 00052 * through its ring entry field, e.g. 00053 * <pre> 00054 * struct my_element_t { 00055 * APR_RING_ENTRY(my_element_t) link; 00056 * int foo; 00057 * char *bar; 00058 * }; 00059 * </pre> 00060 * 00061 * An element struct may be put on more than one ring if it has more 00062 * than one APR_RING_ENTRY field. Each APR_RING_ENTRY has a corresponding 00063 * APR_RING_HEAD declaration. 00064 * 00065 * @warning For strict C standards compliance you should put the APR_RING_ENTRY 00066 * first in the element struct unless the head is always part of a larger 00067 * object with enough earlier fields to accommodate the offsetof() used 00068 * to compute the ring sentinel below. You can usually ignore this caveat. 00069 */ 00070 #define APR_RING_ENTRY(elem) \ 00071 struct { \ 00072 struct elem * volatile next; \ 00073 struct elem * volatile prev; \ 00074 } 00075 00076 /** 00077 * The Ring Head 00078 * 00079 * Each ring is managed via its head, which is a struct declared like this: 00080 * <pre> 00081 * APR_RING_HEAD(my_ring_t, my_element_t); 00082 * struct my_ring_t ring, *ringp; 00083 * </pre> 00084 * 00085 * This struct looks just like the element link struct so that we can 00086 * be sure that the typecasting games will work as expected. 00087 * 00088 * The first element in the ring is next after the head, and the last 00089 * element is just before the head. 00090 */ 00091 #define APR_RING_HEAD(head, elem) \ 00092 struct head { \ 00093 struct elem *next; \ 00094 struct elem *prev; \ 00095 } 00096 00097 /** 00098 * The Ring Sentinel 00099 * 00100 * This is the magic pointer value that occurs before the first and 00101 * after the last elements in the ring, computed from the address of 00102 * the ring's head. The head itself isn't an element, but in order to 00103 * get rid of all the special cases when dealing with the ends of the 00104 * ring, we play typecasting games to make it look like one. 00105 * 00106 * Here is a diagram to illustrate the arrangements of the next and 00107 * prev pointers of each element in a single ring. Note that they point 00108 * to the start of each element, not to the APR_RING_ENTRY structure. 00109 * 00110 * <pre> 00111 * +->+------+<-+ +->+------+<-+ +->+------+<-+ 00112 * | |struct| | | |struct| | | |struct| | 00113 * / | elem | \/ | elem | \/ | elem | \ 00114 * ... | | /\ | | /\ | | ... 00115 * +------+ | | +------+ | | +------+ 00116 * ...--|prev | | +--|ring | | +--|prev | 00117 * | next|--+ | entry|--+ | next|--... 00118 * +------+ +------+ +------+ 00119 * | etc. | | etc. | | etc. | 00120 * : : : : : : 00121 * </pre> 00122 * 00123 * The APR_RING_HEAD is nothing but a bare APR_RING_ENTRY. The prev 00124 * and next pointers in the first and last elements don't actually 00125 * point to the head, they point to a phantom place called the 00126 * sentinel. Its value is such that last->next->next == first because 00127 * the offset from the sentinel to the head's next pointer is the same 00128 * as the offset from the start of an element to its next pointer. 00129 * This also works in the opposite direction. 00130 * 00131 * <pre> 00132 * last first 00133 * +->+------+<-+ +->sentinel<-+ +->+------+<-+ 00134 * | |struct| | | | | |struct| | 00135 * / | elem | \/ \/ | elem | \ 00136 * ... | | /\ /\ | | ... 00137 * +------+ | | +------+ | | +------+ 00138 * ...--|prev | | +--|ring | | +--|prev | 00139 * | next|--+ | head|--+ | next|--... 00140 * +------+ +------+ +------+ 00141 * | etc. | | etc. | 00142 * : : : : 00143 * </pre> 00144 * 00145 * Note that the offset mentioned above is different for each kind of 00146 * ring that the element may be on, and each kind of ring has a unique 00147 * name for its APR_RING_ENTRY in each element, and has its own type 00148 * for its APR_RING_HEAD. 00149 * 00150 * Note also that if the offset is non-zero (which is required if an 00151 * element has more than one APR_RING_ENTRY), the unreality of the 00152 * sentinel may have bad implications on very perverse implementations 00153 * of C -- see the warning in APR_RING_ENTRY. 00154 * 00155 * @param hp The head of the ring 00156 * @param elem The name of the element struct 00157 * @param link The name of the APR_RING_ENTRY in the element struct 00158 */ 00159 #define APR_RING_SENTINEL(hp, elem, link) \ 00160 (struct elem *)((char *)(&(hp)->next) - APR_OFFSETOF(struct elem, link)) 00161 00162 /** 00163 * The first element of the ring 00164 * @param hp The head of the ring 00165 */ 00166 #define APR_RING_FIRST(hp) (hp)->next 00167 /** 00168 * The last element of the ring 00169 * @param hp The head of the ring 00170 */ 00171 #define APR_RING_LAST(hp) (hp)->prev 00172 /** 00173 * The next element in the ring 00174 * @param ep The current element 00175 * @param link The name of the APR_RING_ENTRY in the element struct 00176 */ 00177 #define APR_RING_NEXT(ep, link) (ep)->link.next 00178 /** 00179 * The previous element in the ring 00180 * @param ep The current element 00181 * @param link The name of the APR_RING_ENTRY in the element struct 00182 */ 00183 #define APR_RING_PREV(ep, link) (ep)->link.prev 00184 00185 00186 /** 00187 * Initialize a ring 00188 * @param hp The head of the ring 00189 * @param elem The name of the element struct 00190 * @param link The name of the APR_RING_ENTRY in the element struct 00191 */ 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 00197 /** 00198 * Determine if a ring is empty 00199 * @param hp The head of the ring 00200 * @param elem The name of the element struct 00201 * @param link The name of the APR_RING_ENTRY in the element struct 00202 * @return true or false 00203 */ 00204 #define APR_RING_EMPTY(hp, elem, link) \ 00205 (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link)) 00206 00207 /** 00208 * Initialize a singleton element 00209 * @param ep The element 00210 * @param link The name of the APR_RING_ENTRY in the element struct 00211 */ 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 00218 /** 00219 * Splice the sequence ep1..epN into the ring before element lep 00220 * (..lep.. becomes ..ep1..epN..lep..) 00221 * @warning This doesn't work for splicing before the first element or on 00222 * empty rings... see APR_RING_SPLICE_HEAD for one that does 00223 * @param lep Element in the ring to splice before 00224 * @param ep1 First element in the sequence to splice in 00225 * @param epN Last element in the sequence to splice in 00226 * @param link The name of the APR_RING_ENTRY in the element struct 00227 */ 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 00235 /** 00236 * Splice the sequence ep1..epN into the ring after element lep 00237 * (..lep.. becomes ..lep..ep1..epN..) 00238 * @warning This doesn't work for splicing after the last element or on 00239 * empty rings... see APR_RING_SPLICE_TAIL for one that does 00240 * @param lep Element in the ring to splice after 00241 * @param ep1 First element in the sequence to splice in 00242 * @param epN Last element in the sequence to splice in 00243 * @param link The name of the APR_RING_ENTRY in the element struct 00244 */ 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 00252 /** 00253 * Insert the element nep into the ring before element lep 00254 * (..lep.. becomes ..nep..lep..) 00255 * @warning This doesn't work for inserting before the first element or on 00256 * empty rings... see APR_RING_INSERT_HEAD for one that does 00257 * @param lep Element in the ring to insert before 00258 * @param nep Element to insert 00259 * @param link The name of the APR_RING_ENTRY in the element struct 00260 */ 00261 #define APR_RING_INSERT_BEFORE(lep, nep, link) \ 00262 APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link) 00263 00264 /** 00265 * Insert the element nep into the ring after element lep 00266 * (..lep.. becomes ..lep..nep..) 00267 * @warning This doesn't work for inserting after the last element or on 00268 * empty rings... see APR_RING_INSERT_TAIL for one that does 00269 * @param lep Element in the ring to insert after 00270 * @param nep Element to insert 00271 * @param link The name of the APR_RING_ENTRY in the element struct 00272 */ 00273 #define APR_RING_INSERT_AFTER(lep, nep, link) \ 00274 APR_RING_SPLICE_AFTER((lep), (nep), (nep), link) 00275 00276 00277 /** 00278 * Splice the sequence ep1..epN into the ring before the first element 00279 * (..hp.. becomes ..hp..ep1..epN..) 00280 * @param hp Head of the ring 00281 * @param ep1 First element in the sequence to splice in 00282 * @param epN Last element in the sequence to splice in 00283 * @param elem The name of the element struct 00284 * @param link The name of the APR_RING_ENTRY in the element struct 00285 */ 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 00290 /** 00291 * Splice the sequence ep1..epN into the ring after the last element 00292 * (..hp.. becomes ..ep1..epN..hp..) 00293 * @param hp Head of the ring 00294 * @param ep1 First element in the sequence to splice in 00295 * @param epN Last element in the sequence to splice in 00296 * @param elem The name of the element struct 00297 * @param link The name of the APR_RING_ENTRY in the element struct 00298 */ 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 00303 /** 00304 * Insert the element nep into the ring before the first element 00305 * (..hp.. becomes ..hp..nep..) 00306 * @param hp Head of the ring 00307 * @param nep Element to insert 00308 * @param elem The name of the element struct 00309 * @param link The name of the APR_RING_ENTRY in the element struct 00310 */ 00311 #define APR_RING_INSERT_HEAD(hp, nep, elem, link) \ 00312 APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link) 00313 00314 /** 00315 * Insert the element nep into the ring after the last element 00316 * (..hp.. becomes ..nep..hp..) 00317 * @param hp Head of the ring 00318 * @param nep Element to insert 00319 * @param elem The name of the element struct 00320 * @param link The name of the APR_RING_ENTRY in the element struct 00321 */ 00322 #define APR_RING_INSERT_TAIL(hp, nep, elem, link) \ 00323 APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link) 00324 00325 /** 00326 * Concatenate ring h2 onto the end of ring h1, leaving h2 empty. 00327 * @param h1 Head of the ring to concatenate onto 00328 * @param h2 Head of the ring to concatenate 00329 * @param elem The name of the element struct 00330 * @param link The name of the APR_RING_ENTRY in the element struct 00331 */ 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 00341 /** 00342 * Prepend ring h2 onto the beginning of ring h1, leaving h2 empty. 00343 * @param h1 Head of the ring to prepend onto 00344 * @param h2 Head of the ring to prepend 00345 * @param elem The name of the element struct 00346 * @param link The name of the APR_RING_ENTRY in the element struct 00347 */ 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 00357 /** 00358 * Unsplice a sequence of elements from a ring 00359 * @warning The unspliced sequence is left with dangling pointers at either end 00360 * @param ep1 First element in the sequence to unsplice 00361 * @param epN Last element in the sequence to unsplice 00362 * @param link The name of the APR_RING_ENTRY in the element struct 00363 */ 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 00371 /** 00372 * Remove a single element from a ring 00373 * @warning The unspliced element is left with dangling pointers at either end 00374 * @param ep Element to remove 00375 * @param link The name of the APR_RING_ENTRY in the element struct 00376 */ 00377 #define APR_RING_REMOVE(ep, link) \ 00378 APR_RING_UNSPLICE((ep), (ep), link) 00379 00380 /** 00381 * Iterate over a ring 00382 * @param ep The current element 00383 * @param head The head of the ring 00384 * @param elem The name of the element struct 00385 * @param link The name of the APR_RING_ENTRY in the element struct 00386 */ 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 00392 /** 00393 * Iterate over a ring safe against removal of the current element 00394 * @param ep1 The current element 00395 * @param ep2 Iteration cursor 00396 * @param head The head of the ring 00397 * @param elem The name of the element struct 00398 * @param link The name of the APR_RING_ENTRY in the element struct 00399 */ 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 /** 00460 * Print a single pointer value to STDERR 00461 * (This is a no-op unless APR_RING_DEBUG is defined.) 00462 * @param msg Descriptive message 00463 * @param ptr Pointer value to print 00464 */ 00465 #define APR_RING_CHECK_ONE(msg, ptr) 00466 /** 00467 * Dump all ring pointers to STDERR, starting with the head and looping all 00468 * the way around the ring back to the head. Aborts if an inconsistency 00469 * is found. 00470 * (This is a no-op unless APR_RING_DEBUG is defined.) 00471 * @param hp Head of the ring 00472 * @param elem The name of the element struct 00473 * @param link The name of the APR_RING_ENTRY in the element struct 00474 * @param msg Descriptive message 00475 */ 00476 #define APR_RING_CHECK(hp, elem, link, msg) 00477 /** 00478 * Loops around a ring and checks all the pointers for consistency. Pops 00479 * an assertion if any inconsistency is found. Same idea as APR_RING_CHECK() 00480 * except that it's silent if all is well. 00481 * (This is a no-op unless APR_RING_DEBUG is defined.) 00482 * @param hp Head of the ring 00483 * @param elem The name of the element struct 00484 * @param link The name of the APR_RING_ENTRY in the element struct 00485 */ 00486 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link) 00487 /** 00488 * Dump all ring pointers to STDERR, starting with the given element and 00489 * looping all the way around the ring back to that element. Aborts if 00490 * an inconsistency is found. 00491 * (This is a no-op unless APR_RING_DEBUG is defined.) 00492 * @param ep The element 00493 * @param elem The name of the element struct 00494 * @param link The name of the APR_RING_ENTRY in the element struct 00495 * @param msg Descriptive message 00496 */ 00497 #define APR_RING_CHECK_ELEM(ep, elem, link, msg) 00498 /** 00499 * Loops around a ring, starting with the given element, and checks all 00500 * the pointers for consistency. Pops an assertion if any inconsistency 00501 * is found. Same idea as APR_RING_CHECK_ELEM() except that it's silent 00502 * if all is well. 00503 * (This is a no-op unless APR_RING_DEBUG is defined.) 00504 * @param ep The element 00505 * @param elem The name of the element struct 00506 * @param link The name of the APR_RING_ENTRY in the element struct 00507 */ 00508 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link) 00509 #endif 00510 00511 /** @} */ 00512 00513 #endif /* !APR_RING_H */
1.5.6