// Creates a node for each capture also takse care of parent child relationship
760455
func (p *Pattern) CreateCaptureNodes(data string, pos int, d parser.DataSource,
	mo textmate.MatchObject, parent *parser.Node, capt textmate.Captures) {
	// each couple of match objects will be a range
	ranges := make([]text.Region, len(mo)/2)
	// maps indexes from child to parent, the default int value is 0 so
	// by default each child parent will be the parent node
	parentIndex := make([]int, len(ranges))
	parents := make([]*parser.Node, len(parentIndex))
	for i := range ranges {
		// converting each couple of match objects to region
		ranges[i] = text.Region{A: mo[i*2], B: mo[i*2+1]}
		// the first 2 elements of parents node should be parent so we
		// could append childs easier later
		if i < 2 {
			parents[i] = parent
			continue
		}
		// if each pervious ranges covers current range we will store it
		// in parentIndex variable, because the node with wider range
		// should be the parent
		for j := i - 1; j >= 0; j-- {
			if ranges[j].Covers(ranges[i]) {
				parentIndex[i] = j
				break
			}
		}
	}

	for _, v := range capt {
		i := v.Key
		// ???: when do we set a range to -1?
		if i >= len(parents) || ranges[i].A == -1 {
			continue
		}
		// creating a node for each capture
		child := &parser.Node{Name: v.Name, Range: ranges[i], P: d}
		parents[i] = child
		if i == 0 {
			parent.Append(child)
			continue
		}
		var n *parser.Node
		// searches for child node parent then appends it
		for n == nil {
			i = parentIndex[i]
			n = parents[i]
		}
		n.Append(child)
	}
}
944428
func (ncs *nodeCacheStandard) newChildForParentLocked(parent Node) (*nodeStandard, error) {
	nodeStandard, ok := parent.Unwrap().(*nodeStandard)
	if !ok {
		return nil, ParentNodeNotFoundError{data.BlockRef{}}
	}

	ref := nodeStandard.core.pathNode.Ref()
	entry, ok := ncs.nodes[ref]
	if !ok {
		return nil, ParentNodeNotFoundError{ref}
	}
	if nodeStandard.core != entry.core {
		return nil, ParentNodeNotFoundError{ref}
	}
	return nodeStandard, nil
}
40542
func (p *Pattern) CreateNode(data string, pos int, d parser.DataSource, mo textmate.MatchObject) (ret *parser.Node) {
	ret = &parser.Node{Name: p.Name, Range: text.Region{A: mo[0], B: mo[1]}, P: d}
	defer ret.UpdateRange()

	if !p.Match.Empty() {
		p.CreateCaptureNodes(data, pos, d, mo, ret, p.Captures)
	}
	if p.Begin.Empty() {
		return
	}
	if len(p.BeginCaptures) > 0 {
		p.CreateCaptureNodes(data, pos, d, mo, ret, p.BeginCaptures)
	} else {
		p.CreateCaptureNodes(data, pos, d, mo, ret, p.Captures)
	}

	if p.End.Empty() {
		return
	}
	var (
		found  = false
		i, end int
	)
	for i, end = ret.Range.B, len(data); i < len(data); {
		endmatch := p.End.Find(data, i)
		if endmatch == nil {
			if !found {
				// oops.. no end found at all, set it to the next line
				if e2 := strings.IndexRune(data[i:], '\n'); e2 != -1 {
					end = i + e2
				} else {
					end = len(data)
				}
				break
			}
			end = i
			break
		}
		end = endmatch[1]

		if len(p.cachedPatterns) > 0 {
			// Might be more recursive patterns to apply before the end is reached
			pattern2, match2 := p.FirstMatch(data, i)
			if match2 != nil && (match2[0] < endmatch[0] || (match2[0] == endmatch[0] && ret.Range.A == ret.Range.B)) {
				found = true
				r := pattern2.CreateNode(data, i, d, match2)
				ret.Append(r)
				i = r.Range.B
				continue
			}
		}
		if len(p.EndCaptures) > 0 {
			p.CreateCaptureNodes(data, i, d, endmatch, ret, p.EndCaptures)
		} else {
			p.CreateCaptureNodes(data, i, d, endmatch, ret, p.Captures)
		}
		break
	}
	ret.Range.B = end
	return
}
297337
func (b *Bucket) node(pgid pgid, parent *node) *node {
	_assert(b.nodes != nil, "nodes map expected")

	// Retrieve node if it's already been created.
	if n := b.nodes[pgid]; n != nil {
		return n
	}

	// Otherwise create a node and cache it.
	n := &node{bucket: b, parent: parent}
	if parent == nil {
		b.rootNode = n
	} else {
		parent.children = append(parent.children, n)
	}

	// Use the inline page if this is an inline bucket.
	var p = b.page
	if p == nil {
		p = b.tx.page(pgid)
	}

	// Read the page into the node and cache it.
	n.read(p)
	b.nodes[pgid] = n

	// Update statistics.
	b.tx.stats.NodeCount++

	return n
}
358177
func (t *EmbedNode) All() []Node {
	r := t.IncludeNode.All()
	for _, blk := range t.Blocks {
		r = append(r, blk)
	}
	return r
}
1010727
func (n *Node) createNodeEvals(nodeID string, nodeIndex uint64) ([]string, uint64, error) {
	// Snapshot the state
	snap, err := n.srv.fsm.State().Snapshot()
	if err != nil {
		return nil, 0, fmt.Errorf("failed to snapshot state: %v", err)
	}

	// Find all the allocations for this node
	ws := memdb.NewWatchSet()
	allocs, err := snap.AllocsByNode(ws, nodeID)
	if err != nil {
		return nil, 0, fmt.Errorf("failed to find allocs for '%s': %v", nodeID, err)
	}

	sysJobsIter, err := snap.JobsByScheduler(ws, "system")
	if err != nil {
		return nil, 0, fmt.Errorf("failed to find system jobs for '%s': %v", nodeID, err)
	}

	var sysJobs []*structs.Job
	for job := sysJobsIter.Next(); job != nil; job = sysJobsIter.Next() {
		sysJobs = append(sysJobs, job.(*structs.Job))
	}

	// Fast-path if nothing to do
	if len(allocs) == 0 && len(sysJobs) == 0 {
		return nil, 0, nil
	}

	// Create an eval for each JobID affected
	var evals []*structs.Evaluation
	var evalIDs []string
	jobIDs := make(map[string]struct{})

	for _, alloc := range allocs {
		// Deduplicate on JobID
		if _, ok := jobIDs[alloc.JobID]; ok {
			continue
		}
		jobIDs[alloc.JobID] = struct{}{}

		// Create a new eval
		eval := &structs.Evaluation{
			ID:              uuid.Generate(),
			Namespace:       alloc.Namespace,
			Priority:        alloc.Job.Priority,
			Type:            alloc.Job.Type,
			TriggeredBy:     structs.EvalTriggerNodeUpdate,
			JobID:           alloc.JobID,
			NodeID:          nodeID,
			NodeModifyIndex: nodeIndex,
			Status:          structs.EvalStatusPending,
		}
		evals = append(evals, eval)
		evalIDs = append(evalIDs, eval.ID)
	}

	// Create an evaluation for each system job.
	for _, job := range sysJobs {
		// Still dedup on JobID as the node may already have the system job.
		if _, ok := jobIDs[job.ID]; ok {
			continue
		}
		jobIDs[job.ID] = struct{}{}

		// Create a new eval
		eval := &structs.Evaluation{
			ID:              uuid.Generate(),
			Namespace:       job.Namespace,
			Priority:        job.Priority,
			Type:            job.Type,
			TriggeredBy:     structs.EvalTriggerNodeUpdate,
			JobID:           job.ID,
			NodeID:          nodeID,
			NodeModifyIndex: nodeIndex,
			Status:          structs.EvalStatusPending,
		}
		evals = append(evals, eval)
		evalIDs = append(evalIDs, eval.ID)
	}

	// Create the Raft transaction
	update := &structs.EvalUpdateRequest{
		Evals:        evals,
		WriteRequest: structs.WriteRequest{Region: n.srv.config.Region},
	}

	// Commit this evaluation via Raft
	// XXX: There is a risk of partial failure where the node update succeeds
	// but that the EvalUpdate does not.
	_, evalIndex, err := n.srv.raftApply(structs.EvalUpdateRequestType, update)
	if err != nil {
		return nil, 0, err
	}
	return evalIDs, evalIndex, nil
}
878897
func (n *NodeList) ParentIs(a xml.Name) bool {
	if len(n.nodes) == 0 {
		return false
	}
	return NameEquals(a, n.nodes[len(n.nodes)-1].Name)
}
601891
func (fs *KBFSOpsStandard) InvalidateNodeAndChildren(
	ctx context.Context, node Node) error {
	timeTrackerDone := fs.longOperationDebugDumper.Begin(ctx)
	defer timeTrackerDone()

	ops := fs.getOpsByNode(ctx, node)
	return ops.InvalidateNodeAndChildren(ctx, node)
}
922083
func (tc *TreeCache) SetCreateParentNodes(yes bool) *TreeCache {
	tc.createParentNodes = yes
	return tc
}
819754
func newNode(parent *node, entry Entry) *node {
	return &node{
		children: [2]*node{},
		entry:    entry,
		parent:   parent,
	}
}
57884
func (c *Commit) Parent(n int) (*Commit, error) {
	id, err := c.ParentID(n)
	if err != nil {
		return nil, err
	}
	parent, err := c.repo.getCommit(id)
	if err != nil {
		return nil, err
	}
	return parent, nil
}
264803
func FindParent(node *html.Node, matcher Matcher) (n *html.Node, ok bool) {
	for p := node.Parent; p != nil; p = p.Parent {
		if matcher(p) {
			return p, true
		}
	}
	return nil, false
}
215887
func getParentsNodes(nodes []*html.Node, stopm Matcher, stopNodes []*html.Node) []*html.Node {
	return mapNodes(nodes, func(i int, n *html.Node) (result []*html.Node) {
		for p := n.Parent; p != nil; p = p.Parent {
			sel := newSingleSelection(p, nil)
			if stopm != nil {
				if sel.IsMatcher(stopm) {
					break
				}
			} else if len(stopNodes) > 0 {
				if sel.IsNodes(stopNodes...) {
					break
				}
			}
			if p.Type == html.ElementNode {
				result = append(result, p)
			}
		}
		return
	})
}
1319647
func (ncs *nodeCacheStandard) AllNodeChildren(n Node) (nodes []Node) {
	ncs.lock.RLock()
	defer ncs.lock.RUnlock()
	nodes = make([]Node, 0, len(ncs.nodes))
	entryIDs := make(map[NodeID]bool)
	for _, entry := range ncs.nodes {
		var pathIDs []NodeID
		parent := entry.core.parent
		for parent != nil {
			// If the node's parent is what we're looking for (or on
			// the path to what we're looking for), include it in the
			// list.
			parentID := parent.GetID()
			if parentID == n.GetID() || entryIDs[parentID] {
				nodes = append(nodes, ncs.makeNodeStandardForEntryLocked(entry))
				for _, id := range pathIDs {
					entryIDs[id] = true
				}
				entryIDs[entry.core] = true
				break
			}

			// Otherwise, remember this parent and continue back
			// toward the root.
			pathIDs = append(pathIDs, parentID)
			ns, ok := parent.Unwrap().(*nodeStandard)
			if !ok {
				break
			}
			parent = ns.core.parent
		}
	}
	return nodes
}
319285
func gatherChildren(n node, children *[]common.Hash) {
	switch n := n.(type) {
	case *rawShortNode:
		gatherChildren(n.Val, children)

	case rawFullNode:
		for i := 0; i < 16; i++ {
			gatherChildren(n[i], children)
		}
	case hashNode:
		*children = append(*children, common.BytesToHash(n))

	case valueNode, nil:

	default:
		panic(fmt.Sprintf("unknown node type: %T", n))
	}
}
813994
func (s *Selection) ParentsUntilNodes(nodes ...*html.Node) *Selection {
	return pushStack(s, getParentsNodes(s.Nodes, nil, nodes))
}
750008
func (n *XMLNode) AddChild(child *XMLNode) {
	child.parent = n
	if _, ok := n.Children[child.Name.Local]; !ok {
		n.Children[child.Name.Local] = []*XMLNode{}
	}
	n.Children[child.Name.Local] = append(n.Children[child.Name.Local], child)
}