main.go

package main

import (
	"math/rand"
	"sync/atomic"
	"time"
)

const (
	numGs    = 10
	numNodes = 100000 / numGs
)

var insertRate int64 = 90

func main() {
	done := make(chan int)
	for i := 0; i < numGs; i++ {
		go worker(done)
	}

	<-time.After(5 * time.Second)
	atomic.StoreInt64(&insertRate, 50)

	<-time.After(5 * time.Second)
	atomic.StoreInt64(&insertRate, 0)
	for i := 0; i < numGs; i++ {
		<-done
	}
}

func worker(done chan<- int) {
	// Create a local splay tree.
	tree := &Tree{nil}
	for i := 0; i < numNodes; i++ {
		k := Key(rand.Float64())
		tree.Insert(k, newVal())
	}

	for atomic.LoadInt64(&insertRate) != 0 {
		if int64(rand.Intn(100)) <= insertRate {
			// Perform insertion
			doInsert(tree)
		} else {
			// Perform lookup
			doLookup(tree)
		}
	}
	done <- 1
}

func newVal() interface{} {
	return new([128]*byte)
}

func doInsert(tree *Tree) {
	for {
		k := Key(rand.Float64())
		if _, ok := tree.Find(k); !ok {
			tree.Insert(k, newVal())
			if gk, _, ok := tree.FindGreatestLessThan(k); ok {
				tree.Remove(gk)
			} else {
				tree.Remove(k)
			}
			break
		}
	}
}

func doLookup(tree *Tree) {
	k := Key(rand.Float64())
	tree.FindGreatestLessThan(k)
}

// Derived from splay.js in the Octane benchmark suite:
//   https://code.google.com/p/octane-benchmark/source/browse/trunk/splay.js
//
// Copyright 2009 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * 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.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// 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 AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR 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.

type Key float64

type Val interface{}

// A splay tree is a self-balancing binary search tree with the
// additional property that recently accessed elements are quick to
// access again. It performs basic operations such as insertion,
// look-up and removal in O(log(n)) amortized time.
type Tree struct {
	root *node
}

type node struct {
	k           Key
	v           Val
	left, right *node
}

var k0 Key

var v0 Val

// IsEmpty returns whether the tree is empty.
func (tree *Tree) IsEmpty() bool {
	return tree.root == nil
}

// Insert inserts a node into the tree with the specified key and
// value if the tree does not already contain a node with the
// specified key. If the value is inserted, it becomes the root of the
// tree.
func (tree *Tree) Insert(k Key, v Val) {
	if tree.IsEmpty() {
		tree.root = &node{k: k, v: v}
		return
	}

	// Splay on the key to move the last node on the search path
	// for the key to the root of the tree.
	tree.splay(k)
	if tree.root.k == k {
		return
	}

	node := &node{k: k, v: v}
	if k > tree.root.k {
		node.left = tree.root
		node.right = tree.root.right
		tree.root.right = nil
	} else {
		node.right = tree.root
		node.left = tree.root.left
		tree.root.left = nil
	}
	tree.root = node
}

// Remove removes a node with the specified key from the tree. If the
// tree contains a node with this key, Remove returns the node's value
// and true. If the key is not found, Remove returns the zero value
// and false.
func (tree *Tree) Remove(k Key) (Val, bool) {
	if tree.IsEmpty() {
		return v0, false
	}
	tree.splay(k)
	if tree.root.k != k {
		return v0, false
	}
	removed := tree.root
	if tree.root.left == nil {
		tree.root = tree.root.right
	} else {
		right := tree.root.right
		tree.root = tree.root.left
		// Splay to make sure that the new root has an empty
		// right child.
		tree.splay(k)
		// Insert the original right child as the right child
		// of the new root.
		tree.root.right = right
	}
	return removed.v, true
}

// Find returns the value of the node having the specified key or the
// zero value and false if the tree doesn't contain a node with the
// specified key.
func (tree *Tree) Find(k Key) (Val, bool) {
	if tree.IsEmpty() {
		return v0, false
	}
	tree.splay(k)
	if tree.root.k == k {
		return tree.root.v, true
	}
	return v0, false
}

// findMax returns the node with the largest key in the subtree rooted
// at n.
func (n *node) findMax() *node {
	if n == nil {
		return nil
	}
	for n.right != nil {
		n = n.right
	}
	return n
}

// FindGreatestLessThan returns the key/value pair having the maximum
// key value that is less than k.  If no such pair exists,
// FindGreatestLessThan returns the zero key, zero value, and false.
func (tree *Tree) FindGreatestLessThan(k Key) (Key, Val, bool) {
	if tree.IsEmpty() {
		return k0, v0, false
	}
	// Splay on the key to move the node with the given key or the
	// last node on the search path to the top of the tree.
	tree.splay(k)
	// Now the result is either the root node or the greatest node
	// in the left subtree.
	if tree.root.k < k {
		return tree.root.k, tree.root.v, true
	} else if tree.root.left != nil {
		max := tree.root.left.findMax()
		return max.k, max.v, true
	} else {
		return k0, v0, false
	}
}

// KeysToSlice returns a slice of all the keys of tree's nodes.
func (tree *Tree) KeysToSlice() []Key {
	out := make([]Key, 0)
	var rec func(n *node)
	rec = func(n *node) {
		if n != nil {
			rec(n.left)
			out = append(out, n.k)
			rec(n.right)
		}
	}
	rec(tree.root)
	return out
}

// splay moves the node with the given key to the top of the tree.  If
// no node has the given key, the last node on the search path is
// moved to the top of the tree. This is the simplified top-down
// splaying algorithm from: "Self-adjusting Binary Search Trees" by
// Sleator and Tarjan.
func (tree *Tree) splay(k Key) {
	// Create a dummy node.  The use of the dummy node is a bit
	// counter-intuitive: The right child of the dummy node will
	// hold the L tree of the algorithm.  The left child of the
	// dummy node will hold the R tree of the algorithm.  Using a
	// dummy node, left and right will always be nodes and we
	// avoid special cases.
	dummy := new(node)
	left := dummy
	right := dummy

	cur := tree.root
	for {
		if k < cur.k {
			if cur.left == nil {
				break
			}
			if k < cur.left.k {
				// Rotate right
				tmp := cur.left
				cur.left = tmp.right
				tmp.right = cur
				cur = tmp
				if cur.left == nil {
					break
				}
			}
			// Link right
			right.left = cur
			right = cur
			cur = cur.left
		} else if k > cur.k {
			if cur.right == nil {
				break
			}
			if k > cur.right.k {
				// Rotate left
				tmp := cur.right
				cur.right = tmp.left
				tmp.left = cur
				cur = tmp
				if cur.right == nil {
					break
				}
			}
			// Left left
			left.right = cur
			left = cur
			cur = cur.right
		} else {
			break
		}
	}
	// Assemble
	left.right = cur.left
	right.left = cur.right
	cur.left = dummy.right
	cur.right = dummy.left
	tree.root = cur
}