func (b *block) prune() (*block, error) {
	if b.level() == 0 || b.intervals() > 1 {
		return b, nil
	}
	r := b.readRecord(0)
	fb, err := readBlock(b.bks, int(r.idx))
	if err == nil {
		if b.freeThisOnly() != nil {
			return b, errCorrupted
		}
		return fb.prune()
	}
	return b, err
}
prune allows to reduce the height of the tree. It frees the blocks with high level,
but which have only one interval with its child. The method returns the new root
or an error, if any.
package tmindex
import (
	"fmt"
	"github.com/logrange/range/pkg/bstorage"
	"github.com/logrange/range/pkg/utils/encoding/xbinary"
	"github.com/logrange/range/pkg/utils/errors"
	"strings"
	"sync"
)
type (
	ckindex struct {
		lock  sync.Mutex
		cond  *sync.Cond
		users int
		state int
		bks   *bstorage.Blocks
	}
	block struct {
		idx int
		buf []byte
		bks *bstorage.Blocks
	}
	record struct {
		ts  int64
		idx uint32
	}
	interval struct {
		p0, p1 record
	}
)
var (
	errFullBlock  = fmt.Errorf("block is full")
	errAllMatches = fmt.Errorf("all values from the block matches the condition")
	errNoMatches  = fmt.Errorf("no matches in the block")
	errCorrupted  = fmt.Errorf("fatal error, storage is corrupted")
	emptyBlock    [blockSize]byte
)
const (
	hdrRecCountOffs = 0
	hdrLevelOffset  = 1
	hdrSize = 2
	recSize = 12
	maxRecsPerBlock      = 41
	maxIntervalsPerBlock = maxRecsPerBlock - 1
	blockSize = 512
)
const (
	stOk = iota
	stWaiting
	stWriting
	stClosed
)
var (
	stateNames = map[int]string{stOk: "Ok", stWaiting: "Waiting", stWriting: "Writing", stClosed: "Closed"}
)
func readBlock(bks *bstorage.Blocks, idx int) (*block, error) {
	buf, err := bks.Block(idx)
	if err != nil {
		return nil, errCorrupted
	}
	return &block{idx, buf, bks}, nil
}
func newCkIndex(bks *bstorage.Blocks) *ckindex {
	ci := new(ckindex)
	ci.cond = sync.NewCond(&ci.lock)
	ci.state = stOk
	ci.bks = bks
	return ci
}
func (ci *ckindex) addInterval(idx int, it interval) (int, error) {
	if err := ci.acquireRead(); err != nil {
		return idx, err
	}
	if idx < 0 {
		var err error
		idx, err = ci.bks.ArrangeBlock()
		if err != nil {
			ci.releaseRead()
			return -1, err
		}
	}
	for {
		b, err := readBlock(ci.bks, idx)
		if err != nil {
			ci.releaseRead()
			return -1, err
		}
		lr, err := b.addInterval(it)
		if err == errFullBlock {
			idx1, err := ci.bks.ArrangeBlock()
			if err != nil {
				ci.releaseRead()
				return -1, err
			}
			b1, err := readBlock(ci.bks, idx1)
			if err != nil {
				ci.releaseRead()
				return -1, err
			}
			b1.makeRootFor(b)
			idx = idx1
			it.applyPrevRecord(lr)
			continue
		}
		if err == nil {
			b, err := b.prune()
			if err == nil {
				idx = b.idx
			}
		}
		ci.releaseRead()
		return idx, err
	}
}
func (ci *ckindex) deleteIndex(idx int) error {
	if err := ci.acquireRead(); err != nil {
		return err
	}
	b, err := readBlock(ci.bks, idx)
	if err != nil {
		ci.releaseRead()
		return err
	}
	err = b.free()
	ci.releaseRead()
	return err
}
func (ci *ckindex) grEq(idx int, ts int64) (record, error) {
	if err := ci.acquireRead(); err != nil {
		return record{}, err
	}
	r, err := ci.grEqInt(idx, ts)
	ci.releaseRead()
	return r, err
}
func (ci *ckindex) grEqInt(idx int, ts int64) (record, error) {
	b, err := readBlock(ci.bks, idx)
	if err != nil {
		return record{}, err
	}
	intIdx := b.findIntervalIdx(ts)
	if intIdx < 0 {
		return record{}, errAllMatches
	}
	if intIdx == b.intervals() {
		return b.readLastRecordInTheTree(), nil
	}
	r := b.readRecord(intIdx)
	if b.level() == 0 {
		return r, nil
	}
	return ci.grEqInt(int(r.idx), ts)
}
func (ci *ckindex) less(idx int, ts int64) (record, error) {
	if err := ci.acquireRead(); err != nil {
		return record{}, err
	}
	r, err := ci.lessInt(idx, ts)
	ci.releaseRead()
	return r, err
}
func (ci *ckindex) lessInt(idx int, ts int64) (record, error) {
	b, err := readBlock(ci.bks, idx)
	if err != nil {
		return record{}, err
	}
	intIdx := b.findIntervalIdx(ts)
	if intIdx < 0 {
		return b.readFirstRecordInTheTree(), nil
	}
	if intIdx == b.intervals() {
		return record{}, errAllMatches
	}
	r := b.readRecord(intIdx)
	if b.level() == 0 {
		return b.readRecord(intIdx + 1), nil
	}
	return ci.lessInt(int(r.idx), ts)
}
func (ci *ckindex) count(idx int) (int, error) {
	if err := ci.acquireRead(); err != nil {
		return 0, err
	}
	cnt, err := ci.countInt(idx)
	ci.releaseRead()
	return cnt, err
}
func (ci *ckindex) countInt(idx int) (int, error) {
	b, err := readBlock(ci.bks, idx)
	if err != nil {
		return -1, err
	}
	if b.level() == 0 {
		return b.intervals(), nil
	}
	cnt := 0
	for i := 0; i < b.intervals(); i++ {
		r := b.readRecord(i)
		c, err := ci.countInt(int(r.idx))
		if err != nil {
			return -1, err
		}
		cnt += c
	}
	return cnt, nil
}
func (ci *ckindex) traversal(root int, res []interval) ([]interval, error) {
	if err := ci.acquireRead(); err != nil {
		return nil, err
	}
	res, err := ci.traversalInt(root, res)
	ci.releaseRead()
	return res, err
}
func (ci *ckindex) traversalInt(root int, res []interval) ([]interval, error) {
	b, err := readBlock(ci.bks, root)
	if err != nil {
		return res, err
	}
	if b.level() == 0 {
		for i := 0; i < b.intervals(); i++ {
			p0 := b.readRecord(i)
			p1 := b.readRecord(i + 1)
			res = append(res, interval{p0, p1})
		}
		return res, nil
	}
	for i := 0; i < b.records()-1; i++ {
		r := b.readRecord(i)
		res, err = ci.traversalInt(int(r.idx), res)
		if err != nil {
			return res, err
		}
	}
	return res, nil
}
func (ci *ckindex) acquireRead() error {
	ci.lock.Lock()
	for {
		if ci.state == stOk {
			ci.users++
			ci.lock.Unlock()
			return nil
		}
		if ci.state == stClosed {
			ci.lock.Unlock()
			return errors.ClosedState
		}
		ci.cond.Wait()
	}
}
func (ci *ckindex) releaseRead() {
	ci.lock.Lock()
	ci.users--
	if ci.state == stWaiting && ci.users == 0 {
		ci.cond.Broadcast()
	}
	ci.lock.Unlock()
}
func (ci *ckindex) Close() error {
	ci.lock.Lock()
	for ci.users > 0 || (ci.state != stWaiting && ci.state != stOk) {
		if ci.state == stClosed {
			ci.lock.Unlock()
			return errors.ClosedState
		}
		ci.state = stWaiting
		ci.cond.Wait()
	}
	ci.state = stClosed
	ci.cond.Broadcast()
	ci.lock.Unlock()
	return ci.bks.Close()
}
func (ci *ckindex) execExclusively(fn func()) error {
	ci.lock.Lock()
	for ci.users > 0 || (ci.state != stWaiting && ci.state != stOk) {
		if ci.state == stClosed {
			ci.lock.Unlock()
			return errors.ClosedState
		}
		ci.state = stWaiting
		ci.cond.Wait()
	}
	ci.state = stWriting
	ci.lock.Unlock()
	defer func() {
		ci.lock.Lock()
		if ci.state == stWriting {
			ci.state = stOk
		}
		ci.cond.Broadcast()
		ci.lock.Unlock()
	}()
	fn()
	return nil
}
func (ci *ckindex) String() string {
	return fmt.Sprintf("ckindex: {users: %d, state: %s, bks: %s}", ci.users, stateNames[ci.state], ci.bks)
}
func (b *block) makeRootFor(br *block) {
	b.buf[hdrRecCountOffs] = 0
	b.buf[hdrLevelOffset] = byte(br.level() + 1)
	b.setLastInterval(br.theBlockInterval())
}
func (b *block) free() error {
	lvl := b.level()
	if lvl > 0 {
		recs := b.records()
		for i := 0; i < recs-1; i++ {
			r := b.readRecord(i)
			rb, err := readBlock(b.bks, int(r.idx))
			if err != nil {
				return err
			}
			err = rb.free()
			if err != nil {
				return err
			}
		}
	}
	return b.freeThisOnly()
}
func maxInt64(i1, i2 int64) int64 {
	if i1 > i2 {
		return i1
	}
	return i2
}
func minInt64(i1, i2 int64) int64 {
	if i1 < i2 {
		return i1
	}
	return i2
}
func maxUint32(i1, i2 uint32) uint32 {
	if i1 > i2 {
		return i1
	}
	return i2
}
func minUint32(i1, i2 uint32) uint32 {
	if i1 < i2 {
		return i1
	}
	return i2
}
func maxInt(i1, i2 int) int {
	if i1 > i2 {
		return i1
	}
	return i2
}
func (b *block) readFirstRecordInTheTree() record {
	if b.records() == 0 {
		return record{}
	}
	r := b.readRecord(0)
	if b.level() == 0 {
		return r
	}
	if bl, err := readBlock(b.bks, int(r.idx)); err == nil {
		return bl.readFirstRecordInTheTree()
	}
	return record{}
}
func (b *block) readLastRecordInTheTree() record {
	rcrds := b.records()
	if rcrds == 0 {
		return record{}
	}
	if b.level() == 0 {
		return b.readRecord(rcrds - 1)
	}
	r := b.readRecord(rcrds - 2)
	if bl, err := readBlock(b.bks, int(r.idx)); err == nil {
		return bl.readLastRecordInTheTree()
	}
	return record{}
}
func (b *block) findIntervalInsertIdx(ts int64) int {
	recs := b.records()
	if recs == 0 {
		return 0
	}
	i, j := 0, recs
	for i < j {
		h := int(uint(i+j) >> 1)
		r := b.readRecord(h)
		if r.ts <= ts {
			i = h + 1
		} else {
			j = h
		}
	}
	if b.level() == 0 {
		return i - 1
	}
	if i == recs {
		return recs - 2
	}
	return maxInt(0, i-1)
}
func (b *block) findIntervalIdx(ts int64) int {
	recs := b.records()
	if recs == 0 {
		return 0
	}
	i, j := 0, recs
	for i < j {
		h := int(uint(i+j) >> 1)
		r := b.readRecord(h)
		if r.ts <= ts {
			i = h + 1
		} else {
			j = h
		}
	}
	return i - 1
}
func (b *block) removeLastInterval() error {
	recs := b.records()
	if recs == 0 {
		return nil
	}
	if b.level() > 0 {
		r := b.readRecord(recs - 2)
		lb, err := readBlock(b.bks, int(r.idx))
		if err != nil {
			return err
		}
		err = lb.free()
		if err != nil {
			return err
		}
	}
	if recs == 2 {
		recs = 1
	}
	b.buf[hdrRecCountOffs] = byte(recs - 1)
	return nil
}
func (b *block) theBlockInterval() interval {
	recs := b.records()
	if recs == 0 {
		panic("must not be invoked with 0 records")
	}
	fr := b.readRecord(0)
	lr := b.readRecord(recs - 1)
	fr.idx = uint32(b.idx)
	return interval{fr, lr}
}
func (b *block) setLastInterval(it interval) {
	recs := b.records()
	if recs == 0 {
		b.writeRecord(0, it.p0)
		b.writeRecord(1, it.p1)
		return
	}
	b.writeRecord(recs-2, it.p0)
	b.writeRecord(recs-1, it.p1)
}
func (b *block) appendInterval(it *interval) (record, error) {
	recs := b.records()
	if recs == maxRecsPerBlock {
		return b.readRecord(recs - 1), errFullBlock
	}
	if recs == 0 {
		b.writeRecord(0, it.p0)
		b.writeRecord(1, it.p1)
		return it.p1, nil
	}
	b.writeRecord(recs, it.p1)
	return it.p1, nil
}
func (b *block) addInterval(it interval) (record, error) {
	var err error
	insIdx := b.findIntervalInsertIdx(it.p0.ts)
	ints := b.intervals()
	lvl := b.level()
	if lvl == 0 {
		if insIdx == ints {
			return b.appendInterval(&it)
		}
		if ints > 0 {
			lastRec := b.readRecord(ints)
			it.p1.ts = maxInt64(it.p1.ts, lastRec.ts)
		}
		if insIdx < 0 {
			if ints > 0 {
				firstRec := b.readRecord(0)
				it.p0 = it.p0.reduce(firstRec)
			}
			b.buf[hdrRecCountOffs] = 0
		} else {
			it.p0 = b.readRecord(insIdx)
			b.buf[hdrRecCountOffs] = byte(insIdx + 2)
		}
		b.setLastInterval(it)
		return it.p1, nil
	}
	for i := insIdx + 1; i < ints; i++ {
		if err := b.removeLastInterval(); err != nil {
			return record{}, err
		}
	}
	ints = b.intervals()
	newBlock := ints == 0
	for {
		var lb *block
		if newBlock {
			bidx, err := b.bks.ArrangeBlock()
			if err != nil {
				return record{}, err
			}
			lb, err = readBlock(b.bks, bidx)
			if err != nil {
				return record{}, err
			}
			lb.buf[hdrRecCountOffs] = 0
			lb.buf[hdrLevelOffset] = byte(lvl - 1)
		} else {
			lastInt := b.readRecord(insIdx)
			lb, err = readBlock(b.bks, int(lastInt.idx))
			if err != nil {
				return record{}, err
			}
		}
		lr, err := lb.addInterval(it)
		if err == nil {
			b.setLastInterval(lb.theBlockInterval())
			return lr, nil
		}
		if err != errFullBlock {
			if newBlock {
				_ = lb.freeThisOnly()
			}
			return lr, err
		}
		if _, err = b.appendInterval(&it); err != nil {
			return lr, errFullBlock
		}
		it.applyPrevRecord(lr)
		newBlock = true
	}
}
func (b *block) freeThisOnly() error {
	copy(b.buf, emptyBlock[:])
	err := b.bks.FreeBlock(b.idx)
	b.buf = nil
	b.bks = nil
	return err
}