func (t *xtree) SeekFirst() (e *xenumerator, err error) {
	q := t.first
	if q == nil {
		return nil, io.EOF
	}
	return &xenumerator{nil, true, 0, q.xd[0].k, q, t, t.ver}, nil
}
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.
package ql
import (
	"bytes"
	"fmt"
	"io"
	"math/big"
	"sync"
	"time"
)
var (
	_ btreeIndex    = (*memIndex)(nil)
	_ btreeIterator = (*memBTreeIterator)(nil)
	_ indexIterator = (*xenumerator2)(nil)
	_ storage       = (*mem)(nil)
	_ temp          = (*memTemp)(nil)
)
type memIndex struct {
	m      *mem
	t      *xtree
	unique bool
}
func newMemIndex(m *mem, unique bool) *memIndex {
	r := &memIndex{t: xtreeNew(), unique: unique, m: m}
	return r
}
func (x *memIndex) Clear() error {
	x.m.newUndo(undoClearX, 0, []interface{}{x, x.t})
	x.t = xtreeNew()
	return nil
}
func (x *memIndex) Create(indexedValues []interface{}, h int64) error {
	t := x.t
	switch {
	case !x.unique:
		k := indexKey{indexedValues, h}
		x.m.newUndo(undoCreateX, 0, []interface{}{x, k})  
		t.Set(k, 0)
	case isIndexNull(indexedValues):  
		k := indexKey{nil, h}
		x.m.newUndo(undoCreateX, 0, []interface{}{x, k})  
		t.Set(k, 0)
	default:  
		k := indexKey{indexedValues, 0}
		if _, ok := t.Get(k); ok {  
			return fmt.Errorf("cannot insert into unique index: duplicate value(s): %v", indexedValues)
		}
		x.m.newUndo(undoCreateX, 0, []interface{}{x, k})  
		t.Set(k, int(h))
	}
	return nil
}
func (x *memIndex) Delete(indexedValues []interface{}, h int64) error {
	t := x.t
	var k indexKey
	var v interface{}
	var ok, okv bool
	switch {
	case !x.unique:
		k = indexKey{indexedValues, h}
		v, okv = t.Get(k)
		ok = t.delete(k)
	case isIndexNull(indexedValues):  
		k = indexKey{nil, h}
		v, okv = t.Get(k)
		ok = t.delete(k)
	default:  
		k = indexKey{indexedValues, 0}
		v, okv = t.Get(k)
		ok = t.delete(k)
	}
	if ok {
		if okv {
			x.m.newUndo(undoDeleteX, int64(v.(int)), []interface{}{x, k})
		}
		return nil
	}
	return fmt.Errorf("internal error 047")
}
func (x *memIndex) Drop() error {
	x.m.newUndo(undoDropX, 0, []interface{}{x, *x})
	*x = memIndex{}
	return nil
}
func (x *memIndex) Seek(indexedValues []interface{}) (indexIterator, bool, error) {
	it, hit := x.t.Seek(indexKey{indexedValues, 0})
	return &xenumerator2{*it, x.unique}, hit, nil
}
func (x *memIndex) SeekFirst() (iter indexIterator, err error) {
	it, err := x.t.SeekFirst()
	if err != nil {
		return nil, err
	}
	return &xenumerator2{*it, x.unique}, nil
}
func (x *memIndex) SeekLast() (iter indexIterator, err error) {
	it, err := x.t.SeekLast()
	if err != nil {
		return nil, err
	}
	return &xenumerator2{*it, x.unique}, nil
}
type xenumerator2 struct {
	it     xenumerator
	unique bool
}
func (it *xenumerator2) Next() ([]interface{}, int64, error) {
	k, h, err := it.it.Next()
	if err != nil {
		return nil, -1, err
	}
	switch it.unique {
	case true:
		if k.value == nil {
			return nil, k.h, nil
		}
		return k.value, h, nil
	default:
		return k.value, k.h, nil
	}
}
func (it *xenumerator2) Prev() ([]interface{}, int64, error) {
	k, h, err := it.it.Prev()
	if err != nil {
		return nil, -1, err
	}
	switch it.unique {
	case true:
		if k.value == nil {
			return nil, k.h, nil
		}
		return k.value, h, nil
	default:
		return k.value, k.h, nil
	}
}
type memBTreeIterator enumerator
func (it *memBTreeIterator) Next() (k, v []interface{}, err error) {
	return (*enumerator)(it).Next()
}
type memTemp struct {
	tree  *tree
	store *mem
}
func (t *memTemp) BeginTransaction() (err error) {
	return nil
}
func (t *memTemp) Get(k []interface{}) (v []interface{}, err error) {
	v, _ = t.tree.Get(k)
	return
}
func (t *memTemp) Create(data ...interface{}) (h int64, err error) {
	s := t.store
	switch n := len(s.recycler); {
	case n != 0:
		h = int64(s.recycler[n-1])
		s.recycler = s.recycler[:n-1]
		s.data[h] = s.clone(data...)
	default:
		h = int64(len(s.data))
		s.data = append(s.data, s.clone(data...))
	}
	return
}
func (t *memTemp) Read(dst []interface{}, h int64, cols ...*col) (data []interface{}, err error) {
	return t.store.Read(dst, h, cols...)
}
func (*memTemp) Drop() (err error) { return }
func (t *memTemp) Set(k, v []interface{}) (err error) {
	t.tree.Set(append([]interface{}(nil), k...), t.store.clone(v...))
	return
}
func (t *memTemp) SeekFirst() (e btreeIterator, err error) {
	en, err := t.tree.SeekFirst()
	if err != nil {
		return
	}
	return (*memBTreeIterator)(en), nil
}
const (
	undoCreateNewHandle = iota
	undoCreateRecycledHandle
	undoUpdate
	undoDelete
	undoClearX   
	undoCreateX  
	undoDeleteX  
	undoDropX    
)
type undo struct {
	tag  int
	h    int64
	data []interface{}
}
type undos struct {
	list   []undo
	parent *undos
}
type mem struct {
	data     [][]interface{}
	id       int64
	recycler []int
	tnl      int
	rollback *undos
	mu       sync.RWMutex
}
func newMemStorage() (s *mem, err error) {
	s = &mem{data: [][]interface{}{nil}}
	if err = s.BeginTransaction(); err != nil {
		return nil, err
	}
	h, err := s.Create()
	if h != 1 {
		panic("internal error 048")
	}
	if err = s.Commit(); err != nil {
		return nil, err
	}
	return
}
func (s *mem) OpenIndex(unique bool, handle int64) (btreeIndex, error) {  
	panic("internal error 049")
}
func (s *mem) newUndo(tag int, h int64, data []interface{}) {
	s.rollback.list = append(s.rollback.list, undo{tag, h, data})
}
func (s *mem) Acid() bool { return false }
func (s *mem) Close() (err error) {
	s.mu.Lock()
	defer s.mu.Unlock()
	if s.tnl != 0 {
		return fmt.Errorf("cannot close DB while open transaction exist")
	}
	s.data, s.recycler, s.rollback = nil, nil, nil
	s.id, s.tnl = 0, 0
	return
}
func (s *mem) CreateIndex(unique bool) (   int64, btreeIndex, error) {
	return -1, newMemIndex(s, unique), nil  
}
func (s *mem) Name() string { return fmt.Sprintf("/proc/self/mem/%p", s) }  
func OpenMem() (db *DB, err error) {
	s, err := newMemStorage()
	if err != nil {
		return
	}
	if db, err = newDB(s); err != nil {
		return nil, err
	}
	db.isMem = true
	return db, nil
}
func (s *mem) Verify() (allocs int64, err error) {
	for _, v := range s.recycler {
		if s.data[v] != nil {
			return 0, fmt.Errorf("corrupted: non nil free handle %d", s.data[v])
		}
	}
	for _, v := range s.data {
		if v != nil {
			allocs++
		}
	}
	if allocs != int64(len(s.data))-1-int64(len(s.recycler)) {
		return 0, fmt.Errorf("corrupted: len(data) %d, len(recycler) %d, allocs %d", len(s.data), len(s.recycler), allocs)
	}
	return
}
func (s *mem) String() string {
	var b bytes.Buffer
	for i, v := range s.data {
		b.WriteString(fmt.Sprintf("s.data[%d] %#v\n", i, v))
	}
	for i, v := range s.recycler {
		b.WriteString(fmt.Sprintf("s.recycler[%d] %v\n", i, v))
	}
	return b.String()
}
func (s *mem) CreateTemp(asc bool) (_ temp, err error) {
	st, err := newMemStorage()
	if err != nil {
		return
	}
	return &memTemp{
		tree:  treeNew(collators[asc]),
		store: st,
	}, nil
}
func (s *mem) ResetID() (err error) {
	s.id = 0
	return
}
func (s *mem) ID() (id int64, err error) {
	s.id++
	return s.id, nil
}
func (s *mem) clone(data ...interface{}) []interface{} {
	r := make([]interface{}, len(data))
	for i, v := range data {
		switch x := v.(type) {
		case nil:
		case idealComplex:
			r[i] = complex128(x)
		case idealFloat:
			r[i] = float64(x)
		case idealInt:
			r[i] = int64(x)
		case idealRune:
			r[i] = int32(x)
		case idealUint:
			r[i] = uint64(x)
		case bool:
			r[i] = x
		case complex64:
			r[i] = x
		case complex128:
			r[i] = x
		case float32:
			r[i] = x
		case float64:
			r[i] = x
		case int:
			r[i] = int64(x)
		case int8:
			r[i] = x
		case int16:
			r[i] = x
		case int32:
			r[i] = x
		case int64:
			r[i] = x
		case string:
			r[i] = x
		case uint:
			r[i] = uint64(x)
		case uint8:
			r[i] = x
		case uint16:
			r[i] = x
		case uint32:
			r[i] = x
		case uint64:
			r[i] = x
		case []byte:
			r[i] = append([]byte(nil), x...)
		case *big.Int:
			r[i] = big.NewInt(0).Set(x)
		case *big.Rat:
			r[i] = big.NewRat(1, 2).Set(x)
		case time.Time:
			t := x
			r[i] = t
		case time.Duration:
			r[i] = x
		case map[string]interface{}:  
			r[i] = x
		default:
			panic("internal error 050")
		}
	}
	return r
}
func (s *mem) Create(data ...interface{}) (h int64, err error) {
	switch n := len(s.recycler); {
	case n != 0:
		h = int64(s.recycler[n-1])
		s.recycler = s.recycler[:n-1]
		s.data[h] = s.clone(data...)
		r := s.rollback
		r.list = append(r.list, undo{
			tag: undoCreateRecycledHandle,
			h:   h,
		})
	default:
		h = int64(len(s.data))
		s.data = append(s.data, s.clone(data...))
		r := s.rollback
		r.list = append(r.list, undo{
			tag: undoCreateNewHandle,
			h:   h,
		})
	}
	return
}
func (s *mem) Read(dst []interface{}, h int64, cols ...*col) (data []interface{}, err error) {
	s.mu.RLock()
	defer s.mu.RUnlock()
	if i := int(h); i != 0 && i < len(s.data) {
		d := s.clone(s.data[h]...)
		if cols == nil {
			return d, nil
		}
		for n, dn := len(cols)+2, len(d); dn < n; dn++ {
			d = append(d, nil)
		}
		return d, nil
	}
	return nil, errNoDataForHandle
}
func (s *mem) UpdateRow(h int64, _ []*col, data ...interface{}) (err error) {
	return s.Update(h, data...)
}
func (s *mem) Update(h int64, data ...interface{}) (err error) {
	r := s.rollback
	r.list = append(r.list, undo{
		tag:  undoUpdate,
		h:    h,
		data: s.data[h],
	})
	s.data[h] = s.clone(data...)
	return
}
func (s *mem) Delete(h int64, _ ...*col) (err error) {
	r := s.rollback
	r.list = append(r.list, undo{
		tag:  undoDelete,
		h:    h,
		data: s.data[h],
	})
	s.recycler = append(s.recycler, int(h))
	s.data[h] = nil
	return
}
func (s *mem) BeginTransaction() (err error) {
	s.rollback = &undos{parent: s.rollback}
	s.tnl++
	return nil
}
func (s *mem) Rollback() (err error) {
	if s.tnl == 0 {
		return errRollbackNotInTransaction
	}
	list := s.rollback.list
	for i := len(list) - 1; i >= 0; i-- {
		undo := list[i]
		switch h, data := int(undo.h), undo.data; undo.tag {
		case undoCreateNewHandle:
			d := s.data
			s.data = d[:len(d)-1]
		case undoCreateRecycledHandle:
			s.data[h] = nil
			r := s.recycler
			s.recycler = append(r, h)
		case undoUpdate:
			s.data[h] = data
		case undoDelete:
			s.data[h] = data
			s.recycler = s.recycler[:len(s.recycler)-1]
		case undoClearX:
			x, t := data[0].(*memIndex), data[1].(*xtree)
			x.t = t
		case undoCreateX:
			x, k := data[0].(*memIndex), data[1].(indexKey)
			x.t.delete(k)
		case undoDeleteX:
			x, k := data[0].(*memIndex), data[1].(indexKey)
			x.t.Set(k, h)
		case undoDropX:
			x, v := data[0].(*memIndex), data[1].(memIndex)
			*x = v
		default:
			panic("internal error 051")
		}
	}
	s.tnl--
	s.rollback = s.rollback.parent
	return nil
}
func (s *mem) Commit() (err error) {
	if s.tnl == 0 {
		return errCommitNotInTransaction
	}
	s.tnl--
	s.rollback = s.rollback.parent
	return nil
}
type (
	xd struct {  
		c  int
		xd [2*kd + 1]xde
		n  *xd
		p  *xd
	}
	xde struct {  
		k indexKey
		v int
	}
	xenumerator struct {
		err error
		hit bool
		i   int
		k   indexKey
		q   *xd
		t   *xtree
		ver int64
	}
	xtree struct {
		c     int
		first *xd
		last  *xd
		r     interface{}
		ver   int64
	}
	xxe struct {  
		ch  interface{}
		sep *xd
	}
	xx struct {  
		c  int
		xx [2*kx + 2]xxe
	}
)
func (a *indexKey) cmp(b *indexKey) int {
	r := collate(a.value, b.value)
	if r != 0 {
		return r
	}
	return int(a.h) - int(b.h)
}
var (  
	zxd  xd
	zxde xde
	zxx  xx
	zxxe xxe
)
func xclr(q interface{}) {
	switch xx := q.(type) {
	case *xx:
		for i := 0; i <= xx.c; i++ {  
			xclr(xx.xx[i].ch)
		}
		*xx = zxx  
	case *xd:
		*xx = zxd  
	}
}
func xnewX(ch0 interface{}) *xx {
	r := &xx{}
	r.xx[0].ch = ch0
	return r
}
func (q *xx) extract(i int) {
	q.c--
	if i < q.c {
		copy(q.xx[i:], q.xx[i+1:q.c+1])
		q.xx[q.c].ch = q.xx[q.c+1].ch
		q.xx[q.c].sep = nil  
		q.xx[q.c+1] = zxxe   
	}
}
func (q *xx) insert(i int, xd *xd, ch interface{}) *xx {
	c := q.c
	if i < c {
		q.xx[c+1].ch = q.xx[c].ch
		copy(q.xx[i+2:], q.xx[i+1:c])
		q.xx[i+1].sep = q.xx[i].sep
	}
	c++
	q.c = c
	q.xx[i].sep = xd
	q.xx[i+1].ch = ch
	return q
}
func (q *xx) siblings(i int) (l, r *xd) {
	if i >= 0 {
		if i > 0 {
			l = q.xx[i-1].ch.(*xd)
		}
		if i < q.c {
			r = q.xx[i+1].ch.(*xd)
		}
	}
	return
}
func (l *xd) mvL(r *xd, c int) {
	copy(l.xd[l.c:], r.xd[:c])
	copy(r.xd[:], r.xd[c:r.c])
	l.c += c
	r.c -= c
}
func (l *xd) mvR(r *xd, c int) {
	copy(r.xd[c:], r.xd[:r.c])
	copy(r.xd[:c], l.xd[l.c-c:])
	r.c += c
	l.c -= c
}
func xtreeNew() *xtree {
	return &xtree{}
}
func (t *xtree) Clear() {
	if t.r == nil {
		return
	}
	xclr(t.r)
	t.c, t.first, t.last, t.r = 0, nil, nil, nil
	t.ver++
}
func (t *xtree) cat(p *xx, q, r *xd, pi int) {
	t.ver++
	q.mvL(r, r.c)
	if r.n != nil {
		r.n.p = q
	} else {
		t.last = q
	}
	q.n = r.n
	if p.c > 1 {
		p.extract(pi)
		p.xx[pi].ch = q
	} else {
		t.r = q
	}
}
func (t *xtree) catX(p, q, r *xx, pi int) {
	t.ver++
	q.xx[q.c].sep = p.xx[pi].sep
	copy(q.xx[q.c+1:], r.xx[:r.c])
	q.c += r.c + 1
	q.xx[q.c].ch = r.xx[r.c].ch
	if p.c > 1 {
		p.c--
		pc := p.c
		if pi < pc {
			p.xx[pi].sep = p.xx[pi+1].sep
			copy(p.xx[pi+1:], p.xx[pi+2:pc+1])
			p.xx[pc].ch = p.xx[pc+1].ch
			p.xx[pc].sep = nil   
			p.xx[pc+1].ch = nil  
		}
		return
	}
	t.r = q
}
func (t *xtree) delete(k indexKey) (ok bool) {
	pi := -1
	var p *xx
	q := t.r
	if q == nil {
		return
	}
	for {
		var i int
		i, ok = t.find(q, k)
		if ok {
			switch xx := q.(type) {
			case *xx:
				dp := xx.xx[i].sep
				switch {
				case dp.c > kd:
					t.extract(dp, 0)
				default:
					if xx.c < kx && q != t.r {
						t.underflowX(p, &xx, pi, &i)
					}
					pi = i + 1
					p = xx
					q = xx.xx[pi].ch
					ok = false
					continue
				}
			case *xd:
				t.extract(xx, i)
				if xx.c >= kd {
					return
				}
				if q != t.r {
					t.underflow(p, xx, pi)
				} else if t.c == 0 {
					t.Clear()
				}
			}
			return
		}
		switch xx := q.(type) {
		case *xx:
			if xx.c < kx && q != t.r {
				t.underflowX(p, &xx, pi, &i)
			}
			pi = i
			p = xx
			q = xx.xx[i].ch
		case *xd:
			return
		}
	}
}
func (t *xtree) extract(q *xd, i int) {  
	t.ver++
	q.c--
	if i < q.c {
		copy(q.xd[i:], q.xd[i+1:q.c+1])
	}
	q.xd[q.c] = zxde  
	t.c--
}
func (t *xtree) find(q interface{}, k indexKey) (i int, ok bool) {
	var mk indexKey
	l := 0
	switch xx := q.(type) {
	case *xx:
		h := xx.c - 1
		for l <= h {
			m := (l + h) >> 1
			mk = xx.xx[m].sep.xd[0].k
			switch cmp := k.cmp(&mk); {
			case cmp > 0:
				l = m + 1
			case cmp == 0:
				return m, true
			default:
				h = m - 1
			}
		}
	case *xd:
		h := xx.c - 1
		for l <= h {
			m := (l + h) >> 1
			mk = xx.xd[m].k
			switch cmp := k.cmp(&mk); {
			case cmp > 0:
				l = m + 1
			case cmp == 0:
				return m, true
			default:
				h = m - 1
			}
		}
	}
	return l, false
}
func (t *xtree) First() (k indexKey, v int) {
	if q := t.first; q != nil {
		q := &q.xd[0]
		k, v = q.k, q.v
	}
	return
}
func (t *xtree) Get(k indexKey) (v int, ok bool) {
	q := t.r
	if q == nil {
		return
	}
	for {
		var i int
		if i, ok = t.find(q, k); ok {
			switch xx := q.(type) {
			case *xx:
				return xx.xx[i].sep.xd[0].v, true
			case *xd:
				return xx.xd[i].v, true
			}
		}
		switch xx := q.(type) {
		case *xx:
			q = xx.xx[i].ch
		default:
			return
		}
	}
}
func (t *xtree) insert(q *xd, i int, k indexKey, v int) *xd {
	t.ver++
	c := q.c
	if i < c {
		copy(q.xd[i+1:], q.xd[i:c])
	}
	c++
	q.c = c
	q.xd[i].k, q.xd[i].v = k, v
	t.c++
	return q
}
func (t *xtree) Last() (k indexKey, v int) {
	if q := t.last; q != nil {
		q := &q.xd[q.c-1]
		k, v = q.k, q.v
	}
	return
}
func (t *xtree) Len() int {
	return t.c
}
func (t *xtree) overflow(p *xx, q *xd, pi, i int, k indexKey, v int) {
	t.ver++
	l, r := p.siblings(pi)
	if l != nil && l.c < 2*kd {
		l.mvL(q, 1)
		t.insert(q, i-1, k, v)
		return
	}
	if r != nil && r.c < 2*kd {
		if i < 2*kd {
			q.mvR(r, 1)
			t.insert(q, i, k, v)
		} else {
			t.insert(r, 0, k, v)
		}
		return
	}
	t.split(p, q, pi, i, k, v)
}
func (t *xtree) Seek(k indexKey) (e *xenumerator, ok bool) {
	q := t.r
	if q == nil {
		e = &xenumerator{nil, false, 0, k, nil, t, t.ver}
		return
	}
	for {
		var i int
		if i, ok = t.find(q, k); ok {
			switch xx := q.(type) {
			case *xx:
				e = &xenumerator{nil, ok, 0, k, xx.xx[i].sep, t, t.ver}
				return
			case *xd:
				e = &xenumerator{nil, ok, i, k, xx, t, t.ver}
				return
			}
		}
		switch xx := q.(type) {
		case *xx:
			q = xx.xx[i].ch
		case *xd:
			e = &xenumerator{nil, ok, i, k, xx, t, t.ver}
			return
		}
	}
}