// Recursively consider v and each of its children, updating pointer information
435368
func (pm *pointerMap) getAllAndReusedPointers(v reflect.Value) {
	if v.Kind() == reflect.Invalid {
		return
	}
	if isPointerValue(v) && v.Pointer() != 0 { // pointer is 0 for unexported fields
		reused := pm.addPointer(v.Pointer())
		if reused {
			// No use descending inside this value, since it have been seen before and all its descendants
			// have been considered
			return
		}
	}

	// Now descend into any children of this value
	switch v.Kind() {
	case reflect.Slice, reflect.Array:
		numEntries := v.Len()
		for i := 0; i < numEntries; i++ {
			pm.getAllAndReusedPointers(v.Index(i))
		}

	case reflect.Interface:
		pm.getAllAndReusedPointers(v.Elem())

	case reflect.Ptr:
		pm.getAllAndReusedPointers(v.Elem())

	case reflect.Map:
		for _, key := range v.MapKeys() {
			pm.getAllAndReusedPointers(v.MapIndex(key))
		}

	case reflect.Struct:
		numFields := v.NumField()
		for i := 0; i < numFields; i++ {
			pm.getAllAndReusedPointers(v.Field(i))
		}
	}
}
302634
func (s *ShapeIndex) updateEdges(pcell *PaddedCell, edges []*clippedEdge, t *tracker, disjointFromIndex bool) {
	// This function is recursive with a maximum recursion depth of 30 (maxLevel).

	// Incremental updates are handled as follows. All edges being added or
	// removed are combined together in edges, and all shapes with interiors
	// are tracked using tracker. We subdivide recursively as usual until we
	// encounter an existing index cell. At this point we absorb the index
	// cell as follows:
	//
	//   - Edges and shapes that are being removed are deleted from edges and
	//     tracker.
	//   - All remaining edges and shapes from the index cell are added to
	//     edges and tracker.
	//   - Continue subdividing recursively, creating new index cells as needed.
	//   - When the recursion gets back to the cell that was absorbed, we
	//     restore edges and tracker to their previous state.
	//
	// Note that the only reason that we include removed shapes in the recursive
	// subdivision process is so that we can find all of the index cells that
	// contain those shapes efficiently, without maintaining an explicit list of
	// index cells for each shape (which would be expensive in terms of memory).
	indexCellAbsorbed := false
	if !disjointFromIndex {
		// There may be existing index cells contained inside pcell. If we
		// encounter such a cell, we need to combine the edges being updated with
		// the existing cell contents by absorbing the cell.
		iter := s.Iterator()
		r := iter.LocateCellID(pcell.id)
		if r == Disjoint {
			disjointFromIndex = true
		} else if r == Indexed {
			// Absorb the index cell by transferring its contents to edges and
			// deleting it. We also start tracking the interior of any new shapes.
			s.absorbIndexCell(pcell, iter, edges, t)
			indexCellAbsorbed = true
			disjointFromIndex = true
		} else {
			// DCHECK_EQ(SUBDIVIDED, r)
		}
	}

	// If there are existing index cells below us, then we need to keep
	// subdividing so that we can merge with those cells. Otherwise,
	// makeIndexCell checks if the number of edges is small enough, and creates
	// an index cell if possible (returning true when it does so).
	if !disjointFromIndex || !s.makeIndexCell(pcell, edges, t) {
		// TODO(roberts): If it turns out to have memory problems when there
		// are 10M+ edges in the index, look into pre-allocating space so we
		// are not always appending.
		childEdges := [2][2][]*clippedEdge{} // [i][j]

		// Compute the middle of the padded cell, defined as the rectangle in
		// (u,v)-space that belongs to all four (padded) children. By comparing
		// against the four boundaries of middle we can determine which children
		// each edge needs to be propagated to.
		middle := pcell.Middle()

		// Build up a vector edges to be passed to each child cell. The (i,j)
		// directions are left (i=0), right (i=1), lower (j=0), and upper (j=1).
		// Note that the vast majority of edges are propagated to a single child.
		for _, edge := range edges {
			if edge.bound.X.Hi <= middle.X.Lo {
				// Edge is entirely contained in the two left children.
				a, b := s.clipVAxis(edge, middle.Y)
				if a != nil {
					childEdges[0][0] = append(childEdges[0][0], a)
				}
				if b != nil {
					childEdges[0][1] = append(childEdges[0][1], b)
				}
			} else if edge.bound.X.Lo >= middle.X.Hi {
				// Edge is entirely contained in the two right children.
				a, b := s.clipVAxis(edge, middle.Y)
				if a != nil {
					childEdges[1][0] = append(childEdges[1][0], a)
				}
				if b != nil {
					childEdges[1][1] = append(childEdges[1][1], b)
				}
			} else if edge.bound.Y.Hi <= middle.Y.Lo {
				// Edge is entirely contained in the two lower children.
				if a := s.clipUBound(edge, 1, middle.X.Hi); a != nil {
					childEdges[0][0] = append(childEdges[0][0], a)
				}
				if b := s.clipUBound(edge, 0, middle.X.Lo); b != nil {
					childEdges[1][0] = append(childEdges[1][0], b)
				}
			} else if edge.bound.Y.Lo >= middle.Y.Hi {
				// Edge is entirely contained in the two upper children.
				if a := s.clipUBound(edge, 1, middle.X.Hi); a != nil {
					childEdges[0][1] = append(childEdges[0][1], a)
				}
				if b := s.clipUBound(edge, 0, middle.X.Lo); b != nil {
					childEdges[1][1] = append(childEdges[1][1], b)
				}
			} else {
				// The edge bound spans all four children. The edge
				// itself intersects either three or four padded children.
				left := s.clipUBound(edge, 1, middle.X.Hi)
				a, b := s.clipVAxis(left, middle.Y)
				if a != nil {
					childEdges[0][0] = append(childEdges[0][0], a)
				}
				if b != nil {
					childEdges[0][1] = append(childEdges[0][1], b)
				}
				right := s.clipUBound(edge, 0, middle.X.Lo)
				a, b = s.clipVAxis(right, middle.Y)
				if a != nil {
					childEdges[1][0] = append(childEdges[1][0], a)
				}
				if b != nil {
					childEdges[1][1] = append(childEdges[1][1], b)
				}
			}
		}

		// Now recursively update the edges in each child. We call the children in
		// increasing order of CellID so that when the index is first constructed,
		// all insertions into cellMap are at the end (which is much faster).
		for pos := 0; pos < 4; pos++ {
			i, j := pcell.ChildIJ(pos)
			if len(childEdges[i][j]) > 0 || len(t.shapeIDs) > 0 {
				s.updateEdges(PaddedCellFromParentIJ(pcell, i, j), childEdges[i][j],
					t, disjointFromIndex)
			}
		}
	}

	if indexCellAbsorbed {
		// Restore the state for any edges being removed that we are tracking.
		t.restoreStateBefore(s.pendingAdditionsPos)
	}
}
85692
func ChildrenRecursive(ctx context.Context, zconn *ZkConn, zkPath string) ([]string, error) {
	var err error
	mutex := sync.Mutex{}
	wg := sync.WaitGroup{}
	pathList := make([]string, 0, 32)
	children, _, err := zconn.Children(ctx, zkPath)
	if err != nil {
		return nil, err
	}

	for _, child := range children {
		wg.Add(1)
		go func(child string) {
			childPath := path.Join(zkPath, child)
			rChildren, zkErr := ChildrenRecursive(ctx, zconn, childPath)
			if zkErr != nil {
				// If other processes are deleting nodes, we need to ignore
				// the missing nodes.
				if zkErr != zk.ErrNoNode {
					mutex.Lock()
					err = zkErr
					mutex.Unlock()
				}
			} else {
				mutex.Lock()
				pathList = append(pathList, child)
				for _, rChild := range rChildren {
					pathList = append(pathList, path.Join(child, rChild))
				}
				mutex.Unlock()
			}
			wg.Done()
		}(child)
	}

	wg.Wait()

	mutex.Lock()
	defer mutex.Unlock()
	if err != nil {
		return nil, err
	}
	return pathList, nil
}
24235
func (n *node) prevSibling() *node {
	if n.parent == nil {
		return nil
	}
	index := n.parent.childIndex(n)
	if index == 0 {
		return nil
	}
	return n.parent.childAt(index - 1)
}
1330337
func (lkp *lookupInternal) Update(vcursor VCursor, oldValues []sqltypes.Value, ksid sqltypes.Value, newValues []sqltypes.Value) error {
	if err := lkp.Delete(vcursor, [][]sqltypes.Value{oldValues}, ksid); err != nil {
		return err
	}
	return lkp.Create(vcursor, [][]sqltypes.Value{newValues}, []sqltypes.Value{ksid}, false /* ignoreMode */)
}
74865
func (d *Decoder) indirect(v reflect.Value) (reflect.Value, error) {
	rv := v
	for rv.Kind() == reflect.Ptr {
		// Allocate pointer if needed.
		isNil := rv.IsNil()
		if isNil && !rv.CanSet() {
			msg := fmt.Sprintf("unable to allocate pointer for '%v'",
				rv.Type().String())
			err := unmarshalError("indirect", ErrNotSettable, msg,
				nil, nil)
			return rv, err
		}
		if isNil {
			rv.Set(reflect.New(rv.Type().Elem()))
		}
		rv = rv.Elem()
	}
	return rv, nil
}
756403
func recalculateCount(m *tree) {
	count := 0
	for _, t := range m.children {
		count += t.Size()
	}
	m.count = count + 1 // add one to count ourself
}
1027598
func (n *node) recursiveSearch(lineParts []string) *Template {
	// Nothing to search
	if len(lineParts) == 0 || len(n.children) == 0 {
		return n.template
	}

	// If last element is a wildcard, don't include it in this search since it's sorted
	// to the end but lexicographically it would not always be and sort.Search assumes
	// the slice is sorted.
	length := len(n.children)
	if n.children[length-1].value == "*" {
		length--
	}

	// Find the index of child with an exact match
	i := sort.Search(length, func(i int) bool {
		return n.children[i].value >= lineParts[0]
	})

	// Found an exact match, so search that child sub-tree
	if i < len(n.children) && n.children[i].value == lineParts[0] {
		return n.children[i].recursiveSearch(lineParts[1:])
	}
	// Not an exact match, see if we have a wildcard child to search
	if n.children[len(n.children)-1].value == "*" {
		return n.children[len(n.children)-1].recursiveSearch(lineParts[1:])
	}
	return n.template
}
829477
func (ts *Server) UpdateSrvVSchema(ctx context.Context, cell string, srvVSchema *vschemapb.SrvVSchema) error {
	conn, err := ts.ConnForCell(ctx, cell)
	if err != nil {
		return err
	}

	nodePath := SrvVSchemaFile
	data, err := proto.Marshal(srvVSchema)
	if err != nil {
		return err
	}
	_, err = conn.Update(ctx, nodePath, data, nil)
	return err
}
375533
func (e *Element) updateChildNodeCount(newValue int) {
	e.lock.Lock()
	defer e.lock.Unlock()

	e.childNodeCount = newValue
}
1305013
func (a *API) updateTopLevelShapeReferences() {
	for _, o := range a.Operations {
		// these are for REST-XML services
		if o.InputRef.LocationName != "" {
			o.InputRef.Shape.LocationName = o.InputRef.LocationName
		}
		if o.InputRef.Location != "" {
			o.InputRef.Shape.Location = o.InputRef.Location
		}
		if o.InputRef.Payload != "" {
			o.InputRef.Shape.Payload = o.InputRef.Payload
		}
		if o.InputRef.XMLNamespace.Prefix != "" {
			o.InputRef.Shape.XMLNamespace.Prefix = o.InputRef.XMLNamespace.Prefix
		}
		if o.InputRef.XMLNamespace.URI != "" {
			o.InputRef.Shape.XMLNamespace.URI = o.InputRef.XMLNamespace.URI
		}
	}

}
211922
func (s *ShapeIndexIterator) Prev() bool {
	if s.position <= 0 {
		return false
	}

	s.position--
	s.refresh()
	return true
}
829569
func (n *node) eachKeyValue(key Key, visitor func(key Key, value interface{})) {
	if n.isSet() {
		visitor(key, n.value)
		return
	}
	for keyPart, childNode := range n.children {
		childNode.eachKeyValue(append(NewKey(key...), keyPart), visitor)
	}
}
635697
func NewTree(v interface{}, duplicates bool) Tree {
	return &tree{
		container: newNodeContainer(justValue{v}, duplicates),
	}
}
546732
func AllocStructPtrs(val reflect.Value) {
	switch val.Kind() {
	case reflect.Struct:
		for i := 0; i < val.Type().NumField(); i++ {
			field := val.Field(i)
			AllocStructPtrs(field)
		}
	case reflect.Ptr:
		v := MakeNewType(val.Type(), 0)
		//TODO: Make recursivy better, include val.Type == v.Type....
		if isRecursive(v) {
			//panic(fmt.Sprintf("struct %v have a field of the same type of this struct", NameOf(v.Type())))
			return
		}
		if val.Type() == v.Type() {
			return
		}
		AllocStructPtrs(v.Elem())
		if val.CanSet() {
			val.Set(v)
		}
	case reflect.Slice:
		v := MakeNewType(val.Type(), 0)
		elem := v.Type().Elem()
		if elem.Kind() == reflect.Ptr && elem.Elem() == v.Type() {
			return
		}
		if val.CanSet() {
			val.Set(v)
		}
	}
}
626934
func (iter *Iterator) Prev() bool {
	if iter.isNew {
		return iter.Last()
	}

	if iter.node == nil {
		return false
	}

	// Reseek the previous key without allowing for an exact match if a
	// force seek was requested.  This results in the key smaller than the
	// previous one or an exhausted iterator if there is no such key.
	if seekKey := iter.seekKey; seekKey != nil {
		iter.seekKey = nil
		return iter.seek(seekKey, false, false)
	}

	// When there is no left node walk the parents until the parent's left
	// node is not equal to the previous child.  This will be the previous
	// node.
	for iter.node.left == nil {
		parent := iter.parents.Pop()
		for parent != nil && parent.left == iter.node {
			iter.node = parent
			parent = iter.parents.Pop()
		}
		iter.node = parent
		return iter.limitIterator()
	}

	// There is a left node, so the previous node is the right-most node
	// down the left sub-tree.
	iter.parents.Push(iter.node)
	iter.node = iter.node.left
	for node := iter.node.right; node != nil; node = node.right {
		iter.parents.Push(iter.node)
		iter.node = node
	}
	return iter.limitIterator()
}
870475
func parseRecursive(parsers Parsers, val reflect.Value) reflect.Value {
	switch val.Kind() {
	case reflect.Ptr:
		o := val.Elem()
		if o.IsValid() {
			res := parseRecursive(parsers, o)
			if res != reflect.ValueOf(nil) {
				return res
			}
		}
	case reflect.Interface:
		res := parseRecursive(parsers, val.Elem())
		if res != reflect.ValueOf(nil) {
			return res
		}
	case reflect.Struct:
		for i := 0; i < val.NumField(); i++ {
			res := parseRecursive(parsers, val.Field(i))
			if res != reflect.ValueOf(nil) {
				val.Field(i).Set(res)
			}
		}
		return val
	case reflect.Slice:
		for i := 0; i < val.Len(); i++ {
			res := parseRecursive(parsers, val.Index(i))
			if res != reflect.ValueOf(nil) {
				val.Index(i).Set(res)
			}
		}
		return val
	case reflect.Map:
		for _, k := range val.MapKeys() {
			mapVal := val.MapIndex(k)
			res := parseRecursive(parsers, mapVal)
			if res != reflect.ValueOf(nil) {
				val.SetMapIndex(k, res)
			}
		}
		return val
	case reflect.String:
		if parsers.StringParser != nil {
			value := parsers.StringParser.ParseString(val.String())
			return reflect.ValueOf(value)
		}
		return val
	case reflect.Int:
		if parsers.IntParser != nil {
			value := parsers.IntParser.ParseInt(val.Int())
			return reflect.ValueOf(value)
		}
		return val
	case reflect.Float64:
		if parsers.FloatParser != nil {
			value := parsers.FloatParser.ParseFloat(val.Float())
			return reflect.ValueOf(value)
		}
		return val
	default:
		return val
	}

	return reflect.ValueOf(nil)
}