// GetRangeWithProof gets key/value pairs within the specified range and limit.
426297
func (t *ImmutableTree) GetRangeWithProof(startKey []byte, endKey []byte, limit int) (keys, values [][]byte, proof *RangeProof, err error) {
	proof, keys, values, err = t.getRangeProof(startKey, endKey, limit)
	return
}
367595
func CheckProof(m libkb.MetaContext, pvlS string, service keybase1.ProofType, info ProofInfo) libkb.ProofError {
	m1 := newMetaContext(m, info.stubDNS)
	perr := checkProofInner(m1, pvlS, service, info)
	if perr != nil {
		debug(m1, "CheckProof failed: %v", perr)
	}
	if perr != nil && perr.GetProofStatus() == keybase1.ProofStatus_INVALID_PVL {
		return libkb.NewProofError(keybase1.ProofStatus_INVALID_PVL,
			"Invalid proof verification instructions! Let us know at https://github.com/keybase/keybase-issues/new")
	}
	return perr
}
781234
func GetDiffRange(repoPath, beforeCommitID, afterCommitID string, maxLines, maxLineCharacteres, maxFiles int) (*Diff, error) {
	repo, err := OpenRepository(repoPath)
	if err != nil {
		return nil, err
	}

	commit, err := repo.GetCommit(afterCommitID)
	if err != nil {
		return nil, err
	}

	cmd := NewCommand()
	if len(beforeCommitID) == 0 {
		// First commit of repository
		if commit.ParentCount() == 0 {
			cmd.AddArguments("show", "--full-index", afterCommitID)
		} else {
			c, _ := commit.Parent(0)
			cmd.AddArguments("diff", "--full-index", "-M", c.ID.String(), afterCommitID)
		}
	} else {
		cmd.AddArguments("diff", "--full-index", "-M", beforeCommitID, afterCommitID)
	}

	stdout, w := io.Pipe()
	done := make(chan error)
	var diff *Diff
	go func() {
		diff = ParsePatch(done, maxLines, maxLineCharacteres, maxFiles, stdout)
	}()

	stderr := new(bytes.Buffer)
	err = cmd.RunInDirTimeoutPipeline(2*time.Minute, repoPath, w, stderr)
	w.Close() // Close writer to exit parsing goroutine
	if err != nil {
		return nil, concatenateError(err, stderr.String())
	}

	return diff, <-done
}
703914
func getStateByRangeAndDecrypt(stub shim.ChaincodeStubInterface, ent entities.Encrypter, startKey, endKey string) ([]byte, error) {
	// we call get state by range to go through the entire range
	iterator, err := stub.GetStateByRange(startKey, endKey)
	if err != nil {
		return nil, err
	}
	defer iterator.Close()

	// we decrypt each entry - the assumption is that they have all been encrypted with the same key
	keyvalueset := []keyValuePair{}
	for iterator.HasNext() {
		el, err := iterator.Next()
		if err != nil {
			return nil, err
		}

		v, err := ent.Decrypt(el.Value)
		if err != nil {
			return nil, err
		}

		keyvalueset = append(keyvalueset, keyValuePair{el.Key, string(v)})
	}

	bytes, err := json.Marshal(keyvalueset)
	if err != nil {
		return nil, err
	}

	return bytes, nil
}
157962
func (j *blockJournal) getDeferredGCRange() (
	len int, earliest, latest journalOrdinal, err error) {
	earliest, err = j.deferredGC.readEarliestOrdinal()
	if ioutil.IsNotExist(err) {
		return 0, 0, 0, nil
	} else if err != nil {
		return 0, 0, 0, err
	}

	latest, err = j.deferredGC.readLatestOrdinal()
	if ioutil.IsNotExist(err) {
		return 0, 0, 0, nil
	} else if err != nil {
		return 0, 0, 0, err
	}

	return int(latest - earliest + 1), earliest, latest, nil
}
784215
func (h *receivedPacketHistory) GetAckRanges() []wire.AckRange {
	if h.ranges.Len() == 0 {
		return nil
	}

	ackRanges := make([]wire.AckRange, h.ranges.Len())
	i := 0
	for el := h.ranges.Back(); el != nil; el = el.Prev() {
		ackRanges[i] = wire.AckRange{Smallest: el.Value.Start, Largest: el.Value.End}
		i++
	}
	return ackRanges
}
136551
func (ss *SortedSlice) RangeLessThan(e Sortable) (int, int) {
	i := ss.searchLessThan(&e, 0, len(ss.s)-1)
	return i, len(ss.s) - 1
}
257022
func (j journalMDOps) getRange(
	ctx context.Context, id tlf.ID, bid kbfsmd.BranchID, mStatus kbfsmd.MergeStatus,
	start, stop kbfsmd.Revision, lockBeforeGet *keybase1.LockID,
	delegateFn func(ctx context.Context, id tlf.ID,
		start, stop kbfsmd.Revision, lockBeforeGet *keybase1.LockID) (
		[]ImmutableRootMetadata, error)) (
	[]ImmutableRootMetadata, error) {
	// Grab the range from the journal first.
	jirmds, err := j.getRangeFromJournal(ctx, id, bid, mStatus, start, stop)
	switch errors.Cause(err).(type) {
	case nil:
		break
	case errTLFJournalDisabled:
		// Fall back to the server.
		return delegateFn(ctx, id, start, stop, lockBeforeGet)
	default:
		return nil, err
	}

	if len(jirmds) != 0 && lockBeforeGet != nil {
		// We need to grab locks, so we have to hit the server. But it's
		// dangerous to bypass journal if we have revisions in this range from
		// the journal. For now, we just return error here.
		// NOTE: In the future if we ever need locking in places other than
		// SyncFromServer, we can use the naked Lock RPC to grab the lock if
		// everything we need is in the journal already.
		return nil, errors.New(
			"cannot lock when getting revisions that exist in journal")
	}

	// If it's empty, fall back to the server if this isn't a local
	// squash branch.  TODO: we should be able to avoid server access
	// for regular conflict branches when the journal is enabled, as
	// well, once we're confident that all old server-based branches
	// have been resolved.
	if len(jirmds) == 0 {
		if bid == kbfsmd.PendingLocalSquashBranchID {
			return jirmds, nil
		}
		return delegateFn(ctx, id, start, stop, lockBeforeGet)
	}

	// If the first revision from the journal is the first revision we
	// asked for (or this is a local squash that doesn't require
	// server access), then just return the range from the journal.
	// TODO: we should be able to avoid server access for regular
	// conflict branches, as well.
	if jirmds[0].Revision() == start || bid == kbfsmd.PendingLocalSquashBranchID {
		return jirmds, nil
	}

	// Otherwise, fetch the rest from the server and prepend them.
	serverStop := jirmds[0].Revision() - 1
	irmds, err := delegateFn(ctx, id, start, serverStop, lockBeforeGet)
	if err != nil {
		return nil, err
	}

	if len(irmds) == 0 {
		return jirmds, nil
	}

	lastRev := irmds[len(irmds)-1].Revision()
	if lastRev != serverStop {
		return nil, fmt.Errorf(
			"Expected last server rev %d, got %d",
			serverStop, lastRev)
	}

	return append(irmds, jirmds...), nil
}
1216975
func GetTableHandleKeyRange(tableID int64) (startKey, endKey []byte) {
	startKey = EncodeRowKeyWithHandle(tableID, math.MinInt64)
	endKey = EncodeRowKeyWithHandle(tableID, math.MaxInt64)
	return
}
916675
func (d *indirectIndex) TombstoneRange(key []byte, buf []TimeRange) []TimeRange {
	d.mu.RLock()
	rs := d.prefixTombstones.Search(key, buf[:0])
	iter := d.ro.Iterator()
	exact, _ := iter.Seek(key, &d.b)
	if exact {
		rs = append(rs, d.tombstones[iter.Offset()]...)
	}
	d.mu.RUnlock()
	return rs
}
1041466
func (conf *Config) GetPartitionRange(partNum, totalParts int) (start int, end int) {
	perPart := conf.InitialBuckets / totalParts
	leftOver := conf.InitialBuckets % totalParts
	start = partNum * perPart
	if leftOver > 0 {
		if partNum == 0 {
			end++
		} else if partNum < leftOver {
			start += partNum
			end++
		} else {
			start += leftOver
		}
	}
	end += start + perPart
	if partNum == totalParts-1 {
		end = conf.InitialBuckets
	}
	return
}
1279343
func (md *MDServerRemote) GetRange(ctx context.Context, id tlf.ID,
	bid kbfsmd.BranchID, mStatus kbfsmd.MergeStatus,
	start, stop kbfsmd.Revision, lockBeforeGet *keybase1.LockID) (
	rmdses []*RootMetadataSigned, err error) {
	ctx = rpc.WithFireNow(ctx)
	md.log.LazyTrace(ctx, "MDServer: GetRange %s %s %s %d-%d", id, bid, mStatus, start, stop)
	defer func() {
		md.deferLog.LazyTrace(ctx, "MDServer: GetRange %s %s %s %d-%d done (err=%v)", id, bid, mStatus, start, stop, err)
	}()

	arg := keybase1.GetMetadataArg{
		FolderID:      id.String(),
		BranchID:      bid.String(),
		Unmerged:      mStatus == kbfsmd.Unmerged,
		StartRevision: start.Number(),
		StopRevision:  stop.Number(),
		LockBeforeGet: lockBeforeGet,
	}

	_, rmds, err := md.get(ctx, arg)
	return rmds, err
}
1083856
func (l *Limiter) GetForwardedForIndexFromBehind() int {
	l.RLock()
	defer l.RUnlock()
	return l.forwardedForIndex
}
208251
func (h *histogram) getRandomBoundIdx() int {
	cnt := h.Buckets[len(h.Buckets)-1].Count
	randCnt := randInt64(0, cnt)
	for i, bkt := range h.Buckets {
		if bkt.Count >= randCnt {
			if bkt.Count-bkt.Repeat > randCnt {
				return 2 * i
			}
			return 2*i + 1
		}
	}
	return 0
}
461014
func validateIDRanges(rng []securityapi.IDRange, fldPath *field.Path) field.ErrorList {
	allErrs := field.ErrorList{}

	for i, r := range rng {
		// if 0 <= Min <= Max then we do not need to validate max.  It is always greater than or
		// equal to 0 and Min.
		minPath := fldPath.Child("ranges").Index(i).Child("min")
		maxPath := fldPath.Child("ranges").Index(i).Child("max")

		if r.Min < 0 {
			allErrs = append(allErrs, field.Invalid(minPath, r.Min, "min cannot be negative"))
		}
		if r.Max < 0 {
			allErrs = append(allErrs, field.Invalid(maxPath, r.Max, "max cannot be negative"))
		}
		if r.Min > r.Max {
			allErrs = append(allErrs, field.Invalid(minPath, r, "min cannot be greater than max"))
		}
	}

	return allErrs
}
220355
func (proof *RangeProof) VerifyItem(key, value []byte) error {
	leaves := proof.Leaves
	if proof == nil {
		return cmn.ErrorWrap(ErrInvalidProof, "proof is nil")
	}
	if !proof.rootVerified {
		return cmn.NewError("must call Verify(root) first.")
	}
	i := sort.Search(len(leaves), func(i int) bool {
		return bytes.Compare(key, leaves[i].Key) <= 0
	})
	if i >= len(leaves) || !bytes.Equal(leaves[i].Key, key) {
		return cmn.ErrorWrap(ErrInvalidProof, "leaf key not found in proof")
	}
	valueHash := tmhash.Sum(value)
	if !bytes.Equal(leaves[i].ValueHash, valueHash) {
		return cmn.ErrorWrap(ErrInvalidProof, "leaf value hash not same")
	}
	return nil
}
102735
func ParseShardingSpec(spec string) ([]*topodatapb.KeyRange, error) {
	parts := strings.Split(spec, "-")
	if len(parts) == 1 {
		return nil, fmt.Errorf("malformed spec: doesn't define a range: %q", spec)
	}
	old := parts[0]
	ranges := make([]*topodatapb.KeyRange, len(parts)-1)

	for i, p := range parts[1:] {
		if p == "" && i != (len(parts)-2) {
			return nil, fmt.Errorf("malformed spec: MinKey/MaxKey cannot be in the middle of the spec: %q", spec)
		}
		if p != "" && p <= old {
			return nil, fmt.Errorf("malformed spec: shard limits should be in order: %q", spec)
		}
		s, err := hex.DecodeString(old)
		if err != nil {
			return nil, err
		}
		if len(s) == 0 {
			s = nil
		}
		e, err := hex.DecodeString(p)
		if err != nil {
			return nil, err
		}
		if len(e) == 0 {
			e = nil
		}
		ranges[i] = &topodatapb.KeyRange{Start: s, End: e}
		old = p
	}
	return ranges, nil
}