func (d *indirectIndex) Delete(keys [][]byte) {
	if len(keys) == 0 {
		return
	}
	if !bytesutil.IsSorted(keys) {
		bytesutil.Sort(keys)
	}
	d.mu.Lock()
	start := d.searchOffset(keys[0])
	for i := start * 4; i+4 <= len(d.offsets) && len(keys) > 0; i += 4 {
		offset := binary.BigEndian.Uint32(d.offsets[i : i+4])
		_, indexKey := readKey(d.b[offset:])
		for len(keys) > 0 && bytes.Compare(keys[0], indexKey) < 0 {
			keys = keys[1:]
		}
		if len(keys) > 0 && bytes.Equal(keys[0], indexKey) {
			keys = keys[1:]
			copy(d.offsets[i:i+4], nilOffset[:])
		}
	}
	d.offsets = bytesutil.Pack(d.offsets, 4, 255)
	d.mu.Unlock()
}
Delete removes the given keys from the index.
package tsm1
import (
	"bytes"
	"encoding/binary"
	"fmt"
	"io"
	"math"
	"os"
	"runtime"
	"sort"
	"sync"
	"sync/atomic"
	"github.com/influxdata/influxdb/pkg/bytesutil"
)
var ErrFileInUse = fmt.Errorf("file still in use")
var nilOffset = []byte{255, 255, 255, 255}
type TSMReader struct {
	refs   int64
	refsWG sync.WaitGroup
	mu sync.RWMutex
	accessor blockAccessor
	index TSMIndex
	tombstoner *Tombstoner
	size int64
	lastModified int64
	deleteMu sync.Mutex
}
type TSMIndex interface {
	Delete(keys [][]byte)
	DeleteRange(keys [][]byte, minTime, maxTime int64)
	ContainsKey(key []byte) bool
	Contains(key []byte) bool
	ContainsValue(key []byte, timestamp int64) bool
	Entries(key []byte) []IndexEntry
	ReadEntries(key []byte, entries *[]IndexEntry) []IndexEntry
	Entry(key []byte, timestamp int64) *IndexEntry
	Key(index int, entries *[]IndexEntry) ([]byte, byte, []IndexEntry)
	KeyAt(index int) ([]byte, byte)
	KeyCount() int
	Seek(key []byte) int
	OverlapsTimeRange(min, max int64) bool
	OverlapsKeyRange(min, max []byte) bool
	Size() uint32
	TimeRange() (int64, int64)
	TombstoneRange(key []byte) []TimeRange
	KeyRange() ([]byte, []byte)
	Type(key []byte) (byte, error)
	UnmarshalBinary(b []byte) error
	Close() error
}
type BlockIterator struct {
	r *TSMReader
	i int
	n int
	key     []byte
	cache   []IndexEntry
	entries []IndexEntry
	err     error
	typ     byte
}
func (b *BlockIterator) PeekNext() []byte {
	if len(b.entries) > 1 {
		return b.key
	} else if b.n-b.i > 1 {
		key, _ := b.r.KeyAt(b.i + 1)
		return key
	}
	return nil
}
func (b *BlockIterator) Next() bool {
	if b.err != nil {
		return false
	}
	if b.n-b.i == 0 && len(b.entries) == 0 {
		return false
	}
	if len(b.entries) > 0 {
		b.entries = b.entries[1:]
		if len(b.entries) > 0 {
			return true
		}
	}
	if b.n-b.i > 0 {
		b.key, b.typ, b.entries = b.r.Key(b.i, &b.cache)
		b.i++
		if b.n != b.r.KeyCount() {
			b.err = fmt.Errorf("delete during iteration")
			return false
		}
		if len(b.entries) > 0 {
			return true
		}
	}
	return false
}
func (b *BlockIterator) Read() (key []byte, minTime int64, maxTime int64, typ byte, checksum uint32, buf []byte, err error) {
	if b.err != nil {
		return nil, 0, 0, 0, 0, nil, b.err
	}
	checksum, buf, err = b.r.ReadBytes(&b.entries[0], nil)
	if err != nil {
		return nil, 0, 0, 0, 0, nil, err
	}
	return b.key, b.entries[0].MinTime, b.entries[0].MaxTime, b.typ, checksum, buf, err
}
func (b *BlockIterator) Err() error {
	return b.err
}
type blockAccessor interface {
	init() (*indirectIndex, error)
	read(key []byte, timestamp int64) ([]Value, error)
	readAll(key []byte) ([]Value, error)
	readBlock(entry *IndexEntry, values []Value) ([]Value, error)
	readFloatBlock(entry *IndexEntry, values *[]FloatValue) ([]FloatValue, error)
	readIntegerBlock(entry *IndexEntry, values *[]IntegerValue) ([]IntegerValue, error)
	readUnsignedBlock(entry *IndexEntry, values *[]UnsignedValue) ([]UnsignedValue, error)
	readStringBlock(entry *IndexEntry, values *[]StringValue) ([]StringValue, error)
	readBooleanBlock(entry *IndexEntry, values *[]BooleanValue) ([]BooleanValue, error)
	readBytes(entry *IndexEntry, buf []byte) (uint32, []byte, error)
	rename(path string) error
	path() string
	close() error
	free() error
}
func NewTSMReader(f *os.File) (*TSMReader, error) {
	t := &TSMReader{}
	stat, err := f.Stat()
	if err != nil {
		return nil, err
	}
	t.size = stat.Size()
	t.lastModified = stat.ModTime().UnixNano()
	t.accessor = &mmapAccessor{
		f: f,
	}
	index, err := t.accessor.init()
	if err != nil {
		return nil, err
	}
	t.index = index
	t.tombstoner = &Tombstoner{Path: t.Path(), FilterFn: index.ContainsKey}
	if err := t.applyTombstones(); err != nil {
		return nil, err
	}
	return t, nil
}
func (t *TSMReader) applyTombstones() error {
	var cur, prev Tombstone
	batch := make([][]byte, 0, 4096)
	if err := t.tombstoner.Walk(func(ts Tombstone) error {
		cur = ts
		if len(batch) > 0 {
			if prev.Min != cur.Min || prev.Max != cur.Max {
				t.index.DeleteRange(batch, prev.Min, prev.Max)
				batch = batch[:0]
			}
		}
		n := len(batch)
		batch = batch[:n+1]
		if cap(batch[n]) < len(ts.Key) {
			batch[n] = make([]byte, len(ts.Key))
		} else {
			batch[n] = batch[n][:len(ts.Key)]
		}
		copy(batch[n], ts.Key)
		if len(batch) >= 4096 {
			t.index.DeleteRange(batch, prev.Min, prev.Max)
			batch = batch[:0]
		}
		prev = ts
		return nil
	}); err != nil {
		return fmt.Errorf("init: read tombstones: %v", err)
	}
	if len(batch) > 0 {
		t.index.DeleteRange(batch, cur.Min, cur.Max)
	}
	return nil
}
func (t *TSMReader) Free() error {
	t.mu.RLock()
	defer t.mu.RUnlock()
	return t.accessor.free()
}
func (t *TSMReader) Path() string {
	t.mu.RLock()
	p := t.accessor.path()
	t.mu.RUnlock()
	return p
}
func (t *TSMReader) Key(index int, entries *[]IndexEntry) ([]byte, byte, []IndexEntry) {
	return t.index.Key(index, entries)
}
func (t *TSMReader) KeyAt(idx int) ([]byte, byte) {
	return t.index.KeyAt(idx)
}
func (t *TSMReader) Seek(key []byte) int {
	return t.index.Seek(key)
}
func (t *TSMReader) ReadAt(entry *IndexEntry, vals []Value) ([]Value, error) {
	t.mu.RLock()
	v, err := t.accessor.readBlock(entry, vals)
	t.mu.RUnlock()
	return v, err
}
func (t *TSMReader) ReadFloatBlockAt(entry *IndexEntry, vals *[]FloatValue) ([]FloatValue, error) {
	t.mu.RLock()
	v, err := t.accessor.readFloatBlock(entry, vals)
	t.mu.RUnlock()
	return v, err
}
func (t *TSMReader) ReadIntegerBlockAt(entry *IndexEntry, vals *[]IntegerValue) ([]IntegerValue, error) {
	t.mu.RLock()
	v, err := t.accessor.readIntegerBlock(entry, vals)
	t.mu.RUnlock()
	return v, err
}
func (t *TSMReader) ReadUnsignedBlockAt(entry *IndexEntry, vals *[]UnsignedValue) ([]UnsignedValue, error) {
	t.mu.RLock()
	v, err := t.accessor.readUnsignedBlock(entry, vals)
	t.mu.RUnlock()
	return v, err
}
func (t *TSMReader) ReadStringBlockAt(entry *IndexEntry, vals *[]StringValue) ([]StringValue, error) {
	t.mu.RLock()
	v, err := t.accessor.readStringBlock(entry, vals)
	t.mu.RUnlock()
	return v, err
}
func (t *TSMReader) ReadBooleanBlockAt(entry *IndexEntry, vals *[]BooleanValue) ([]BooleanValue, error) {
	t.mu.RLock()
	v, err := t.accessor.readBooleanBlock(entry, vals)
	t.mu.RUnlock()
	return v, err
}
func (t *TSMReader) Read(key []byte, timestamp int64) ([]Value, error) {
	t.mu.RLock()
	v, err := t.accessor.read(key, timestamp)
	t.mu.RUnlock()
	return v, err
}
func (t *TSMReader) ReadAll(key []byte) ([]Value, error) {
	t.mu.RLock()
	v, err := t.accessor.readAll(key)
	t.mu.RUnlock()
	return v, err
}
func (t *TSMReader) ReadBytes(e *IndexEntry, b []byte) (uint32, []byte, error) {
	t.mu.RLock()
	n, v, err := t.accessor.readBytes(e, b)
	t.mu.RUnlock()
	return n, v, err
}
func (t *TSMReader) Type(key []byte) (byte, error) {
	return t.index.Type(key)
}
func (t *TSMReader) Close() error {
	t.refsWG.Wait()
	t.mu.Lock()
	defer t.mu.Unlock()
	if err := t.accessor.close(); err != nil {
		return err
	}
	return t.index.Close()
}
func (t *TSMReader) Ref() {
	atomic.AddInt64(&t.refs, 1)
	t.refsWG.Add(1)
}
func (t *TSMReader) Unref() {
	atomic.AddInt64(&t.refs, -1)
	t.refsWG.Done()
}
func (t *TSMReader) InUse() bool {
	refs := atomic.LoadInt64(&t.refs)
	return refs > 0
}
func (t *TSMReader) Remove() error {
	t.mu.Lock()
	defer t.mu.Unlock()
	return t.remove()
}
func (t *TSMReader) Rename(path string) error {
	t.mu.Lock()
	defer t.mu.Unlock()
	return t.accessor.rename(path)
}
func (t *TSMReader) remove() error {
	path := t.accessor.path()
	if t.InUse() {
		return ErrFileInUse
	}
	if path != "" {
		err := os.RemoveAll(path)
		if err != nil {
			return err
		}
	}
	if err := t.tombstoner.Delete(); err != nil {
		return err
	}
	return nil
}
func (t *TSMReader) Contains(key []byte) bool {
	return t.index.Contains(key)
}
func (t *TSMReader) ContainsValue(key []byte, ts int64) bool {
	return t.index.ContainsValue(key, ts)
}
func (t *TSMReader) DeleteRange(keys [][]byte, minTime, maxTime int64) error {
	if len(keys) == 0 {
		return nil
	}
	batch := t.BatchDelete()
	if err := batch.DeleteRange(keys, minTime, maxTime); err != nil {
		batch.Rollback()
		return err
	}
	return batch.Commit()
}
func (t *TSMReader) Delete(keys [][]byte) error {
	if err := t.tombstoner.Add(keys); err != nil {
		return err
	}
	if err := t.tombstoner.Flush(); err != nil {
		return err
	}
	t.index.Delete(keys)
	return nil
}
func (t *TSMReader) OverlapsTimeRange(min, max int64) bool {
	return t.index.OverlapsTimeRange(min, max)
}
func (t *TSMReader) OverlapsKeyRange(min, max []byte) bool {
	return t.index.OverlapsKeyRange(min, max)
}
func (t *TSMReader) TimeRange() (int64, int64) {
	return t.index.TimeRange()
}
func (t *TSMReader) KeyRange() ([]byte, []byte) {
	return t.index.KeyRange()
}
func (t *TSMReader) KeyCount() int {
	return t.index.KeyCount()
}
func (t *TSMReader) Entries(key []byte) []IndexEntry {
	return t.index.Entries(key)
}
func (t *TSMReader) ReadEntries(key []byte, entries *[]IndexEntry) []IndexEntry {
	return t.index.ReadEntries(key, entries)
}
func (t *TSMReader) IndexSize() uint32 {
	return t.index.Size()
}
func (t *TSMReader) Size() uint32 {
	t.mu.RLock()
	size := t.size
	t.mu.RUnlock()
	return uint32(size)
}
func (t *TSMReader) LastModified() int64 {
	t.mu.RLock()
	lm := t.lastModified
	for _, ts := range t.tombstoner.TombstoneFiles() {
		if ts.LastModified > lm {
			lm = ts.LastModified
		}
	}
	t.mu.RUnlock()
	return lm
}
func (t *TSMReader) HasTombstones() bool {
	t.mu.RLock()
	b := t.tombstoner.HasTombstones()
	t.mu.RUnlock()
	return b
}
func (t *TSMReader) TombstoneFiles() []FileStat {
	t.mu.RLock()
	fs := t.tombstoner.TombstoneFiles()
	t.mu.RUnlock()
	return fs
}
func (t *TSMReader) TombstoneRange(key []byte) []TimeRange {
	t.mu.RLock()
	tr := t.index.TombstoneRange(key)
	t.mu.RUnlock()
	return tr
}
func (t *TSMReader) Stats() FileStat {
	minTime, maxTime := t.index.TimeRange()
	minKey, maxKey := t.index.KeyRange()
	return FileStat{
		Path:         t.Path(),
		Size:         t.Size(),
		LastModified: t.LastModified(),
		MinTime:      minTime,
		MaxTime:      maxTime,
		MinKey:       minKey,
		MaxKey:       maxKey,
		HasTombstone: t.tombstoner.HasTombstones(),
	}
}
func (t *TSMReader) BlockIterator() *BlockIterator {
	return &BlockIterator{
		r: t,
		n: t.index.KeyCount(),
	}
}
type BatchDeleter interface {
	DeleteRange(keys [][]byte, min, max int64) error
	Commit() error
	Rollback() error
}
type batchDelete struct {
	r *TSMReader
}
func (b *batchDelete) DeleteRange(keys [][]byte, minTime, maxTime int64) error {
	if len(keys) == 0 {
		return nil
	}
	minKey, maxKey := keys[0], keys[len(keys)-1]
	if !b.r.index.OverlapsKeyRange(minKey, maxKey) {
		return nil
	}
	if !b.r.index.OverlapsTimeRange(minTime, maxTime) {
		return nil
	}
	if err := b.r.tombstoner.AddRange(keys, minTime, maxTime); err != nil {
		return err
	}
	return nil
}
func (b *batchDelete) Commit() error {
	defer b.r.deleteMu.Unlock()
	if err := b.r.tombstoner.Flush(); err != nil {
		return err
	}
	return b.r.applyTombstones()
}
func (b *batchDelete) Rollback() error {
	defer b.r.deleteMu.Unlock()
	return b.r.tombstoner.Rollback()
}
func (r *TSMReader) BatchDelete() BatchDeleter {
	r.deleteMu.Lock()
	return &batchDelete{r: r}
}
type BatchDeleters []BatchDeleter
func (a BatchDeleters) DeleteRange(keys [][]byte, min, max int64) error {
	errC := make(chan error, len(a))
	for _, b := range a {
		go func(b BatchDeleter) { errC <- b.DeleteRange(keys, min, max) }(b)
	}
	var err error
	for i := 0; i < len(a); i++ {
		dErr := <-errC
		if dErr != nil {
			err = dErr
		}
	}
	return err
}
func (a BatchDeleters) Commit() error {
	errC := make(chan error, len(a))
	for _, b := range a {
		go func(b BatchDeleter) { errC <- b.Commit() }(b)
	}
	var err error
	for i := 0; i < len(a); i++ {
		dErr := <-errC
		if dErr != nil {
			err = dErr
		}
	}
	return err
}
func (a BatchDeleters) Rollback() error {
	errC := make(chan error, len(a))
	for _, b := range a {
		go func(b BatchDeleter) { errC <- b.Rollback() }(b)
	}
	var err error
	for i := 0; i < len(a); i++ {
		dErr := <-errC
		if dErr != nil {
			err = dErr
		}
	}
	return err
}
type indirectIndex struct {
	mu sync.RWMutex
	b []byte
	offsets []byte
	minKey, maxKey []byte
	minTime, maxTime int64
	tombstones map[string][]TimeRange
}
type TimeRange struct {
	Min, Max int64
}
func (t TimeRange) Overlaps(min, max int64) bool {
	return t.Min <= max && t.Max >= min
}
func NewIndirectIndex() *indirectIndex {
	return &indirectIndex{
		tombstones: make(map[string][]TimeRange),
	}
}
func (d *indirectIndex) offset(i int) int {
	if i < 0 || i+4 > len(d.offsets) {
		return -1
	}
	return int(binary.BigEndian.Uint32(d.offsets[i*4 : i*4+4]))
}
func (d *indirectIndex) Seek(key []byte) int {
	d.mu.RLock()
	defer d.mu.RUnlock()
	return d.searchOffset(key)
}
func (d *indirectIndex) searchOffset(key []byte) int {
	i := bytesutil.SearchBytesFixed(d.offsets, 4, func(x []byte) bool {
		offset := int32(binary.BigEndian.Uint32(x))
		keyLen := int32(binary.BigEndian.Uint16(d.b[offset : offset+2]))
		return bytes.Compare(d.b[offset+2:offset+2+keyLen], key) >= 0
	})
	if i < len(d.offsets) {
		return int(i / 4)
	}
	return int(len(d.offsets)) / 4
}
func (d *indirectIndex) search(key []byte) int {
	i := bytesutil.SearchBytesFixed(d.offsets, 4, func(x []byte) bool {
		offset := int32(binary.BigEndian.Uint32(x))
		keyLen := int32(binary.BigEndian.Uint16(d.b[offset : offset+2]))
		return bytes.Compare(d.b[offset+2:offset+2+keyLen], key) >= 0
	})
	if i < len(d.offsets) {
		ofs := binary.BigEndian.Uint32(d.offsets[i : i+4])
		_, k := readKey(d.b[ofs:])
		if !bytes.Equal(key, k) {
			return len(d.b)
		}
		return int(ofs)
	}
	return len(d.b)
}
func (d *indirectIndex) ContainsKey(key []byte) bool {
	return bytes.Compare(key, d.minKey) >= 0 && bytes.Compare(key, d.maxKey) <= 0
}
func (d *indirectIndex) Entries(key []byte) []IndexEntry {
	return d.ReadEntries(key, nil)
}
func (d *indirectIndex) readEntriesAt(ofs int, entries *[]IndexEntry) ([]byte, []IndexEntry) {
	n, k := readKey(d.b[ofs:])
	ofs += n
	var ie indexEntries
	if entries != nil {
		ie.entries = *entries
	}
	if _, err := readEntries(d.b[ofs:], &ie); err != nil {
		panic(fmt.Sprintf("error reading entries: %v", err))
	}
	if entries != nil {
		*entries = ie.entries
	}
	return k, ie.entries
}
func (d *indirectIndex) ReadEntries(key []byte, entries *[]IndexEntry) []IndexEntry {
	d.mu.RLock()
	defer d.mu.RUnlock()
	ofs := d.search(key)
	if ofs < len(d.b) {
		k, entries := d.readEntriesAt(ofs, entries)
		if !bytes.Equal(key, k) {
			return nil
		}
		return entries
	}
	return nil
}
func (d *indirectIndex) Entry(key []byte, timestamp int64) *IndexEntry {
	entries := d.Entries(key)
	for _, entry := range entries {
		if entry.Contains(timestamp) {
			return &entry
		}
	}
	return nil
}
func (d *indirectIndex) Key(idx int, entries *[]IndexEntry) ([]byte, byte, []IndexEntry) {
	d.mu.RLock()
	defer d.mu.RUnlock()
	if idx < 0 || idx*4+4 > len(d.offsets) {
		return nil, 0, nil
	}
	ofs := binary.BigEndian.Uint32(d.offsets[idx*4 : idx*4+4])
	n, key := readKey(d.b[ofs:])
	typ := d.b[int(ofs)+n]
	var ie indexEntries
	if entries != nil {
		ie.entries = *entries
	}
	if _, err := readEntries(d.b[int(ofs)+n:], &ie); err != nil {
		return nil, 0, nil
	}
	if entries != nil {
		*entries = ie.entries
	}
	return key, typ, ie.entries
}
func (d *indirectIndex) KeyAt(idx int) ([]byte, byte) {
	d.mu.RLock()
	if idx < 0 || idx*4+4 > len(d.offsets) {
		d.mu.RUnlock()
		return nil, 0
	}
	ofs := int32(binary.BigEndian.Uint32(d.offsets[idx*4 : idx*4+4]))
	n, key := readKey(d.b[ofs:])
	ofs = ofs + int32(n)
	typ := d.b[ofs]
	d.mu.RUnlock()
	return key, typ
}
func (d *indirectIndex) KeyCount() int {
	d.mu.RLock()
	n := len(d.offsets) / 4
	d.mu.RUnlock()
	return n
}