// TODO: make this array'd so we can do bin search?
// likely not worth it?  need to measure how many
// floor blocks we "typically" get
172168
func (f *segmentTermsEnumFrame) scanToFloorFrame(target []byte) {
	if !f.isFloor || len(target) <= f.prefix {
		// fmt.Printf("    scanToFloorFrame skip: isFloor=%v target.length=%v vs prefix=%v\n",
		// 	f.isFloor, len(target), f.prefix)
		return
	}

	targetLabel := int(target[f.prefix])
	fmt.Printf("    scanToFloorFrame fpOrig=%v targetLabel=%x vs nextFloorLabel=%x numFollowFloorBlocks=%v\n",
		f.fpOrig, targetLabel, f.nextFloorLabel, f.numFollowFloorBlocks)
	if targetLabel < f.nextFloorLabel {
		fmt.Println("      already on correct block")
		return
	}

	assert(f.numFollowFloorBlocks != 0)

	var newFP int64
	for {
		code, _ := f.floorDataReader.ReadVLong() // ignore error
		newFP = f.fpOrig + int64(uint64(code)>>1)
		f.hasTerms = (code & 1) != 0
		// fmt.Printf("      label=%x fp=%v hasTerms?=%v numFollorFloor=%v\n",
		// f.nextFloorLabel, newFP, f.hasTerms, f.numFollowFloorBlocks)

		f.isLastInFloor = f.numFollowFloorBlocks == 1
		f.numFollowFloorBlocks--

		if f.isLastInFloor {
			f.nextFloorLabel = 256
			fmt.Printf("        stop!  last block nextFloorLabel=%x\n", f.nextFloorLabel)
			break
		} else {
			panic("niy")
		}
	}

	if newFP != f.fp {
		// Force re-load of the block:
		fmt.Printf("      force switch to fp=%v oldFP=%v\n", newFP, f.fp)
		f.nextEnt = -1
		f.fp = newFP
	} else {
		//
	}
}
534190
func (f *FileStore) BlockCount(path string, idx int) int {
	f.mu.RLock()
	defer f.mu.RUnlock()

	if idx < 0 {
		return 0
	}

	for _, fd := range f.files {
		if fd.Path() == path {
			iter := fd.BlockIterator()
			for i := 0; i < idx; i++ {
				if !iter.Next() {
					return 0
				}
			}
			_, _, _, _, _, block, _ := iter.Read()
			return BlockCount(block)
		}
	}
	return 0
}
1089331
func (s *Store) Search(ctx context.Context, key schema.AMKey, ttl, start, end uint32) ([]chunk.IterGen, error) {
	log.Debugf("btStore: fetching chunks for metric %s in range %d %d", key, start, end)
	_, span := tracing.NewSpan(ctx, s.tracer, "BigtableStore.Search")
	defer span.Finish()
	tags.SpanKindRPCClient.Set(span)
	tags.PeerService.Set(span, "bigtable")

	itgens := make([]chunk.IterGen, 0)
	if start > end {
		tracing.Failure(span)
		tracing.Error(span, errStartBeforeEnd)
		return itgens, errStartBeforeEnd
	}

	// limit number of inflight requests
	log.Debugf("btStore: waiting for Search slot. len=%d cap=%d", len(s.readLimiter), cap(s.readLimiter))
	pre := time.Now()
	if !s.readLimiter.Acquire(ctx) {
		return itgens, errCtxCanceled
	}
	log.Debug("btStore: acquired a Search slot")
	btblGetWaitDuration.Value(time.Since(pre))

	startMonth := start / Month_sec   // starting row has to be at, or before, requested start
	endMonth := (end - 1) / Month_sec // ending row has to include the last point we might need (end-1)

	// unfortunately in the database we only have the t0's of all chunks.
	// this means we can easily make sure to include the correct last chunk (just query for a t0 < end, the last chunk will contain the last needed data)
	// but it becomes hard to find which should be the first chunk to include. we can't just query for start <= t0 because then we will miss some data at
	// the beginning. We can't assume we know the chunkSpan so we can't just calculate the t0 >= (start - <some-predefined-number>) because ChunkSpans
	// may change over time.
	// We effectively need all chunks with a t0 > start, as well as the last chunk with a t0 <= start.
	// Bigtable doesn't allow us to fetch the most recent chunk older then start, so instead we just fetch from (start - maxChunkSpan) to enure we get the data. This
	// will usually result in more data being fetched then is needed, but that is an acceptable tradeoff.
	adjustedStart := start - uint32(s.cfg.MaxChunkSpan.Seconds())

	// chunkspans are aligned with Month_sec.  If start is > startMonth*Month_sec then the T0 of the chunk that start is in will also be >= startMonth*Month_sec.
	adjustedStart = util.Max(adjustedStart, startMonth*Month_sec)

	agg := "raw"
	var intervalHint uint32
	if key.Archive > 0 {
		agg = key.Archive.String()
		intervalHint = key.Archive.Span()
	}
	// filter the results to just the agg method (Eg raw, min_60, max_1800, etc..) and the timerange we want.
	// we fetch all columnFamilies (which are the different TTLs).  Typically there will be only one columnFamily
	// that has data, unless the TTL of the agg has changed.  In which case we want all columnFamilies anyway.
	filter := bigtable.ChainFilters(
		bigtable.ColumnFilter(agg),
		bigtable.TimestampRangeFilterMicros(bigtable.Timestamp(int64(adjustedStart)*1e6), bigtable.Timestamp(int64(end)*1e6)),
	)

	firstRow := formatRowKey(key, startMonth)
	lastRow := formatRowKey(key, endMonth+1) // bigtable.RowRange is start inclusive, end exclusive
	rr := bigtable.NewRange(firstRow, lastRow)
	var err error
	rowCount := 0
	pre = time.Now()
	queryCtx, cancel := context.WithTimeout(ctx, s.cfg.ReadTimeout)
	reqErr := s.tbl.ReadRows(queryCtx, rr, func(row bigtable.Row) bool {
		rowCount++
		chunks := 0
		var itgen chunk.IterGen
		for _, items := range row {
			for _, rItem := range items {
				chunkSizeAtLoad.Value(len(rItem.Value))
				if len(rItem.Value) < 2 {
					log.Errorf("btStore: bigtable readRows error. %s", err)
					err = errChunkTooSmall
					return false
				}
				itgen, err = chunk.NewIterGen(uint32(rItem.Timestamp/1e6), intervalHint, rItem.Value)
				if err != nil {
					log.Errorf("btStore: unable to create chunk from bytes. %s", err)
					return false
				}
				chunks++

				// This function is called serially so we don't need synchronization here
				itgens = append(itgens, itgen)
			}
		}
		btblChunksPerRow.Value(chunks)

		return true
	}, bigtable.RowFilter(filter))
	cancel()
	btblRowsPerResponse.Value(rowCount)
	btblGetExecDuration.Value(time.Since(pre))

	// free a slot in the readLimiter
	s.readLimiter.Release()

	if reqErr != nil {
		log.Errorf("btStore: bigtable readRows error. %s", reqErr)
		err = reqErr
	}
	if err != nil {
		tracing.Failure(span)
		tracing.Error(span, err)
		btblReadError.Inc()
	}
	// TODO: do we need to ensure that itgens is sorted by chunk T0?
	sort.Sort(chunk.IterGensAsc(itgens))
	return itgens, err
}
868360
func (c *KeyCursor) ReadIntegerArrayBlock(values *tsdb.IntegerArray) (*tsdb.IntegerArray, error) {
LOOP:
	// No matching blocks to decode
	if len(c.current) == 0 {
		values.Timestamps = values.Timestamps[:0]
		values.Values = values.Values[:0]
		return values, nil
	}

	// First block is the oldest block containing the points we're searching for.
	first := c.current[0]
	err := first.r.ReadIntegerArrayBlockAt(&first.entry, values)
	if err != nil {
		return nil, err
	}
	if c.col != nil {
		c.col.GetCounter(integerBlocksDecodedCounter).Add(1)
		c.col.GetCounter(integerBlocksSizeCounter).Add(int64(first.entry.Size))
	}

	// Remove values we already read
	values.Exclude(first.readMin, first.readMax)

	// Remove any tombstones
	c.trbuf = first.r.TombstoneRange(c.key, c.trbuf[:0])
	excludeTombstonesIntegerArray(c.trbuf, values)
	// If there are no values in this first block (all tombstoned or previously read) and
	// we have more potential blocks too search.  Try again.
	if values.Len() == 0 && len(c.current) > 0 {
		c.current = c.current[1:]
		goto LOOP
	}

	// Only one block with this key and time range so return it
	if len(c.current) == 1 {
		if values.Len() > 0 {
			first.markRead(values.MinTime(), values.MaxTime())
		}
		return values, nil
	}

	// Use the current block time range as our overlapping window
	minT, maxT := first.readMin, first.readMax
	if values.Len() > 0 {
		minT, maxT = values.MinTime(), values.MaxTime()
	}
	if c.ascending {
		// Blocks are ordered by generation, we may have values in the past in later blocks, if so,
		// expand the window to include the min time range to ensure values are returned in ascending
		// order
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			if cur.entry.MinTime < minT && !cur.read() {
				minT = cur.entry.MinTime
			}
		}

		// Find first block that overlaps our window
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			if cur.entry.OverlapsTimeRange(minT, maxT) && !cur.read() {
				// Shrink our window so it's the intersection of the first overlapping block and the
				// first block.  We do this to minimize the region that overlaps and needs to
				// be merged.
				if cur.entry.MaxTime > maxT {
					maxT = cur.entry.MaxTime
				}
				values.Include(minT, maxT)
				break
			}
		}

		// Search the remaining blocks that overlap our window and append their values so we can
		// merge them.
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			// Skip this block if it doesn't contain points we looking for or they have already been read
			if !cur.entry.OverlapsTimeRange(minT, maxT) || cur.read() {
				cur.markRead(minT, maxT)
				continue
			}

			v := &tsdb.IntegerArray{}
			err := cur.r.ReadIntegerArrayBlockAt(&cur.entry, v)
			if err != nil {
				return nil, err
			}
			if c.col != nil {
				c.col.GetCounter(integerBlocksDecodedCounter).Add(1)
				c.col.GetCounter(integerBlocksSizeCounter).Add(int64(cur.entry.Size))
			}

			c.trbuf = cur.r.TombstoneRange(c.key, c.trbuf[:0])
			// Remove any tombstoned values
			excludeTombstonesIntegerArray(c.trbuf, v)

			// Remove values we already read
			v.Exclude(cur.readMin, cur.readMax)

			if v.Len() > 0 {
				// Only use values in the overlapping window
				v.Include(minT, maxT)
				// Merge the remaining values with the existing
				values.Merge(v)
			}
			cur.markRead(minT, maxT)
		}

	} else {
		// Blocks are ordered by generation, we may have values in the past in later blocks, if so,
		// expand the window to include the max time range to ensure values are returned in descending
		// order
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			if cur.entry.MaxTime > maxT && !cur.read() {
				maxT = cur.entry.MaxTime
			}
		}

		// Find first block that overlaps our window
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			if cur.entry.OverlapsTimeRange(minT, maxT) && !cur.read() {
				// Shrink our window so it's the intersection of the first overlapping block and the
				// first block.  We do this to minimize the region that overlaps and needs to
				// be merged.
				if cur.entry.MinTime < minT {
					minT = cur.entry.MinTime
				}
				values.Include(minT, maxT)
				break
			}
		}

		// Search the remaining blocks that overlap our window and append their values so we can
		// merge them.
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			// Skip this block if it doesn't contain points we looking for or they have already been read
			if !cur.entry.OverlapsTimeRange(minT, maxT) || cur.read() {
				cur.markRead(minT, maxT)
				continue
			}

			v := &tsdb.IntegerArray{}
			err := cur.r.ReadIntegerArrayBlockAt(&cur.entry, v)
			if err != nil {
				return nil, err
			}
			if c.col != nil {
				c.col.GetCounter(integerBlocksDecodedCounter).Add(1)
				c.col.GetCounter(integerBlocksSizeCounter).Add(int64(cur.entry.Size))
			}
			c.trbuf = cur.r.TombstoneRange(c.key, c.trbuf[:0])
			// Remove any tombstoned values
			excludeTombstonesIntegerArray(c.trbuf, v)

			// Remove values we already read
			v.Exclude(cur.readMin, cur.readMax)

			// If the block we decoded should have all of it's values included, mark it as read so we
			// don't use it again.
			if v.Len() > 0 {
				v.Include(minT, maxT)
				// Merge the remaining values with the existing
				v.Merge(values)
				*values = *v
			}
			cur.markRead(minT, maxT)
		}
	}

	first.markRead(minT, maxT)

	return values, err
}
1010691
func binSearchRuns(v uint16, a []interval16) (int32, bool) {
	i := int32(sort.Search(len(a),
		func(i int) bool { return a[i].last >= v }))
	if i < int32(len(a)) {
		return i, (v >= a[i].start) && (v <= a[i].last)
	}

	return i, false
}
670305
func (bA *CompactBitArray) NumTrueBitsBefore(index int) int {
	numTrueValues := 0
	for i := 0; i < index; i++ {
		if bA.GetIndex(i) {
			numTrueValues++
		}
	}
	return numTrueValues
}
1002027
func GetRandomIndices(indiceCount, highestIndex int) []int {
	if highestIndex+1 < indiceCount {
		return nil
	}

	indices := make([]int, 0)
	if highestIndex+1 == indiceCount {
		for i := 0; i < indiceCount; i++ {
			indices = append(indices, i)
		}
		return indices
	}

	for len(indices) < indiceCount {
		n := RandomInt(highestIndex + 1)
		if IndexInSlice(indices, n, numbericEqual) != -1 {
			continue
		}
		indices = append(indices, n)
	}
	return indices
}
1122911
func unaryOpFloor(rate int8, in Input, numOutputs int) Input {
	CheckRate(rate)
	return NewInput(UnaryOpUgenName, rate, UnaryOpFloor, numOutputs, in)
}
1175974
func CountBitsBytes(b []byte) int {
	c := 0
	for _, x := range b {
		c += CountBitsByte(x)
	}
	return c
}
1066191
func (ssa *SQLStorageAuthority) checkFQDNSetExists(selector oneSelectorFunc, names []string) (bool, error) {
	var count int64
	err := selector(
		&count,
		`SELECT COUNT(1) FROM fqdnSets
		WHERE setHash = ?
		LIMIT 1`,
		hashNames(names),
	)
	return count > 0, err
}
661694
func (t Term) Floor(args ...interface{}) Term {
	return constructMethodTerm(t, "Floor", p.Term_FLOOR, args, map[string]interface{}{})
}
1055991
func (i *Index) Chunks(rid int, beg, end int) []bgzf.Chunk {
	if rid < 0 || rid >= len(i.refs) {
		return nil
	}
	i.sort()
	ref := i.refs[rid]

	// Collect candidate chunks according to a scheme modified
	// from the one described in the SAM spec under section 5
	// Indexing BAM.
	var chunks []bgzf.Chunk
	for _, bin := range reg2bins(int64(beg), int64(end), i.minShift, i.depth) {
		b := uint32(bin)
		c := sort.Search(len(ref.bins), func(i int) bool { return ref.bins[i].bin >= b })
		if c < len(ref.bins) && ref.bins[c].bin == b {
			left := vOffset(ref.bins[c].left)
			for _, chunk := range ref.bins[c].chunks {
				if vOffset(chunk.End) > left {
					chunks = append(chunks, chunk)
				}
			}
		}
	}

	// Sort and merge overlaps.
	if !sort.IsSorted(byBeginOffset(chunks)) {
		sort.Sort(byBeginOffset(chunks))
	}

	return adjacent(chunks)
}
1192999
func (commit *Commit) BitArray() *cmn.BitArray {
	if commit.bitArray == nil {
		commit.bitArray = cmn.NewBitArray(len(commit.Precommits))
		for i, precommit := range commit.Precommits {
			// TODO: need to check the BlockID otherwise we could be counting conflicts,
			// not just the one with +2/3 !
			commit.bitArray.SetIndex(i, precommit != nil)
		}
	}
	return commit.bitArray
}
1368263
func (c *KeyCursor) ReadBooleanArrayBlock(values *tsdb.BooleanArray) (*tsdb.BooleanArray, error) {
LOOP:
	// No matching blocks to decode
	if len(c.current) == 0 {
		values.Timestamps = values.Timestamps[:0]
		values.Values = values.Values[:0]
		return values, nil
	}

	// First block is the oldest block containing the points we're searching for.
	first := c.current[0]
	err := first.r.ReadBooleanArrayBlockAt(&first.entry, values)
	if err != nil {
		return nil, err
	}
	if c.col != nil {
		c.col.GetCounter(booleanBlocksDecodedCounter).Add(1)
		c.col.GetCounter(booleanBlocksSizeCounter).Add(int64(first.entry.Size))
	}

	// Remove values we already read
	values.Exclude(first.readMin, first.readMax)

	// Remove any tombstones
	c.trbuf = first.r.TombstoneRange(c.key, c.trbuf[:0])
	excludeTombstonesBooleanArray(c.trbuf, values)
	// If there are no values in this first block (all tombstoned or previously read) and
	// we have more potential blocks too search.  Try again.
	if values.Len() == 0 && len(c.current) > 0 {
		c.current = c.current[1:]
		goto LOOP
	}

	// Only one block with this key and time range so return it
	if len(c.current) == 1 {
		if values.Len() > 0 {
			first.markRead(values.MinTime(), values.MaxTime())
		}
		return values, nil
	}

	// Use the current block time range as our overlapping window
	minT, maxT := first.readMin, first.readMax
	if values.Len() > 0 {
		minT, maxT = values.MinTime(), values.MaxTime()
	}
	if c.ascending {
		// Blocks are ordered by generation, we may have values in the past in later blocks, if so,
		// expand the window to include the min time range to ensure values are returned in ascending
		// order
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			if cur.entry.MinTime < minT && !cur.read() {
				minT = cur.entry.MinTime
			}
		}

		// Find first block that overlaps our window
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			if cur.entry.OverlapsTimeRange(minT, maxT) && !cur.read() {
				// Shrink our window so it's the intersection of the first overlapping block and the
				// first block.  We do this to minimize the region that overlaps and needs to
				// be merged.
				if cur.entry.MaxTime > maxT {
					maxT = cur.entry.MaxTime
				}
				values.Include(minT, maxT)
				break
			}
		}

		// Search the remaining blocks that overlap our window and append their values so we can
		// merge them.
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			// Skip this block if it doesn't contain points we looking for or they have already been read
			if !cur.entry.OverlapsTimeRange(minT, maxT) || cur.read() {
				cur.markRead(minT, maxT)
				continue
			}

			v := &tsdb.BooleanArray{}
			err := cur.r.ReadBooleanArrayBlockAt(&cur.entry, v)
			if err != nil {
				return nil, err
			}
			if c.col != nil {
				c.col.GetCounter(booleanBlocksDecodedCounter).Add(1)
				c.col.GetCounter(booleanBlocksSizeCounter).Add(int64(cur.entry.Size))
			}

			c.trbuf = cur.r.TombstoneRange(c.key, c.trbuf[:0])
			// Remove any tombstoned values
			excludeTombstonesBooleanArray(c.trbuf, v)

			// Remove values we already read
			v.Exclude(cur.readMin, cur.readMax)

			if v.Len() > 0 {
				// Only use values in the overlapping window
				v.Include(minT, maxT)
				// Merge the remaining values with the existing
				values.Merge(v)
			}
			cur.markRead(minT, maxT)
		}

	} else {
		// Blocks are ordered by generation, we may have values in the past in later blocks, if so,
		// expand the window to include the max time range to ensure values are returned in descending
		// order
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			if cur.entry.MaxTime > maxT && !cur.read() {
				maxT = cur.entry.MaxTime
			}
		}

		// Find first block that overlaps our window
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			if cur.entry.OverlapsTimeRange(minT, maxT) && !cur.read() {
				// Shrink our window so it's the intersection of the first overlapping block and the
				// first block.  We do this to minimize the region that overlaps and needs to
				// be merged.
				if cur.entry.MinTime < minT {
					minT = cur.entry.MinTime
				}
				values.Include(minT, maxT)
				break
			}
		}

		// Search the remaining blocks that overlap our window and append their values so we can
		// merge them.
		for i := 1; i < len(c.current); i++ {
			cur := c.current[i]
			// Skip this block if it doesn't contain points we looking for or they have already been read
			if !cur.entry.OverlapsTimeRange(minT, maxT) || cur.read() {
				cur.markRead(minT, maxT)
				continue
			}

			v := &tsdb.BooleanArray{}
			err := cur.r.ReadBooleanArrayBlockAt(&cur.entry, v)
			if err != nil {
				return nil, err
			}
			if c.col != nil {
				c.col.GetCounter(booleanBlocksDecodedCounter).Add(1)
				c.col.GetCounter(booleanBlocksSizeCounter).Add(int64(cur.entry.Size))
			}
			c.trbuf = cur.r.TombstoneRange(c.key, c.trbuf[:0])
			// Remove any tombstoned values
			excludeTombstonesBooleanArray(c.trbuf, v)

			// Remove values we already read
			v.Exclude(cur.readMin, cur.readMax)

			// If the block we decoded should have all of it's values included, mark it as read so we
			// don't use it again.
			if v.Len() > 0 {
				v.Include(minT, maxT)
				// Merge the remaining values with the existing
				v.Merge(values)
				*values = *v
			}
			cur.markRead(minT, maxT)
		}
	}

	first.markRead(minT, maxT)

	return values, err
}
796868
func (p *PostingsList) Count() uint64 {
	var n, e uint64
	if p.normBits1Hit != 0 {
		n = 1
		if p.except != nil && p.except.Contains(uint32(p.docNum1Hit)) {
			e = 1
		}
	} else if p.postings != nil {
		n = p.postings.GetCardinality()
		if p.except != nil {
			e = p.postings.AndCardinality(p.except)
		}
	}
	return n - e
}
869095
func (p *deviceFolderDownloadState) GetBlockCounts() map[string]int {
	p.mut.RLock()
	res := make(map[string]int, len(p.files))
	for name, state := range p.files {
		res[name] = len(state.blockIndexes)
	}
	p.mut.RUnlock()
	return res
}
1223598
func (db *DB) RetrieveHighestBlockHash() (string, error) {
	var blockHash string
	err := db.QueryRow(db.getHighestBlockHashSQL).Scan(&blockHash)
	return blockHash, err
}