Ravenbrook / Projects / Memory Pool System / Version 1.111 Product Sources / Design Documents

Memory Pool System Project

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

    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"

## A. References

## B. Document History

2002-06-07 | RB | Converted from MMInfo database design document.

## C. Copyright and License

This document is copyright © 1995-2002 Ravenbrook Limited. All rights reserved. This is an open source license. Contact Ravenbrook for commercial licensing options.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3. Redistributions in any form must be accompanied by information on how to obtain complete source code for the this software and any accompanying software that uses this software. The source code must either be included in the distribution or be available for no more than the cost of distribution plus a nominal fee, and must be freely redistributable under reasonable conditions. For an executable file, complete source code means the source code for all modules it contains. It does not include source code for modules or files that typically accompany the major components of the operating system on which the executable file runs.

This software is provided by the copyright holders and contributors "as is" and any express or implied warranties, including, but not limited to, the implied warranties of merchantability, fitness for a particular purpose, or non-infringement, are disclaimed. In no event shall the copyright holders and contributors be liable for any direct, indirect, incidental, special, exemplary, or consequential damages (including, but not limited to, procurement of substitute goods or services; loss of use, data, or profits; or business interruption) however caused and on any theory of liability, whether in contract, strict liability, or tort (including negligence or otherwise) arising in any way out of the use of this software, even if advised of the possibility of such damage.

`$Id: //info.ravenbrook.com/project/mps/version/1.111/design/ring/index.html#2 $`

Ravenbrook / Projects / Memory Pool System / Version 1.111 Product Sources / Design Documents