Loading...
Searching...
No Matches
Ring Macro Implementations
Apache Portability Runtime library
Collaboration diagram for Ring Macro Implementations:

## Macros

#define | APR_RING_ENTRY(elem)
#define | APR_RING_HEAD(head, elem)
#define | APR_RING_SENTINEL(hp, elem, link) (struct elem *)((char *)(&(hp)->next) - APR_OFFSETOF(struct elem, link))
#define | APR_RING_FIRST(hp) (hp)->next
#define | APR_RING_LAST(hp) (hp)->prev
#define | APR_RING_NEXT(ep, link) (ep)->link.next
#define | APR_RING_PREV(ep, link) (ep)->link.prev
#define | APR_RING_INIT(hp, elem, link)
#define | APR_RING_EMPTY(hp, elem, link) (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))
#define | APR_RING_ELEM_INIT(ep, link)
#define | APR_RING_SPLICE_BEFORE(lep, ep1, epN, link)
#define | APR_RING_SPLICE_AFTER(lep, ep1, epN, link)
#define | APR_RING_INSERT_BEFORE(lep, nep, link) APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link)
#define | APR_RING_INSERT_AFTER(lep, nep, link) APR_RING_SPLICE_AFTER((lep), (nep), (nep), link)
#define | APR_RING_SPLICE_HEAD(hp, ep1, epN, elem, link)
#define | APR_RING_SPLICE_TAIL(hp, ep1, epN, elem, link)
#define | APR_RING_INSERT_HEAD(hp, nep, elem, link) APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link)
#define | APR_RING_INSERT_TAIL(hp, nep, elem, link) APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link)
#define | APR_RING_CONCAT(h1, h2, elem, link)
#define | APR_RING_PREPEND(h1, h2, elem, link)
#define | APR_RING_UNSPLICE(ep1, epN, link)
#define | APR_RING_REMOVE(ep, link) APR_RING_UNSPLICE((ep), (ep), link)
#define | APR_RING_FOREACH(ep, head, elem, link)
#define | APR_RING_FOREACH_SAFE(ep1, ep2, head, elem, link)
#define | APR_RING_CHECK_ONE(msg, ptr)
#define | APR_RING_CHECK(hp, elem, link, msg)
#define | APR_RING_CHECK_CONSISTENCY(hp, elem, link)
#define | APR_RING_CHECK_ELEM(ep, elem, link, msg)
#define | APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link)

## Detailed Description

A ring is a kind of doubly-linked list that can be manipulated without knowing where its head is.

## Macro Definition Documentation

## APR_RING_CHECK

#define APR_RING_CHECK | ( |  | hp,
|  |  | elem,
|  |  | link,
|  |  | msg
| ) |  |

Dump all ring pointers to STDERR, starting with the head and looping all the way around the ring back to the head. Aborts if an inconsistency is found. (This is a no-op unless APR_RING_DEBUG is defined.)

Parameters

  hp | Head of the ring
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct
  msg | Descriptive message

## APR_RING_CHECK_CONSISTENCY

#define APR_RING_CHECK_CONSISTENCY | ( |  | hp,
|  |  | elem,
|  |  | link
| ) |  |

Loops around a ring and checks all the pointers for consistency. Pops an assertion if any inconsistency is found. Same idea as APR_RING_CHECK() except that it's silent if all is well. (This is a no-op unless APR_RING_DEBUG is defined.)

Parameters

  hp | Head of the ring
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_CHECK_ELEM

#define APR_RING_CHECK_ELEM | ( |  | ep,
|  |  | elem,
|  |  | link,
|  |  | msg
| ) |  |

Dump all ring pointers to STDERR, starting with the given element and looping all the way around the ring back to that element. Aborts if an inconsistency is found. (This is a no-op unless APR_RING_DEBUG is defined.)

Parameters

  ep | The element
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct
  msg | Descriptive message

