b+ tree, hand transposed from c

bplus.go

/*
 * // Copyright (c) 2021. Scott Cagno. All rights reserved.
 * // Use of this source code is governed by a BSD-style (clause 3)
 * // license that can be found in the root of this project in the LICENSE file.
 */

package bptree

import (
	"bytes"
	"log"
	"unsafe"
)

const ORDER = 32

type KeyType = []byte
type ValType = []byte

/*
 *	node represents a node of the Tree
 */
type node struct {
	numKeys  int
	keys     [ORDER - 1]KeyType
	pointers [ORDER]unsafe.Pointer
	parent   *node
	isLeaf   bool
}

func (n *node) hasKey(key KeyType) bool {
	if n.isLeaf {
		for i := 0; i < n.numKeys; i++ {
			if bytes.Equal(key, n.keys[i]) {
				return true
			}
		}
	}
	return false
}

func (n *node) record(key KeyType) (*Record, bool) {
	if n.isLeaf {
		for i := 0; i < n.numKeys; i++ {
			if bytes.Equal(key, n.keys[i]) {
				return (*Record)(n.pointers[i]), true
			}
		}
	}
	return nil, false
}

/*
 *	Record represents a Record pointed to by a leaf node
 */
type Record struct {
	Key   KeyType
	Value ValType
}

/*
 *	Tree represents the root of a b+tree
 */
type Tree struct {
	root *node
}

// NewTree creates and returns a new tree
func NewTree() *Tree {
	return new(Tree)
}

// Has returns a boolean indicating weather or not
// the provided key and associated record exists.
func (t *Tree) Has(key KeyType) bool {
	return t.findRecord(key) != nil
}

// Add inserts a new record using the provided key. It
// only inserts and entry if the key does not already exist.
func (t *Tree) Add(key KeyType, value ValType) {
	// If the tree is empty, start a new one and return.
	if t.root == nil {
		t.root = startNewTree(key, &Record{key, value})
		return
	}
	// If the tree already exists, let's see what we
	// get when we try to find the correct leaf.
	leaf := findLeaf(t.root, key)
	if leaf.hasKey(key) {
		return // Key already exists! So lets just return.
	}
	// If the tree already exists and the key has not been
	// found, then let's insert it into the tree and return!
	if leaf.numKeys < ORDER-1 {
		insertIntoLeaf(leaf, key, &Record{key, value})
		return
	}
	// Otherwise, insert, split and balance returning the updated root.
	t.root = insertIntoLeafAfterSplitting(t.root, leaf, key, &Record{key, value})
}

// Set inserts a new record using the provided key. It
// only inserts and entry if the key does not already exist.
func (t *Tree) Set(key KeyType, value ValType) {
	t.insert(key, value)
}

// Get returns the record for a given key if it exists
func (t *Tree) Get(key KeyType) *Record {
	return t.findRecord(key)
}

func (t *Tree) Del(key KeyType) {
	t.delete(key)
}

func (t *Tree) Range(iter func(r *Record) bool) {
	c := findFirstLeaf(t.root)
	if c == nil {
		return
	}
	var record *Record
	for {
		for i := 0; i < c.numKeys; i++ {
			record = (*Record)(c.pointers[i])
			if record != nil && !iter(record) {
				continue
			}
		}
		if c.pointers[ORDER-1] != nil {
			c = (*node)(c.pointers[ORDER-1])
		} else {
			break
		}
	}
}

func (t *Tree) Min() *Record {
	c := findFirstLeaf(t.root)
	if c == nil {
		return nil
	}
	return (*Record)(c.pointers[0])
}

func (t *Tree) Max() *Record {
	c := findLastLeaf(t.root)
	if c == nil {
		return nil
	}
	return (*Record)(c.pointers[c.numKeys-1])
}

func (t *Tree) Len() int {
	var count int
	for n := findFirstLeaf(t.root); n != nil; n = n.nextLeaf() {
		count += n.numKeys
	}
	return count
}

func (t *Tree) Close() {
	//t.destroyTree()
	t.root = nil
}

/*
 * insert is the "master" insertion function.
 * Inserts a key and an associated Value into
 * the B+ tree, causing the tree to be adjusted
 * however necessary to maintain the B+ tree
 * properties
 */
func (t *Tree) insert(key KeyType, value ValType) {
	/*
	 * CASE: Tree does not exist yet, start a new tree
	 */
	if t.root == nil {
		t.root = startNewTree(key, &Record{key, value})
		return
	}

	/*
	 * The current implementation ignores duplicates (will treat it kind of like a set operation)
	 */
	leaf, recordPointer := t.find(key)
	if recordPointer != nil {
		/*
		 * If the key already exists in this tree then proceed to update Value and return
		 */
		recordPointer.Value = value
		return
	}

	/*
	 * No Record found, so create a new Record for the Value
	 */
	//recordPointer = makeRecord(Value)

	/*
	 * CASE: Tree already exists (continue through the rest of the function)
	 */

	/*
	 * Leaf has room for the key and recordPointer--insert into leaf and return
	 */
	if leaf.numKeys < ORDER-1 {
		insertIntoLeaf(leaf, key, &Record{key, value})
		return
	}

	/*
	 * Leaf does not have enough room and needs to be split
	 */
	t.root = insertIntoLeafAfterSplitting(t.root, leaf, key, &Record{key, value})
	return
}

/*
 * startNewTree first insertion case: starts a new tree
 */
func startNewTree(key KeyType, pointer *Record) *node {
	root := makeLeaf()
	root.keys[0] = key
	root.pointers[0] = unsafe.Pointer(pointer)
	root.pointers[ORDER-1] = nil
	root.parent = nil
	root.numKeys++
	return root
}

/*
 * insertIntoNewRoot creates a new root for two subtrees and inserts the appropriate key into the new root
 */
func insertIntoNewRoot(left *node, key KeyType, right *node) *node {
	root := makeNode()
	root.keys[0] = key
	root.pointers[0] = unsafe.Pointer(left)
	root.pointers[1] = unsafe.Pointer(right)
	root.numKeys++
	root.parent = nil
	left.parent = root
	right.parent = root
	return root
}

