Main Page | Modules | Data Structures | File List | Data Fields | Globals | Related Pages

apr_ring.h

Go to the documentation of this file.
00001 /* Copyright 2000-2004 The Apache Software Foundation 00002 * 00003 * Licensed under the Apache License, Version 2.0 (the "License"); 00004 * you may not use this file except in compliance with the License. 00005 * You may obtain a copy of the License at 00006 * 00007 * http://www.apache.org/licenses/LICENSE-2.0 00008 * 00009 * Unless required by applicable law or agreed to in writing, software 00010 * distributed under the License is distributed on an "AS IS" BASIS, 00011 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00012 * See the License for the specific language governing permissions and 00013 * limitations under the License. 00014 */ 00015 00016 /* 00017 * This code draws heavily from the 4.4BSD <sys/queue.h> macros 00018 * and Dean Gaudet's "splim/ring.h". 00019 * <http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/queue.h> 00020 * <http://www.arctic.org/~dean/splim/> 00021 * 00022 * We'd use Dean's code directly if we could guarantee the 00023 * availability of inline functions. 00024 */ 00025 00026 #ifndef APR_RING_H 00027 #define APR_RING_H 00028 00029 /** 00030 * @file apr_ring.h 00031 * @brief APR Rings 00032 */ 00033 00034 /* 00035 * for offsetof() 00036 */ 00037 #include "apr_general.h" 00038 00039 /** 00040 * @defgroup apr_ring Ring Macro Implementations 00041 * @ingroup APR 00042 * A ring is a kind of doubly-linked list that can be manipulated 00043 * without knowing where its head is. 00044 * @{ 00045 */ 00046 00047 /** 00048 * The Ring Element 00049 * 00050 * A ring element struct is linked to the other elements in the ring 00051 * through its ring entry field, e.g. 00052 * <pre> 00053 * struct my_element_t { 00054 * APR_RING_ENTRY(my_element_t) link; 00055 * int foo; 00056 * char *bar; 00057 * }; 00058 * </pre> 00059 * 00060 * An element struct may be put on more than one ring if it has more 00061 * than one APR_RING_ENTRY field. Each APR_RING_ENTRY has a corresponding 00062 * APR_RING_HEAD declaration. 00063 * 00064 * @warning For strict C standards compliance you should put the APR_RING_ENTRY 00065 * first in the element struct unless the head is always part of a larger 00066 * object with enough earlier fields to accommodate the offsetof() used 00067 * to compute the ring sentinel below. You can usually ignore this caveat. 00068 */ 00069 #define APR_RING_ENTRY(elem) \ 00070 struct { \ 00071 struct elem *next; \ 00072 struct elem *prev; \ 00073 } 00074 00075 /** 00076 * The Ring Head 00077 * 00078 * Each ring is managed via its head, which is a struct declared like this: 00079 * <pre> 00080 * APR_RING_HEAD(my_ring_t, my_element_t); 00081 * struct my_ring_t ring, *ringp; 00082 * </pre> 00083 * 00084 * This struct looks just like the element link struct so that we can 00085 * be sure that the typecasting games will work as expected. 00086 * 00087 * The first element in the ring is next after the head, and the last 00088 * element is just before the head. 00089 */ 00090 #define APR_RING_HEAD(head, elem) \ 00091 struct head { \ 00092 struct elem *next; \ 00093 struct elem *prev; \ 00094 } 00095 00096 /** 00097 * The Ring Sentinel 00098 * 00099 * This is the magic pointer value that occurs before the first and 00100 * after the last elements in the ring, computed from the address of 00101 * the ring's head. The head itself isn't an element, but in order to 00102 * get rid of all the special cases when dealing with the ends of the 00103 * ring, we play typecasting games to make it look like one. 00104 * 00105 * Here is a diagram to illustrate the arrangements of the next and 00106 * prev pointers of each element in a single ring. Note that they point 00107 * to the start of each element, not to the APR_RING_ENTRY structure. 00108 * 00109 * <pre> 00110 * +->+------+<-+ +->+------+<-+ +->+------+<-+ 00111 * | |struct| | | |struct| | | |struct| | 00112 * / | elem | \/ | elem | \/ | elem | \ 00113 * ... | | /\ | | /\ | | ... 00114 * +------+ | | +------+ | | +------+ 00115 * ...--|prev | | +--|ring | | +--|prev | 00116 * | next|--+ | entry|--+ | next|--... 00117 * +------+ +------+ +------+ 00118 * | etc. | | etc. | | etc. | 00119 * : : : : : : 00120 * </pre> 00121 * 00122 * The APR_RING_HEAD is nothing but a bare APR_RING_ENTRY. The prev 00123 * and next pointers in the first and last elements don't actually 00124 * point to the head, they point to a phantom place called the 00125 * sentinel. Its value is such that last->next->next == first because 00126 * the offset from the sentinel to the head's next pointer is the same 00127 * as the offset from the start of an element to its next pointer. 00128 * This also works in the opposite direction. 00129 * 00130 * <pre> 00131 * last first 00132 * +->+------+<-+ +->sentinel<-+ +->+------+<-+ 00133 * | |struct| | | | | |struct| | 00134 * / | elem | \/ \/ | elem | \ 00135 * ... | | /\ /\ | | ... 00136 * +------+ | | +------+ | | +------+ 00137 * ...--|prev | | +--|ring | | +--|prev | 00138 * | next|--+ | head|--+ | next|--... 00139 * +------+ +------+ +------+ 00140 * | etc. | | etc. | 00141 * : : : : 00142 * </pre> 00143 * 00144 * Note that the offset mentioned above is different for each kind of 00145 * ring that the element may be on, and each kind of ring has a unique 00146 * name for its APR_RING_ENTRY in each element, and has its own type 00147 * for its APR_RING_HEAD. 00148 * 00149 * Note also that if the offset is non-zero (which is required if an 00150 * element has more than one APR_RING_ENTRY), the unreality of the 00151 * sentinel may have bad implications on very perverse implementations 00152 * of C -- see the warning in APR_RING_ENTRY. 00153 * 00154 * @param hp The head of the ring 00155 * @param elem The name of the element struct 00156 * @param link The name of the APR_RING_ENTRY in the element struct 00157 */ 00158 #define APR_RING_SENTINEL(hp, elem, link) \ 00159 (struct elem *)((char *)(hp) - APR_OFFSETOF(struct elem, link)) 00160 00161 /** 00162 * The first element of the ring 00163 * @param hp The head of the ring 00164 */ 00165 #define APR_RING_FIRST(hp) (hp)->next 00166 /** 00167 * The last element of the ring 00168 * @param hp The head of the ring 00169 */ 00170 #define APR_RING_LAST(hp) (hp)->prev 00171 /** 00172 * The next element in the ring 00173 * @param ep The current element 00174 * @param link The name of the APR_RING_ENTRY in the element struct 00175 */ 00176 #define APR_RING_NEXT(ep, link) (ep)->link.next 00177 /** 00178 * The previous element in the ring 00179 * @param ep The current element 00180 * @param link The name of the APR_RING_ENTRY in the element struct 00181 */ 00182 #define APR_RING_PREV(ep, link) (ep)->link.prev 00183 00184 00185 /** 00186 * Initialize a ring 00187 * @param hp The head of the ring 00188 * @param elem The name of the element struct 00189 * @param link The name of the APR_RING_ENTRY in the element struct 00190 */ 00191 #define APR_RING_INIT(hp, elem, link) do { \ 00192 APR_RING_FIRST((hp)) = APR_RING_SENTINEL((hp), elem, link); \ 00193 APR_RING_LAST((hp)) = APR_RING_SENTINEL((hp), elem, link); \ 00194 } while (0) 00195 00196 /** 00197 * Determine if a ring is empty 00198 * @param hp The head of the ring 00199 * @param elem The name of the element struct 00200 * @param link The name of the APR_RING_ENTRY in the element struct 00201 * @return true or false 00202 */ 00203 #define APR_RING_EMPTY(hp, elem, link) \ 00204 (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link)) 00205 00206 /** 00207 * Initialize a singleton element 00208 * @param ep The element 00209 * @param link The name of the APR_RING_ENTRY in the element struct 00210 */ 00211 #define APR_RING_ELEM_INIT(ep, link) do { \ 00212 APR_RING_NEXT((ep), link) = (ep); \ 00213 APR_RING_PREV((ep), link) = (ep); \ 00214 } while (0) 00215 00216 00217 /** 00218 * Splice the sequence ep1..epN into the ring before element lep 00219 * (..lep.. becomes ..ep1..epN..lep..) 00220 * @warning This doesn't work for splicing before the first element or on 00221 * empty rings... see APR_RING_SPLICE_HEAD for one that does 00222 * @param lep Element in the ring to splice before 00223 * @param ep1 First element in the sequence to splice in 00224 * @param epN Last element in the sequence to splice in 00225 * @param link The name of the APR_RING_ENTRY in the element struct 00226 */ 00227 #define APR_RING_SPLICE_BEFORE(lep, ep1, epN, link) do { \ 00228 APR_RING_NEXT((epN), link) = (lep); \ 00229 APR_RING_PREV((ep1), link) = APR_RING_PREV((lep), link); \ 00230 APR_RING_NEXT(APR_RING_PREV((lep), link), link) = (ep1); \ 00231 APR_RING_PREV((lep), link) = (epN); \ 00232 } while (0) 00233 00234 /** 00235 * Splice the sequence ep1..epN into the ring after element lep 00236 * (..lep.. becomes ..lep..ep1..epN..) 00237 * @warning This doesn't work for splicing after the last element or on 00238 * empty rings... see APR_RING_SPLICE_TAIL for one that does 00239 * @param lep Element in the ring to splice after 00240 * @param ep1 First element in the sequence to splice in 00241 * @param epN Last element in the sequence to splice in 00242 * @param link The name of the APR_RING_ENTRY in the element struct 00243 */ 00244 #define APR_RING_SPLICE_AFTER(lep, ep1, epN, link) do { \ 00245 APR_RING_PREV((ep1), link) = (lep); \ 00246 APR_RING_NEXT((epN), link) = APR_RING_NEXT((lep), link); \ 00247 APR_RING_PREV(APR_RING_NEXT((lep), link), link) = (epN); \ 00248 APR_RING_NEXT((lep), link) = (ep1); \ 00249 } while (0) 00250 00251 /** 00252 * Insert the element nep into the ring before element lep 00253 * (..lep.. becomes ..nep..lep..) 00254 * @warning This doesn't work for inserting before the first element or on 00255 * empty rings... see APR_RING_INSERT_HEAD for one that does 00256 * @param lep Element in the ring to insert before 00257 * @param nep Element to insert 00258 * @param link The name of the APR_RING_ENTRY in the element struct 00259 */ 00260 #define APR_RING_INSERT_BEFORE(lep, nep, link) \ 00261 APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link) 00262 00263 /** 00264 * Insert the element nep into the ring after element lep 00265 * (..lep.. becomes ..lep..nep..) 00266 * @warning This doesn't work for inserting after the last element or on 00267 * empty rings... see APR_RING_INSERT_TAIL for one that does 00268 * @param lep Element in the ring to insert after 00269 * @param nep Element to insert 00270 * @param link The name of the APR_RING_ENTRY in the element struct 00271 */ 00272 #define APR_RING_INSERT_AFTER(lep, nep, link) \ 00273 APR_RING_SPLICE_AFTER((lep), (nep), (nep), link) 00274 00275 00276 /** 00277 * Splice the sequence ep1..epN into the ring before the first element 00278 * (..hp.. becomes ..hp..ep1..epN..) 00279 * @param hp Head of the ring 00280 * @param ep1 First element in the sequence to splice in 00281 * @param epN Last element in the sequence to splice in 00282 * @param elem The name of the element struct 00283 * @param link The name of the APR_RING_ENTRY in the element struct 00284 */ 00285 #define APR_RING_SPLICE_HEAD(hp, ep1, epN, elem, link) \ 00286 APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((hp), elem, link), \ 00287 (ep1), (epN), link) 00288 00289 /** 00290 * Splice the sequence ep1..epN into the ring after the last element 00291 * (..hp.. becomes ..ep1..epN..hp..) 00292 * @param hp Head of the ring 00293 * @param ep1 First element in the sequence to splice in 00294 * @param epN Last element in the sequence to splice in 00295 * @param elem The name of the element struct 00296 * @param link The name of the APR_RING_ENTRY in the element struct 00297 */ 00298 #define APR_RING_SPLICE_TAIL(hp, ep1, epN, elem, link) \ 00299 APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((hp), elem, link), \ 00300 (ep1), (epN), link) 00301 00302 /** 00303 * Insert the element nep into the ring before the first element 00304 * (..hp.. becomes ..hp..nep..) 00305 * @param hp Head of the ring 00306 * @param nep Element to insert 00307 * @param elem The name of the element struct 00308 * @param link The name of the APR_RING_ENTRY in the element struct 00309 */ 00310 #define APR_RING_INSERT_HEAD(hp, nep, elem, link) \ 00311 APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link) 00312 00313 /** 00314 * Insert the element nep into the ring after the last element 00315 * (..hp.. becomes ..nep..hp..) 00316 * @param hp Head of the ring 00317 * @param nep Element to insert 00318 * @param elem The name of the element struct 00319 * @param link The name of the APR_RING_ENTRY in the element struct 00320 */ 00321 #define APR_RING_INSERT_TAIL(hp, nep, elem, link) \ 00322 APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link) 00323 00324 /** 00325 * Concatenate ring h2 onto the end of ring h1, leaving h2 empty. 00326 * @param h1 Head of the ring to concatenate onto 00327 * @param h2 Head of the ring to concatenate 00328 * @param elem The name of the element struct 00329 * @param link The name of the APR_RING_ENTRY in the element struct 00330 */ 00331 #define APR_RING_CONCAT(h1, h2, elem, link) do { \ 00332 if (!APR_RING_EMPTY((h2), elem, link)) { \ 00333 APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((h1), elem, link), \ 00334 APR_RING_FIRST((h2)), \ 00335 APR_RING_LAST((h2)), link); \ 00336 APR_RING_INIT((h2), elem, link); \ 00337 } \ 00338 } while (0) 00339 00340 /** 00341 * Prepend ring h2 onto the beginning of ring h1, leaving h2 empty. 00342 * @param h1 Head of the ring to prepend onto 00343 * @param h2 Head of the ring to prepend 00344 * @param elem The name of the element struct 00345 * @param link The name of the APR_RING_ENTRY in the element struct 00346 */ 00347 #define APR_RING_PREPEND(h1, h2, elem, link) do { \ 00348 if (!APR_RING_EMPTY((h2), elem, link)) { \ 00349 APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((h1), elem, link), \ 00350 APR_RING_FIRST((h2)), \ 00351 APR_RING_LAST((h2)), link); \ 00352 APR_RING_INIT((h2), elem, link); \ 00353 } \ 00354 } while (0) 00355 00356 /** 00357 * Unsplice a sequence of elements from a ring 00358 * @warning The unspliced sequence is left with dangling pointers at either end 00359 * @param ep1 First element in the sequence to unsplice 00360 * @param epN Last element in the sequence to unsplice 00361 * @param link The name of the APR_RING_ENTRY in the element struct 00362 */ 00363 #define APR_RING_UNSPLICE(ep1, epN, link) do { \ 00364 APR_RING_NEXT(APR_RING_PREV((ep1), link), link) = \ 00365 APR_RING_NEXT((epN), link); \ 00366 APR_RING_PREV(APR_RING_NEXT((epN), link), link) = \ 00367 APR_RING_PREV((ep1), link); \ 00368 } while (0) 00369 00370 /** 00371 * Remove a single element from a ring 00372 * @warning The unspliced element is left with dangling pointers at either end 00373 * @param ep Element to remove 00374 * @param link The name of the APR_RING_ENTRY in the element struct 00375 */ 00376 #define APR_RING_REMOVE(ep, link) \ 00377 APR_RING_UNSPLICE((ep), (ep), link) 00378 00379 00380 /* Debugging tools: */ 00381 00382 #ifdef APR_RING_DEBUG 00383 #include <stdio.h> 00384 #include <assert.h> 00385 00386 #define APR_RING_CHECK_ONE(msg, ptr) \ 00387 fprintf(stderr, "*** %s %p\n", msg, ptr) 00388 00389 #define APR_RING_CHECK(hp, elem, link, msg) \ 00390 APR_RING_CHECK_ELEM(APR_RING_SENTINEL(hp, elem, link), elem, link, msg) 00391 00392 #define APR_RING_CHECK_ELEM(ep, elem, link, msg) do { \ 00393 struct elem *start = (ep); \ 00394 struct elem *here = start; \ 00395 fprintf(stderr, "*** ring check start -- %s\n", msg); \ 00396 do { \ 00397 fprintf(stderr, "\telem %p\n", here); \ 00398 fprintf(stderr, "\telem->next %p\n", \ 00399 APR_RING_NEXT(here, link)); \ 00400 fprintf(stderr, "\telem->prev %p\n", \ 00401 APR_RING_PREV(here, link)); \ 00402 fprintf(stderr, "\telem->next->prev %p\n", \ 00403 APR_RING_PREV(APR_RING_NEXT(here, link), link)); \ 00404 fprintf(stderr, "\telem->prev->next %p\n", \ 00405 APR_RING_NEXT(APR_RING_PREV(here, link), link)); \ 00406 if (APR_RING_PREV(APR_RING_NEXT(here, link), link) != here) { \ 00407 fprintf(stderr, "\t*** elem->next->prev != elem\n"); \ 00408 break; \ 00409 } \ 00410 if (APR_RING_NEXT(APR_RING_PREV(here, link), link) != here) { \ 00411 fprintf(stderr, "\t*** elem->prev->next != elem\n"); \ 00412 break; \ 00413 } \ 00414 here = APR_RING_NEXT(here, link); \ 00415 } while (here != start); \ 00416 fprintf(stderr, "*** ring check end\n"); \ 00417 } while (0) 00418 00419 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link) \ 00420 APR_RING_CHECK_ELEM_CONSISTENCY(APR_RING_SENTINEL(hp, elem, link),\ 00421 elem, link) 00422 00423 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link) do { \ 00424 struct elem *start = (ep); \ 00425 struct elem *here = start; \ 00426 do { \ 00427 assert(APR_RING_PREV(APR_RING_NEXT(here, link), link) == here); \ 00428 assert(APR_RING_NEXT(APR_RING_PREV(here, link), link) == here); \ 00429 here = APR_RING_NEXT(here, link); \ 00430 } while (here != start); \ 00431 } while (0) 00432 00433 #else 00434 /** 00435 * Print a single pointer value to STDERR 00436 * (This is a no-op unless APR_RING_DEBUG is defined.) 00437 * @param msg Descriptive message 00438 * @param ptr Pointer value to print 00439 */ 00440 #define APR_RING_CHECK_ONE(msg, ptr) 00441 /** 00442 * Dump all ring pointers to STDERR, starting with the head and looping all 00443 * the way around the ring back to the head. Aborts if an inconsistency 00444 * is found. 00445 * (This is a no-op unless APR_RING_DEBUG is defined.) 00446 * @param hp Head of the ring 00447 * @param elem The name of the element struct 00448 * @param link The name of the APR_RING_ENTRY in the element struct 00449 * @param msg Descriptive message 00450 */ 00451 #define APR_RING_CHECK(hp, elem, link, msg) 00452 /** 00453 * Loops around a ring and checks all the pointers for consistency. Pops 00454 * an assertion if any inconsistency is found. Same idea as APR_RING_CHECK() 00455 * except that it's silent if all is well. 00456 * (This is a no-op unless APR_RING_DEBUG is defined.) 00457 * @param hp Head of the ring 00458 * @param elem The name of the element struct 00459 * @param link The name of the APR_RING_ENTRY in the element struct 00460 */ 00461 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link) 00462 /** 00463 * Dump all ring pointers to STDERR, starting with the given element and 00464 * looping all the way around the ring back to that element. Aborts if 00465 * an inconsistency is found. 00466 * (This is a no-op unless APR_RING_DEBUG is defined.) 00467 * @param ep The element 00468 * @param elem The name of the element struct 00469 * @param link The name of the APR_RING_ENTRY in the element struct 00470 * @param msg Descriptive message 00471 */ 00472 #define APR_RING_CHECK_ELEM(ep, elem, link, msg) 00473 /** 00474 * Loops around a ring, starting with the given element, and checks all 00475 * the pointers for consistency. Pops an assertion if any inconsistency 00476 * is found. Same idea as APR_RING_CHECK_ELEM() except that it's silent 00477 * if all is well. 00478 * (This is a no-op unless APR_RING_DEBUG is defined.) 00479 * @param ep The element 00480 * @param elem The name of the element struct 00481 * @param link The name of the APR_RING_ENTRY in the element struct 00482 */ 00483 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link) 00484 #endif 00485 00486 /** @} */ 00487 00488 #endif /* !APR_RING_H */

Generated on Thu Sep 16 13:47:10 2004 for Apache Portable Runtime by doxygen 1.3.7