blob: 6308fc93368e66e685b431554e9f6697dd3bc629 [file] [log] [blame]
package gkvlite
import (
"fmt"
)
// The core algorithms for treaps are straightforward. However, that
// algorithmic simplicity is obscured by the additional useful
// features, such as persistence, garbage-avoidance, stats tracking,
// and error handling. For a simple, memory-only implementation of
// the union/split/join treap algorithms that may be easier to
// understand, see:
// https://github.com/steveyen/gtreap/blob/master/treap.go
// Memory management rules: the union/split/join functions will not
// free their input nodeLoc's, but are responsible instead for
// invoking markReclaimable() on the directly pointed-at input nodes.
// The union/split/join functions must copy the input nodeLoc's if
// they wish to keep the nodeLoc's data.
//
// The caller is responsible for freeing the returned nodeLoc's and
// (if appropriate) the input nodeLoc's. The caller also takes
// responsibility for markReclaimable() on returned output nodes.
// Returns a treap that is the union of this treap and that treap.
func (o *Store) union(t *Collection, this *nodeLoc, that *nodeLoc,
reclaimMark *node) (
res *nodeLoc, err error) {
thisNode, err := this.read(o)
if err != nil {
return empty_nodeLoc, err
}
thatNode, err := that.read(o)
if err != nil {
return empty_nodeLoc, err
}
if this.isEmpty() || thisNode == nil {
return t.mkNodeLoc(nil).Copy(that), nil
}
if that.isEmpty() || thatNode == nil {
return t.mkNodeLoc(nil).Copy(this), nil
}
thisItemLoc := &thisNode.item
thisItem, err := thisItemLoc.read(t, false)
if err != nil {
return empty_nodeLoc, err
}
thatItemLoc := &thatNode.item
thatItem, err := thatItemLoc.read(t, false)
if err != nil {
return empty_nodeLoc, err
}
if thisItem.Priority > thatItem.Priority {
left, middle, right, err :=
o.split(t, that, thisItem.Key, reclaimMark)
if err != nil {
return empty_nodeLoc, err
}
newLeft, err := o.union(t, &thisNode.left, left, reclaimMark)
if err != nil {
return empty_nodeLoc, err
}
newRight, err := o.union(t, &thisNode.right, right, reclaimMark)
if err != nil {
return empty_nodeLoc, err
}
leftNum, leftBytes, rightNum, rightBytes, err :=
numInfo(o, newLeft, newRight)
if err != nil {
return empty_nodeLoc, err
}
var middleNode *node
if !middle.isEmpty() {
middleNode, err = middle.read(o)
if err != nil {
return empty_nodeLoc, err
}
middleItemLoc := &middleNode.item
res = t.mkNodeLoc(t.mkNode(middleItemLoc, newLeft, newRight,
leftNum+rightNum+1,
leftBytes+rightBytes+uint64(middleItemLoc.NumBytes(t))))
} else {
res = t.mkNodeLoc(t.mkNode(thisItemLoc, newLeft, newRight,
leftNum+rightNum+1,
leftBytes+rightBytes+uint64(thisItemLoc.NumBytes(t))))
}
t.freeNodeLoc(left)
t.freeNodeLoc(right)
t.freeNodeLoc(middle)
t.freeNodeLoc(newLeft)
t.freeNodeLoc(newRight)
t.markReclaimable(thisNode, reclaimMark)
t.markReclaimable(middleNode, reclaimMark)
return res, nil
}
// We don't use middle because the "that" node has precedence.
left, middle, right, err :=
o.split(t, this, thatItem.Key, reclaimMark)
if err != nil {
return empty_nodeLoc, err
}
newLeft, err := o.union(t, left, &thatNode.left, reclaimMark)
if err != nil {
return empty_nodeLoc, err
}
newRight, err := o.union(t, right, &thatNode.right, reclaimMark)
if err != nil {
return empty_nodeLoc, err
}
leftNum, leftBytes, rightNum, rightBytes, err :=
numInfo(o, newLeft, newRight)
if err != nil {
return empty_nodeLoc, err
}
res = t.mkNodeLoc(t.mkNode(thatItemLoc, newLeft, newRight,
leftNum+rightNum+1,
leftBytes+rightBytes+uint64(thatItemLoc.NumBytes(t))))
middleNode := middle.Node()
t.freeNodeLoc(left)
t.freeNodeLoc(right)
t.freeNodeLoc(middle)
t.freeNodeLoc(newLeft)
t.freeNodeLoc(newRight)
t.markReclaimable(thatNode, reclaimMark)
t.markReclaimable(middleNode, reclaimMark)
return res, nil
}
// Splits a treap into two treaps based on a split key "s". The
// result is (left, middle, right), where left treap has keys < s,
// right treap has keys > s, and middle is either...
// * empty/nil - meaning key s was not in the original treap.
// * non-empty - returning the original nodeLoc/item that had key s.
func (o *Store) split(t *Collection, n *nodeLoc, s []byte,
reclaimMark *node) (
*nodeLoc, *nodeLoc, *nodeLoc, error) {
nNode, err := n.read(o)
if err != nil || n.isEmpty() || nNode == nil {
return empty_nodeLoc, empty_nodeLoc, empty_nodeLoc, err
}
nItemLoc := &nNode.item
nItem, err := nItemLoc.read(t, false)
if err != nil {
return empty_nodeLoc, empty_nodeLoc, empty_nodeLoc, err
}
c := t.compare(s, nItem.Key)
if c == 0 {
left := t.mkNodeLoc(nil).Copy(&nNode.left)
right := t.mkNodeLoc(nil).Copy(&nNode.right)
middle := t.mkNodeLoc(nil).Copy(n)
return left, middle, right, nil
}
if c < 0 {
if nNode.left.isEmpty() {
return empty_nodeLoc, empty_nodeLoc, t.mkNodeLoc(nil).Copy(n), nil
}
left, middle, right, err :=
o.split(t, &nNode.left, s, reclaimMark)
if err != nil {
return empty_nodeLoc, empty_nodeLoc, empty_nodeLoc, err
}
leftNum, leftBytes, rightNum, rightBytes, err := numInfo(o, right, &nNode.right)
if err != nil {
return empty_nodeLoc, empty_nodeLoc, empty_nodeLoc, err
}
newRight := t.mkNodeLoc(t.mkNode(nItemLoc, right, &nNode.right,
leftNum+rightNum+1,
leftBytes+rightBytes+uint64(nItemLoc.NumBytes(t))))
t.freeNodeLoc(right)
t.markReclaimable(nNode, reclaimMark)
return left, middle, newRight, nil
}
if nNode.right.isEmpty() {
return t.mkNodeLoc(nil).Copy(n), empty_nodeLoc, empty_nodeLoc, nil
}
left, middle, right, err :=
o.split(t, &nNode.right, s, reclaimMark)
if err != nil {
return empty_nodeLoc, empty_nodeLoc, empty_nodeLoc, err
}
leftNum, leftBytes, rightNum, rightBytes, err := numInfo(o, &nNode.left, left)
if err != nil {
return empty_nodeLoc, empty_nodeLoc, empty_nodeLoc, err
}
newLeft := t.mkNodeLoc(t.mkNode(nItemLoc, &nNode.left, left,
leftNum+rightNum+1,
leftBytes+rightBytes+uint64(nItemLoc.NumBytes(t))))
t.freeNodeLoc(left)
t.markReclaimable(nNode, reclaimMark)
return newLeft, middle, right, nil
}
// Joins this treap and that treap into one treap. Unlike union(),
// the join() function assumes all keys from this treap should be less
// than keys from that treap.
func (o *Store) join(t *Collection, this *nodeLoc, that *nodeLoc,
reclaimMark *node) (
res *nodeLoc, err error) {
thisNode, err := this.read(o)
if err != nil {
return empty_nodeLoc, err
}
thatNode, err := that.read(o)
if err != nil {
return empty_nodeLoc, err
}
if this.isEmpty() || thisNode == nil {
return t.mkNodeLoc(nil).Copy(that), nil
}
if that.isEmpty() || thatNode == nil {
return t.mkNodeLoc(nil).Copy(this), nil
}
thisItemLoc := &thisNode.item
thisItem, err := thisItemLoc.read(t, false)
if err != nil {
return empty_nodeLoc, err
}
thatItemLoc := &thatNode.item
thatItem, err := thatItemLoc.read(t, false)
if err != nil {
return empty_nodeLoc, err
}
if thisItem.Priority > thatItem.Priority {
newRight, err :=
o.join(t, &thisNode.right, that, reclaimMark)
if err != nil {
return empty_nodeLoc, err
}
leftNum, leftBytes, rightNum, rightBytes, err :=
numInfo(o, &thisNode.left, newRight)
if err != nil {
return empty_nodeLoc, err
}
res = t.mkNodeLoc(t.mkNode(thisItemLoc, &thisNode.left, newRight,
leftNum+rightNum+1,
leftBytes+rightBytes+uint64(thisItemLoc.NumBytes(t))))
t.markReclaimable(thisNode, reclaimMark)
t.freeNodeLoc(newRight)
return res, nil
}
newLeft, err :=
o.join(t, this, &thatNode.left, reclaimMark)
if err != nil {
return empty_nodeLoc, err
}
leftNum, leftBytes, rightNum, rightBytes, err :=
numInfo(o, newLeft, &thatNode.right)
if err != nil {
return empty_nodeLoc, err
}
res = t.mkNodeLoc(t.mkNode(thatItemLoc, newLeft, &thatNode.right,
leftNum+rightNum+1,
leftBytes+rightBytes+uint64(thatItemLoc.NumBytes(t))))
t.markReclaimable(thatNode, reclaimMark)
t.freeNodeLoc(newLeft)
return res, nil
}
func (o *Store) walk(t *Collection, withValue bool, cfn func(*node) (*nodeLoc, bool)) (
res *Item, err error) {
rnl := t.rootAddRef()
defer t.rootDecRef(rnl)
n := rnl.root
nNode, err := n.read(o)
if err != nil || n.isEmpty() || nNode == nil {
return nil, err
}
for {
child, ok := cfn(nNode)
if !ok {
return nil, nil
}
childNode, err := child.read(o)
if err != nil {
return nil, err
}
if child.isEmpty() || childNode == nil {
i, err := nNode.item.read(t, withValue)
if err != nil {
return nil, err
}
o.ItemAddRef(t, i)
return i, nil
}
nNode = childNode
}
}
func (o *Store) visitNodes(t *Collection, n *nodeLoc, target []byte,
withValue bool, visitor ItemVisitorEx, depth uint64,
choiceFunc func(int, *node) (bool, *nodeLoc, *nodeLoc)) (bool, error) {
nNode, err := n.read(o)
if err != nil {
return false, err
}
if n.isEmpty() || nNode == nil {
return true, nil
}
nItemLoc := &nNode.item
nItem, err := nItemLoc.read(t, false)
if err != nil {
return false, err
}
if nItem == nil {
panic(fmt.Sprintf("visitNodes nItem nil: %#v", nNode))
}
choice, choiceT, choiceF := choiceFunc(t.compare(target, nItem.Key), nNode)
if choice {
keepGoing, err :=
o.visitNodes(t, choiceT, target, withValue, visitor, depth+1, choiceFunc)
if err != nil || !keepGoing {
return false, err
}
nItem, err := nItemLoc.read(t, withValue)
if err != nil {
return false, err
}
if !visitor(nItem, depth) {
return false, nil
}
}
return o.visitNodes(t, choiceF, target, withValue, visitor, depth+1, choiceFunc)
}