On Wed, Aug 28, 2002 at 03:18:22PM +0100, Tony Finch wrote: > 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.
This is *really* good stuff, including the ascii art. We should find a home for this in the docs. :) -aaron
