func (r *Reader) SortedPostings(p Postings) Postings {
	return p
}
SortedPostings returns the given postings list reordered so that the backing series
are sorted.
package index
import (
	"bufio"
	"encoding/binary"
	"hash"
	"hash/crc32"
	"io"
	"io/ioutil"
	"math"
	"os"
	"path/filepath"
	"sort"
	"strings"
	"github.com/pkg/errors"
	"github.com/prometheus/prometheus/tsdb/chunks"
	"github.com/prometheus/prometheus/tsdb/encoding"
	tsdb_errors "github.com/prometheus/prometheus/tsdb/errors"
	"github.com/prometheus/prometheus/tsdb/fileutil"
	"github.com/prometheus/prometheus/tsdb/labels"
)
const (
	MagicIndex = 0xBAAAD700
	HeaderLen = 5
	FormatV1 = 1
	FormatV2 = 2
	labelNameSeperator = "\xff"
	indexFilename = "index"
)
type indexWriterSeries struct {
	labels labels.Labels
	chunks []chunks.Meta  
}
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   TOC
	stage indexWriterStage
	buf1    encoding.Encbuf
	buf2    encoding.Encbuf
	uint32s []uint32
	symbols       map[string]uint32      
	seriesOffsets map[uint64]uint64      
	labelIndexes  []labelIndexHashEntry  
	postings      []postingsHashEntry    
	lastSeries labels.Labels
	crc32 hash.Hash
	Version int
}
type TOC struct {
	Symbols           uint64
	Series            uint64
	LabelIndices      uint64
	LabelIndicesTable uint64
	Postings          uint64
	PostingsTable     uint64
}
func NewTOCFromByteSlice(bs ByteSlice) (*TOC, error) {
	if bs.Len() < indexTOCLen {
		return nil, encoding.ErrInvalidSize
	}
	b := bs.Range(bs.Len()-indexTOCLen, bs.Len())
	expCRC := binary.BigEndian.Uint32(b[len(b)-4:])
	d := encoding.Decbuf{B: b[:len(b)-4]}
	if d.Crc32(castagnoliTable) != expCRC {
		return nil, errors.Wrap(encoding.ErrInvalidChecksum, "read TOC")
	}
	if err := d.Err(); err != nil {
		return nil, err
	}
	return &TOC{
		Symbols:           d.Be64(),
		Series:            d.Be64(),
		LabelIndices:      d.Be64(),
		LabelIndicesTable: d.Be64(),
		Postings:          d.Be64(),
		PostingsTable:     d.Be64(),
	}, nil
}
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 := df.Sync(); err != nil {
		return nil, errors.Wrap(err, "sync dir")
	}
	iw := &Writer{
		f:     f,
		fbuf:  bufio.NewWriterSize(f, 1<<22),
		pos:   0,
		stage: idxStageNone,
		buf1:    encoding.Encbuf{B: make([]byte, 0, 1<<22)},
		buf2:    encoding.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.writeLabelIndexesOffsetTable(); err != nil {
			return err
		}
		w.toc.PostingsTable = w.pos
		if err := w.writePostingsOffsetTable(); 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(FormatV2)
	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)
	}
	if err := w.addPadding(16); err != nil {
		return errors.Errorf("failed to write padding bytes: %v", err)
	}
	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)
	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, labelIndexHashEntry{
		keys:   names,
		offset: w.pos,
	})
	w.buf2.Reset()
	w.buf2.PutBE32int(len(names))
	w.buf2.PutBE32int(valt.Len())
	for _, v := range valt.entries {
		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) writeLabelIndexesOffsetTable() error {
	w.buf2.Reset()
	w.buf2.PutBE32int(len(w.labelIndexes))
	for _, e := range w.labelIndexes {
		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())
}
func (w *Writer) writePostingsOffsetTable() error {
	w.buf2.Reset()
	w.buf2.PutBE32int(len(w.postings))
	for _, e := range w.postings {
		w.buf2.PutUvarint(2)
		w.buf2.PutUvarintStr(e.name)
		w.buf2.PutUvarintStr(e.value)
		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, postingsHashEntry{
		name:   name,
		value:  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 labelIndexHashEntry struct {
	keys   []string
	offset uint64
}
type postingsHashEntry struct {
	name, value 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 := w.f.Sync(); err != nil {
		return err
	}
	return w.f.Close()
}
type StringTuples interface {
	Len() int
	At(i int) ([]string, error)
}
type Reader struct {
	b ByteSlice
	c io.Closer
	labels map[string]uint64
	postings map[string]map[string]uint64
	symbolsV1        map[uint32]string
	symbolsV2        []string
	symbolsTableSize uint64
	dec *Decoder
	version int
}
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, ioutil.NopCloser(nil))
}
func NewFileReader(path string) (*Reader, error) {
	f, err := fileutil.OpenMmapFile(path)
	if err != nil {
		return nil, err
	}
	r, err := newReader(realByteSlice(f.Bytes()), f)
	if err != nil {
		var merr tsdb_errors.MultiError
		merr.Add(err)
		merr.Add(f.Close())
		return nil, merr
	}
	return r, nil
}
func newReader(b ByteSlice, c io.Closer) (*Reader, error) {
	r := &Reader{
		b:        b,
		c:        c,
		labels:   map[string]uint64{},
		postings: map[string]map[string]uint64{},
	}
	if r.b.Len() < HeaderLen {
		return nil, errors.Wrap(encoding.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 != FormatV1 && r.version != FormatV2 {
		return nil, errors.Errorf("unknown index file version %d", r.version)
	}
	toc, err := NewTOCFromByteSlice(b)
	if err != nil {
		return nil, errors.Wrap(err, "read TOC")
	}
	r.symbolsV2, r.symbolsV1, err = ReadSymbols(r.b, r.version, int(toc.Symbols))
	if err != nil {
		return nil, errors.Wrap(err, "read symbols")
	}
	allocatedSymbols := make(map[string]string, len(r.symbolsV1)+len(r.symbolsV2))
	for _, s := range r.symbolsV1 {
		r.symbolsTableSize += uint64(len(s) + 8)
		allocatedSymbols[s] = s
	}
	for _, s := range r.symbolsV2 {
		r.symbolsTableSize += uint64(len(s) + 8)
		allocatedSymbols[s] = s
	}
	if err := ReadOffsetTable(r.b, toc.LabelIndicesTable, func(key []string, off uint64) error {
		if len(key) != 1 {
			return errors.Errorf("unexpected key length for label indices table %d", len(key))
		}
		r.labels[allocatedSymbols[key[0]]] = off
		return nil
	}); err != nil {
		return nil, errors.Wrap(err, "read label index table")
	}
	r.postings[""] = map[string]uint64{}
	if err := ReadOffsetTable(r.b, toc.PostingsTable, func(key []string, off uint64) error {
		if len(key) != 2 {
			return errors.Errorf("unexpected key length for posting table %d", len(key))
		}
		if _, ok := r.postings[key[0]]; !ok {
			r.postings[allocatedSymbols[key[0]]] = map[string]uint64{}
		}
		r.postings[key[0]][allocatedSymbols[key[1]]] = off
		return nil
	}); err != nil {
		return nil, errors.Wrap(err, "read postings table")
	}
	r.dec = &Decoder{LookupSymbol: r.lookupSymbol}
	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 k, e := range r.postings {
		for v, start := range e {
			d := encoding.NewDecbufAt(r.b, int(start), castagnoliTable)
			if d.Err() != nil {
				return nil, d.Err()
			}
			m[labels.Label{Name: k, Value: v}] = Range{
				Start: int64(start) + 4,
				End:   int64(start) + 4 + int64(d.Len()),
			}
		}
	}
	return m, nil
}
func ReadSymbols(bs ByteSlice, version int, off int) ([]string, map[uint32]string, error) {
	if off == 0 {
		return nil, nil, nil
	}
	d := encoding.NewDecbufAt(bs, off, castagnoliTable)
	var (
		origLen     = d.Len()
		cnt         = d.Be32int()
		basePos     = uint32(off) + 4
		nextPos     = basePos + uint32(origLen-d.Len())
		symbolSlice []string
		symbols     = map[uint32]string{}
	)
	if version == FormatV2 {
		symbolSlice = make([]string, 0, cnt)
	}
	for d.Err() == nil && d.Len() > 0 && cnt > 0 {
		s := d.UvarintStr()
		if version == FormatV2 {
			symbolSlice = append(symbolSlice, s)
		} else {
			symbols[nextPos] = s
			nextPos = basePos + uint32(origLen-d.Len())
		}
		cnt--
	}
	return symbolSlice, symbols, errors.Wrap(d.Err(), "read symbols")
}
func ReadOffsetTable(bs ByteSlice, off uint64, f func([]string, uint64) error) error {
	d := encoding.NewDecbufAt(bs, int(off), castagnoliTable)
	cnt := d.Be32()
	keys := make([]string, 0, 2)
	for d.Err() == nil && d.Len() > 0 && cnt > 0 {
		keyCount := d.Uvarint()
		keys = keys[:0]
		for i := 0; i < keyCount; i++ {
			keys = append(keys, d.UvarintStr())
		}
		o := d.Uvarint64()
		if d.Err() != nil {
			break
		}
		if err := f(keys, o); err != nil {
			return err
		}
		cnt--
	}
	return d.Err()
}
func (r *Reader) Close() error {
	return r.c.Close()
}
func (r *Reader) lookupSymbol(o uint32) (string, error) {
	if int(o) < len(r.symbolsV2) {
		return r.symbolsV2[o], nil
	}
	s, ok := r.symbolsV1[o]
	if !ok {
		return "", errors.Errorf("unknown symbol offset %d", o)
	}
	return s, nil
}
func (r *Reader) Symbols() (map[string]struct{}, error) {
	res := make(map[string]struct{}, len(r.symbolsV1)+len(r.symbolsV2))
	for _, s := range r.symbolsV1 {
		res[s] = struct{}{}
	}
	for _, s := range r.symbolsV2 {
		res[s] = struct{}{}
	}
	return res, nil
}
func (r *Reader) SymbolTableSize() uint64 {
	return r.symbolsTableSize
}
func (r *Reader) LabelValues(names ...string) (StringTuples, error) {
	key := strings.Join(names, labelNameSeperator)
	off, ok := r.labels[key]
	if !ok {
		return emptyStringTuples{}, nil
	}
	d := encoding.NewDecbufAt(r.b, int(off), castagnoliTable)
	nc := d.Be32int()
	d.Be32()  
	if d.Err() != nil {
		return nil, errors.Wrap(d.Err(), "read label value index")
	}
	st := &serializedStringTuples{
		idsCount: nc,
		idsBytes: d.Get(),
		lookup:   r.lookupSymbol,
	}
	return st, nil
}
type emptyStringTuples struct{}
func (emptyStringTuples) At(i int) ([]string, error) { return nil, nil }
func (emptyStringTuples) Len() int                   { return 0 }
func (r *Reader) LabelIndices() ([][]string, error) {
	var res [][]string
	for s := range r.labels {
		res = append(res, strings.Split(s, labelNameSeperator))
	}
	return res, nil
}
func (r *Reader) Series(id uint64, lbls *labels.Labels, chks *[]chunks.Meta) error {
	offset := id
	if r.version == FormatV2 {
		offset = id * 16
	}
	d := encoding.NewDecbufUvarintAt(r.b, int(offset), castagnoliTable)
	if d.Err() != nil {
		return d.Err()
	}
	return errors.Wrap(r.dec.Series(d.Get(), lbls, chks), "read series")
}
func (r *Reader) Postings(name, value string) (Postings, error) {
	e, ok := r.postings[name]
	if !ok {
		return EmptyPostings(), nil
	}
	off, ok := e[value]
	if !ok {
		return EmptyPostings(), nil
	}
	d := encoding.NewDecbufAt(r.b, int(off), castagnoliTable)
	if d.Err() != nil {
		return nil, errors.Wrap(d.Err(), "get postings entry")
	}
	_, p, err := r.dec.Postings(d.Get())
	if err != nil {
		return nil, errors.Wrap(err, "decode postings")
	}
	return p, nil
}