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 [ST85] and [Sleator96]. As CBS is a client, design.mps.cbs. As PoolMVFF is an indirect client, design.mps.poolmvff. Also, as PoolMVT is an indirect client, design.mps.poolmvt.

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

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.

Definitions

.def.splay-tree: A splay tree is a self-adjusting binary tree as described in [ST85] and [Sleator96].

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

.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.tree.compare.method).

.def.successor: Node N₂ is the successor of node N₁ if N₁ and N₂ are both in the same tree, and the key of N₂ immediately follows the key of N₁ 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: The left neighbour of a key K is the node N with the largest key that compares less than K in the total order. The right neighbour of a key K is the node N with the smaller key that compares greater than K in the total order. A node is a neighbour of a key if it is either the left or right neighbour of the key.

.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.poolmvt, design.mps.poolmvff, design.mps.cbs, and general inferred MPS requirements.

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

.req.fast: Common operations must have low amortized cost.

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

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

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

.req.neighbours: Must be able to locate the neighbouring nodes of a key (see .def.neighbour). This is a common operation.

.req.iterate: Must be able to iterate over all nodes in key 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).

Generic binary tree interface

Splay tree interface

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

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 Tree (see .type.tree):

typedef struct FreeBlockStruct {
  TreeStruct treeStruct; /* 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 splay, Tree tree)
{
  /* 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 = FreeBlockOfTree(tree);

  Size maxSize = freeNode.size;

  if (TreeHasLeft(tree)) {
    FreeBlock leftNode = FreeBlockOfTree(TreeLeft(tree));
    if(leftNode.maxSize > maxSize)
      maxSize = leftNode->maxSize;
  }

  if (TreeHasRight(tree)) {
    FreeBlock rightNode = FreeBlockOfTree(TreeRight(tree));
    if(rightNode.maxSize > maxSize)
      maxSize = rightNode->maxSize;
  }

  freeNode->maxSize = maxSize;
}

.usage.compare: Comparison function (see .type.tree.compare.method):

Compare FreeBlockCompare(Tree tree, TreeKey key) {
  Addr base1, base2, limit2;
  FreeBlock freeNode = FreeBlockOfTree(tree);

  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 splay, Tree tree
                       void *closureP, Size 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 = closureS;
  FreeBlock freeNode = FreeBlockOfTree(tree);
  return freeNode->maxSize >= size;
}

.usage.test.node: Test node function (see .type.splay.test.node.method):

Bool FreeBlockTestNode(SplayTree splay, Tree tree
                       void *closureP, Size 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 = closureS;
  FreeBlock freeNode = FreeBlockOfTree(tree);
  return freeNode->size >= size;
}

.usage.initialization: Client's initialization function (see .function.splay.tree.init):

void FreeTreeInit(FreeTree freeTree) {
  /* Initialize the embedded splay tree. */
  SplayTreeInit(&freeTree->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 freeTree, Addr base, Addr limit) {
  SplayTree splayTree = &freeTree->splayTree;
  Tree leftNeighbour, rightNeighbour;
  TreeKey key = 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 != TreeEMPTY &&
      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(splayTree, leftNeighbour, key);

  } else if (rightNeighbour != TreeEMPTY &&
             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(splayTree, rightNeighbour, key);

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

    newBlock->base = base;
    newBlock->size = AddrOffset(base, limit);
    TreeInit(newTree);  /* `.function.tree.init`_ */
    SplayNodeUpdate(splayTree, newTree); /* `.function.splay.node.update`_ */
    /* `.function.splay.tree.insert`_ */
    res = SplayTreeInsert(splayTree, newTree, 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 freeTree, Size size) {
  SplayTree splayTree = &freeTree->splayTree;
  Tree 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, size);

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

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

    /* `.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 [ST85]. For more details of how to implement operations on splay trees, see [Sleator96]. Here we describe the operations involved.

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

.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.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 [ST85] to implement this, at a slight cost to all other tree operations, and an increase in code complexity. [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.

References

Document History

• 1998-05-01 Gavin Matthews. Initial draft.
• 1998-09-09 Gavin Matthews. Added client properties.
• 1999-03-10 David Jones. Polished for review (chiefly adding a definitions section).
• 1999-03-31 Tony Mann. Edited after review.
• 2002-06-07 RB Converted from MMInfo database design document.
• 2014-02-22 RB Fixing abuses of Res and ResFAIL.
• 2014-03-11 RB Updating in response to code review. Removing .future.tree and .future.reverse, both now implemented.

Copyright and License

Copyright © 2013-2014 Ravenbrook Limited. All rights reserved. <http://www.ravenbrook.com/>. 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 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.