## APR_RING_CHECK_ELEM_CONSISTENCY

#define APR_RING_CHECK_ELEM_CONSISTENCY | ( |  | ep,
|  |  | elem,
|  |  | link
| ) |  |

Loops around a ring, starting with the given element, and checks all the pointers for consistency. Pops an assertion if any inconsistency is found. Same idea as APR_RING_CHECK_ELEM() except that it's silent if all is well. (This is a no-op unless APR_RING_DEBUG is defined.)

Parameters

  ep | The element
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_CHECK_ONE

#define APR_RING_CHECK_ONE | ( |  | msg,
|  |  | ptr
| ) |  |

Print a single pointer value to STDERR (This is a no-op unless APR_RING_DEBUG is defined.)

Parameters

  msg | Descriptive message
  ptr | Pointer value to print

## APR_RING_CONCAT

#define APR_RING_CONCAT | ( |  | h1,
|  |  | h2,
|  |  | elem,
|  |  | link
| ) |  |

Value:
do { \
if (!APR_RING_EMPTY((h2), elem, link)) { \
APR_RING_SPLICE_TAIL((h1), APR_RING_FIRST((h2)), \
APR_RING_LAST((h2)), elem, link); \
APR_RING_INIT((h2), elem, link); \
} \
} while (0)
APR_RING_LAST
#define APR_RING_LAST(hp)
Definition apr_ring.h:171
APR_RING_EMPTY
#define APR_RING_EMPTY(hp, elem, link)
Definition apr_ring.h:204
APR_RING_FIRST
#define APR_RING_FIRST(hp)
Definition apr_ring.h:166

Concatenate ring h2 onto the end of ring h1, leaving h2 empty.

Parameters

  h1 | Head of the ring to concatenate onto
  h2 | Head of the ring to concatenate
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_ELEM_INIT

#define APR_RING_ELEM_INIT | ( |  | ep,
|  |  | link
| ) |  |

Value:
do { \
APR_RING_NEXT((ep), link) = (ep); \
APR_RING_PREV((ep), link) = (ep); \
} while (0)

Initialize a singleton element

Parameters

  ep | The element
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_EMPTY

#define APR_RING_EMPTY | ( |  | hp,
|  |  | elem,
|  |  | link
| ) |  | (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))

Determine if a ring is empty

Parameters

  hp | The head of the ring
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

Returns
  true or false

## APR_RING_ENTRY

#define APR_RING_ENTRY | ( |  | elem | ) |

Value:
struct { \
struct elem * volatile next; \
struct elem * volatile prev; \
}

The Ring Element

A ring element struct is linked to the other elements in the ring through its ring entry field, e.g.

         struct my_element_t {
             APR_RING_ENTRY(my_element_t) link;
             int foo;
             char *bar;
         };

An element struct may be put on more than one ring if it has more than one APR_RING_ENTRY field. Each APR_RING_ENTRY has a corresponding APR_RING_HEAD declaration.

Warning
  For strict C standards compliance you should put the APR_RING_ENTRY first in the element struct unless the head is always part of a larger object with enough earlier fields to accommodate the offsetof() used to compute the ring sentinel below. You can usually ignore this caveat.

## APR_RING_FIRST

#define APR_RING_FIRST | ( |  | hp | ) | (hp)->next

The first element of the ring

Parameters

  hp | The head of the ring

## APR_RING_FOREACH

#define APR_RING_FOREACH | ( |  | ep,
|  |  | head,
|  |  | elem,
|  |  | link
| ) |  |

Value:
for (ep = APR_RING_FIRST(head); \
ep != APR_RING_SENTINEL(head, elem, link); \
ep = APR_RING_NEXT(ep, link))
APR_RING_SENTINEL
#define APR_RING_SENTINEL(hp, elem, link)
Definition apr_ring.h:159
APR_RING_NEXT
#define APR_RING_NEXT(ep, link)
Definition apr_ring.h:177