/*
 * insertIntoParent inserts a new node (leaf or internal node) into the tree--returns the root of
 * the tree after insertion is complete
 */
func insertIntoParent(root *node, left *node, key KeyType, right *node) *node {

	/*
	 * Case: new root
	 */
	if left.parent == nil {
		return insertIntoNewRoot(left, key, right)
	}

	/*
	 * Case: leaf or node. (Remainder of function body.)
	 * Find the parents pointer to the left node
	 */
	leftIndex := getLeftIndex(left.parent, left)

	/*
	 * Simple case: the new key fits into the node.
	 */
	if left.parent.numKeys < ORDER-1 {
		return insertIntoNode(root, left.parent, leftIndex, key, right)
	}

	/* Harder case:  split a node in ORDER
	 * to preserve the B+ tree properties.
	 */
	return insertIntoNodeAfterSplitting(root, left.parent, leftIndex, key, right)
}

/*
 *	getLeftIndex helper function used in insertIntoParent to find the index of the parents
 *  pointer to the node to the left of the key to be inserted
 */
func getLeftIndex(parent, left *node) int {
	var leftIndex int
	for leftIndex <= parent.numKeys && (*node)(parent.pointers[leftIndex]) != left {
		leftIndex++
	}
	return leftIndex
}

/*
 * insertIntoNode inserts a new key and pointer to a node into a node into which these can fit without violating the
 * tree's properties
 */
func insertIntoNode(root, n *node, leftIndex int, key KeyType, right *node) *node {
	// Consider using copy, it might be better
	copy(n.pointers[leftIndex+2:], n.pointers[leftIndex+1:])
	copy(n.keys[leftIndex+1:], n.keys[leftIndex:])

	/* // ORIG
	for i := n.numKeys; i > leftIndex; i-- {
		n.pointers[i+1] = n.pointers[i]
		n.keys[i] = n.keys[i-1]
	}
	*/

	n.pointers[leftIndex+1] = unsafe.Pointer(right)
	n.keys[leftIndex] = key
	n.numKeys++
	return root
}

/*
 * insertIntoNodeAfterSplitting inserts a new key and pointer to a node into a node, causing the nodes
 * size to exceed the ORDER, and causing the node to split in two
 */
func insertIntoNodeAfterSplitting(root, oldNode *node, leftIndex int, key KeyType, right *node) *node {
	/*
	 * First create a temp set of keys and pointers to hold everything in ORDER, including
	 * the new key and pointer, inserted in their correct places--then create a new node
	 * and copy half of the keys and pointers to the old node and the other half to the new
	 */

	var i, j int
	var tempKeys [ORDER]KeyType                //tempKeys := make([]int, ORDER)
	var tempPointers [ORDER + 1]unsafe.Pointer //tempPointers := make([]interface{}, ORDER+1)

	for i, j = 0, 0; i < oldNode.numKeys+1; i, j = i+1, j+1 {
		if j == leftIndex+1 {
			j++
		}
		tempPointers[j] = oldNode.pointers[i]
	}

	for i, j = 0, 0; i < oldNode.numKeys; i, j = i+1, j+1 {
		if j == leftIndex {
			j++
		}
		tempKeys[j] = oldNode.keys[i]
	}

	tempPointers[leftIndex+1] = unsafe.Pointer(right)
	tempKeys[leftIndex] = key

	/*
	 * copy half the keys and pointers to the old node...
	 */
	split := cut(ORDER)

	oldNode.numKeys = 0

	for i = 0; i < split-1; i++ {
		oldNode.pointers[i] = tempPointers[i]
		oldNode.keys[i] = tempKeys[i]
		oldNode.numKeys++
	}
	oldNode.pointers[i] = tempPointers[i]
	kPrime := tempKeys[split-1]

	/*
	 * ...create the new node and copy the other half the keys and pointers
	 */
	newNode := makeNode()

	for i, j = i+1, 0; i < ORDER; i, j = i+1, j+1 {
		newNode.pointers[j] = tempPointers[i]
		newNode.keys[j] = tempKeys[i]
		newNode.numKeys++
	}
	newNode.pointers[j] = tempPointers[i]
	newNode.parent = oldNode.parent

	/*
	 * Free up tempPointers and tempKeys
	 */
	for i = 0; i < ORDER; i++ {
		tempKeys[i] = nil     // zero values
		tempPointers[i] = nil // zero values
	}
	tempPointers[ORDER] = nil

	var child *node
	for i = 0; i <= newNode.numKeys; i++ {
		child = (*node)(newNode.pointers[i])
		child.parent = newNode
	}

	/* Insert a new key into the parent of the two
	 * nodes resulting from the split, with
	 * the old node to the left and the new to the right.
	 */
	return insertIntoParent(root, oldNode, kPrime, newNode)
}

// insertIntoLeaf inserts a new pointer to a Record and its
// corresponding key into a leaf.
func insertIntoLeaf(leaf *node, key KeyType, pointer *Record) /* *node */ {
	var i, insertionPoint int
	for insertionPoint < leaf.numKeys && bytes.Compare(leaf.keys[insertionPoint], key) == -1 {
		insertionPoint++
	}
	for i = leaf.numKeys; i > insertionPoint; i-- {
		leaf.keys[i] = leaf.keys[i-1]
		leaf.pointers[i] = leaf.pointers[i-1]
	}
	leaf.keys[insertionPoint] = key
	leaf.pointers[insertionPoint] = unsafe.Pointer(pointer)
	leaf.numKeys++
	//return leaf // might not need to return this leaf
}

/*
 * insertIntoLeafAfterSplitting inserts a new key and pointer to a new Record into a leaf so as to exceed the tree's
 * ORDER, causing the leaf to be split in half
 */
