secondary_btree.go

// btree.go Copyright 2014 The b Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// This file has been generated by http://github.com/cznic/b

package btree2d

import (
	"fmt"
	"io"
	"sync"
	"sync/atomic"

	"github.com/joeshaw/gengen/generic"
)

const (
	kx2 = 64 //TODO benchmark tune this number if using custom key/value type(s).
	kd2 = 64 //TODO benchmark tune this number if using custom key/value type(s).
)

func init() {
	if kd2 < 1 {
		panic(fmt.Errorf("kd2 %d: out of range", kd2))
	}

	if kx2 < 2 {
		panic(fmt.Errorf("kx2 %d: out of range", kx2))
	}
}

var (
	btDPool2 = sync.Pool{New: func() interface{} { return &d2{} }}
	btEPool2 = btEpool2{sync.Pool{New: func() interface{} { return &SecondaryEnumerator{} }}}
	btTPool2 = btTpool2{sync.Pool{New: func() interface{} { return &SecondaryTree{} }}}
	btXPool2 = sync.Pool{New: func() interface{} { return &x2{} }}
)

type btTpool2 struct{ sync.Pool }

func (p *btTpool2) get(cmp SecondaryCmpFunc) *SecondaryTree {
	x := p.Get().(*SecondaryTree)
	x.cmp = cmp
	return x
}

type btEpool2 struct{ sync.Pool }

func (p *btEpool2) get(err error, hit bool, i int, k generic.U, q *d2, t *SecondaryTree, ver uint64) *SecondaryEnumerator {
	x := p.Get().(*SecondaryEnumerator)
	x.err, x.hit, x.i, x.k, x.q, x.t, x.ver = err, hit, i, k, q, t, ver
	return x
}

type (
	d2 struct { // data page
		c int
		d [2*kd2 + 1]de2
		n *d2
		p *d2
	}

	de2 struct { // d element
		k generic.U
		v *FinalizerList
	}

	// SecondaryEnumerator captures the state of enumerating a tree. It is returned
	// from the Seek* methods. The enumerator is aware of any mutations
	// made to the tree in the process of enumerating it and automatically
	// resumes the enumeration at the proper key, if possible.
	//
	// However, once an SecondaryEnumerator returns io.EOF to signal "no more
	// items", it does no more attempt to "resync" on tree mutation(s).  In
	// other words, io.EOF from an SecondaryEnumerator is "sticky" (idempotent).
	SecondaryEnumerator struct {
		err error
		hit bool
		i   int
		k   generic.U
		q   *d2
		t   *SecondaryTree
		ver uint64
	}

	// SecondaryTree is a B+tree.
	SecondaryTree struct {
		c     int
		cmp   SecondaryCmpFunc
		first *d2
		last  *d2
		r     interface{}
		ver   uint64
	}

	xe2 struct { // x element
		ch interface{}
		k  generic.U
	}

	x2 struct { // index page
		c int
		x [2*kx2 + 2]xe2
	}
)

var ( // R/O zero values
	zd2  d2
	zde2 de2
	ze2  SecondaryEnumerator
	zk2  generic.U
	zt2  SecondaryTree
	zx2  x2
	zxe2 xe2
)

func clr2(q interface{}) {
	switch x := q.(type) {
	case *x2:
		for i := 0; i <= x.c; i++ { // Ch0 Sep0 ... Chn-1 Sepn-1 Chn
			clr2(x.x[i].ch)
		}
		*x = zx2
		btXPool2.Put(x)
	case *d2:
		*x = zd2
		btDPool2.Put(x)
	}
}

// -------------------------------------------------------------------------- x

func newX2(ch0 interface{}) *x2 {
	r := btXPool2.Get().(*x2)
	r.x[0].ch = ch0
	return r
}

func (q *x2) extract(i int) {
	q.c--
	if i < q.c {
		copy(q.x[i:], q.x[i+1:q.c+1])
		q.x[q.c].ch = q.x[q.c+1].ch
		q.x[q.c].k = zk2  // GC
		q.x[q.c+1] = zxe2 // GC
	}
}