Iterate over a ring

Parameters

  ep | The current element
  head | The head of the ring
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_FOREACH_SAFE

#define APR_RING_FOREACH_SAFE | ( |  | ep1,
|  |  | ep2,
|  |  | head,
|  |  | elem,
|  |  | link
| ) |  |

Value:
for (ep1 = APR_RING_FIRST(head), ep2 = APR_RING_NEXT(ep1, link); \
ep1 != APR_RING_SENTINEL(head, elem, link); \
ep1 = ep2, ep2 = APR_RING_NEXT(ep1, link))

Iterate over a ring safe against removal of the current element

Parameters

  ep1 | The current element
  ep2 | Iteration cursor
  head | The head of the ring
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_HEAD

#define APR_RING_HEAD | ( |  | head,
|  |  | elem
| ) |  |

Value:
struct head { \
struct elem * volatile next; \
struct elem * volatile prev; \
}

The Ring Head

Each ring is managed via its head, which is a struct declared like this:

         APR_RING_HEAD(my_ring_t, my_element_t);
         struct my_ring_t ring, *ringp;

This struct looks just like the element link struct so that we can be sure that the typecasting games will work as expected.

The first element in the ring is next after the head, and the last element is just before the head.

## APR_RING_INIT

#define APR_RING_INIT | ( |  | hp,
|  |  | elem,
|  |  | link
| ) |  |

Value:
do { \
APR_RING_FIRST((hp)) = APR_RING_SENTINEL((hp), elem, link); \
APR_RING_LAST((hp)) = APR_RING_SENTINEL((hp), elem, link); \
} while (0)

Initialize a ring

Parameters

  hp | The head of the ring
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_INSERT_AFTER

#define APR_RING_INSERT_AFTER | ( |  | lep,
|  |  | nep,
|  |  | link
| ) |  | APR_RING_SPLICE_AFTER((lep), (nep), (nep), link)

Insert the element nep into the ring after element lep (..lep.. becomes ..lep..nep..)

Warning
  This doesn't work for inserting after the last element or on empty rings... see APR_RING_INSERT_TAIL for one that does

Parameters

  lep | Element in the ring to insert after
  nep | Element to insert
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_INSERT_BEFORE

#define APR_RING_INSERT_BEFORE | ( |  | lep,
|  |  | nep,
|  |  | link
| ) |  | APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link)

Insert the element nep into the ring before element lep (..lep.. becomes ..nep..lep..)

Warning
  This doesn't work for inserting before the first element or on empty rings... see APR_RING_INSERT_HEAD for one that does

Parameters

  lep | Element in the ring to insert before
  nep | Element to insert
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_INSERT_HEAD

#define APR_RING_INSERT_HEAD | ( |  | hp,
|  |  | nep,
|  |  | elem,
|  |  | link
| ) |  | APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link)

Insert the element nep into the ring before the first element (..hp.. becomes ..hp..nep..)

Parameters

  hp | Head of the ring
  nep | Element to insert
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_INSERT_TAIL

#define APR_RING_INSERT_TAIL | ( |  | hp,
|  |  | nep,
|  |  | elem,
|  |  | link
| ) |  | APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link)

Insert the element nep into the ring after the last element (..hp.. becomes ..nep..hp..)

Parameters

  hp | Head of the ring
  nep | Element to insert
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_LAST

#define APR_RING_LAST | ( |  | hp | ) | (hp)->prev

The last element of the ring

Parameters

  hp | The head of the ring

## APR_RING_NEXT

#define APR_RING_NEXT | ( |  | ep,
|  |  | link
| ) |  | (ep)->link.next

The next element in the ring

Parameters

  ep | The current element
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_PREPEND

#define APR_RING_PREPEND | ( |  | h1,
|  |  | h2,
|  |  | elem,
|  |  | link
| ) |  |