func insertIntoLeafAfterSplitting(root, leaf *node, key KeyType, pointer *Record) *node {

	var insertionIndex int
	for insertionIndex < ORDER-1 && bytes.Compare(leaf.keys[insertionIndex], key) == -1 {
		insertionIndex++
	}

	var i, j int
	var tempKeys [ORDER]KeyType
	var tempPointers [ORDER]unsafe.Pointer

	for i, j = 0, 0; i < leaf.numKeys; i, j = i+1, j+1 {
		if j == insertionIndex {
			j++
		}
		tempKeys[j] = leaf.keys[i]
		tempPointers[j] = leaf.pointers[i]
	}

	tempKeys[insertionIndex] = key
	tempPointers[insertionIndex] = unsafe.Pointer(pointer)

	leaf.numKeys = 0

	split := cut(ORDER - 1)

	for i = 0; i < split; i++ {
		leaf.keys[i] = tempKeys[i]
		leaf.pointers[i] = tempPointers[i]
		leaf.numKeys++
	}

	newLeaf := makeLeaf()

	for i, j = split, 0; i < ORDER; i, j = i+1, j+1 {
		newLeaf.keys[j] = tempKeys[i]
		newLeaf.pointers[j] = tempPointers[i]
		newLeaf.numKeys++
	}

	// free temps
	for i = 0; i < ORDER; i++ {
		tempKeys[i] = nil     // zero Value
		tempPointers[i] = nil // zero Value
	}

	newLeaf.pointers[ORDER-1] = leaf.pointers[ORDER-1]
	leaf.pointers[ORDER-1] = unsafe.Pointer(newLeaf)

	for i = leaf.numKeys; i < ORDER-1; i++ {
		leaf.pointers[i] = nil
	}
	for i = newLeaf.numKeys; i < ORDER-1; i++ {
		newLeaf.pointers[i] = nil
	}

	newLeaf.parent = leaf.parent
	newKey := newLeaf.keys[0]

	return insertIntoParent(root, leaf, newKey, newLeaf)
}

/*
 *	findRecord finds and returns the Record to which a key refers
 */
func (t *Tree) find(key KeyType) (*node, *Record) {
	leaf := findLeaf(t.root, key)
	if leaf == nil {
		return nil, nil
	}
	/*
	 * If root/leaf != nil, leaf must have a Value, even if it does not contain the desired key.
	 * The leaf holds the range of keys that would include the desired key
	 */
	var i int
	for i = 0; i < leaf.numKeys; i++ {
		if bytes.Equal(leaf.keys[i], key) {
			break
		}
	}
	if i == leaf.numKeys {
		return leaf, nil
	}
	return leaf, (*Record)(leaf.pointers[i])
}

/*
 *	findRecord finds and returns the Record to which a key refers
 */
func (t *Tree) findRecord(key KeyType) *Record {
	leaf := findLeaf(t.root, key)
	if leaf == nil {
		return nil
	}
	/*
	 * If root/leaf != nil, leaf must have a Value, even if it does not contain the desired key.
	 * The leaf holds the range of keys that would include the desired key
	 */
	var i int
	for i = 0; i < leaf.numKeys; i++ {
		if bytes.Equal(leaf.keys[i], key) {
			break
		}
	}
	if i == leaf.numKeys {
		return nil
	}
	return (*Record)(leaf.pointers[i])
}

/*
 *	findLeaf traces the path from the root to a leaf, searching by key and displaying information about the path if the
 *  verbose flag is set--findLeaf returns the leaf containing the given key
 */
func findLeaf(root *node, key KeyType) *node {
	if root == nil {
		return root
	}
	i, c := 0, root
	for !c.isLeaf {
		i = 0
		for i < c.numKeys {
			if bytes.Compare(key, c.keys[i]) >= 0 {
				i++
			} else {
				break
			}
		}
		c = (*node)(c.pointers[i])
	}
	// c is the found leaf node
	return c
}

/*
 * findFirstLeaf traces the path from the root to the leftmost leaf in the tree
 */
func findFirstLeaf(root *node) *node {
	if root == nil {
		return root
	}
	c := root
	for !c.isLeaf {
		c = (*node)(c.pointers[0])
	}
	return c
}

func findLastLeaf(root *node) *node {
	if root == nil {
		return root
	}
	c := root
	for !c.isLeaf {
		c = (*node)(c.pointers[c.numKeys])
	}
	return c
}

/*
 *  nextLeaf returns the next non-nil leaf in the chain (to the right) of the current leaf
 */
func (n *node) nextLeaf() *node {
	if p := (*node)(n.pointers[ORDER-1]); p != nil && p.isLeaf {
		return p
	}
	return nil
}

/*
 * delete is the master delete function
 */
func (t *Tree) delete(key KeyType) {
	keyLeaf, keyRecord := t.find(key)
	if keyRecord != nil && keyLeaf != nil {
		t.root = deleteEntry(t.root, keyLeaf, key, unsafe.Pointer(keyRecord))
		keyRecord = nil
	}
}

/*
 * getNeighborIndex is a utility function for deletion. It gets the index of a node's nearest
 * sibling (that exists) to the left. If not then node is already the leftmost child and (in
 * such a case the node) will return -1
 */
func getNeighborIndex(n *node) int {
	var i int
	for i = 0; i <= n.parent.numKeys; i++ {
		if (*node)(n.parent.pointers[i]) == n {
			return i - 1
		}
	}
	log.Panicf("getNeighborIndex: Search for nonexistent pointer to node in parent.\nNode: %#v\n", n)
	return i
}

/*
 * removeEntryFromNode does just that
 */
func removeEntryFromNode(n *node, key KeyType, pointer unsafe.Pointer) *node {

	/*
	 * Remove the key and shift the other keys accordingly
	 */
	var i, numPointers int
	for !bytes.Equal(n.keys[i], key) {
		i++
	}
	for i++; i < n.numKeys; i++ { // was for i+=1;
		n.keys[i-1] = n.keys[i]
	}

	/*
	 * Remove the pointer and shift other pointers accordingly
	 */
	if n.isLeaf {
		numPointers = n.numKeys
	} else {
		numPointers = n.numKeys + 1
	}

	i = 0
	for n.pointers[i] != pointer {
		i++
	}
	for i++; i < numPointers; i++ { // was for i+=1;
		n.pointers[i-1] = n.pointers[i]
	}

	/*
	 * One key fewer
	 */
	n.numKeys--

	/*
	 * Set the other pointers to nil for tidiness. A leaf uses
	 * the last pointer to point to the next leaf
	 */
	if n.isLeaf {
		for i = n.numKeys; i < ORDER-1; i++ {
			n.pointers[i] = nil
		}
	} else {
		for i = n.numKeys + 1; i < ORDER; i++ {
			n.pointers[i] = nil
		}
	}
	return n
}

