1 files changed, 91 insertions, 0 deletions
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/iter.go b/vendor/github.com/hashicorp/go-immutable-radix/iter.go
new file mode 100644
index 000000000..9815e0253
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/iter.go
@@ -0,0 +1,91 @@
+package iradix
+
+import "bytes"
+
+// Iterator is used to iterate over a set of nodes
+// in pre-order
+type Iterator struct {
+	node  *Node
+	stack []edges
+}
+
+// SeekPrefixWatch is used to seek the iterator to a given prefix
+// and returns the watch channel of the finest granularity
+func (i *Iterator) SeekPrefixWatch(prefix []byte) (watch <-chan struct{}) {
+	// Wipe the stack
+	i.stack = nil
+	n := i.node
+	watch = n.mutateCh
+	search := prefix
+	for {
+		// Check for key exhaution
+		if len(search) == 0 {
+			i.node = n
+			return
+		}
+
+		// Look for an edge
+		_, n = n.getEdge(search[0])
+		if n == nil {
+			i.node = nil
+			return
+		}
+
+		// Update to the finest granularity as the search makes progress
+		watch = n.mutateCh
+
+		// Consume the search prefix
+		if bytes.HasPrefix(search, n.prefix) {
+			search = search[len(n.prefix):]
+
+		} else if bytes.HasPrefix(n.prefix, search) {
+			i.node = n
+			return
+		} else {
+			i.node = nil
+			return
+		}
+	}
+}
+
+// SeekPrefix is used to seek the iterator to a given prefix
+func (i *Iterator) SeekPrefix(prefix []byte) {
+	i.SeekPrefixWatch(prefix)
+}
+
+// Next returns the next node in order
+func (i *Iterator) Next() ([]byte, interface{}, bool) {
+	// Initialize our stack if needed
+	if i.stack == nil && i.node != nil {
+		i.stack = []edges{
+			edges{
+				edge{node: i.node},
+			},
+		}
+	}
+
+	for len(i.stack) > 0 {
+		// Inspect the last element of the stack
+		n := len(i.stack)
+		last := i.stack[n-1]
+		elem := last[0].node
+
+		// Update the stack
+		if len(last) > 1 {
+			i.stack[n-1] = last[1:]
+		} else {
+			i.stack = i.stack[:n-1]
+		}
+
+		// Push the edges onto the frontier
+		if len(elem.edges) > 0 {
+			i.stack = append(i.stack, elem.edges)
+		}
+
+		// Return the leaf values if any
+		if elem.leaf != nil {
+			return elem.leaf.key, elem.leaf.val, true
+		}
+	}
+	return nil, nil, false
+}