func (q *x2) insert(i int, k generic.U, ch interface{}) *x2 {
	c := q.c
	if i < c {
		q.x[c+1].ch = q.x[c].ch
		copy(q.x[i+2:], q.x[i+1:c])
		q.x[i+1].k = q.x[i].k
	}
	c++
	q.c = c
	q.x[i].k = k
	q.x[i+1].ch = ch
	return q
}

func (q *x2) siblings(i int) (l, r *d2) {
	if i >= 0 {
		if i > 0 {
			l = q.x[i-1].ch.(*d2)
		}
		if i < q.c {
			r = q.x[i+1].ch.(*d2)
		}
	}
	return
}

// -------------------------------------------------------------------------- d

func (l *d2) mvL(r *d2, c int) {
	copy(l.d[l.c:], r.d[:c])
	copy(r.d[:], r.d[c:r.c])
	l.c += c
	r.c -= c
}

func (l *d2) mvR(r *d2, c int) {
	copy(r.d[c:], r.d[:r.c])
	copy(r.d[:c], l.d[l.c-c:])
	r.c += c
	l.c -= c
}

// ----------------------------------------------------------------------- SecondaryTree

// NewSecondaryTree returns a newly created, empty SecondaryTree. The compare function is used
// for key collation.
func NewSecondaryTree(cmp SecondaryCmpFunc) *SecondaryTree {
	return btTPool2.get(cmp)
}

// Clear removes all K/V pairs from the tree.
func (t *SecondaryTree) Clear() {
	if t.r == nil {
		return
	}

	clr2(t.r)
	t.c, t.first, t.last, t.r = 0, nil, nil, nil
	atomic.AddUint64(&t.ver, 1)
}

// Close performs Clear and recycles t to a pool for possible later reuse. No
// references to t should exist or such references must not be used afterwards.
func (t *SecondaryTree) Close() {
	t.Clear()
	*t = zt2
	btTPool2.Put(t)
}

func (t *SecondaryTree) cat(p *x2, q, r *d2, pi int) {
	atomic.AddUint64(&t.ver, 1)
	q.mvL(r, r.c)
	if r.n != nil {
		r.n.p = q
	} else {
		t.last = q
	}
	q.n = r.n
	*r = zd2
	btDPool2.Put(r)
	if p.c > 1 {
		p.extract(pi)
		p.x[pi].ch = q
		return
	}

	switch x := t.r.(type) {
	case *x2:
		*x = zx2
		btXPool2.Put(x)
	case *d2:
		*x = zd2
		btDPool2.Put(x)
	}
	t.r = q
}

func (t *SecondaryTree) catX(p, q, r *x2, pi int) {
	atomic.AddUint64(&t.ver, 1)
	q.x[q.c].k = p.x[pi].k
	copy(q.x[q.c+1:], r.x[:r.c])
	q.c += r.c + 1
	q.x[q.c].ch = r.x[r.c].ch
	*r = zx2
	btXPool2.Put(r)
	if p.c > 1 {
		p.c--
		pc := p.c
		if pi < pc {
			p.x[pi].k = p.x[pi+1].k
			copy(p.x[pi+1:], p.x[pi+2:pc+1])
			p.x[pc].ch = p.x[pc+1].ch
			p.x[pc].k = zk2    // GC
			p.x[pc+1].ch = nil // GC
		}
		return
	}

	switch x := t.r.(type) {
	case *x2:
		*x = zx2
		btXPool2.Put(x)
	case *d2:
		*x = zd2
		btDPool2.Put(x)
	}
	t.r = q
}