/*
 * deleteEntry deletes and entry from the tree. Removes the Record and it's key and pointer from
 * the leaf, and then makes all appropriate changes to preserve the tree's properties
 */
func deleteEntry(root, n *node, key KeyType, pointer unsafe.Pointer) *node {

	var minKeys, kPrimeIndex, capacity int

	/*
	 * Remove key and pointer from node
	 */
	n = removeEntryFromNode(n, key, pointer)

	/*
	 * CASE: deletion from the root node
	 */
	if n == root {
		return adjustRoot(root)
	}

	/*
	 * CASE: deletion from a node below the root (continue rest of function)
	 *
	 * Determine minimum allowable size of node to be preserved after deletion
	 */
	if n.isLeaf {
		minKeys = cut(ORDER - 1)
	} else {
		minKeys = cut(ORDER) - 1
	}

	/*
	 * CASE: node stays at or above minimum (simple case)
	 */
	if n.numKeys >= minKeys {
		return root
	}

	/*
			 * CASE: node falls below minimum. Either coalescence or redistribution is needed
		     *
			 * Find the appropriate neighbor node with which to coalesce. Also find the key (kPrime)
			 * in the parent between the pointer to node n and the pointer to the neighbor
	*/
	neighborIndex := getNeighborIndex(n)
	if neighborIndex == -1 {
		kPrimeIndex = 0
	} else {
		kPrimeIndex = neighborIndex
	}

	kPrime := n.parent.keys[kPrimeIndex]

	var neighbor *node
	if neighborIndex == -1 {
		neighbor = (*node)(n.parent.pointers[1])
	} else {
		neighbor = (*node)(n.parent.pointers[neighborIndex])
	}

	if n.isLeaf {
		capacity = ORDER
	} else {
		capacity = ORDER - 1
	}

	/*
	 * Coalescence
	 */
	if neighbor.numKeys+n.numKeys < capacity {
		return coalesceNodes(root, n, neighbor, neighborIndex, kPrime)
	}

	/*S
	 * Redistribution
	 */
	return redistributeNodes(root, n, neighbor, neighborIndex, kPrimeIndex, kPrime)
}

/*
 * adjustRoot does some magic in the root node (not really)
 */
func adjustRoot(root *node) *node {
	/*
	 * CASE: nonempty root. key and pointer have already been deleted, so nothing to be done
	 */
	if root.numKeys > 0 {
		return root
	}

	/*
	 * CASE: empty root. If it has a child, promote the first (only) child as the new root
	 */
	var newRoot *node
	if !root.isLeaf {
		newRoot = (*node)(root.pointers[0])
		newRoot.parent = nil
	} else {
		/*
		 * If it is a leaf (has no children), then the whole tree is in fact empty
		 */
		newRoot = nil // free
	}
	root = nil
	return newRoot
}

/*
 * coalesceNodes coalesces a node that has become too small after deletion with a
 * neighboring node that can accept the additional entries without exceeing the maximum
 */
func coalesceNodes(root, n, neighbor *node, neighborIndex int, kPrime KeyType) *node {

	var tmp *node

	/*
	 * Swap neighbor with node if node is on the extreme left and neighbor is to it's right
	 */
	if neighborIndex == -1 {
		tmp = n
		n = neighbor
		neighbor = tmp
	}

	/*
	 * Starting point in the neighbor for copying keys and pointers from n. Recall that n and
	 * neighbor have swapped places in the special case of n being a leftmost child
	 */
	neighborInsertionIndex := neighbor.numKeys
	var i, j, nEnd int

	/*
	 * CASE: Nonleaf node. Append kPrime and the following pointer and append all pointers and keys from the neighbor
	 */
	if !n.isLeaf {
		/*
		 * Append kPrime
		 */
		neighbor.keys[neighborInsertionIndex] = kPrime
		neighbor.numKeys++
		nEnd = n.numKeys

		// TODO: THIS MIGHT BE WRONG - NEVERMIND
		for i, j = neighborInsertionIndex+1, 0; j < nEnd; i, j = i+1, j+1 {
			neighbor.keys[i] = n.keys[j]
			neighbor.pointers[i] = n.pointers[j]
			neighbor.numKeys++
			n.numKeys--
		}

		/*
		 * The number of pointers is always one more than the number of keys
		 */
		neighbor.pointers[i] = n.pointers[j]

		/*
		 * All children must now point up to the same parent
		 */
		for i = 0; i < neighbor.numKeys+1; i++ {
			tmp = (*node)(neighbor.pointers[i])
			tmp.parent = neighbor
		}
		/*
		 * CASE: In a leaf, append the keys and pointers of n to the neighbor.
		 * Set the neighbor's last pointer to point to what had been n's right neighbor.
		 */
	} else {
		for i, j = neighborInsertionIndex, 0; j < n.numKeys; i, j = i+1, j+1 {
			neighbor.keys[i] = n.keys[j]
			neighbor.pointers[i] = n.pointers[j]
			neighbor.numKeys++
		}
		neighbor.pointers[ORDER-1] = n.pointers[ORDER-1]
	}
	root = deleteEntry(root, n.parent, kPrime, unsafe.Pointer(n))
	n = nil // free
	return root
}

/*
 * redistributeNodes redistributes entries between two nodes when one has become too small
 * after deletion but its neighbor is too big to append the small node's entries without
 * exceeding the maximum
 */