Value:
do { \
if (!APR_RING_EMPTY((h2), elem, link)) { \
APR_RING_SPLICE_HEAD((h1), APR_RING_FIRST((h2)), \
APR_RING_LAST((h2)), elem, link); \
APR_RING_INIT((h2), elem, link); \
} \
} while (0)

Prepend ring h2 onto the beginning of ring h1, leaving h2 empty.

Parameters

  h1 | Head of the ring to prepend onto
  h2 | Head of the ring to prepend
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_PREV

#define APR_RING_PREV | ( |  | ep,
|  |  | link
| ) |  | (ep)->link.prev

The previous element in the ring

Parameters

  ep | The current element
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_REMOVE

#define APR_RING_REMOVE | ( |  | ep,
|  |  | link
| ) |  | APR_RING_UNSPLICE((ep), (ep), link)

Remove a single element from a ring

Warning
  The unspliced element is left with dangling pointers at either end

Parameters

  ep | Element to remove
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_SENTINEL

#define APR_RING_SENTINEL | ( |  | hp,
|  |  | elem,
|  |  | link
| ) |  | (struct elem *)((char *)(&(hp)->next) - APR_OFFSETOF(struct elem, link))

The Ring Sentinel

This is the magic pointer value that occurs before the first and after the last elements in the ring, computed from the address of the ring's head. The head itself isn't an element, but in order to get rid of all the special cases when dealing with the ends of the ring, we play typecasting games to make it look like one.

Here is a diagram to illustrate the arrangements of the next and prev pointers of each element in a single ring. Note that they point to the start of each element, not to the APR_RING_ENTRY structure.

        +->+------+<-+  +->+------+<-+  +->+------+<-+
        |  |struct|  |  |  |struct|  |  |  |struct|  |
       /   | elem |   \/   | elem |   \/   | elem |  \
    ...    |      |   /\   |      |   /\   |      |   ...
           +------+  |  |  +------+  |  |  +------+
      ...--|prev  |  |  +--|ring  |  |  +--|prev  |
           |  next|--+     | entry|--+     |  next|--...
           +------+        +------+        +------+
           | etc. |        | etc. |        | etc. |
           :      :        :      :        :      :

The APR_RING_HEAD is nothing but a bare APR_RING_ENTRY. The prev and next pointers in the first and last elements don't actually point to the head, they point to a phantom place called the sentinel. Its value is such that last->next->next == first because the offset from the sentinel to the head's next pointer is the same as the offset from the start of an element to its next pointer. This also works in the opposite direction.

           last                            first
        +->+------+<-+  +->sentinel<-+  +->+------+<-+
        |  |struct|  |  |            |  |  |struct|  |
       /   | elem |   \/              \/   | elem |  \
    ...    |      |   /\              /\   |      |   ...
           +------+  |  |  +------+  |  |  +------+
      ...--|prev  |  |  +--|ring  |  |  +--|prev  |
           |  next|--+     |  head|--+     |  next|--...
           +------+        +------+        +------+
           | etc. |                        | etc. |
           :      :                        :      :

Note that the offset mentioned above is different for each kind of ring that the element may be on, and each kind of ring has a unique name for its APR_RING_ENTRY in each element, and has its own type for its APR_RING_HEAD.

Note also that if the offset is non-zero (which is required if an element has more than one APR_RING_ENTRY), the unreality of the sentinel may have bad implications on very perverse implementations of C – see the warning in APR_RING_ENTRY.

Parameters

  hp | The head of the ring
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_SPLICE_AFTER

#define APR_RING_SPLICE_AFTER | ( |  | lep,
|  |  | ep1,
|  |  | epN,
|  |  | link
| ) |  |

Value:
do { \
APR_RING_PREV((ep1), link) = (lep); \
APR_RING_NEXT((epN), link) = APR_RING_NEXT((lep), link); \
APR_RING_PREV(APR_RING_NEXT((lep), link), link) = (epN); \
APR_RING_NEXT((lep), link) = (ep1); \
} while (0)

