Apache Portable Runtime
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 
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) 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 
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) 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 
309 /**
310  * Insert the element nep into the ring before the first element
311  * (..hp.. becomes ..hp..nep..)
312  * @param hp Head of the ring
313  * @param nep Element to insert
314  * @param elem The name of the element struct
315  * @param link The name of the APR_RING_ENTRY in the element struct
316  */
317 #define APR_RING_INSERT_HEAD(hp, nep, elem, link) \
318  APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link)
319 
320 /**
321  * Insert the element nep into the ring after the last element
322  * (..hp.. becomes ..nep..hp..)
323  * @param hp Head of the ring
324  * @param nep Element to insert
325  * @param elem The name of the element struct
326  * @param link The name of the APR_RING_ENTRY in the element struct
327  */
328 #define APR_RING_INSERT_TAIL(hp, nep, elem, link) \
329  APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link)
330 
331 /**
332  * Concatenate ring h2 onto the end of ring h1, leaving h2 empty.
333  * @param h1 Head of the ring to concatenate onto
334  * @param h2 Head of the ring to concatenate
335  * @param elem The name of the element struct
336  * @param link The name of the APR_RING_ENTRY in the element struct
337  */
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 
346 /**
347  * Prepend ring h2 onto the beginning of ring h1, leaving h2 empty.
348  * @param h1 Head of the ring to prepend onto
349  * @param h2 Head of the ring to prepend
350  * @param elem The name of the element struct
351  * @param link The name of the APR_RING_ENTRY in the element struct
352  */
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 
361 /**
362  * Unsplice a sequence of elements from a ring
363  * @warning The unspliced sequence is left with dangling pointers at either end
364  * @param ep1 First element in the sequence to unsplice
365  * @param epN Last element in the sequence to unsplice
366  * @param link The name of the APR_RING_ENTRY in the element struct
367  */
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 
375 /**
376  * Remove a single element from a ring
377  * @warning The unspliced element is left with dangling pointers at either end
378  * @param ep Element to remove
379  * @param link The name of the APR_RING_ENTRY in the element struct
380  */
381 #define APR_RING_REMOVE(ep, link) \
382  APR_RING_UNSPLICE((ep), (ep), link)
383 
384 /**
385  * Iterate over a ring
386  * @param ep The current element
387  * @param head The head of the ring
388  * @param elem The name of the element struct
389  * @param link The name of the APR_RING_ENTRY in the element struct
390  */
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 
396 /**
397  * Iterate over a ring safe against removal of the current element
398  * @param ep1 The current element
399  * @param ep2 Iteration cursor
400  * @param head The head of the ring
401  * @param elem The name of the element struct
402  * @param link The name of the APR_RING_ENTRY in the element struct
403  */
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
463 /**
464  * Print a single pointer value to STDERR
465  * (This is a no-op unless APR_RING_DEBUG is defined.)
466  * @param msg Descriptive message
467  * @param ptr Pointer value to print
468  */
469 #define APR_RING_CHECK_ONE(msg, ptr)
470 /**
471  * Dump all ring pointers to STDERR, starting with the head and looping all
472  * the way around the ring back to the head. Aborts if an inconsistency
473  * is found.
474  * (This is a no-op unless APR_RING_DEBUG is defined.)
475  * @param hp Head of the ring
476  * @param elem The name of the element struct
477  * @param link The name of the APR_RING_ENTRY in the element struct
478  * @param msg Descriptive message
479  */
480 #define APR_RING_CHECK(hp, elem, link, msg)
481 /**
482  * Loops around a ring and checks all the pointers for consistency. Pops
483  * an assertion if any inconsistency is found. Same idea as APR_RING_CHECK()
484  * except that it's silent if all is well.
485  * (This is a no-op unless APR_RING_DEBUG is defined.)
486  * @param hp Head of the ring
487  * @param elem The name of the element struct
488  * @param link The name of the APR_RING_ENTRY in the element struct
489  */
490 #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)
491 /**
492  * Dump all ring pointers to STDERR, starting with the given element and
493  * looping all the way around the ring back to that element. Aborts if
494  * an inconsistency is found.
495  * (This is a no-op unless APR_RING_DEBUG is defined.)
496  * @param ep The element
497  * @param elem The name of the element struct
498  * @param link The name of the APR_RING_ENTRY in the element struct
499  * @param msg Descriptive message
500  */
501 #define APR_RING_CHECK_ELEM(ep, elem, link, msg)
502 /**
503  * Loops around a ring, starting with the given element, and checks all
504  * the pointers for consistency. Pops an assertion if any inconsistency
505  * is found. Same idea as APR_RING_CHECK_ELEM() except that it's silent
506  * if all is well.
507  * (This is a no-op unless APR_RING_DEBUG is defined.)
508  * @param ep The element
509  * @param elem The name of the element struct
510  * @param link The name of the APR_RING_ENTRY in the element struct
511  */
512 #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link)
513 #endif
514 
515 /** @} */
516 
517 #endif /* !APR_RING_H */
APR Miscellaneous library routines.