func redistributeNodes(root, n, neighbor *node, neighborIndex, kPrimeIndex int, kPrime KeyType) *node {

	var i int
	var tmp *node

	/*
	 * CASE: n has a neighbor to the left. Pull the neighbor's last key-pointer pair over
	 * from the neighbor's right end to n's lef end
	 */
	if neighborIndex != -1 {
		if !n.isLeaf {
			n.pointers[n.numKeys+1] = n.pointers[n.numKeys]
		}
		for i = n.numKeys; i > 0; i-- {
			n.keys[i] = n.keys[i-1]
			n.pointers[i] = n.pointers[i-1]
		}
		if !n.isLeaf {
			n.pointers[0] = neighbor.pointers[neighbor.numKeys]
			tmp = (*node)(n.pointers[0])
			tmp.parent = n
			neighbor.pointers[neighbor.numKeys] = nil
			n.keys[0] = kPrime
			n.parent.keys[kPrimeIndex] = neighbor.keys[neighbor.numKeys-1]
		} else {
			n.pointers[0] = neighbor.pointers[neighbor.numKeys-1]
			neighbor.pointers[neighbor.numKeys-1] = nil
			n.keys[0] = neighbor.keys[neighbor.numKeys-1]
			n.parent.keys[kPrimeIndex] = n.keys[0]
		}

		/*
		 * CASE: n is the leftmost child. Take a key-pointer pair from the neighbor
		 * to the right.  Move the neighbor's leftmost key-pointer pair to n's rightmost position
		 */
	} else {
		if n.isLeaf {
			n.keys[n.numKeys] = neighbor.keys[0]
			n.pointers[n.numKeys] = neighbor.pointers[0]
			n.parent.keys[kPrimeIndex] = neighbor.keys[1]
		} else {
			n.keys[n.numKeys] = kPrime
			n.pointers[n.numKeys+1] = neighbor.pointers[0]
			tmp = (*node)(n.pointers[n.numKeys+1])
			tmp.parent = n
			n.parent.keys[kPrimeIndex] = neighbor.keys[0]
		}
		for i = 0; i < neighbor.numKeys-1; i++ {
			neighbor.keys[i] = neighbor.keys[i+1]
			neighbor.pointers[i] = neighbor.pointers[i+1]
		}
		if !n.isLeaf {
			neighbor.pointers[i] = neighbor.pointers[i+1]
		}
	}

	/*
	 * n now has one more key and one more pointer; the neighbor has one fewer of each
	 */
	n.numKeys++
	neighbor.numKeys--
	return root
}

func destroyTreeNodes(n *node) {
	if n == nil {
		return
	}
	if n.isLeaf {
		for i := 0; i < n.numKeys; i++ {
			n.pointers[i] = nil
		}
	} else {
		for i := 0; i < n.numKeys+1; i++ {
			destroyTreeNodes((*node)(n.pointers[i]))
		}
	}
	n = nil
}

func (t *Tree) destroyTree() {
	destroyTreeNodes(t.root)
}

/*
 *	cut finds the appropriate place to split a node that is too big
 */
func cut(length int) int {
	if length%2 == 0 {
		return length / 2
	}
	return length/2 + 1
}

// makeRecord create a new Record to hold the Value to which a key refers
func makeRecord(value ValType) *Record {
	return &Record{
		Value: value,
	}
}

// makeNode creates a new general node, which can be adapted to serve as either a leaf or internal node
func makeNode() *node {
	return &node{}
}

// makeLeaf creates a new leaf by creating a node and then adapting it appropriately
func makeLeaf() *node {
	leaf := makeNode()
	leaf.isLeaf = true
	return leaf
}

func Btoi(b []byte) int64 {
	return int64(b[7]) |
		int64(b[6])<<8 |
		int64(b[5])<<16 |
		int64(b[4])<<24 |
		int64(b[3])<<32 |
		int64(b[2])<<40 |
		int64(b[1])<<48 |
		int64(b[0])<<56
}

func Itob(i int64) []byte {
	return []byte{
		byte(i >> 56),
		byte(i >> 48),
		byte(i >> 40),
		byte(i >> 32),
		byte(i >> 24),
		byte(i >> 16),
		byte(i >> 8),
		byte(i),
	}
}

bpt.go

package bpt

import (
	"bytes"
	"fmt"
	"log"
)

const ORDER = 64

type record struct {
	value []byte
}

type node struct {
	num_keys int
	keys     [][]byte
	ptrs     []interface{}
	parent   *node
	next     *node
	is_leaf  bool
}

var queue *node = nil

// helper function for printing the
// tree out. (see print_tree)
func enqueue(new_node *node) {
	var c *node
	if queue == nil {
		queue = new_node
		queue.next = nil
	} else {
		c = queue
		for c.next != nil {
			c = c.next
		}
		c.next = new_node
		new_node.next = nil
	}
}

// helper function for printing the
// tree out. (see print_tree)
func dequeue() *node {
	var n *node = queue
	queue = queue.next
	n.next = nil
	return n
}

// prints the bottom row of keys of the tree
func print_leaves(root *node) {
	var i int
	var c *node = root
	if root == nil {
		fmt.Printf("Empty tree.\n")
		return
	}
	for !c.is_leaf {
		c = c.ptrs[0].(*node)
	}
	for {
		for i = 0; i < c.num_keys; i++ {
			fmt.Printf("%s ", c.keys[i])
		}
		if c.ptrs[ORDER-1] != nil {
			fmt.Printf(" | ")
			c = c.ptrs[ORDER-1].(*node)
		} else {
			break
		}
	}
	fmt.Printf("\n")
}

// utility to give the height of the tree
func height(root *node) int {
	var h int
	var c *node = root
	for !c.is_leaf {
		c = c.ptrs[0].(*node)
		h++
	}
	return h
}

// utility function to give the length in edges
// for the path from any node to the root
func path_to_root(root, child *node) int {
	var length int
	var c *node = child
	for c != root {
		c = c.parent
		length++
	}
	return length
}

