GME
13
|
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 00035 /* 00036 * for offsetof() 00037 */ 00038 #include "apr_general.h" 00039 00070 #define APR_RING_ENTRY(elem) \ 00071 struct { \ 00072 struct elem * volatile next; \ 00073 struct elem * volatile prev; \ 00074 } 00075 00091 #define APR_RING_HEAD(head, elem) \ 00092 struct head { \ 00093 struct elem * volatile next; \ 00094 struct elem * volatile prev; \ 00095 } 00096 00159 #define APR_RING_SENTINEL(hp, elem, link) \ 00160 (struct elem *)((char *)(&(hp)->next) - APR_OFFSETOF(struct elem, link)) 00161 00166 #define APR_RING_FIRST(hp) (hp)->next 00167 00171 #define APR_RING_LAST(hp) (hp)->prev 00172 00177 #define APR_RING_NEXT(ep, link) (ep)->link.next 00178 00183 #define APR_RING_PREV(ep, link) (ep)->link.prev 00184 00185 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 00204 #define APR_RING_EMPTY(hp, elem, link) \ 00205 (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link)) 00206 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 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 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 00261 #define APR_RING_INSERT_BEFORE(lep, nep, link) \ 00262 APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link) 00263 00273 #define APR_RING_INSERT_AFTER(lep, nep, link) \ 00274 APR_RING_SPLICE_AFTER((lep), (nep), (nep), link) 00275 00276 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 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 00311 #define APR_RING_INSERT_HEAD(hp, nep, elem, link) \ 00312 APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link) 00313 00322 #define APR_RING_INSERT_TAIL(hp, nep, elem, link) \ 00323 APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link) 00324 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 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 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 00377 #define APR_RING_REMOVE(ep, link) \ 00378 APR_RING_UNSPLICE((ep), (ep), link) 00379 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 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 00465 #define APR_RING_CHECK_ONE(msg, ptr) 00466 00476 #define APR_RING_CHECK(hp, elem, link, msg) 00477 00486 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link) 00487 00497 #define APR_RING_CHECK_ELEM(ep, elem, link, msg) 00498 00508 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link) 00509 #endif 00510 00513 #endif /* !APR_RING_H */