VOL-1691 Fix openolt adapter getting stuck while registartion with core
Change-Id: Ide8131f325bc15f1b909e14d7af6ee9bcd6b3b5b
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/iter.go b/vendor/github.com/hashicorp/go-immutable-radix/iter.go
index 9815e02..1ecaf83 100644
--- a/vendor/github.com/hashicorp/go-immutable-radix/iter.go
+++ b/vendor/github.com/hashicorp/go-immutable-radix/iter.go
@@ -1,6 +1,8 @@
package iradix
-import "bytes"
+import (
+ "bytes"
+)
// Iterator is used to iterate over a set of nodes
// in pre-order
@@ -53,6 +55,101 @@
i.SeekPrefixWatch(prefix)
}
+func (i *Iterator) recurseMin(n *Node) *Node {
+ // Traverse to the minimum child
+ if n.leaf != nil {
+ return n
+ }
+ if len(n.edges) > 0 {
+ // Add all the other edges to the stack (the min node will be added as
+ // we recurse)
+ i.stack = append(i.stack, n.edges[1:])
+ return i.recurseMin(n.edges[0].node)
+ }
+ // Shouldn't be possible
+ return nil
+}
+
+// SeekLowerBound is used to seek the iterator to the smallest key that is
+// greater or equal to the given key. There is no watch variant as it's hard to
+// predict based on the radix structure which node(s) changes might affect the
+// result.
+func (i *Iterator) SeekLowerBound(key []byte) {
+ // Wipe the stack. Unlike Prefix iteration, we need to build the stack as we
+ // go because we need only a subset of edges of many nodes in the path to the
+ // leaf with the lower bound.
+ i.stack = []edges{}
+ n := i.node
+ search := key
+
+ found := func(n *Node) {
+ i.node = n
+ i.stack = append(i.stack, edges{edge{node: n}})
+ }
+
+ for {
+ // Compare current prefix with the search key's same-length prefix.
+ var prefixCmp int
+ if len(n.prefix) < len(search) {
+ prefixCmp = bytes.Compare(n.prefix, search[0:len(n.prefix)])
+ } else {
+ prefixCmp = bytes.Compare(n.prefix, search)
+ }
+
+ if prefixCmp > 0 {
+ // Prefix is larger, that means the lower bound is greater than the search
+ // and from now on we need to follow the minimum path to the smallest
+ // leaf under this subtree.
+ n = i.recurseMin(n)
+ if n != nil {
+ found(n)
+ }
+ return
+ }
+
+ if prefixCmp < 0 {
+ // Prefix is smaller than search prefix, that means there is no lower
+ // bound
+ i.node = nil
+ return
+ }
+
+ // Prefix is equal, we are still heading for an exact match. If this is a
+ // leaf we're done.
+ if n.leaf != nil {
+ if bytes.Compare(n.leaf.key, key) < 0 {
+ i.node = nil
+ return
+ }
+ found(n)
+ return
+ }
+
+ // Consume the search prefix
+ if len(n.prefix) > len(search) {
+ search = []byte{}
+ } else {
+ search = search[len(n.prefix):]
+ }
+
+ // Otherwise, take the lower bound next edge.
+ idx, lbNode := n.getLowerBoundEdge(search[0])
+ if lbNode == nil {
+ i.node = nil
+ return
+ }
+
+ // Create stack edges for the all strictly higher edges in this node.
+ if idx+1 < len(n.edges) {
+ i.stack = append(i.stack, n.edges[idx+1:])
+ }
+
+ i.node = lbNode
+ // Recurse
+ n = lbNode
+ }
+}
+
// Next returns the next node in order
func (i *Iterator) Next() ([]byte, interface{}, bool) {
// Initialize our stack if needed