// print tree out
func print_tree(root *node) {
	var n *node = nil
	var i, rank, new_rank int
	if root == nil {
		fmt.Printf("Empty tree.\n")
		return
	}
	queue = nil
	enqueue(root)
	for queue != nil {
		n = dequeue()
		if n.parent != nil && n == n.parent.ptrs[0] {
			new_rank = path_to_root(root, n)
			if new_rank != rank {
				rank = new_rank
				fmt.Printf("\n")
			}
		}
		for i = 0; i < n.num_keys; i++ {
			fmt.Printf("%s ", n.keys[i])
		}
		if !n.is_leaf {
			for i = 0; i <= n.num_keys; i++ {
				enqueue(n.ptrs[i].(*node))
			}
		}
		fmt.Printf("| ")
	}
	fmt.Printf("\n")
}

// find leaf type node for a given key
func find_leaf(root *node, key []byte) *node {
	var c *node = root
	if c == nil {
		return c
	}
	var i int
	for !c.is_leaf {
		i = 0
		for i < c.num_keys {
			if bytes.Compare(key, c.keys[i]) >= 0 {
				i++
			} else {
				break
			}
		}
		// TODO: DEBUG LINE
		if c.ptrs[i] == nil {
			log.Printf(">> i=%d, c.num_keys=%d, c.ptrs=%+v\n", i, c.num_keys, c.ptrs)
		}
		c = c.ptrs[i].(*node)
	}
	return c
}

// find first leaf
func find_first_leaf(root *node) *node {
	if root == nil {
		return root
	}
	var c *node = root
	for !c.is_leaf {
		c = c.ptrs[0].(*node)
	}
	return c
}

// find record for a given key
func find(root *node, key []byte) *record {
	var c *node = find_leaf(root, key)
	if c == nil {
		return nil
	}
	var i int
	for i = 0; i < c.num_keys; i++ {
		if bytes.Equal(c.keys[i], key) {
			break
		}
	}
	if i == c.num_keys {
		return nil
	}
	return c.ptrs[i].(*record)

}

// find split point of full node
func cut(length int) int {
	if length%2 == 0 {
		return length / 2
	}
	return length/2 + 1
}

// create a record to hold a value for a given key
func make_record(val []byte) *record {
	return &record{
		value: val,
	}
}

// create a new general node... can be adapted
// to serve as either an internal or leaf node
func make_node() *node {
	return &node{
		num_keys: 0,
		keys:     make([][]byte, ORDER-1),
		ptrs:     make([]interface{}, ORDER),
		parent:   nil,
		next:     nil,
		is_leaf:  false,
	}
}

// create a new leaf node by addapting a general node
func make_leaf() *node {
	var leaf *node
	leaf = make_node()
	leaf.is_leaf = true
	return leaf
}

// helper->insert_into_parent
// used to find index of the parent's ptr to the
// node to the left of the key to be inserted
func get_left_index(parent, left *node) int {
	left_index := 0
	for left_index <= parent.num_keys && parent.ptrs[left_index] != left {
		left_index++
	}
	return left_index
}

// inserts a new key and *record into a leaf, then returns leaf
func insert_into_leaf(leaf *node, key []byte, ptr *record) *node {
	var i, insertion_point int
	for insertion_point < leaf.num_keys && bytes.Compare(leaf.keys[insertion_point], key) == -1 {
		insertion_point++
	}
	for i = leaf.num_keys; i > insertion_point; i-- {
		leaf.keys[i] = leaf.keys[i-1]
		leaf.ptrs[i] = leaf.ptrs[i-1]
	}
	leaf.keys[insertion_point] = key
	leaf.ptrs[insertion_point] = ptr
	leaf.num_keys++
	return leaf
}

// inserts a new key and *record into a leaf, so as
// to exceed the order, causing the leaf to be split
func insert_into_leaf_after_splitting(root, leaf *node, key []byte, ptr *record) *node {

	var new_leaf *node
	var tmp_keys [ORDER][]byte
	var tmp_ptrs [ORDER]interface{}
	var insertion_index, split, i, j int
	var new_key []byte

	new_leaf = make_leaf()

	for insertion_index < ORDER-1 && bytes.Compare(leaf.keys[insertion_index], key) == -1 {
		insertion_index++
	}

	for i < leaf.num_keys {
		if j == insertion_index {
			j++
		}
		tmp_keys[j] = leaf.keys[i]
		tmp_ptrs[j] = leaf.ptrs[i]
		i++
		j++
	}
	tmp_keys[insertion_index] = key
	tmp_ptrs[insertion_index] = ptr

	leaf.num_keys = 0

	split = cut(ORDER - 1)

	for i = 0; i < split; i++ {
		leaf.ptrs[i] = tmp_ptrs[i]
		leaf.keys[i] = tmp_keys[i]
		leaf.num_keys++
	}

	j = 0
	for i = split; i < ORDER; i++ {
		new_leaf.ptrs[j] = tmp_ptrs[i]
		new_leaf.keys[j] = tmp_keys[i]
		new_leaf.num_keys++
		j++
	}

	// freeing tmps...
	for i = 0; i < ORDER; i++ {
		tmp_ptrs[i] = nil
		tmp_keys[i] = nil
	}

	new_leaf.ptrs[ORDER-1] = leaf.ptrs[ORDER-1]
	leaf.ptrs[ORDER-1] = new_leaf

	for i = leaf.num_keys; i < ORDER-1; i++ {
		leaf.ptrs[i] = nil
	}

	for i = new_leaf.num_keys; i < ORDER-1; i++ {
		new_leaf.ptrs[i] = nil
	}

	new_leaf.parent = leaf.parent
	new_key = new_leaf.keys[0]

	return insert_into_parent(root, leaf, new_key, new_leaf)
}

// insert a new key, ptr to a node
func insert_into_node(root, n *node, left_index int, key []byte, right *node) *node {
	var i int
	for i = n.num_keys; i > left_index; i-- {
		n.ptrs[i+1] = n.ptrs[i]
		n.keys[i] = n.keys[i-1]
	}
	n.ptrs[left_index+1] = right
	n.keys[left_index] = key
	n.num_keys++
	return root
}

