<commit_before>// +build !goji_router_simple

package goji

import (
	"net/http"
	"sort"
	"strings"

	"goji.io/internal"
	"golang.org/x/net/context"
)

type router struct {
	routes   []route
	methods  map[string]*trieNode
	wildcard trieNode
}

type route struct {
	Pattern
	Handler
}

type child struct {
	prefix string
	node   *trieNode
}

type trieNode struct {
	routes   []int
	children []child
}

func (rt *router) add(p Pattern, h Handler) {
	i := len(rt.routes)
	rt.routes = append(rt.routes, route{p, h})

	var prefix string
	if pp, ok := p.(pathPrefix); ok {
		prefix = pp.PathPrefix()
	}

	var methods map[string]struct{}
	if hm, ok := p.(httpMethods); ok {
		methods = hm.HTTPMethods()
	}
	if methods == nil {
		rt.wildcard.add(prefix, i)
		for _, sub := range rt.methods {
			sub.add(prefix, i)
		}
	} else {
		if rt.methods == nil {
			rt.methods = make(map[string]*trieNode)
		}

		for method := range methods {
			if _, ok := rt.methods[method]; !ok {
				rt.methods[method] = rt.wildcard.clone()
			}
			rt.methods[method].add(prefix, i)
		}
	}
}

func (rt *router) route(ctx context.Context, r *http.Request) context.Context {
	tn := &rt.wildcard
	if tn2, ok := rt.methods[r.Method]; ok {
		tn = tn2
	}

	path := ctx.Value(internal.Path).(string)
	for {
		i := sort.Search(len(tn.children), func(i int) bool {
			p := tn.children[i].prefix
			return path < p || strings.HasPrefix(path, p)
		})
		if i == len(tn.children) || !strings.HasPrefix(path, tn.children[i].prefix) {<commit_msg>goji: work less when searching for trie children<commit_after>// +build !goji_router_simple

package goji

import (
	"net/http"
	"sort"
	"strings"

	"goji.io/internal"
	"golang.org/x/net/context"
)

type router struct {
	routes   []route
	methods  map[string]*trieNode
	wildcard trieNode
}

type route struct {
	Pattern
	Handler
}

type child struct {
	prefix string
	node   *trieNode
}

type trieNode struct {
	routes   []int
	children []child
}

func (rt *router) add(p Pattern, h Handler) {
	i := len(rt.routes)
	rt.routes = append(rt.routes, route{p, h})

	var prefix string
	if pp, ok := p.(pathPrefix); ok {
		prefix = pp.PathPrefix()
	}

	var methods map[string]struct{}
	if hm, ok := p.(httpMethods); ok {
		methods = hm.HTTPMethods()
	}
	if methods == nil {
		rt.wildcard.add(prefix, i)
		for _, sub := range rt.methods {
			sub.add(prefix, i)
		}
	} else {
		if rt.methods == nil {
			rt.methods = make(map[string]*trieNode)
		}

		for method := range methods {
			if _, ok := rt.methods[method]; !ok {
				rt.methods[method] = rt.wildcard.clone()
			}
			rt.methods[method].add(prefix, i)
		}
	}
}

func (rt *router) route(ctx context.Context, r *http.Request) context.Context {
	tn := &rt.wildcard
	if tn2, ok := rt.methods[r.Method]; ok {
		tn = tn2
	}

	path := ctx.Value(internal.Path).(string)
	for path != "" {
		i := sort.Search(len(tn.children), func(i int) bool {
			return path[0] <= tn.children[i].prefix[0]
		})
		if i == len(tn.children) || !strings.HasPrefix(path, tn.children[i].prefix) {
{'fraction_non_alphanumeric': 0.15787728026533995, 'fraction_numerical': 0.001990049751243781, 'mean_word_length': 3.3773584905660377, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3340676', 'n_tokens_mistral': 1237, 'n_tokens_neox': 1164, 'n_words': 280}