10. Ring data structure

10.1. Introduction

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

10.2. Description

RingStruct *Ring

.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 inlined 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 Arena) to a number of “child” structures (such as Pool), 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.

[missing figure]

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

[missing figure]

.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.

[missing figure]

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

[missing figure]

10.3. Init / Finish

void RingInit(Ring ring)

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

void RingFinish(Ring ring)

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

10.4. Iteration

RING_FOR(Ring node, Ring ring, Ring next)

.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().

10.5. Subclass

RING_ELT(type, field, Ring node)

.elt: RING_ELT() is a macro that converts a pointer to a ring structure into 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.

Note

RING_ELT() does not work for arrays of rings.

10.6. Append / Remove

void RingAppend(Ring ring, Ring new)

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

void (RingInsert)(Ring ring, Ring new)

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

void (RingRemove)(Ring old)

.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 that joined two rings. This is not done as it is not required.

10.7. Naming

.naming: By convention, when one structure Foo contains one ring of Bar structures, the field in 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.

10.8. 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.

10.9. 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.