// NewTree creates Tree and preallocates (if preallocate not zero) number of nodes that would be ready to fill with data.
328426
func NewTree(preallocate int) *Tree {
	tree := new(Tree)
	tree.root = tree.newnode()
	if preallocate == 0 {
		return tree
	}

	// Simplification, static preallocate max 6 bits
	if preallocate > 6 || preallocate < 0 {
		preallocate = 6
	}

	var key, mask uint32

	for inc := startbit; preallocate > 0; inc, preallocate = inc>>1, preallocate-1 {
		key = 0
		mask >>= 1
		mask |= startbit

		for {
			tree.insert32(key, mask, nil, false)
			key += inc
			if key == 0 { // magic bits collide
				break
			}
		}
	}

	return tree
}
788720
func NewThrow(Expr node.Node) *Throw {
	return &Throw{
		FreeFloating: nil,
		Expr:         Expr,
	}
}
141671
func (imf *ImmutableForest) newTree(prefix []byte) *RWTree {
	p := string(prefix)
	tree := NewRWTree(NewPrefixDB(imf.treeDB, p), imf.cacheSize)
	imf.treeCache.Add(p, tree)
	return tree
}
978314
func isTree(mtype reflect.Type) bool {
	switch mtype.Kind() {
	case reflect.Map:
		return true
	case reflect.Struct:
		return !isPrimitive(mtype)
	default:
		return false
	}
}
550554
func (h *Hasher) getTree() *tree {
	if h.bmt != nil {
		return h.bmt
	}
	t := h.pool.reserve()
	h.bmt = t
	return t
}
834251
func NewCachedTree(h hash.Hash, cachedNodeHeight uint64) *CachedTree {
	return &CachedTree{
		cachedNodeHeight: cachedNodeHeight,

		Tree: Tree{
			hash: h,

			cachedTree: true,
		},
	}
}
453835
func NewImmutableTree(db dbm.DB, cacheSize int) *ImmutableTree {
	if db == nil {
		// In-memory Tree.
		return &ImmutableTree{}
	}
	return &ImmutableTree{
		// NodeDB-backed Tree.
		ndb: newNodeDB(db, cacheSize),
	}
}
713154
func NewTreeBlobChannelWrapper(treeBlobChan <-chan TreeBlob, errorChan <-chan error) *TreeBlobChannelWrapper {
	return &TreeBlobChannelWrapper{tools.NewBaseChannelWrapper(errorChan), treeBlobChan}
}
86812
func NewType(t string) (*Type, error) {
	if strings.ContainsAny(t, " \t\n\r") {
		return nil, fmt.Errorf("node.NewType(%q) does not allow spaces", t)
	}
	if !strings.HasPrefix(t, "/") || strings.HasSuffix(t, "/") {
		return nil, fmt.Errorf("node.NewType(%q) should start with a '/' and do not end with '/'", t)
	}
	if t == "" {
		return nil, fmt.Errorf("node.NewType(%q) cannot create empty types", t)
	}
	nt := Type(t)
	return &nt, nil
}
315205
func NewTrie() *Trie {
	t := &Trie{
		Root: &Branch{
			Branches: make(map[byte]*Branch),
		},
	}
	return t
}
723260
func (n *NodeEvalableProvider) EvalTree() EvalNode {
	addr := n.Addr
	relAddr := addr.ProviderConfig

	return &EvalInitProvider{
		TypeName: relAddr.Type,
		Addr:     addr.ProviderConfig,
	}
}
1337190
func (tr *RTree) Load(mins, maxs [][]float64, items []interface{}) {
	if len(items) < tr.minEntries {
		for i := 0; i < len(items); i++ {
			tr.Insert(mins[i], maxs[i], items[i])
		}
		return
	}

	// prefill the items
	fitems := make([]*treeNode, len(items))
	for i := 0; i < len(items); i++ {
		item := &treeItem{min: mins[i], max: maxs[i], item: items[i]}
		fitems[i] = item.unsafeNode()
	}

	// following equations are defined in the paper describing OMT
	N := len(fitems)
	M := tr.maxEntries
	h := int(math.Ceil(math.Log(float64(N)) / math.Log(float64(M))))
	Nsubtree := int(math.Pow(float64(M), float64(h-1)))
	S := int(math.Ceil(math.Sqrt(float64(N) / float64(Nsubtree))))

	// sort by the initial axis
	axis := 0
	sortByAxis(fitems, axis)

	// build the root node. it's split differently from the subtrees.
	children := make([]*treeNode, 0, S)
	for i := 0; i < S; i++ {
		var part []*treeNode
		if i == S-1 {
			// last split
			part = fitems[len(fitems)/S*i:]
		} else {
			part = fitems[len(fitems)/S*i : len(fitems)/S*(i+1)]
		}
		children = append(children, tr.omt(part, h-1, axis+1))
	}

	node := tr.createNode(children)
	node.leaf = false
	node.height = h
	tr.calcBBox(node)

	if tr.data.count == 0 {
		// save as is if tree is empty
		tr.data = node
	} else if tr.data.height == node.height {
		// split root if trees have the same height
		tr.splitRoot(tr.data, node)
	} else {
		if tr.data.height < node.height {
			// swap trees if inserted one is bigger
			tr.data, node = node, tr.data
		}

		// insert the small tree into the large tree at appropriate level
		tr.insert(node, nil, tr.data.height-node.height-1, true)
	}
}
684034
func (t *Tree) First() (k generic.T, v generic.U) {
	if q := t.first; q != nil {
		q := &q.d[0]
		k, v = q.k, q.v
	}
	return
}
1286110
func (t *ImmutableTree) IterateRange(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool) {
	if t.root == nil {
		return false
	}
	return t.root.traverseInRange(t, start, end, ascending, false, 0, func(node *Node, _ uint8) bool {
		if node.height == 0 {
			return fn(node.key, node.value)
		}
		return false
	})
}
1096308
func NewTreeRootNode(t *Tree) noder.Noder {
	if t == nil {
		return &treeNoder{}
	}

	return &treeNoder{
		parent: t,
		name:   "",
		mode:   filemode.Dir,
		hash:   t.Hash,
	}
}
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)
}
1281206
func (n *NodeApplyableModuleVariable) EvalTree() EvalNode {
	// If we have no value, do nothing
	if n.Expr == nil {
		return &EvalNoop{}
	}

	// Otherwise, interpolate the value of this variable and set it
	// within the variables mapping.
	vals := make(map[string]cty.Value)

	_, call := n.Addr.Module.CallInstance()

	return &EvalSequence{
		Nodes: []EvalNode{
			&EvalOpFilter{
				Ops: []walkOperation{walkRefresh, walkPlan, walkApply,
					walkDestroy, walkValidate},
				Node: &EvalModuleCallArgument{
					Addr:   n.Addr.Variable,
					Config: n.Config,
					Expr:   n.Expr,
					Values: vals,

					IgnoreDiagnostics: false,
				},
			},

			&EvalSetModuleCallArguments{
				Module: call,
				Values: vals,
			},
		},
	}
}