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

Memory Pool System Project

                             DESIGN OF SPLAY TREES
                                design.mps.splay
                                   draft doc
                               gavinm 1998-05-01

    INTRODUCTION

    .intro: This document explains the design of impl.c.splay, an implementation of
    Splay Trees, including its interface and implementation.

    .readership: This document is intended for any MM developer.

    .source: The primary sources for this design are paper.st85(0) and
    paper.sleator96(0).  Also as CBS is a client, design.mps.cbs.  As PoolMVFF is
    an indirect client, design.mps.poolmvff(1). Also, as PoolMV2 is an
    (obsolescent?) indirect client, design.mps.poolmv2.

    .background: The following background documents influence the design:
    guide.impl.c.adt(0).

    Document History

    .hist.0: Written by GavinM 1998-05-01, made draft 1998-05-27.

    .hist.1: Added client properties.  GavinM 1998-09-09

    .hist.2: Polished for review (chiefly adding a DEFINITIONS section).  drj
    1999-03-10

    .hist.3: Edited after review. tony 1999-03-31

    OVERVIEW

    .overview: Splay trees are a form of binary tree where each access brings the
    accessed element (or the nearest element) to the root of the tree.  The
    restructuring of the tree caused by the access gives excellent amortised
    performance, as the splay tree adapts its shape to usage patterns.  Unused
    nodes have essentially no time overhead.  For a cute animation of splay trees,
    see <URL:http://langevin.usc.edu/BST/SplayTree-Example.html>.

    DEFINITIONS

    .def.splay-tree: A "Splay Tree" is a self-adjusting binary tree as described in
    paper.st85(0), paper.sleator96(0).

    .def.node: A "node" is used in the typical datastructure sense to mean an
    element of a tree (see also .type.splay.node).

    .def.key:  A "key" is a value associated with each node; the keys are totally
    ordered by a client provided comparator.

    .def.comparator: A "comparator" is a function that compares keys to determine
    their ordering (see also .type.splay.compare.method).

    .def.successor: Node N1 is the "successor" of node N2 if N1 and N2 are both in
    the same tree, and the key of N1 immediately follows the key of N2 in the
    ordering of all keys for the tree.

    .def.left-child: Each node N contains a "left child", which is a (possibly
    empty) sub-tree of nodes. The key of N is ordered after the keys of all nodes
    in this sub-tree.

    .def.right-child: Each node N contains a "right child", which is a (possibly
    empty) sub-tree of nodes. The key of N is ordered before the keys of all nodes
    in this sub-tree.

    .def.neighbour: A node N which has key Kn is a "neighbour" of a key K if either
    Kn is the first key in the total order which compares greater than K or if Kn
    is the last key in the total order which compares less than K.

    .def.first: A node is the "first" node in a set of nodes if its key compares
    less than the keys of all other nodes in the set.

    .def.last: A node is the "last" node in a set of nodes if its key compares
    greater than the keys of all other nodes in the set.

    .def.client-property: A "client property" is a value that the client may
    associate with each node in addition to the key (a block size, for example).
    This splay tree implementation provides support for efficiently finding the
    first or last nodes with suitably large client property values.  See also .prop
    below.

    REQUIREMENTS

    .req: These requirements are drawn from those implied by design.mps.poolmv2,
    design.mps.poolmvff(1), design.mps.cbs(2) and general inferred MPS requirements.

    .req.order: Must maintain a set of abstract keys which is totally ordered for a
    comparator.

    .req.tree: The keys must be associated with nodes arranged in a Splay Tree.

    .req.splay: Common operations must balance the tree by splaying it, to achieve
    low amortized cost (see paper.st85(0)).

    .req.add: Must be able to add new members. This is a common operation.

    .req.remove: Must be able to remove members. This is a common operation.

    .req.locate: Must be able to locate a member, given a key. This is a common
    operation.

    .req.neighbours: Must be able to locate the neighbouring members (in order) of
    a non-member, given a key (see .def.neighbour).  This is a common operation.

    .req.iterate: Must be able to iterate over all members in order with reasonable
    efficiency.

    .req.protocol: Must support detection of protocol violations.

    .req.debug: Must support debugging of clients.

    .req.stack: Must do all non-debugging operations with stack usage bounded by a
    constant size.

    .req.adapt: Must adapt to regularities in usage pattern, for better performance.

    .req.property: Must permit a client to associate a client property (such as a
    size) with each node in the tree.

    .req.property.change: Must permit a client to dynamically reassign client
    properties to nodes in the tree.  This is a common operation.

    .req.property.find: Must support rapid finding of the first and last nodes
    which have a suitably large value for their client property.  This is a common
    operation.

    .req.root: Must be able to find the root of a splay tree (if one exists).

    EXTERNAL TYPES

    .type.splay.tree: SplayTree is the type of the main object at the root of the
    splay tree.  It is intended that the SplayTreeStruct can be embedded in another
    structure (see .usage.client-tree for an example).  No convenience functions
    are provided for allocation or deallocation.
      typedef struct SplayTreeStruct SplayTreeStruct, *SplayTree;

    .type.splay.node: SplayNode is the type of a node of the splay tree.
    SplayNodeStruct contains no fields to store the key associated with the node,
    or the client property. Again, it is intended that the SplayNodeStruct can be
    embedded in another structure, and that this is how the association will be
    made (see .usage.client-node for an example).  No convenience functions are
    provided for allocation or deallocation.
      typedef struct SplayNodeStruct SplayNodeStruct, *SplayNode;

    .type.splay.compare.method: SplayCompareMethod is a pointer to a function with
    the following prototype:
      Compare compare(void *key, SplayNode node);
    The function is required to compare the key with the key the client associates
    with that splay tree node, and return the appropriate Compare value (see
    .usage.compare for an example). The function compares a key with a node, rather
    than a pair of keys or nodes as might seem more obvious. This is because the
    details of the mapping between nodes and keys is left to the client (see
    .type.splay.node), and the splaying operations compare keys with nodes (see
    .impl.splay).

    .type.splay.node.describe.method: SplayNodeDescribeMethod is a pointer to a
    function with the following prototype:
      Res nodeDescribe(SplayNode node, mps_lib_FILE *stream)
    The function is required to write (via WriteF) a client-oriented representation
    of the splay node.  The output should be non-empty, short, and without return
    characters.  This is provided for debugging purposes only.

    .type.splay.test.node.method: SplayTestNodeMethod is a pointer to a function
    with the following prototype:
      Bool testNode(SplayTree tree, SplayNode node, void *closureP, unsigned long
    closureS);
    The function is required to determine whether the node itself meets some client
    determined property (see .prop and .usage.test.node for an example). Parameters
    closureP and closureS describe the environment for the function (see
    .function.splay.find.first and .function.splay.find.last).

    .type.splay.test.tree.method: SplayTestTreeMethod is a pointer to a function
    with the following prototype:
      Bool testTree(SplayTree tree, SplayNode node, void *closureP, unsigned long
    closureS);
    The function is required to determine whether any of the nodes in the sub-tree
    rooted at the given node meet some client determined property (see .prop and
    .usage.test.tree for an example).  In particular, it must be a precise (not
    conservative) indication of whether there are any nodes in the sub-tree for
    which the testNode method (see .type.splay.test.node.method) would return TRUE.
    Parameters closureP and closureS describe the environment for the function (see
    .function.splay.find.first and .function.splay.find.last).

    .type.splay.update.node.method: SplayUpdateNodeMethod is a pointer to a
    function with the following prototype:
      void updateNode(SplayTree tree, SplayNode node, SplayNode leftChild,
    SplayNode rightChild);
    The function is required to update any client datastructures associated with a
    node to maintain some client determined property (see .prop) given that the
    children of the node have changed.  If the node does not have one or both
    children, then NULL will be passed as the relevant parameter.  (See
    .usage.callback for an example)

    EXTERNAL FUNCTIONS

    .function.no-thread: The interface functions are not designed to be either
    thread-safe or re-entrant. Clients of the interface are responsible for
    synchronization, and for ensuring that client-provided methods invoked by the
    splay module (.type.splay.compare.method, .type.splay.test.node.method,
    .type.splay.test.tree.method, .type.splay.update.node.method) do not call
    functions of the splay module.

    .function.splay.tree.check: This is a check function for the SplayTree type
    (see guide.impl.c.adt.method.check & design.mps.check(0)):
      Bool SplayTreeCheck(SplayTree tree);

    .function.splay.node.check: This is a check function for the SplayNode type
    (see guide.impl.c.adt.method.check & design.mps.check(0)):
      Bool SplayNodeCheck(SplayNode node);

    .function.splay.tree.init: This function initialises a SplayTree  (see
    guide.impl.c.adt.method.init).  It requires a compare method that defines a
    total ordering on nodes (see .req.order); the effect of supplying a compare
    method that does not implement a total ordering is undefined.  It also requires
    an updateNode method, which will be used to keep client properties up to date
    when the tree structure changes; the value SplayTrivUpdateNode may be used for
    this method if there is no need to maintain client properties.  (See
    .usage.initialization for an example use).
      void SplayTreeInit(SplayTree tree, SplayCompareMethod compare,
    SplayUpdateNodeMethod updateNode);

    .function.splay.tree.finish: This function clears the fields of a SplayTree
    (see guide.impl.c.adt.method.finish).  Note that it does not attempt to finish
    or deallocate any associated SplayNode objects; clients wishing to destroy a
    non-empty SplayTree must first explicitly descend the tree and call
    SplayNodeFinish on each node from the bottom up.
      void SplayTreeFinish(SplayTree tree);

    .function.splay.node.init: This function initialises a SplayNode  (see
    guide.impl.c.adt.method.init).
      void SplayNodeInit(SplayNode node);

    .function.splay.node.finish: This function clears the fields of a SplayNode
    (see guide.impl.c.adt.method.finish).  Note that it does not attempt to finish
    or deallocate any referenced SplayNode objects (see.function.splay.tree.finish).
      void SplayNodeFinish(SplayNode node);

    .function.splay.root: This function returns the root node of the tree, if any
    (see .req.root).  If the tree is empty, FALSE is returned and *nodeReturn is
    not changed.  Otherwise, TRUE is returned and *nodeReturn is set to the root.
      Bool SplayRoot(SplayNode *nodeReturn, SplayTree tree);

    .function.splay.tree.insert: This function is used to insert into a splay tree
    a new node which is associated with the supplied key (see .req.add).  It first
    splays the tree at the key.  If an attempt is made to insert a node that
    compares CompareEQUAL to an existing node in the tree, then ResFAIL will be
    returned and the node will not be inserted.   (See .usage.insert for an example
    use).
      Res SplayTreeInsert(SplayTree tree, SplayNode node, void *key);

    .function.splay.tree.delete: This function is used to delete from a splay tree
    a node which is associated with the supplied key (see .req.remove).  If the
    tree does not contain the given node, or the given node does not compare
    CompareEQUAL with the given key, then ResFAIL will be returned, and the node
    will not be deleted.  The function first splays the tree at the given key.
    (See .usage.delete for an example use).
      Res SplayTreeDelete(SplayTree tree, SplayNode node, void *key);

    .function.splay.tree.search: This function searches the splay tree for a node
    that compares CompareEQUAL to the given key (see .req.locate).  It splays the
    tree at the key.  It returns ResFAIL if there is no such node in the tree,
    otherwise *nodeReturn will be set to the node.
      Res SplayTreeSearch(SplayNode *nodeReturn, SplayTree tree, void *key);

    .function.splay.tree.neighbours: This function searches a splay tree for the
    two nodes that are the neighbours of the given key (see .req.neighbours).  It
    splays the tree at the key.  *leftReturn will be the neighbour which compares
    less than the key if such a neighbour exists; otherwise it will be NULL.
    *rightReturn will be the neighbour which compares greater than the key if such
    a neighbour exists; otherwise it will be NULL.  The function returns ResFAIL if
    any node in the tree compares CompareEQUAL with the given key.    (See
    .usage.insert for an example use).
     Res SplayTreeNeighbours(SplayNode *leftReturn, SplayNode *rightReturn,
    SplayTree tree, void *key);

    .function.splay.tree.first: This function splays the tree at the first node,
    and returns that node (see .req.iterate).  The supplied key should compare
    CompareLESS with all nodes in the tree.  It will return NULL if the tree has no
    nodes.
      SplayNode SplayTreeFirst(SplayTree tree, void *zeroKey);

    .function.splay.tree.next: This function receives a node and key and returns
    the successor node to that node (see .req.iterate).  This function is intended
    for use in iteration when the received node will be the current root of the
    tree, but is robust against being interspersed with other splay operations
    (provided the old node still exists).  The supplied key must compare
    CompareEQUAL to the supplied node.  Note that use of this function rebalances
    the tree for each node accessed. If many nodes are accessed as a result of
    multiple uses, the resultant tree will be generally well balanced. But if the
    tree was previously beneficially balanced for a small working set of accesses,
    then this local optimization will be lost. (see .future.parent).
      SplayNode SplayTreeNext(SplayTree tree, SplayNode oldNode, void *oldKey);

    .function.splay.tree.describe: This function prints (using WriteF) to the
    stream a textual representation of the given splay tree, using nodeDescribe to
    print client-oriented representations of the nodes (see .req.debug).
      Res SplayTreeDescribe(SplayTree tree, mps_lib_FILE *stream,
    SplayNodeDescribeMethod nodeDescribe);

    .function.splay.find.first: SplayFindFirst finds the first node in the tree
    that satisfies some client property (as determined by the testNode and testTree
    methods) (see .req.property.find).  closureP and closureS are arbitrary values,
    and are passed to the testNode and testTree methods which may use the values as
    closure environments.  If there is no satisfactory node, then FALSE is
    returned, otherwise *nodeReturn is set to the node.   (See .usage.delete for an
    example use).
      Bool SplayFindFirst(SplayNode *nodeReturn, SplayTree tree,
    SplayTestNodeMethod testNode, SplayTestTreeMethod testTree, void *closureP,
    unsigned long closureS);

    .function.splay.find.last: SplayFindLast finds the last node in the tree that
    satisfies some client property (as determined by the testNode and testTree
    methods) (see .req.property.find).  closureP and closureS are arbitrary values,
    and are passed to the testNode and testTree methods which may use the values as
    closure environments.  If there is no satisfactory node, then FALSE is
    returned, otherwise *nodeReturn is set to the node.
      Bool SplayFindFirst(SplayNode *nodeReturn, SplayTree tree,
    SplayTestNodeMethod testNode, SplayTestTreeMethod testTree, void *closureP,
    unsigned long closureS);

    .function.splay.node.refresh: SplayNodeRefresh must be called whenever the
    client property (see .prop) at a node changes (see .req.property.change).  It
    will call the updateNode method on the given node, and any other nodes that may
    require update.  The client key for the node must also be supplied; the
    function splays the tree at this key.   (See .usage.insert for an example use).
      void SplayNodeRefresh(SplayTree tree, SplayNode node, void *key);

    CLIENT-DETERMINED PROPERTIES

    .prop: To support .req.property.find, this splay tree implementation provides
    additional features to permit clients to cache maximum (or minimum) values of
    client properties for all the nodes in a subtree.  The splay tree
    implementation uses the cached values as part of SplayFindFirst and
    SplayFindLast via the testNode and testTree methods.  The client is free to
    choose how to represent the client property, and how to compute and store the
    cached value.

    .prop.update: The cached values depend upon the topology of the tree, which may
    vary as a result of operations on the tree.  The client is given the
    opportunity to compute new cache values whenever necessary, via the updateNode
    method (see .function.splay.tree.init). This happens whenever the tree is
    restructured. The client may use the SplayNodeRefresh method to indicate that
    the client attributes at a node have changed (see .req.property.change). A call
    to SplayNodeRefresh splays the tree at the specified node, which may provoke
    calls to the updateNode method as a result of the tree restructuring.  The
    updateNode method will also be called whenever a new splay node is inserted
    into the tree.

    .prop.example: For example, if implementing an address ordered tree of free
    blocks using a splay tree, a client might choose to use the base address of
    each block as the key for each node, and the size of each block as the client
    property. The client can then maintain as a cached value in each node the size
    of the largest block in the subtree rooted at that node. This will permit a
    fast search for the first or last block of at least a given size. See
    .usage.callback for an example updateNode method for such a client.

    .prop.ops: The splay operations must cause client properties for nodes to be
    updated in the following circumstances:- (.impl.* for details):

    .prop.ops.rotate: rotate left, rotate right -- We need to update the value at
    the original root, and the new root, in that order.

    .prop.ops.link: link left, link right -- We know that the line of right descent
    from the root of the left tree and the line of left descent from the root of
    the right tree will both need to be updated.  This is performed at the assembly
    stage. (We could update these chains every time we do a link left or link right
    instead, but this would be less efficient)

    .prop.ops.assemble: assemble -- This operation also invalidates the lines of
    right and left descent of the left and right trees respectively which need to
    be updated (see below).  It also invalidates the root which must be updated
    last.

    .prop.ops.assemble.reverse: To correct the chains of the left and right trees
    without requiring stack or high complexity, we use a judicious amount of
    pointer reversal.

    .prop.ops.assemble.traverse: During the assembly, after the root's children
    have been transplanted, we correct the chains of the left and right trees.  For
    the left tree, we traverse the right child line, reversing pointers, until we
    reach the node that was the last node prior to the transplantation of the
    root's children.  Then we update from that node back to the left tree's root,
    restoring pointers.  Updating the right tree is the same, mutatis mutandis.
    (See .future.reverse for an alternative approach).

    USAGE

    .usage: Here's a simple example of a client which uses a splay tree to
    implement an address ordered tree of free blocks. The significant client usages
    of the splay tree interface might look as follows:-

    .usage.client-tree: Tree structure to embed a SplayTree (see .type.splay.tree):
    typedef struct FreeTreeStruct {
      SplayTreeStruct splayTree;  /* Embedded splay tree */
      /* no obvious client fields for this simple example */
    } FreeTreeStruct;

    .usage.client-node: Node structure to embed a SplayNode (see .type.splay.node):
    typedef struct FreeBlockStruct {
      SplayNodeStruct splayNode; /* embedded splay node */
      Addr base;                 /* base address of block is also the key */
      Size size;                 /* size of block is also the client property */
      Size maxSize;              /* cached value for maximum size in subtree */
    } FreeBlockStruct;

    .usage.callback: updateNode callback method (see
    .type.splay.update.node.method):
    void FreeBlockUpdateNode(SplayTree tree, SplayNode node,
                             SplayNode leftChild, SplayNode rightChild)
    {
      /* Compute the maximum size of any block in this subtree. */
      /* The value to cache is the maximum of the size of this block, */
      /* the cached value for the left subtree (if any) and the cached */
      /* value of the right subtree (if any) */

      FreeBlock freeNode = FreeBlockOfSplayNode(node);

      Size maxSize = freeNode.size;

      if(leftChild != NULL) {
        FreeBlock leftNode = FreeBlockOfSplayNode(leftChild);
        if(leftNode.maxSize > maxSize)
          maxSize = leftNode->maxSize;
      }

      if(rightChild != NULL) {
        FreeBlock rightNode = FreeBlockOfSplayNode(rightChild);
        if(rightNode.maxSize > maxSize)
          maxSize = rightNode->maxSize;
      }

      freeNode->maxSize = maxSize;
    }

    .usage.compare: Comparison function (see .type.splay.compare.method):
    Compare FreeBlockCompare(void *key, SplayNode node) {
      Addr base1, base2, limit2;
      FreeBlock freeNode = FreeBlockOfSplayNode(node);

      base1 = (Addr *)key;
      base2 = freeNode->base;
      limit2 = AddrAdd(base2, freeNode->size);

      if (base1 < base2)
        return CompareLESS;
      else if (base1 >= limit2)
        return CompareGREATER;
      else
        return CompareEQUAL;
    }

    .usage.test.tree: Test tree function (see .type.splay.test.tree.method):
    Bool FreeBlockTestTree(SplayTree tree, SplayNode node
                           void *closureP, unsigned long closureS) {
      /* Closure environment has wanted size as value of closureS. */
      /* Look at the cached value for the node to see if any */
      /* blocks in the subtree are big enough. */

      Size size = (Size)closureS;
      FreeBlock freeNode = FreeBlockOfSplayNode(node);
      return freeNode->maxSize >= size;
    }

    .usage.test.node: Test node function (see .type.splay.test.node.method):
    Bool FreeBlockTestNode(SplayTree tree, SplayNode node
                           void *closureP, unsigned long closureS) {
      /* Closure environment has wanted size as value of closureS. */
      /* Look at the size of the node to see if is big enough. */

      Size size = (Size)closureS;
      FreeBlock freeNode = FreeBlockOfSplayNode(node);
      return freeNode->size >= size;
    }

    .usage.initialization: Client's initialization function (see
    .function.splay.tree.init):
    void FreeTreeInit(FreeTree tree) {
      /* Initialize the embedded splay tree. */
      SplayTreeInit(&tree->splayTree, FreeBlockCompare, FreeBlockUpdateNode);
    }

    .usage.insert: Client function to add a new free block into the tree, merging
    it with an existing block if possible:
    void FreeTreeInsert(FreeTree tree, Addr base, Addr limit) {
      SplayTree splayTree = &tree->splayTree;
      SplayNode leftNeighbour, rightNeighbour;
      void *key = (void *)base;  /* use the base of the block as the key */
      Res res;

      /* Look for any neighbouring blocks. (.function.splay.tree.neighbours) */
      res = SplayTreeNeighbours(&leftNeighbour, &rightNeighbour,
                                splayTree, key);
      AVER(res == ResOK);  /* this client doesn't duplicate free blocks */

      /* Look to see if the neighbours are contiguous. */

      if (leftNeighbour != NULL &&
          FreeBlockLimitOfSplayNode(leftNeighbour) == base) {
        /* Inserted block is contiguous with left neighbour, so merge it. */
        /* The client housekeeping is left as an exercise to the reader. */
        /* This changes the size of a block, which is the client */
        /* property of the splay node. See .function.splay.node.refresh */
        SplayNodeRefresh(tree, leftNeighbour, key);

      } else if (rightNeighbour != NULL &&
                 FreeBlockBaseOfSplayNode(rightNeighbour) == limit) {
        /* Inserted block is contiguous with right neighbour, so merge it. */
        /* The client housekeeping is left as an exercise to the reader. */
        /* This changes the size of a block, which is the client */
        /* property of the splay node. See .function.splay.node.refresh */
        SplayNodeRefresh(tree, rightNeighbour, key);

      } else {
        /* Not contiguous - so insert a new node */
        FreeBlock newBlock = (FreeBlock)allocate(sizeof(FreeBlockStruct));
        splayNode = &newBlock->splayNode;

        newBlock->base = base;
        newBlock->size = AddrOffset(base, limit);
        SplayNodeInit(splayNode);  /* .function.splay.node.init */
        /* .function.splay.tree.insert */
        res = SplayTreeInsert(splayTree, splayNode, key);
        AVER(res == ResOK);  /* this client doesn't duplicate free blocks */
      }
    }

    .usage.delete: Client function to allocate the first block of a given size in
    address order. For simplicity, this allocates the entire block:
    Bool FreeTreeAllocate(Addr *baseReturn, Size *sizeReturn,
                          FreeTree tree, Size size) {
      SplayTree splayTree = &tree->splayTree;
      SplayNode splayNode;
      Bool found;

      /* look for the first node of at least the given size. */
      /* closureP parameter is not used. See .function.splay.find.first.  */
      found = SplayFindFirst(&splayNode, splayTree,
                             FreeBlockTestNode, FreeBlockTestTree,
                             NULL, (unsigned long)size);

      if (found) {
        FreeBlock freeNode = FreeBlockOfSplayNode(splayNode);
        Void *key = (void *)freeNode->base;  /* use base of block as the key */
        Res res;

        /* allocate the block */
        *baseReturn = freeNode->base;
        *sizeReturn = freeNode->size;

        /* remove the node from the splay tree - .function.splay.tree.delete */
        res = SplayTreeDelete(splayTree, splayNode, key);
        AVER(res == ResOK);  /* Must be possible to delete node */

        /* Delete the block */
        deallocate(freeNode, (sizeof(FreeBlockStruct));

        return TRUE;

      } else {
        /* No suitable block */
        return FALSE;
      }
    }

    IMPLEMENTATION

    .impl: For more details of how splay trees work, see paper.st85(0). For more
    details of how to implement operations on splay trees, see paper.sleator96(0).
    Here we describe the operations involved.

    Top-Down Splaying

    .impl.top-down: The method chosen to implement the splaying operation is called
    "top-down splay". This is described as "procedure top-down splay" in
    paper.st85(0) - although the implementation here additionally permits attempts
    to access items which are not known to be in the tree. Top-down splaying is
    particularly efficient for the common case where the location of the node in a
    tree is not known at the start of an operation. Tree restructuring happens as
    the tree is descended, whilst looking for the node.

    .impl.splay: The key to the operation of the splay tree is the internal
    function SplaySplay.  It searches the tree for a node with a given key and
    returns whether it suceeded.  In the process, it brings the found node, or an
    arbitrary neighbour if not found, to the root of the tree.  This
    "bring-to-root" operation is performed top-down during the search, and it is
    not the simplest possible bring-to-root operation, but the resulting tree is
    well-balanced, and will give good amortised cost for future calls to
    SplaySplay. (See paper.st85(0))

    .impl.splay.how: To perform this top-down splay, the tree is broken into three
    parts, a left tree, a middle tree and a right tree. We store the left tree and
    right tree in the right and left children respectively of a "sides" node to
    eliminate some boundary conditions.  The initial condition is that the middle
    tree is the entire splay tree, and the left and right trees are empty.  We also
    keep pointers to the last node in the left tree, and the first node in the
    right tree.  Note that, at all times, the three trees are each validly ordered,
    and they form a partition with the ordering left, middle, right.  The splay is
    then performed by comparing the middle tree with the following six cases, and
    performing the indicated operations, until none apply.

    .impl.splay.cases: Note that paper.st85(0)(Fig. 3) describes only 3 cases: zig,
    zig-zig and zig-zag. The additional cases described here are the symmetric
    variants which are respectively called zag, zag-zag and zag-zig. In the
    descriptions of these cases, "root" is the root of the middle tree; node->left
    is the left child of node; node->right is the right child of node. The
    comparison operators (<, >, ==) are defined to compare a key and a node in the
    obvious way by comparing the supplied key with the node's associated key.

    .impl.splay.zig: The "zig" case is where key < root, and either:
      - key == root->left;
      - key < root->left && root->left->left == NULL; or
      - key > root->left && root->left->right == NULL.

    The operation for the zig case is: link right (see .impl.link.right)

    .impl.splay.zag: The "zag" case is where key > root, and either:
      - key == root->right;
      - key < root->right && root->right->left == NULL; or
      - key > root->right && root->right->right == NULL.

    The operation for the zag case is: link left (see .impl.link.left)

    .impl.splay.zig.zig: The "zig-zig" case is where key < root && key < root->left
    && root->left->left != NULL.  The operation for the zig-zig case is: rotate
    right (see .impl.rotate.right) followed by link right (see .impl.link.right).

    .impl.splay.zig.zag: The "zig-zag" case is where key < root && key > root->left
    && root->left->right != NULL.  The operation for the zig-zag case is: link
    right (see .impl.link.right) followed by link left (see .impl.link.left).

    .impl.splay.zag.zig: The "zag-zig" case is where key > root && key <
    root->right && root->right->left != NULL.  The operation for the zag-zig case
    is: link left (see .impl.link.left) followed by link right (see
    .impl.link.right).

    .impl.splay.zag.zag: The "zag-zag" case is where key > root && key >
    root->right && root->right->right != NULL.  The operation for the zag-zag case
    is: rotate left (see .impl.rotate.left) followed by link left (see
    .impl.link.left).

    .impl.splay.terminal.null: A special terminal case is when root == NULL.  This
    can only happen at the beginning, and cannot arise from the operations above.
    In this case, the splay operation must return NULL, and "not found".

    .impl.splay.terminal.found: One typical terminal case is when key == root.
    This case is tested for at the beginning, in which case "found" is returned
    immediately. If this case happens as a result of other operations, the splay
    operation is complete, the three trees are assembled (see .impl.assemble), and
    "found" is returned.

    .impl.splay.terminal.not-found: The other typical terminal cases are:
      - key < root && root->left == NULL; and
      - key > root && root->right == NULL.
    In these cases, the splay operation is complete, the three trees are assembled
    (see .impl.assemble), and "not found" is returned.

    .impl.rotate.left: The "rotate left" operation (see paper.st85(0) Fig. 1)
    rearranges the middle tree as follows (where any of sub-trees A, B and C may be
    empty):
    .impl.rotate.right: The "rotate right" operation (see paper.st85(0) Fig. 1)
    rearranges the middle tree as follows (where any of sub-trees A, B and C may be
    empty):
    .impl.link.left: The "link left" operation (see paper.st85(0) Fig. 11a for
    symmetric variant) rearranges the left and middle trees as follows (where any
    of sub-trees A, B, L and R may be empty):

    The last node of the left tree is now x.

    .impl.link.right: The "link right" operation (see paper.st85(0) Fig. 11a)
    rearranges the middle and right trees as follows (where any of sub-trees A, B,
    L and R may be empty):
    The first node of the right tree is now x.

    .impl.assemble: The "assemble" operation (see paper.st85(0) Fig. 12) merges the
    left and right trees with the middle tree as follows (where any of sub-trees A,
    B, L and R may be empty):

    Top-Level Operations

    .impl.insert: SplayTreeInsert: (See paper.sleator96(0), chapter 4, function
    insert). If the tree has no nodes, [how does it smell?] add the inserted node
    and we're done; otherwise splay the tree around the supplied key.  If the splay
    successfully found a matching node, return failure.  Otherwise, add the
    inserted node as a new root, with the old (newly splayed, but non-matching)
    root as its left or right child as appropriate, and the opposite child of the
    old root as the other child of the new root.

    .impl.delete: SplayTreeDelete: (See paper.sleator96(0), chapter 4, function
    delete). Splay the tree around the supplied key.  Check that the newly splayed
    root is the same node as given by the caller, and that it matches the key;
    return failure if not.  If the given node (now at the root) has fewer than two
    children, replace it (as root), with the non-null child or null.  Otherwise,
    set the root of the tree to be the left child (arbitrarily) of the node to be
    deleted, and splay around the same key.  The new root will be the last node in
    the sub-tree and will have a null right child; this is set to be the right
    child of the node to be deleted.

    .impl.search: SplayTreeSearch: Splay the node around the supplied key.  If the
    splay found a matching node, return it; otherwise return failure.

    .impl.neighbours: SplayTreeNeighbours: Splay the tree around the supplied key.
    If the splay found a matching node, return failure.  Otherwise, determine
    whether the (non-matching) found node is the left or right neighbour of the key
    (by comparison with the key).  Set the tree root to be the right or left child
    of that first neighbour respectively, and again splay the tree around the
    supplied key.  The new root will be the second neighbour, and will have a null
    left or right child respectively.  Set this null child to be the first
    neighbour.  Return the two neighbours.

    .impl.neighbours.note: Note that it would be possible to implement
    SplayTreeNeighbours with only one splay, and then a normal binary tree search
    for the left or right neighbour of the root.  This would be a cheaper
    operation, but would give poorer amortised cost if the call to
    SplayTreeNeighbours typically precedes a call to SplayTreeInsert (which is
    expected to be a common usage pattern - see .usage.insert). It's also possible
    to implement SplayTreeNeighbours by simply keeping track of both neighbours
    during a single splay. This has about the same cost as a single splay, and
    hence about the same amortised cost if the call to SplayTreeNeighbours typically precedes a call to
    SplayTreeInsert.

    .impl.next: SplayTreeNext: Splay the tree around the supplied oldKey. During
    iteration the "old node" found is probably already at the root, in which case
    this will be a null operation with little cost.  If this old node has no right
    child, return NULL. Otherwise, split the tree into a right tree (which contains
    just the right child of the old node) and a left tree (which contains the old
    node, its left child and no right child). The next node is the first node in
    the right tree. Find this by splaying the right tree around oldKey (which is
    known to compare CompareLESS than any keys in the right tree). Rejoin the full
    tree, using the right tree as the root and setting the left child of root to be
    the left tree. Return the root of this tree.

    TESTING

    .test: There is no plan to test splay trees directly.  It is believed that the
    testing described in design.mps.cbs.test will be sufficient to test this
    implementation.

    ERROR HANDLING

    .error: This module detects and reports most common classes of protocol error.
    The cases it doesn't handle will result in undefined behaviour and probably
    cause an AVER to fire.  These are:

    .error.bad-pointer: Passing an invalid pointer in place of a SplayTree or
    SplayNode.

    .error.bad-compare: Initialising a SplayTree with a compare function that is
    not a valid compare function, or which doesn't implement a total ordering on
    splay nodes.

    .error.bad-describe: Passing an invalid describe method to SplayTreeDescribe.

    .error.out-of-stack: Stack exhaustion under SplayTreeDescribe.

    FUTURE

    .future.tree: It would be possible to split the splay tree module into two: one
    that implements binary trees; and one that implements splay trees on top of a
    binary tree.

    .future.parent: The iterator could be made more efficient (in an amortized
    sense) if it didn't splay at each node.  To implement this (whilst meeting
    .req.stack) we really need parent pointers from the nodes.  We could use the
    (first-child, right-sibling/parent) trick described in paper.st85 to implement
    this, at a slight cost to all other tree operations, and an increase in code
    complexity.  paper.st85 doesn't describe how to distinguish the first-child
    between left-child and right-child, and the right-sibling/parent between
    right-sibling and parent.  One could either use the comparator to make these
    distinctions, or steal some bits from the pointers.

    .future.reverse: The assembly phase could be made more efficient if the link
    left and link right operations were modified to add to the left and right trees
    with pointers reversed. This would remove the need for the assembly phase to
    reverse them.

## 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/splay/index.html#2 $`

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