// insert a new key, ptr to a node causing node to split
func insert_into_node_after_splitting(root, old_node *node, left_index int, key []byte, right *node) *node {
	var i, j, split int
	var new_node, child *node
	var tmp_keys [ORDER][]byte
	var tmp_ptrs [ORDER + 1]interface{}
	var k_prime []byte

	for i < old_node.num_keys+1 {
		if j == left_index+1 {
			j++
		}
		tmp_ptrs[j] = old_node.ptrs[i]
		i++
		j++
	}

	i = 0
	j = 0

	for i < old_node.num_keys {
		if j == left_index {
			j++
		}
		tmp_keys[j] = old_node.keys[i]
		i++
		j++
	}

	tmp_ptrs[left_index+1] = right
	tmp_keys[left_index] = key

	split = cut(ORDER)
	new_node = make_node()
	old_node.num_keys = 0

	for i = 0; i < split-1; i++ {
		old_node.ptrs[i] = tmp_ptrs[i]
		old_node.keys[i] = tmp_keys[i]
		old_node.num_keys++
	}

	old_node.ptrs[i] = tmp_ptrs[i]
	k_prime = tmp_keys[split-1]

	j = 0
	for i += 1; i < ORDER; i++ {
		new_node.ptrs[j] = tmp_ptrs[i]
		new_node.keys[j] = tmp_keys[i]
		new_node.num_keys++
		j++
	}

	new_node.ptrs[j] = tmp_ptrs[i]

	// free tmps...
	for i = 0; i < ORDER; i++ {
		tmp_keys[i] = nil
		tmp_ptrs[i] = nil
	}
	tmp_ptrs[ORDER] = nil

	new_node.parent = old_node.parent

	for i = 0; i <= new_node.num_keys; i++ {
		child = new_node.ptrs[i].(*node)
		child.parent = new_node
	}
	return insert_into_parent(root, old_node, k_prime, new_node)
}

// insert a new node (leaf or internal) into tree, return root of tree
func insert_into_parent(root, left *node, key []byte, right *node) *node {
	var left_index int
	var parent *node
	parent = left.parent
	if parent == nil {
		return insert_into_new_root(left, key, right)
	}
	left_index = get_left_index(parent, left)
	if parent.num_keys < ORDER-1 {
		return insert_into_node(root, parent, left_index, key, right)
	}
	return insert_into_node_after_splitting(root, parent, left_index, key, right)
}

// creates a new root for two sub-trees and inserts the key into the new root
func insert_into_new_root(left *node, key []byte, right *node) *node {
	var root *node = make_node()
	root.keys[0] = key
	root.ptrs[0] = left
	root.ptrs[1] = right
	root.num_keys++
	root.parent = nil
	left.parent = root
	right.parent = root
	return root
}

// first insertion, start a new tree
func start_new_tree(key []byte, ptr *record) *node {
	var root *node = make_leaf()
	root.keys[0] = key
	root.ptrs[0] = ptr
	root.ptrs[ORDER-1] = nil
	root.parent = nil
	root.num_keys++
	return root
}

// master insert function
func insert(root *node, key []byte, val []byte) *node {

	var ptr *record
	var leaf *node

	if find(root, key) != nil {
		return root
	}

	ptr = make_record(val)

	if root == nil {
		return start_new_tree(key, ptr)
	}

	leaf = find_leaf(root, key)

	if leaf.num_keys < ORDER-1 {
		leaf = insert_into_leaf(leaf, key, ptr)
		return root
	}

	return insert_into_leaf_after_splitting(root, leaf, key, ptr)
}

// helper for delete methods... returns index of
// a nodes nearest sibling to the left if one exists
func get_neighbor_index(n *node) int {
	var i int
	for i = 0; i <= n.parent.num_keys; i++ {
		if n.parent.ptrs[i] == n {
			return i - 1
		}
	}
	log.Fatalf("Search for nonexistent ptr to node in parent.\nNode: %p\n", n)
	return 1
}

func remove_entry_from_node(n *node, key []byte, ptr interface{}) *node {
	var i, num_ptrs int
	// remove key and shift over keys accordingly
	for !bytes.Equal(n.keys[i], key) {
		i++
	}
	for i += 1; i < n.num_keys; i++ {
		n.keys[i-1] = n.keys[i]
	}
	// remove ptr and shift other ptrs accordingly
	// first determine the number of ptrs
	if n.is_leaf {
		num_ptrs = n.num_keys
	} else {
		num_ptrs = n.num_keys + 1
	}
	i = 0
	for n.ptrs[i] != ptr {
		i++
	}

	//for n.ptrs[i].(*node) != ptr {
	//	i++
	//}
	for i += 1; i < num_ptrs; i++ {
		n.ptrs[i-1] = n.ptrs[i]
	}
	// one key has been removed
	n.num_keys--
	// set other ptrs to nil for tidiness; remember leaf
	// nodes use the last ptr to point to the next leaf
	if n.is_leaf {
		for i = n.num_keys; i < ORDER-1; i++ {
			n.ptrs[i] = nil
		}
	} else {
		for i = n.num_keys + 1; i < ORDER; i++ {
			n.ptrs[i] = nil
		}
	}
	return n
}

func adjust_root(root *node) *node {
	// if non-empty root key and ptr
	// have already been deleted, so
	// nothing to be done here
	if root.num_keys > 0 {
		return root
	}
	var new_root *node
	// if root is empty and has a child
	// promote first (only) child as the
	// new root node. If it's a leaf then
	// the while tree is empty...
	if !root.is_leaf {
		new_root = root.ptrs[0].(*node)
		new_root.parent = nil
	} else {
		new_root = nil
	}
	root = nil // free root
	return new_root
}