// Delete removes the k's KV pair, if it exists, in which case Delete returns
// true.
func (t *SecondaryTree) Delete(k generic.U) (ok bool) {
	pi := -1
	var p *x2
	q := t.r
	if q == nil {
		return false
	}

	for {
		var i int
		i, ok = t.find(q, k)
		if ok {
			switch x := q.(type) {
			case *x2:
				if x.c < kx2 && q != t.r {
					x, i = t.underflowX(p, x, pi, i)
				}
				pi = i + 1
				p = x
				q = x.x[pi].ch
				ok = false
				continue
			case *d2:
				t.extract(x, i)
				if x.c >= kd2 {
					return true
				}

				if q != t.r {
					t.underflow(p, x, pi)
				} else if t.c == 0 {
					t.Clear()
				}
				return true
			}
		}

		switch x := q.(type) {
		case *x2:
			if x.c < kx2 && q != t.r {
				x, i = t.underflowX(p, x, pi, i)
			}
			pi = i
			p = x
			q = x.x[i].ch
		case *d2:
			return false
		}
	}
}

func (t *SecondaryTree) extract(q *d2, i int) { // (r *FinalizerList) {
	atomic.AddUint64(&t.ver, 1)
	//r = q.d[i].v // prepared for Extract
	q.c--
	if i < q.c {
		copy(q.d[i:], q.d[i+1:q.c+1])
	}
	q.d[q.c] = zde2 // GC
	t.c--
	return
}

func (t *SecondaryTree) find(q interface{}, k generic.U) (i int, ok bool) {
	var mk generic.U
	l := 0
	switch x := q.(type) {
	case *x2:
		h := x.c - 1
		for l <= h {
			m := (l + h) >> 1
			mk = x.x[m].k
			switch cmp := t.cmp(k, mk); {
			case cmp > 0:
				l = m + 1
			case cmp == 0:
				return m, true
			default:
				h = m - 1
			}
		}
	case *d2:
		h := x.c - 1
		for l <= h {
			m := (l + h) >> 1
			mk = x.d[m].k
			switch cmp := t.cmp(k, mk); {
			case cmp > 0:
				l = m + 1
			case cmp == 0:
				return m, true
			default:
				h = m - 1
			}
		}
	}
	return l, false
}

// First returns the first item of the tree in the key collating order, or
// (zero-value, zero-value) if the tree is empty.
func (t *SecondaryTree) First() (k generic.U, v *FinalizerList) {
	if q := t.first; q != nil {
		q := &q.d[0]
		k, v = q.k, q.v
	}
	return
}

// Get returns the value associated with k and true if it exists. Otherwise Get
// returns (zero-value, false).
func (t *SecondaryTree) Get(k generic.U) (v *FinalizerList, ok bool) {
	q := t.r
	if q == nil {
		return
	}

	for {
		var i int
		if i, ok = t.find(q, k); ok {
			switch x := q.(type) {
			case *x2:
				q = x.x[i+1].ch
				continue
			case *d2:
				return x.d[i].v, true
			}
		}
		switch x := q.(type) {
		case *x2:
			q = x.x[i].ch
		default:
			return
		}
	}
}

func (t *SecondaryTree) insert(q *d2, i int, k generic.U, v *FinalizerList) *d2 {
	atomic.AddUint64(&t.ver, 1)
	c := q.c
	if i < c {
		copy(q.d[i+1:], q.d[i:c])
	}
	c++
	q.c = c
	q.d[i].k, q.d[i].v = k, v
	t.c++
	return q
}

// Last returns the last item of the tree in the key collating order, or
// (zero-value, zero-value) if the tree is empty.
func (t *SecondaryTree) Last() (k generic.U, v *FinalizerList) {
	if q := t.last; q != nil {
		q := &q.d[q.c-1]
		k, v = q.k, q.v
	}
	return
}

// Len returns the number of items in the tree.
func (t *SecondaryTree) Len() int {
	return t.c
}

func (t *SecondaryTree) overflow(p *x2, q *d2, pi, i int, k generic.U, v *FinalizerList) {
	atomic.AddUint64(&t.ver, 1)
	l, r := p.siblings(pi)

	if l != nil && l.c < 2*kd2 && i != 0 {
		l.mvL(q, 1)
		t.insert(q, i-1, k, v)
		p.x[pi-1].k = q.d[0].k
		return
	}

	if r != nil && r.c < 2*kd2 {
		if i < 2*kd2 {
			q.mvR(r, 1)
			t.insert(q, i, k, v)
			p.x[pi].k = r.d[0].k
			return
		}

		t.insert(r, 0, k, v)
		p.x[pi].k = k
		return
	}

	t.split(p, q, pi, i, k, v)
}

