THE DESIGN OF THE RING DATA STRUCTURE
                            design.mps.ring
                             incomplete doc
                           richard 1996-09-26

INTRODUCTION

.source: rings are derived from the earlier use of Deques.  See 
design.mps.deque.


DESCRIPTION

.def.ring: Rings are circular doubly-linked lists of ring "nodes".  The nodes 
are fields of structures which are the "elements" of the ring.

Ring node structures (RingStruct) are in-lined in the structures on the ring, 
like this:

  typedef struct FooStruct *Foo;     /* the element type */
  typedef struct FooStruct {         /* the element structure */
    int baz, bim;
    RingStruct ring;                 /* the ring node */
    float bip, bop;
  } FooStruct;

This arrangement means that they do not need to be managed separately.  This is 
especially useful in avoiding re-entrancy and bootstrapping problems in the 
memory manager.  Rings also provide flexible insertion and deletion because the 
entire ring can be found from any node.

In the MPS, rings are used to connect a "parent" structure (such as a Space) to 
a number of "child" structures (such as Pools), as shown in .fig.ring (note the 
slight abuse of naming convention (in that barRing is not called 
barRingStruct)).

.fig.ring: A ring of Bar objects owned by a Foo object.



.fig.empty: An empty ring of Bar objects owned by a Foo object.


.def.singleton: A "singleton" ring is a ring containing one node, whose 
previous and next nodes are itself (see .fig.single).

.fig.single: A singleton Bar object not on any ring.


.fig.elt: How RING_ELT gets a parent pointer from a node pointer.


 - Ring Diagrams 

INIT / FINISH

.init: Rings are initialized with the RingInit function.  They are initialized 
to be a singleton ring (.def.singleton).

.finish: Rings are finished with the RingFinish funtion.  A ring must be a 
singleton ring before it can be finished (it is an error to attempt to finish a 
non-singleton ring).


ITERATION

.for: A macro is used for iterating over the elements in a ring.  This macro is 
called RING_FOR.  RING_FOR takes three arguments, the first is an iteration 
variable: "node", the second is the "parent" element in the ring: "ring", the 
third is a variable used by the iterator for working state (it holds a pointer 
to the next node): "next".  All arguments must be of type Ring.  The "node" and 
"next" variables must be declared and in scope already.  All elements except 
for the "parent" element are iterated over.  The macro expands to a for 
statement.  During execution of the loop, the "node" variable (the first 
argument to the macro) will be the value of successive elements in the Ring (at 
the beginning of the statement in the body of the loop).  .for.error: It is an 
error (possibly unchecked) for the "node" and "next" variables to be modified 
except implicitly by using this iterator.  .for.safe: It is safe to delete the 
current node during the iteration.

.for.ex:

An example:

Ring node, nextNode;
RING_FOR(node, &foo->barRing, nextNode) {
  Bar bar = RING_ELT(Bar, FooRing, node);
  frob(bar);
}

.for.ex.elt: Notice the idiomatic use of RING_ELT which is almost universal 
when using RING_FOR.


SUBCLASS

.elt: RING_ELT is a macro that converts a pointer to a ring structure to a 
pointer to the enclosing parent structure.
RING_ELT has three arguments which are, in order:
type, the type of a pointer to the enclosing structure,
field, the name of the ring structure field within it,
ring, the ring node.
The result is a pointer to the enclosing structure.

[ Why does RING_ELT not use PARENT or even offsetof?  Apparently it's so that 
it can cope with arrays of rings.  GavinM 1997-04-15]
 

APPEND / REMOVE

.append: RingAppend appends a singleton ring to a ring (such that the newly 
added element will be last in the iteration sequence).

.insert: RingInsert adds a singleton rung to a ring (such that the newly added 
element will be first in the
iteration sequence).

.remove: RingRemove removes an element from a ring, the newly removed element 
becomes a singleton ring.  It is an error for the element to already be a 
singleton.

.improve.join:  it would be possible to add a RingJoin operation.  This is not 
done as it is not required.


NAMING

.naming: By convention, when one structure Foo contains one ring of Bar 
structures, the field is Foo is usually known as barRing, and the field in Bar 
is known as fooRing.  If the Foo structure contains more than one ring of Bar 
structures, then they will have names such as spongRing and frobRing.


DEQUES

This section documents where rings differ significantly from deques.

.head: Deques used a distinguished head structure for the head of the ring.  
Rings still have a separate head structure, but it is not distinguished by type.


DEFECTS

This section documents known defects with the current design.

.app_for.misuse: It is easy to pass RingAppend and RING_FOR the arguments in 
the wrong order as all the arguments have the same type.  see .head.

.check.improve: There is no method for performing a full integrity check.  This 
could be added.

ATTACHMENT
   "Ring Diagrams"