// merge (underflow)
func coalesce_nodes(root, n, neighbor *node, neighbor_index int, k_prime []byte) *node {
	var i, j, neighbor_insertion_index, n_end int
	var tmp *node
	// swap neight with node if nod eis on the
	// extreme left and neighbor is to its right
	if neighbor_index == -1 {
		tmp = n
		n = neighbor
		neighbor = tmp
	}
	// starting index for merged pointers
	neighbor_insertion_index = neighbor.num_keys
	// case nonleaf node, append k_prime and the following ptr.
	// append all ptrs and keys for the neighbors.
	if !n.is_leaf {
		// append k_prime (key)
		neighbor.keys[neighbor_insertion_index] = k_prime
		neighbor.num_keys++
		n_end = n.num_keys
		i = neighbor_insertion_index + 1
		j = 0
		for j < n_end {
			neighbor.keys[i] = n.keys[j]
			neighbor.ptrs[i] = n.ptrs[j]
			neighbor.num_keys++
			n.num_keys--
			i++
			j++
		}
		neighbor.ptrs[i] = n.ptrs[j]
		for i = 0; i < neighbor.num_keys+1; i++ {
			tmp = neighbor.ptrs[i].(*node)
			tmp.parent = neighbor
		}
	} else {
		// in a leaf; append the keys and ptrs.
		i = neighbor_insertion_index
		j = 0
		for j < n.num_keys {
			neighbor.keys[i] = n.keys[j]
			neighbor.ptrs[i] = n.ptrs[j]
			neighbor.num_keys++
			i++
			j++
		}
		neighbor.ptrs[ORDER-1] = n.ptrs[ORDER-1]
	}
	root = delete_entry(root, n.parent, k_prime, n)
	n.keys = nil
	n.ptrs = nil
	n = nil // free n
	return root
}

// merge / redistribute
func redistribute_nodes(root, n, neighbor *node, neighbor_index, k_prime_index int, k_prime []byte) *node {
	var i int
	var tmp *node

	// case: node n has a neighnor to the left
	if neighbor_index != -1 {
		if !n.is_leaf {
			n.ptrs[n.num_keys+1] = n.ptrs[n.num_keys]
		}
		for i = n.num_keys; i > 0; i-- {
			n.keys[i] = n.keys[i-1]
			n.ptrs[i] = n.ptrs[i-1]
		}
		if !n.is_leaf {
			n.ptrs[0] = neighbor.ptrs[neighbor.num_keys]
			tmp = n.ptrs[0].(*node)
			tmp.parent = n
			neighbor.ptrs[neighbor.num_keys] = nil
			n.keys[0] = k_prime
			n.parent.keys[k_prime_index] = neighbor.keys[neighbor.num_keys-1]
		} else {
			n.ptrs[0] = neighbor.ptrs[neighbor.num_keys-1]
			neighbor.ptrs[neighbor.num_keys-1] = nil
			n.keys[0] = neighbor.keys[neighbor.num_keys-1]
			n.parent.keys[k_prime_index] = n.keys[0]
		}
	} else {
		// case: n is left most child (n has no left neighbor)
		if n.is_leaf {
			n.keys[n.num_keys] = neighbor.keys[0]
			n.ptrs[n.num_keys] = neighbor.ptrs[0]
			n.parent.keys[k_prime_index] = neighbor.keys[1]
		} else {
			n.keys[n.num_keys] = k_prime
			n.ptrs[n.num_keys+1] = neighbor.ptrs[0]
			tmp = n.ptrs[n.num_keys+1].(*node)
			tmp.parent = n
			n.parent.keys[k_prime_index] = neighbor.keys[0]
		}
		for i = 0; i < neighbor.num_keys-1; i++ {
			neighbor.keys[i] = neighbor.keys[i+1]
			neighbor.ptrs[i] = neighbor.ptrs[i+1]
		}
		if !n.is_leaf {
			neighbor.ptrs[i] = neighbor.ptrs[i+1]
		}
	}

	n.num_keys++
	neighbor.num_keys--
	return root
}

// deletes an entry from the tree; removes record, key, and ptr from leaf and rebalances tree
func delete_entry(root, n *node, key []byte, ptr interface{}) *node {
	var min_keys, neighbor_index, k_prime_index, capacity int
	var neighbor *node
	var k_prime []byte

	// remove key, ptr from node
	n = remove_entry_from_node(n, key, ptr)
	//switch ptr.(type) {
	//case *node:
	//	n = remove_entry_from_node(n, key, ptr.(*node))
	//case *record:
	//	n = remove_entry_from_node(n, key, ptr.(*record))
	//}
	if n == root {
		return adjust_root(root)
	}

	// case: delete from inner node
	if n.is_leaf {
		min_keys = cut(ORDER - 1)
	} else {
		min_keys = cut(ORDER) - 1
	}
	// case: node stays at or above min order
	if n.num_keys >= min_keys {
		return root
	}

	// case: node is bellow min order; coalescence or redistribute
	neighbor_index = get_neighbor_index(n)
	if neighbor_index == -1 {
		k_prime_index = 0
	} else {
		k_prime_index = neighbor_index
	}
	k_prime = n.parent.keys[k_prime_index]
	if neighbor_index == -1 {
		neighbor = n.parent.ptrs[1].(*node)
	} else {
		neighbor = n.parent.ptrs[neighbor_index].(*node)
	}
	if n.is_leaf {
		capacity = ORDER
	} else {
		capacity = ORDER - 1
	}

	// coalescence
	if neighbor.num_keys+n.num_keys < capacity {
		return coalesce_nodes(root, n, neighbor, neighbor_index, k_prime)
	}
	return redistribute_nodes(root, n, neighbor, neighbor_index, k_prime_index, k_prime)
}

// master delete
func delete(root *node, key []byte) *node {
	var key_leaf *node
	var key_record *record

	key_record = find(root, key)
	key_leaf = find_leaf(root, key)
	if key_record != nil && key_leaf != nil {
		root = delete_entry(root, key_leaf, key, key_record)
		key_record = nil // free key_record
	}
	return root
}

func destroy_tree_nodes(root *node) {
	var i int
	if root.is_leaf {
		for i = 0; i < root.num_keys; i++ {
			root.ptrs[i] = nil
		}
	} else {
		for i = 0; i < root.num_keys+1; i++ {
			destroy_tree_nodes(root.ptrs[i].(*node))
		}
	}
	root.ptrs = nil // free
	root.keys = nil // free
	root = nil      // free
}

func destroy_tree(root *node) {
	destroy_tree_nodes(root)
}