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