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 */ 514