Splice the sequence ep1..epN into the ring after element lep (..lep.. becomes ..lep..ep1..epN..)

Warning
  This doesn't work for splicing after the last element or on empty rings... see APR_RING_SPLICE_TAIL for one that does

Parameters

  lep | Element in the ring to splice after
  ep1 | First element in the sequence to splice in
  epN | Last element in the sequence to splice in
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_SPLICE_BEFORE

#define APR_RING_SPLICE_BEFORE | ( |  | lep,
|  |  | ep1,
|  |  | epN,
|  |  | link
| ) |  |

Value:
do { \
APR_RING_NEXT((epN), link) = (lep); \
APR_RING_PREV((ep1), link) = APR_RING_PREV((lep), link); \
APR_RING_NEXT(APR_RING_PREV((lep), link), link) = (ep1); \
APR_RING_PREV((lep), link) = (epN); \
} while (0)
APR_RING_PREV
#define APR_RING_PREV(ep, link)
Definition apr_ring.h:183

Splice the sequence ep1..epN into the ring before element lep (..lep.. becomes ..ep1..epN..lep..)

Warning
  This doesn't work for splicing before the first element or on empty rings... see APR_RING_SPLICE_HEAD for one that does

Parameters

  lep | Element in the ring to splice before
  ep1 | First element in the sequence to splice in
  epN | Last element in the sequence to splice in
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_SPLICE_HEAD

#define APR_RING_SPLICE_HEAD | ( |  | hp,
|  |  | ep1,
|  |  | epN,
|  |  | elem,
|  |  | link
| ) |  |

Value:
do { \
APR_RING_PREV((ep1), link) = APR_RING_SENTINEL((hp), elem, link);\
APR_RING_NEXT((epN), link) = APR_RING_FIRST((hp)); \
APR_RING_PREV(APR_RING_FIRST((hp)), link) = (epN); \
APR_RING_FIRST((hp)) = (ep1); \
} while (0)

Splice the sequence ep1..epN into the ring before the first element (..hp.. becomes ..hp..ep1..epN..)

Parameters

  hp | Head of the ring
  ep1 | First element in the sequence to splice in
  epN | Last element in the sequence to splice in
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_SPLICE_TAIL

#define APR_RING_SPLICE_TAIL | ( |  | hp,
|  |  | ep1,
|  |  | epN,
|  |  | elem,
|  |  | link
| ) |  |

Value:
do { \
APR_RING_NEXT((epN), link) = APR_RING_SENTINEL((hp), elem, link);\
APR_RING_PREV((ep1), link) = APR_RING_LAST((hp)); \
APR_RING_NEXT(APR_RING_LAST((hp)), link) = (ep1); \
APR_RING_LAST((hp)) = (epN); \
} while (0)

Splice the sequence ep1..epN into the ring after the last element (..hp.. becomes ..ep1..epN..hp..)

Parameters

  hp | Head of the ring
  ep1 | First element in the sequence to splice in
  epN | Last element in the sequence to splice in
  elem | The name of the element struct
  link | The name of the APR_RING_ENTRY in the element struct

## APR_RING_UNSPLICE

#define APR_RING_UNSPLICE | ( |  | ep1,
|  |  | epN,
|  |  | link
| ) |  |

Value:
do { \
APR_RING_NEXT(APR_RING_PREV((ep1), link), link) = \
APR_RING_NEXT((epN), link); \
APR_RING_PREV(APR_RING_NEXT((epN), link), link) = \
APR_RING_PREV((ep1), link); \
} while (0)

Unsplice a sequence of elements from a ring

Warning
  The unspliced sequence is left with dangling pointers at either end

Parameters

  ep1 | First element in the sequence to unsplice
  epN | Last element in the sequence to unsplice
  link | The name of the APR_RING_ENTRY in the element struct