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)
}
findIntervalInsertIdx returns the interval index where ts can be added
the result is in [-1 .. b.intervals()] the result == b.intervals() means
the interval must be added to the end. -1 means the ts comes before any
known interval ts
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{}
}