Apache2
apr_ring.h
Go to the documentation of this file.
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 
35 /*
36  * for offsetof()
37  */
38 #include "apr_general.h"
39 
70 #define APR_RING_ENTRY(elem) \
71  struct { \
72  struct elem * volatile next; \
73  struct elem * volatile prev; \
74  }
75 
91 #define APR_RING_HEAD(head, elem) \
92  struct head { \
93  struct elem * volatile next; \
94  struct elem * volatile prev; \
95  }
96 
159 #define APR_RING_SENTINEL(hp, elem, link) \
160  (struct elem *)((char *)(&(hp)->next) - APR_OFFSETOF(struct elem, link))
161 
166 #define APR_RING_FIRST(hp) (hp)->next
171 #define APR_RING_LAST(hp) (hp)->prev
177 #define APR_RING_NEXT(ep, link) (ep)->link.next
183 #define APR_RING_PREV(ep, link) (ep)->link.prev
184 
185 
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 
204 #define APR_RING_EMPTY(hp, elem, link) \
205  (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))
206 
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 
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 
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 
261 #define APR_RING_INSERT_BEFORE(lep, nep, link) \
262  APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link)
263 
273 #define APR_RING_INSERT_AFTER(lep, nep, link) \
274  APR_RING_SPLICE_AFTER((lep), (nep), (nep), link)
275 
276 
286 #define APR_RING_SPLICE_HEAD(hp, ep1, epN, elem, link) do { \
287  APR_RING_PREV((ep1), link) = APR_RING_SENTINEL((hp), elem, link);\
288  APR_RING_NEXT((epN), link) = APR_RING_FIRST((hp)); \
289  APR_RING_PREV(APR_RING_FIRST((hp)), link) = (epN); \
290  APR_RING_FIRST((hp)) = (ep1); \
291  } while (0)
292 
302 #define APR_RING_SPLICE_TAIL(hp, ep1, epN, elem, link) do { \
303  APR_RING_NEXT((epN), link) = APR_RING_SENTINEL((hp), elem, link);\
304  APR_RING_PREV((ep1), link) = APR_RING_LAST((hp)); \
305  APR_RING_NEXT(APR_RING_LAST((hp)), link) = (ep1); \
306  APR_RING_LAST((hp)) = (epN); \
307  } while (0)
308 
317 #define APR_RING_INSERT_HEAD(hp, nep, elem, link) \
318  APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link)
319 
328 #define APR_RING_INSERT_TAIL(hp, nep, elem, link) \
329  APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link)
330 
338 #define APR_RING_CONCAT(h1, h2, elem, link) do { \
339  if (!APR_RING_EMPTY((h2), elem, link)) { \
340  APR_RING_SPLICE_TAIL((h1), APR_RING_FIRST((h2)), \
341  APR_RING_LAST((h2)), elem, link); \
342  APR_RING_INIT((h2), elem, link); \
343  } \
344  } while (0)
345 
353 #define APR_RING_PREPEND(h1, h2, elem, link) do { \
354  if (!APR_RING_EMPTY((h2), elem, link)) { \
355  APR_RING_SPLICE_HEAD((h1), APR_RING_FIRST((h2)), \
356  APR_RING_LAST((h2)), elem, link); \
357  APR_RING_INIT((h2), elem, link); \
358  } \
359  } while (0)
360 
368 #define APR_RING_UNSPLICE(ep1, epN, link) do { \
369  APR_RING_NEXT(APR_RING_PREV((ep1), link), link) = \
370  APR_RING_NEXT((epN), link); \
371  APR_RING_PREV(APR_RING_NEXT((epN), link), link) = \
372  APR_RING_PREV((ep1), link); \
373  } while (0)
374 
381 #define APR_RING_REMOVE(ep, link) \
382  APR_RING_UNSPLICE((ep), (ep), link)
383 
391 #define APR_RING_FOREACH(ep, head, elem, link) \
392  for (ep = APR_RING_FIRST(head); \
393  ep != APR_RING_SENTINEL(head, elem, link); \
394  ep = APR_RING_NEXT(ep, link))
395 
404 #define APR_RING_FOREACH_SAFE(ep1, ep2, head, elem, link) \
405  for (ep1 = APR_RING_FIRST(head), ep2 = APR_RING_NEXT(ep1, link); \
406  ep1 != APR_RING_SENTINEL(head, elem, link); \
407  ep1 = ep2, ep2 = APR_RING_NEXT(ep1, link))
408 
409 /* Debugging tools: */
410 
411 #ifdef APR_RING_DEBUG
412 #include <stdio.h>
413 #include <assert.h>
414 
415 #define APR_RING_CHECK_ONE(msg, ptr) \
416  fprintf(stderr, "*** %s %p\n", msg, ptr)
417 
418 #define APR_RING_CHECK(hp, elem, link, msg) \
419  APR_RING_CHECK_ELEM(APR_RING_SENTINEL(hp, elem, link), elem, link, msg)
420 
421 #define APR_RING_CHECK_ELEM(ep, elem, link, msg) do { \
422  struct elem *start = (ep); \
423  struct elem *here = start; \
424  fprintf(stderr, "*** ring check start -- %s\n", msg); \
425  do { \
426  fprintf(stderr, "\telem %p\n", here); \
427  fprintf(stderr, "\telem->next %p\n", \
428  APR_RING_NEXT(here, link)); \
429  fprintf(stderr, "\telem->prev %p\n", \
430  APR_RING_PREV(here, link)); \
431  fprintf(stderr, "\telem->next->prev %p\n", \
432  APR_RING_PREV(APR_RING_NEXT(here, link), link)); \
433  fprintf(stderr, "\telem->prev->next %p\n", \
434  APR_RING_NEXT(APR_RING_PREV(here, link), link)); \
435  if (APR_RING_PREV(APR_RING_NEXT(here, link), link) != here) { \
436  fprintf(stderr, "\t*** elem->next->prev != elem\n"); \
437  break; \
438  } \
439  if (APR_RING_NEXT(APR_RING_PREV(here, link), link) != here) { \
440  fprintf(stderr, "\t*** elem->prev->next != elem\n"); \
441  break; \
442  } \
443  here = APR_RING_NEXT(here, link); \
444  } while (here != start); \
445  fprintf(stderr, "*** ring check end\n"); \
446  } while (0)
447 
448 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link) \
449  APR_RING_CHECK_ELEM_CONSISTENCY(APR_RING_SENTINEL(hp, elem, link),\
450  elem, link)
451 
452 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link) do { \
453  struct elem *start = (ep); \
454  struct elem *here = start; \
455  do { \
456  assert(APR_RING_PREV(APR_RING_NEXT(here, link), link) == here); \
457  assert(APR_RING_NEXT(APR_RING_PREV(here, link), link) == here); \
458  here = APR_RING_NEXT(here, link); \
459  } while (here != start); \
460  } while (0)
461 
462 #else
469 #define APR_RING_CHECK_ONE(msg, ptr)
480 #define APR_RING_CHECK(hp, elem, link, msg)
490 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)
501 #define APR_RING_CHECK_ELEM(ep, elem, link, msg)
512 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link)
513 #endif
514 
517 #endif /* !APR_RING_H */
APR Miscellaneous library routines.