// Seek returns an SecondaryEnumerator positioned on an item such that k >= item's key.
// ok reports if k == item.key The SecondaryEnumerator's position is possibly after the
// last item in the tree.
func (t *SecondaryTree) Seek(k generic.U) (e *SecondaryEnumerator, ok bool) {
	q := t.r
	if q == nil {
		e = btEPool2.get(nil, false, 0, k, nil, t, atomic.LoadUint64(&t.ver))
		return
	}

	for {
		var i int
		if i, ok = t.find(q, k); ok {
			switch x := q.(type) {
			case *x2:
				q = x.x[i+1].ch
				continue
			case *d2:
				return btEPool2.get(nil, ok, i, k, x, t, atomic.LoadUint64(&t.ver)), true
			}
		}

		switch x := q.(type) {
		case *x2:
			q = x.x[i].ch
		case *d2:
			return btEPool2.get(nil, ok, i, k, x, t, atomic.LoadUint64(&t.ver)), false
		}
	}
}

// SeekFirst returns an enumerator positioned on the first KV pair in the tree,
// if any. For an empty tree, err == io.EOF is returned and e will be nil.
func (t *SecondaryTree) SeekFirst() (e *SecondaryEnumerator, err error) {
	q := t.first
	if q == nil {
		return nil, io.EOF
	}

	return btEPool2.get(nil, true, 0, q.d[0].k, q, t, atomic.LoadUint64(&t.ver)), nil
}

// SeekLast returns an enumerator positioned on the last KV pair in the tree,
// if any. For an empty tree, err == io.EOF is returned and e will be nil.
func (t *SecondaryTree) SeekLast() (e *SecondaryEnumerator, err error) {
	q := t.last
	if q == nil {
		return nil, io.EOF
	}

	return btEPool2.get(nil, true, q.c-1, q.d[q.c-1].k, q, t, atomic.LoadUint64(&t.ver)), nil
}

// Set sets the value associated with k.
func (t *SecondaryTree) Set(k generic.U, v *FinalizerList) {
	//dbg("--- PRE Set(%v, %v)\n%s", k, v, t.dump())
	//defer func() {
	//	dbg("--- POST\n%s\n====\n", t.dump())
	//}()

	pi := -1
	var p *x2
	q := t.r
	if q == nil {
		z := t.insert(btDPool2.Get().(*d2), 0, k, v)
		t.r, t.first, t.last = z, z, z
		return
	}

	for {
		i, ok := t.find(q, k)
		if ok {
			switch x := q.(type) {
			case *x2:
				if x.c > 2*kx2 {
					x, i = t.splitX(p, x, pi, i)
				}
				pi = i + 1
				p = x
				q = x.x[i+1].ch
				continue
			case *d2:
				x.d[i].v = v
			}
			return
		}

		switch x := q.(type) {
		case *x2:
			if x.c > 2*kx2 {
				x, i = t.splitX(p, x, pi, i)
			}
			pi = i
			p = x
			q = x.x[i].ch
		case *d2:
			switch {
			case x.c < 2*kd2:
				t.insert(x, i, k, v)
			default:
				t.overflow(p, x, pi, i, k, v)
			}
			return
		}
	}
}

