func (r *Reader) readSymbols(off int) error {
	if off == 0 {
		return nil
	}
	d := r.decbufAt(off)
	var (
		origLen = d.len()
		cnt     = d.be32int()
		basePos = uint32(off) + 4
		nextPos = basePos + uint32(origLen-d.len())
	)
	if r.version == 2 {
		nextPos = 0
	}
	for d.err() == nil && d.len() > 0 && cnt > 0 {
		s := d.uvarintStr()
		r.symbols[nextPos] = s
		if r.version == 2 {
			nextPos++
		} else {
			nextPos = basePos + uint32(origLen-d.len())
		}
		cnt--
	}
	return errors.Wrap(d.err(), "read symbols")
}
readSymbols reads the symbol table fully into memory and allocates proper strings for them.
Strings backed by the mmap'd memory would cause memory faults if applications keep using them
after the reader is closed.
package index
import (
	"bufio"
	"encoding/binary"
	"fmt"
	"hash"
	"hash/crc32"
	"io"
	"math"
	"os"
	"path/filepath"
	"sort"
	"strings"
	"github.com/pkg/errors"
	"github.com/prometheus/tsdb/chunks"
	"github.com/prometheus/tsdb/fileutil"
	"github.com/prometheus/tsdb/labels"
)
const (
	MagicIndex = 0xBAAAD700
	indexFormatV1 = 1
	indexFormatV2 = 2
)
type indexWriterSeries struct {
	labels labels.Labels
	chunks []chunks.Meta  
	offset uint32         
}
type indexWriterSeriesSlice []*indexWriterSeries
func (s indexWriterSeriesSlice) Len() int      { return len(s) }
func (s indexWriterSeriesSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s indexWriterSeriesSlice) Less(i, j int) bool {
	return labels.Compare(s[i].labels, s[j].labels) < 0
}
type indexWriterStage uint8
const (
	idxStageNone indexWriterStage = iota
	idxStageSymbols
	idxStageSeries
	idxStageLabelIndex
	idxStagePostings
	idxStageDone
)
func (s indexWriterStage) String() string {
	switch s {
	case idxStageNone:
		return "none"
	case idxStageSymbols:
		return "symbols"
	case idxStageSeries:
		return "series"
	case idxStageLabelIndex:
		return "label index"
	case idxStagePostings:
		return "postings"
	case idxStageDone:
		return "done"
	}
	return "<unknown>"
}
var castagnoliTable *crc32.Table
func init() {
	castagnoliTable = crc32.MakeTable(crc32.Castagnoli)
}
func newCRC32() hash.Hash32 {
	return crc32.New(castagnoliTable)
}
type Writer struct {
	f    *os.File
	fbuf *bufio.Writer
	pos  uint64
	toc   indexTOC
	stage indexWriterStage
	buf1    encbuf
	buf2    encbuf
	uint32s []uint32
	symbols       map[string]uint32  
	seriesOffsets map[uint64]uint64  
	labelIndexes  []hashEntry        
	postings      []hashEntry        
	lastSeries labels.Labels
	crc32 hash.Hash
	Version int
}
type indexTOC struct {
	symbols           uint64
	series            uint64
	labelIndices      uint64
	labelIndicesTable uint64
	postings          uint64
	postingsTable     uint64
}
func NewWriter(fn string) (*Writer, error) {
	dir := filepath.Dir(fn)
	df, err := fileutil.OpenDir(dir)
	if err != nil {
		return nil, err
	}
	defer df.Close()  
	if err := os.RemoveAll(fn); err != nil {
		return nil, errors.Wrap(err, "remove any existing index at path")
	}
	f, err := os.OpenFile(fn, os.O_CREATE|os.O_WRONLY, 0666)
	if err != nil {
		return nil, err
	}
	if err := fileutil.Fsync(df); err != nil {
		return nil, errors.Wrap(err, "sync dir")
	}
	iw := &Writer{
		f:     f,
		fbuf:  bufio.NewWriterSize(f, 1<<22),
		pos:   0,
		stage: idxStageNone,
		buf1:    encbuf{b: make([]byte, 0, 1<<22)},
		buf2:    encbuf{b: make([]byte, 0, 1<<22)},
		uint32s: make([]uint32, 0, 1<<15),
		symbols:       make(map[string]uint32, 1<<13),
		seriesOffsets: make(map[uint64]uint64, 1<<16),
		crc32:         newCRC32(),
	}
	if err := iw.writeMeta(); err != nil {
		return nil, err
	}
	return iw, nil
}
func (w *Writer) write(bufs ...[]byte) error {
	for _, b := range bufs {
		n, err := w.fbuf.Write(b)
		w.pos += uint64(n)
		if err != nil {
			return err
		}
		if w.pos > 16*math.MaxUint32 {
			return errors.Errorf("exceeding max size of 64GiB")
		}
	}
	return nil
}
func (w *Writer) addPadding(size int) error {
	p := w.pos % uint64(size)
	if p == 0 {
		return nil
	}
	p = uint64(size) - p
	return errors.Wrap(w.write(make([]byte, p)), "add padding")
}
func (w *Writer) ensureStage(s indexWriterStage) error {
	if w.stage == s {
		return nil
	}
	if w.stage > s {
		return errors.Errorf("invalid stage %q, currently at %q", s, w.stage)
	}
	switch s {
	case idxStageSymbols:
		w.toc.symbols = w.pos
	case idxStageSeries:
		w.toc.series = w.pos
	case idxStageLabelIndex:
		w.toc.labelIndices = w.pos
	case idxStagePostings:
		w.toc.postings = w.pos
	case idxStageDone:
		w.toc.labelIndicesTable = w.pos
		if err := w.writeOffsetTable(w.labelIndexes); err != nil {
			return err
		}
		w.toc.postingsTable = w.pos
		if err := w.writeOffsetTable(w.postings); err != nil {
			return err
		}
		if err := w.writeTOC(); err != nil {
			return err
		}
	}
	w.stage = s
	return nil
}
func (w *Writer) writeMeta() error {
	w.buf1.reset()
	w.buf1.putBE32(MagicIndex)
	w.buf1.putByte(indexFormatV2)
	return w.write(w.buf1.get())
}
func (w *Writer) AddSeries(ref uint64, lset labels.Labels, chunks ...chunks.Meta) error {
	if err := w.ensureStage(idxStageSeries); err != nil {
		return err
	}
	if labels.Compare(lset, w.lastSeries) <= 0 {
		return errors.Errorf("out-of-order series added with label set %q", lset)
	}
	if _, ok := w.seriesOffsets[ref]; ok {
		return errors.Errorf("series with reference %d already added", ref)
	}
	w.addPadding(16)
	if w.pos%16 != 0 {
		return errors.Errorf("series write not 16-byte aligned at %d", w.pos)
	}
	w.seriesOffsets[ref] = w.pos / 16
	w.buf2.reset()
	w.buf2.putUvarint(len(lset))
	for _, l := range lset {
		index, ok := w.symbols[l.Name]
		if !ok {
			return errors.Errorf("symbol entry for %q does not exist", l.Name)
		}
		w.buf2.putUvarint32(index)
		index, ok = w.symbols[l.Value]
		if !ok {
			return errors.Errorf("symbol entry for %q does not exist", l.Value)
		}
		w.buf2.putUvarint32(index)
	}
	w.buf2.putUvarint(len(chunks))
	if len(chunks) > 0 {
		c := chunks[0]
		w.buf2.putVarint64(c.MinTime)
		w.buf2.putUvarint64(uint64(c.MaxTime - c.MinTime))
		w.buf2.putUvarint64(c.Ref)
		t0 := c.MaxTime
		ref0 := int64(c.Ref)
		for _, c := range chunks[1:] {
			w.buf2.putUvarint64(uint64(c.MinTime - t0))
			w.buf2.putUvarint64(uint64(c.MaxTime - c.MinTime))
			t0 = c.MaxTime
			w.buf2.putVarint64(int64(c.Ref) - ref0)
			ref0 = int64(c.Ref)
		}
	}
	w.buf1.reset()
	w.buf1.putUvarint(w.buf2.len())
	w.buf2.putHash(w.crc32)
	if err := w.write(w.buf1.get(), w.buf2.get()); err != nil {
		return errors.Wrap(err, "write series data")
	}
	w.lastSeries = append(w.lastSeries[:0], lset...)
	return nil
}
func (w *Writer) AddSymbols(sym map[string]struct{}) error {
	if err := w.ensureStage(idxStageSymbols); err != nil {
		return err
	}
	symbols := make([]string, 0, len(sym))
	for s := range sym {
		symbols = append(symbols, s)
	}
	sort.Strings(symbols)
	const headerSize = 4
	w.buf1.reset()
	w.buf2.reset()
	w.buf2.putBE32int(len(symbols))
	w.symbols = make(map[string]uint32, len(symbols))
	for index, s := range symbols {
		w.symbols[s] = uint32(index)
		w.buf2.putUvarintStr(s)
	}
	w.buf1.putBE32int(w.buf2.len())
	w.buf2.putHash(w.crc32)
	err := w.write(w.buf1.get(), w.buf2.get())
	return errors.Wrap(err, "write symbols")
}
func (w *Writer) WriteLabelIndex(names []string, values []string) error {
	if len(values)%len(names) != 0 {
		return errors.Errorf("invalid value list length %d for %d names", len(values), len(names))
	}
	if err := w.ensureStage(idxStageLabelIndex); err != nil {
		return errors.Wrap(err, "ensure stage")
	}
	valt, err := NewStringTuples(values, len(names))
	if err != nil {
		return err
	}
	sort.Sort(valt)
	if err := w.addPadding(4); err != nil {
		return err
	}
	w.labelIndexes = append(w.labelIndexes, hashEntry{
		keys:   names,
		offset: w.pos,
	})
	w.buf2.reset()
	w.buf2.putBE32int(len(names))
	w.buf2.putBE32int(valt.Len())
	for _, v := range valt.s {
		index, ok := w.symbols[v]
		if !ok {
			return errors.Errorf("symbol entry for %q does not exist", v)
		}
		w.buf2.putBE32(index)
	}
	w.buf1.reset()
	w.buf1.putBE32int(w.buf2.len())
	w.buf2.putHash(w.crc32)
	err = w.write(w.buf1.get(), w.buf2.get())
	return errors.Wrap(err, "write label index")
}
func (w *Writer) writeOffsetTable(entries []hashEntry) error {
	w.buf2.reset()
	w.buf2.putBE32int(len(entries))
	for _, e := range entries {
		w.buf2.putUvarint(len(e.keys))
		for _, k := range e.keys {
			w.buf2.putUvarintStr(k)
		}
		w.buf2.putUvarint64(e.offset)
	}
	w.buf1.reset()
	w.buf1.putBE32int(w.buf2.len())
	w.buf2.putHash(w.crc32)
	return w.write(w.buf1.get(), w.buf2.get())
}
const indexTOCLen = 6*8 + 4
func (w *Writer) writeTOC() error {
	w.buf1.reset()
	w.buf1.putBE64(w.toc.symbols)
	w.buf1.putBE64(w.toc.series)
	w.buf1.putBE64(w.toc.labelIndices)
	w.buf1.putBE64(w.toc.labelIndicesTable)
	w.buf1.putBE64(w.toc.postings)
	w.buf1.putBE64(w.toc.postingsTable)
	w.buf1.putHash(w.crc32)
	return w.write(w.buf1.get())
}
func (w *Writer) WritePostings(name, value string, it Postings) error {
	if err := w.ensureStage(idxStagePostings); err != nil {
		return errors.Wrap(err, "ensure stage")
	}
	if err := w.addPadding(4); err != nil {
		return err
	}
	w.postings = append(w.postings, hashEntry{
		keys:   []string{name, value},
		offset: w.pos,
	})
	refs := w.uint32s[:0]
	for it.Next() {
		offset, ok := w.seriesOffsets[it.At()]
		if !ok {
			return errors.Errorf("%p series for reference %d not found", w, it.At())
		}
		if offset > (1<<32)-1 {
			return errors.Errorf("series offset %d exceeds 4 bytes", offset)
		}
		refs = append(refs, uint32(offset))
	}
	if err := it.Err(); err != nil {
		return err
	}
	sort.Sort(uint32slice(refs))
	w.buf2.reset()
	w.buf2.putBE32int(len(refs))
	for _, r := range refs {
		w.buf2.putBE32(r)
	}
	w.uint32s = refs
	w.buf1.reset()
	w.buf1.putBE32int(w.buf2.len())
	w.buf2.putHash(w.crc32)
	err := w.write(w.buf1.get(), w.buf2.get())
	return errors.Wrap(err, "write postings")
}
type uint32slice []uint32
func (s uint32slice) Len() int           { return len(s) }
func (s uint32slice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s uint32slice) Less(i, j int) bool { return s[i] < s[j] }
type hashEntry struct {
	keys   []string
	offset uint64
}
func (w *Writer) Close() error {
	if err := w.ensureStage(idxStageDone); err != nil {
		return err
	}
	if err := w.fbuf.Flush(); err != nil {
		return err
	}
	if err := fileutil.Fsync(w.f); err != nil {
		return err
	}
	return w.f.Close()
}
type StringTuples interface {
	Len() int
	At(i int) ([]string, error)
}
type Reader struct {
	b   ByteSlice
	toc indexTOC
	c io.Closer
	labels   map[string]uint64
	postings map[labels.Label]uint64
	symbols map[uint32]string
	dec *Decoder
	crc32 hash.Hash32
	version int
}
var (
	errInvalidSize     = fmt.Errorf("invalid size")
	errInvalidFlag     = fmt.Errorf("invalid flag")
	errInvalidChecksum = fmt.Errorf("invalid checksum")
)
type ByteSlice interface {
	Len() int
	Range(start, end int) []byte
}
type realByteSlice []byte
func (b realByteSlice) Len() int {
	return len(b)
}
func (b realByteSlice) Range(start, end int) []byte {
	return b[start:end]
}
func (b realByteSlice) Sub(start, end int) ByteSlice {
	return b[start:end]
}
func NewReader(b ByteSlice) (*Reader, error) {
	return newReader(b, nil)
}
func NewFileReader(path string) (*Reader, error) {
	f, err := fileutil.OpenMmapFile(path)
	if err != nil {
		return nil, err
	}
	return newReader(realByteSlice(f.Bytes()), f)
}
func newReader(b ByteSlice, c io.Closer) (*Reader, error) {
	r := &Reader{
		b:        b,
		c:        c,
		symbols:  map[uint32]string{},
		labels:   map[string]uint64{},
		postings: map[labels.Label]uint64{},
		crc32:    newCRC32(),
	}
	if b.Len() < 5 {
		return nil, errors.Wrap(errInvalidSize, "index header")
	}
	if m := binary.BigEndian.Uint32(r.b.Range(0, 4)); m != MagicIndex {
		return nil, errors.Errorf("invalid magic number %x", m)
	}
	r.version = int(r.b.Range(4, 5)[0])
	if r.version != 1 && r.version != 2 {
		return nil, errors.Errorf("unknown index file version %d", r.version)
	}
	if err := r.readTOC(); err != nil {
		return nil, errors.Wrap(err, "read TOC")
	}
	if err := r.readSymbols(int(r.toc.symbols)); err != nil {
		return nil, errors.Wrap(err, "read symbols")
	}
	var err error
	err = r.readOffsetTable(r.toc.labelIndicesTable, func(key []string, off uint64) error {
		if len(key) != 1 {
			return errors.Errorf("unexpected key length %d", len(key))
		}
		r.labels[key[0]] = off
		return nil
	})
	if err != nil {
		return nil, errors.Wrap(err, "read label index table")
	}
	err = r.readOffsetTable(r.toc.postingsTable, func(key []string, off uint64) error {
		if len(key) != 2 {
			return errors.Errorf("unexpected key length %d", len(key))
		}
		r.postings[labels.Label{Name: key[0], Value: key[1]}] = off
		return nil
	})
	if err != nil {
		return nil, errors.Wrap(err, "read postings table")
	}
	r.dec = &Decoder{symbols: r.symbols}
	return r, nil
}
func (r *Reader) Version() int {
	return r.version
}
type Range struct {
	Start, End int64
}
func (r *Reader) PostingsRanges() (map[labels.Label]Range, error) {
	m := map[labels.Label]Range{}
	for l, start := range r.postings {
		d := r.decbufAt(int(start))
		if d.err() != nil {
			return nil, d.err()
		}
		m[l] = Range{
			Start: int64(start) + 4,
			End:   int64(start) + 4 + int64(d.len()),
		}
	}
	return m, nil
}
func (r *Reader) readTOC() error {
	if r.b.Len() < indexTOCLen {
		return errInvalidSize
	}
	b := r.b.Range(r.b.Len()-indexTOCLen, r.b.Len())
	expCRC := binary.BigEndian.Uint32(b[len(b)-4:])
	d := decbuf{b: b[:len(b)-4]}
	if d.crc32() != expCRC {
		return errors.Wrap(errInvalidChecksum, "read TOC")
	}
	r.toc.symbols = d.be64()
	r.toc.series = d.be64()
	r.toc.labelIndices = d.be64()
	r.toc.labelIndicesTable = d.be64()
	r.toc.postings = d.be64()
	r.toc.postingsTable = d.be64()
	return d.err()
}
func (r *Reader) decbufAt(off int) decbuf {
	if r.b.Len() < off+4 {
		return decbuf{e: errInvalidSize}
	}
	b := r.b.Range(off, off+4)
	l := int(binary.BigEndian.Uint32(b))
	if r.b.Len() < off+4+l+4 {
		return decbuf{e: errInvalidSize}
	}
	b = r.b.Range(off+4, off+4+l+4)
	dec := decbuf{b: b[:len(b)-4]}
	if exp := binary.BigEndian.Uint32(b[len(b)-4:]); dec.crc32() != exp {
		return decbuf{e: errInvalidChecksum}
	}
	return dec
}
func (r *Reader) decbufUvarintAt(off int) decbuf {
	if r.b.Len() < off+binary.MaxVarintLen32 {
		return decbuf{e: errInvalidSize}
	}
	b := r.b.Range(off, off+binary.MaxVarintLen32)
	l, n := binary.Uvarint(b)
	if n <= 0 || n > binary.MaxVarintLen32 {
		return decbuf{e: errors.Errorf("invalid uvarint %d", n)}
	}
	if r.b.Len() < off+n+int(l)+4 {
		return decbuf{e: errInvalidSize}
	}
	b = r.b.Range(off+n, off+n+int(l)+4)
	dec := decbuf{b: b[:len(b)-4]}
	if dec.crc32() != binary.BigEndian.Uint32(b[len(b)-4:]) {
		return decbuf{e: errInvalidChecksum}
	}
	return dec
}