Nevermind (Was Re: A question about rings.)

["Gregory (Grisha) Trubetskoy" <gr...@ispol.com>]

Oops, nevermind - the head of the ring apr_bucket_brigade.list, as is
evident from

#define APR_BRIGADE_SENTINEL(b) APR_RING_SENTINEL(&(b)->list, apr_bucket, link)


On Wed, 28 Aug 2002, Gregory (Grisha) Trubetskoy wrote:

>
> 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 <do...@dotat.at> http://dotat.at/
> > HUMBER THAMES DOVER WIGHT PORTLAND PLYMOUTH: NORTH BACKING SOUTHWEST 3 OR 4.
> > FAIR. MODERATE OR GOOD.
> >
>
>