// Put combines Get and Set in a more efficient way where the tree is walked
// only once. The upd(ater) receives (old-value, true) if a KV pair for k
// exists or (zero-value, false) otherwise. It can then return a (new-value,
// true) to create or overwrite the existing value in the KV pair, or
// (whatever, false) if it decides not to create or not to update the value of
// the KV pair.
//
// 	tree.Set(k, v) call conceptually equals calling
//
// 	tree.Put(k, func(generic.U, bool){ return v, true })
//
// modulo the differing return values.
func (t *SecondaryTree) Put(k generic.U, upd func(oldV *FinalizerList, exists bool) (newV *FinalizerList, write bool)) (oldV *FinalizerList, written bool) {
	pi := -1
	var p *x2
	q := t.r
	var newV *FinalizerList
	if q == nil {
		// new KV pair in empty tree
		newV, written = upd(newV, false)
		if !written {
			return
		}

		z := t.insert(btDPool2.Get().(*d2), 0, k, newV)
		t.r, t.first, t.last = z, z, z
		return
	}

	for {
		i, ok := t.find(q, k)
		if ok {
			switch x := q.(type) {
			case *x2:
				if x.c > 2*kx2 {
					x, i = t.splitX(p, x, pi, i)
				}
				pi = i + 1
				p = x
				q = x.x[i+1].ch
				continue
			case *d2:
				oldV = x.d[i].v
				newV, written = upd(oldV, true)
				if !written {
					return
				}

				x.d[i].v = newV
			}
			return
		}

		switch x := q.(type) {
		case *x2:
			if x.c > 2*kx2 {
				x, i = t.splitX(p, x, pi, i)
			}
			pi = i
			p = x
			q = x.x[i].ch
		case *d2: // new KV pair
			newV, written = upd(newV, false)
			if !written {
				return
			}

			switch {
			case x.c < 2*kd2:
				t.insert(x, i, k, newV)
			default:
				t.overflow(p, x, pi, i, k, newV)
			}
			return
		}
	}
}

func (t *SecondaryTree) split(p *x2, q *d2, pi, i int, k generic.U, v *FinalizerList) {
	atomic.AddUint64(&t.ver, 1)
	r := btDPool2.Get().(*d2)
	if q.n != nil {
		r.n = q.n
		r.n.p = r
	} else {
		t.last = r
	}
	q.n = r
	r.p = q

	copy(r.d[:], q.d[kd2:2*kd2])
	for i := range q.d[kd2:] {
		q.d[kd2+i] = zde2
	}
	q.c = kd2
	r.c = kd2
	var done bool
	if i > kd2 {
		done = true
		t.insert(r, i-kd2, k, v)
	}
	if pi >= 0 {
		p.insert(pi, r.d[0].k, r)
	} else {
		t.r = newX2(q).insert(0, r.d[0].k, r)
	}
	if done {
		return
	}

	t.insert(q, i, k, v)
}

func (t *SecondaryTree) splitX(p *x2, q *x2, pi int, i int) (*x2, int) {
	atomic.AddUint64(&t.ver, 1)
	r := btXPool2.Get().(*x2)
	copy(r.x[:], q.x[kx2+1:])
	q.c = kx2
	r.c = kx2
	if pi >= 0 {
		p.insert(pi, q.x[kx2].k, r)
		q.x[kx2].k = zk2
		for i := range q.x[kx2+1:] {
			q.x[kx2+i+1] = zxe2
		}

		switch {
		case i < kx2:
			return q, i
		case i == kx2:
			return p, pi
		default: // i > kx2
			return r, i - kx2 - 1
		}
	}

	nr := newX2(q).insert(0, q.x[kx2].k, r)
	t.r = nr
	q.x[kx2].k = zk2
	for i := range q.x[kx2+1:] {
		q.x[kx2+i+1] = zxe2
	}

	switch {
	case i < kx2:
		return q, i
	case i == kx2:
		return nr, 0
	default: // i > kx2
		return r, i - kx2 - 1
	}
}

func (t *SecondaryTree) underflow(p *x2, q *d2, pi int) {
	atomic.AddUint64(&t.ver, 1)
	l, r := p.siblings(pi)

	if l != nil && l.c+q.c >= 2*kd2 {
		l.mvR(q, 1)
		p.x[pi-1].k = q.d[0].k
		return
	}

	if r != nil && q.c+r.c >= 2*kd2 {
		q.mvL(r, 1)
		p.x[pi].k = r.d[0].k
		r.d[r.c] = zde2 // GC
		return
	}

	if l != nil {
		t.cat(p, l, q, pi-1)
		return
	}

	t.cat(p, q, r, pi)
}

