// search performs a binary search for UnixNano() v in a
// and returns the position, i, where v would be inserted.
// An additional check of a[i].UnixNano() == v is necessary
// to determine if the value v exists.
325713
func (a Values) search(v int64) int {
	// Define: f(x) → a[x].UnixNano() < v
	// Define: f(-1) == true, f(n) == false
	// Invariant: f(lo-1) == true, f(hi) == false
	lo := 0
	hi := len(a)
	for lo < hi {
		mid := int(uint(lo+hi) >> 1)
		if a[mid].UnixNano() < v {
			lo = mid + 1 // preserves f(lo-1) == true
		} else {
			hi = mid // preserves f(hi) == false
		}
	}

	// lo == hi
	return lo
}
1352353
func (i *Index) Search(query string, opts ...interface{}) (res QueryRes, err error) {
	body := searchReq{Params: transport.URLEncode(newSearchParams(query, opts...))}
	path := i.path("/query")
	err = i.transport.Request(&res, http.MethodPost, path, body, call.Read, opts...)
	return
}
365630
func (treeNode *TreeNode) Search(patternNode PatternNode) []*TreeNode {
	results := []*TreeNode{}

	// Current node
	if treeNode.compare(patternNode) {
		results = append(results, treeNode)
	}

	// Current node's children
	for _, child := range treeNode.Children {
		for _, subResult := range child.Search(patternNode) {
			results = append(results, subResult)
		}
	}

	return results
}
645788
func (t *Tree) Search(qname string) (*Elem, bool) {
	if t.Root == nil {
		return nil, false
	}
	n, res := t.Root.search(qname)
	if n == nil {
		return nil, res
	}
	return n.Elem, res
}
225287
func (r *Regex) Find(data string, pos int) MatchObject {
	// if the new position is less than last search start position
	// ???: why we can't always do r.lastFound = pos?
	if pos < r.lastIndex {
		r.lastFound = pos
	}
	r.lastIndex = pos
	for ; r.lastFound < len(data); r.lastFound++ {
		ret := r.re.FindStringSubmatchIndex(data[r.lastFound:])
		if ret == nil {
			return nil
		}
		if (ret[0] + r.lastFound) >= pos {
			mo := MatchObject(ret)
			mo.fix(r.lastFound)
			return mo
		}
		if ret[0] != 0 {
			// ???: why shouldn't this be r.lastFound += ret[0]
			r.lastFound += ret[0] - 1
		}
	}
	return nil
}
1164675
func (si *SolrInterface) Search(q *Query) *Search {
	return NewSearch(si.conn, q)
}
105548
func (m Map) Find(pos, end int) (Location, bool) {
	key := Location{
		Pos: pos,
		End: end,
	}
	if loc, ok := m[key]; ok {
		return loc, true
	}
	return key, false
}
189729
func find(data []byte, start int, target rune) (index int) {
	index = bytes.IndexRune(data[start:], target)
	if index != -1 {
		return index + start
	}
	return index
}
338781
func (m *MultiSearchRequestBuilder) Search(interval tsdb.Interval) *SearchRequestBuilder {
	b := NewSearchRequestBuilder(m.version, interval)
	m.requestBuilders = append(m.requestBuilders, b)
	return b
}
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
}
1368943
func (r *TemplateFileSearcher) Search(precise bool, terms ...string) (ComponentMatches, []error) {
	matches := ComponentMatches{}
	var errs []error
	for _, term := range terms {
		if term == "__templatefile_fail" {
			errs = append(errs, fmt.Errorf("unable to find the specified template file: %s", term))
			continue
		}

		var isSingleItemImplied bool
		obj, err := r.Builder.
			WithScheme(scheme.Scheme, scheme.Scheme.PrioritizedVersionsAllGroups()...).
			NamespaceParam(r.Namespace).RequireNamespace().
			FilenameParam(false, &resource.FilenameOptions{Recursive: false, Filenames: terms}).
			Do().
			IntoSingleItemImplied(&isSingleItemImplied).
			Object()

		if err != nil {
			switch {
			case strings.Contains(err.Error(), "does not exist") && strings.Contains(err.Error(), "the path"):
				continue
			case strings.Contains(err.Error(), "not a directory") && strings.Contains(err.Error(), "the path"):
				continue
			default:
				if syntaxErr, ok := err.(*json.SyntaxError); ok {
					err = fmt.Errorf("at offset %d: %v", syntaxErr.Offset, err)
				}
				errs = append(errs, fmt.Errorf("unable to load template file %q: %v", term, err))
				continue
			}
		}

		if list, isList := obj.(*corev1.List); isList && !isSingleItemImplied {
			if len(list.Items) == 1 {
				obj = list.Items[0].Object
				isSingleItemImplied = true
			}
		}

		if !isSingleItemImplied {
			errs = append(errs, fmt.Errorf("there is more than one object in %q", term))
			continue
		}

		template, ok := obj.(*templatev1.Template)
		if !ok {
			errs = append(errs, fmt.Errorf("object in %q is not a template", term))
			continue
		}

		matches = append(matches, &ComponentMatch{
			Value:       term,
			Argument:    fmt.Sprintf("--file=%q", template.Name),
			Name:        template.Name,
			Description: fmt.Sprintf("Template file %s", term),
			Score:       0,
			Template:    template,
		})
	}

	return matches, errs
}
51501
func (tr *RTree) Search(min, max []float64, iter func(item interface{}) bool) bool {
	bbox := &treeNode{min: min, max: max}
	if !tr.data.intersects(bbox) {
		return true
	}
	return tr.search(tr.data, bbox, iter)
}
1354410
func (l *Conn) Search(searchRequest *SearchRequest) (*SearchResult, error) {
	packet := ber.Encode(ber.ClassUniversal, ber.TypeConstructed, ber.TagSequence, nil, "LDAP Request")
	packet.AppendChild(ber.NewInteger(ber.ClassUniversal, ber.TypePrimitive, ber.TagInteger, l.nextMessageID(), "MessageID"))
	// encode search request
	encodedSearchRequest, err := searchRequest.encode()
	if err != nil {
		return nil, err
	}
	packet.AppendChild(encodedSearchRequest)
	// encode search controls
	if searchRequest.Controls != nil {
		packet.AppendChild(encodeControls(searchRequest.Controls))
	}

	l.Debug.PrintPacket(packet)

	msgCtx, err := l.sendMessage(packet)
	if err != nil {
		return nil, err
	}
	defer l.finishMessage(msgCtx)

	result := &SearchResult{
		Entries:   make([]*Entry, 0),
		Referrals: make([]string, 0),
		Controls:  make([]Control, 0)}

	foundSearchResultDone := false
	for !foundSearchResultDone {
		l.Debug.Printf("%d: waiting for response", msgCtx.id)
		packetResponse, ok := <-msgCtx.responses
		if !ok {
			return nil, NewError(ErrorNetwork, errors.New("ldap: response channel closed"))
		}
		packet, err = packetResponse.ReadPacket()
		l.Debug.Printf("%d: got response %p", msgCtx.id, packet)
		if err != nil {
			return nil, err
		}

		if l.Debug {
			if err := addLDAPDescriptions(packet); err != nil {
				return nil, err
			}
			ber.PrintPacket(packet)
		}

		switch packet.Children[1].Tag {
		case 4:
			entry := new(Entry)
			entry.DN = packet.Children[1].Children[0].Value.(string)
			for _, child := range packet.Children[1].Children[1].Children {
				attr := new(EntryAttribute)
				attr.Name = child.Children[0].Value.(string)
				for _, value := range child.Children[1].Children {
					attr.Values = append(attr.Values, value.Value.(string))
					attr.ByteValues = append(attr.ByteValues, value.ByteValue)
				}
				entry.Attributes = append(entry.Attributes, attr)
			}
			result.Entries = append(result.Entries, entry)
		case 5:
			resultCode, resultDescription := getLDAPResultCode(packet)
			if resultCode != 0 {
				return result, NewError(resultCode, errors.New(resultDescription))
			}
			if len(packet.Children) == 3 {
				for _, child := range packet.Children[2].Children {
					result.Controls = append(result.Controls, DecodeControl(child))
				}
			}
			foundSearchResultDone = true
		case 19:
			result.Referrals = append(result.Referrals, packet.Children[1].Children[0].Value.(string))
		}
	}
	l.Debug.Printf("%d: returning", msgCtx.id)
	return result, nil
}
343078
func (m *PolicyDB) Search(tags *policy.TagStore) (int, interface{}) {

	count := make([]int, m.numberOfPolicies+1)

	skip := make([]bool, m.numberOfPolicies+1)

	// Disable all policies that fail the not key exists
	copiedTags := tags.GetSlice()
	var k, v string

	for _, t := range copiedTags {
		if err := m.tagSplit(t, &k, &v); err != nil {
			continue
		}
		for _, policy := range m.notStarTable[k] {
			skip[policy.index] = true
		}
	}

	// Go through the list of tags
	for _, t := range copiedTags {

		// Search for matches of t (tag id)
		if index, action := searchInMapTable(m.equalIDMapTable[t], count, skip); index >= 0 {
			return index, action
		}

		if err := m.tagSplit(t, &k, &v); err != nil {
			continue
		}

		// Search for matches of k=v
		if index, action := searchInMapTable(m.equalMapTable[k][v], count, skip); index >= 0 {
			return index, action
		}

		// Search for matches in prefixes
		for _, i := range m.equalPrefixes[k] {
			if i <= len(v) {
				if index, action := searchInMapTable(m.equalMapTable[k][v[:i]], count, skip); index >= 0 {
					return index, action
				}
			}
		}

		// Parse all of the policies that have a key that matches the incoming tag key
		// and a not equal operator and that has a not match rule
		for value, policies := range m.notEqualMapTable[k] {
			if v == value {
				continue
			}

			if index, action := searchInMapTable(policies, count, skip); index >= 0 {
				return index, action
			}
		}
	}

	if m.defaultNotExistsPolicy != nil && !skip[m.defaultNotExistsPolicy.index] {
		return m.defaultNotExistsPolicy.index, m.defaultNotExistsPolicy.actions
	}

	return -1, nil
}
909364
func (t *Trie) search(key []byte) *node {
	n := &t.root
	for n.internal != nil {
		n = &n.internal.child[n.internal.direction(key)]
	}
	return n
}
268524
func (t list) Search(x uint16) *Transition {
	low, high := 0, len(t)-1
	for low <= high {
		i := (low + high) / 2
		if t[i].hash > x {
			high = i - 1
		} else if t[i].hash < x {
			low = i + 1
		} else {
			return t[i]
		}
	}

	return nil
}
1338374
func (a *BooleanArray) search(v int64) int {
	// Define: f(x) → a.Timestamps[x] < v
	// Define: f(-1) == true, f(n) == false
	// Invariant: f(lo-1) == true, f(hi) == false
	lo := 0
	hi := a.Len()
	for lo < hi {
		mid := int(uint(lo+hi) >> 1)
		if a.Timestamps[mid] < v {
			lo = mid + 1 // preserves f(lo-1) == true
		} else {
			hi = mid // preserves f(hi) == false
		}
	}

	// lo == hi
	return lo
}