Hmm... But doesn't this mean that in apr_bucket_brigade, APR_RING_HEAD
should be first in the structure?
Currently, we have:
struct apr_bucket {
APR_RING_ENTRY(apr_bucket) link;
...
}
struct apr_bucket_brigade {
apr_pool_t *p;
APR_RING_HEAD(apr_bucket_list, apr_bucket) list;
...
}
If I understood Tony's explanation correctly, then assuming we have:
apr_bucket *last;
apr_bucket_brigade *head;
apr_bucket *next;
and the above point to one another same as in Tony's example below, then
last->link.next->link.next
^^^^^^^^^
sentinel
won't quite work, because the sentinel pointer (first link.next) will
point to the pool pointer in apr_bucket_brigade. But it _will_ work if
apr_bucket_brigade looks like this:
struct apr_bucket_brigade {
APR_RING_HEAD(apr_bucket_list, apr_bucket) list;
apr_pool_t *p;
...
}
On Wed, 28 Aug 2002, Tony Finch wrote:
> On Wed, Aug 28, 2002 at 03:09:50AM -0400, Cliff Woolley wrote:
> >
> > Tony? Maybe you can shed some more light on this.
>
> Yes. The comment about the sentinel says it's magic, and it isn't lying.
> It is good and functional magic, though :-)
>
> One misconception to correct: each ring has exactly one head. An element
> may be on multiple rings -- for example, inside a kernel there may be
> a ring of all processes and run queues for each CPU, so the process
> structure will have ring entries for the ring of all processes and the
> run queue that it is on. But each of the rings is distinct -- on a dual
> CPU machine there will be three rings and three heads, and each process
> will be on two of the rings (because it has two ring entry structures).
>
> Time for some ASCII art, I think. This is 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 ring entry structure.
>
> +->+------+<-+ +->+------+<-+ +->+------+<-+
> | |struct| | | |struct| | | |struct| |
> / | elem | \/ | elem | \/ | elem | \
> ... | | /\ | | /\ | | ...
> +------+ | | +------+ | | +------+
> ...--|prev | | +--|ring | | +--|prev |
> | next|--+ | entry|--+ | next|--...
> +------+ +------+ +------+
> | etc. | | etc. | | etc. |
> : : : : : :
>
> Now look at what happens at the head of the ring, which is nothing but
> a bare ring entry structure. 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. (There is a warning in the code's comments
> because pointers like this aren't strictly allowed by C.) Its value is
> such that last->next->next == first and first->prev->prev == last 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.
>
> 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 -- in the example, the ring of all processes
> is a different kind of ring from the per-CPU run queues, and different
> kinds of ring use different names for their entry structures in each
> element.
>
> I hope this makes it clear how it works and what you would use it for.
> I should probably add this to the comments in the code.
>
> Tony.
> --
> f.a.n.finch <[EMAIL PROTECTED]> http://dotat.at/
> HUMBER THAMES DOVER WIGHT PORTLAND PLYMOUTH: NORTH BACKING SOUTHWEST 3 OR 4.
> FAIR. MODERATE OR GOOD.
>