func (t *SecondaryTree) underflowX(p *x2, q *x2, pi int, i int) (*x2, int) {
	atomic.AddUint64(&t.ver, 1)
	var l, r *x2

	if pi >= 0 {
		if pi > 0 {
			l = p.x[pi-1].ch.(*x2)
		}
		if pi < p.c {
			r = p.x[pi+1].ch.(*x2)
		}
	}

	if l != nil && l.c > kx2 {
		q.x[q.c+1].ch = q.x[q.c].ch
		copy(q.x[1:], q.x[:q.c])
		q.x[0].ch = l.x[l.c].ch
		q.x[0].k = p.x[pi-1].k
		q.c++
		i++
		l.c--
		p.x[pi-1].k = l.x[l.c].k
		return q, i
	}

	if r != nil && r.c > kx2 {
		q.x[q.c].k = p.x[pi].k
		q.c++
		q.x[q.c].ch = r.x[0].ch
		p.x[pi].k = r.x[0].k
		copy(r.x[:], r.x[1:r.c])
		r.c--
		rc := r.c
		r.x[rc].ch = r.x[rc+1].ch
		r.x[rc].k = zk2
		r.x[rc+1].ch = nil
		return q, i
	}

	if l != nil {
		i += l.c + 1
		t.catX(p, l, q, pi-1)
		q = l
		return q, i
	}

	t.catX(p, q, r, pi)
	return q, i
}

// ----------------------------------------------------------------- SecondaryEnumerator

// Close recycles e to a pool for possible later reuse. No references to e
// should exist or such references must not be used afterwards.
func (e *SecondaryEnumerator) Close() {
	*e = ze2
	btEPool2.Put(e)
}

// Next returns the currently enumerated item, if it exists and moves to the
// next item in the key collation order. If there is no item to return, err ==
// io.EOF is returned.
func (e *SecondaryEnumerator) Next() (k generic.U, v *FinalizerList, err error) {
	if err = e.err; err != nil {
		return
	}
	if atomic.LoadUint64(&e.ver) != atomic.LoadUint64(&e.t.ver) {
		f, hit := e.t.Seek(e.k)
		if !e.hit && hit {
			if err = f.next(); err != nil {
				return
			}
		}

		*e = *f
		f.Close()
	}
	if e.q == nil {
		e.err, err = io.EOF, io.EOF
		return
	}

	if e.i >= e.q.c {
		if err = e.next(); err != nil {
			return
		}
	}

	i := e.q.d[e.i]
	k, v = i.k, i.v
	e.k, e.hit = k, false
	e.next()
	return
}

func (e *SecondaryEnumerator) next() error {
	if e.q == nil {
		e.err = io.EOF
		return io.EOF
	}

	switch {
	case e.i < e.q.c-1:
		e.i++
	default:
		if e.q, e.i = e.q.n, 0; e.q == nil {
			e.err = io.EOF
		}
	}
	return e.err
}

// Prev returns the currently enumerated item, if it exists and moves to the
// previous item in the key collation order. If there is no item to return, err
// == io.EOF is returned.
func (e *SecondaryEnumerator) Prev() (k generic.U, v *FinalizerList, err error) {
	if err = e.err; err != nil {
		return
	}
	if atomic.LoadUint64(&e.ver) != atomic.LoadUint64(&e.t.ver) {
		f, hit := e.t.Seek(e.k)
		if !e.hit && hit {
			if err = f.prev(); err != nil {
				return
			}
		}

		*e = *f
		f.Close()
	}
	if e.q == nil {
		e.err, err = io.EOF, io.EOF
		return
	}

	if e.i >= e.q.c {
		if err = e.next(); err != nil {
			return
		}
	}

	i := e.q.d[e.i]
	k, v = i.k, i.v
	e.k, e.hit = k, false
	e.prev()
	return
}

func (e *SecondaryEnumerator) prev() error {
	if e.q == nil {
		e.err = io.EOF
		return io.EOF
	}

	switch {
	case e.i > 0:
		e.i--
	default:
		if e.q = e.q.p; e.q == nil {
			e.err = io.EOF
			break
		}

		e.i = e.q.c - 1
	}
	return e.err
}

func (t *SecondaryTree) Ver() uint64 {
	return atomic.LoadUint64(&t.ver)
}