diff options
author | Christopher Speller <crspeller@gmail.com> | 2017-08-17 17:19:06 -0700 |
---|---|---|
committer | GitHub <noreply@github.com> | 2017-08-17 17:19:06 -0700 |
commit | 96eab1202717e073782ec399a4e0820cae15b1bb (patch) | |
tree | 011012982be971c7e9ef91466f026bc0956ac9a2 /vendor/github.com/hashicorp/go-immutable-radix/iter.go | |
parent | 2c895ee66eed626721135acfcc48254c6e3f3b29 (diff) | |
download | chat-96eab1202717e073782ec399a4e0820cae15b1bb.tar.gz chat-96eab1202717e073782ec399a4e0820cae15b1bb.tar.bz2 chat-96eab1202717e073782ec399a4e0820cae15b1bb.zip |
Updating server dependancies. (#7246)
Diffstat (limited to 'vendor/github.com/hashicorp/go-immutable-radix/iter.go')
-rw-r--r-- | vendor/github.com/hashicorp/go-immutable-radix/iter.go | 91 |
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 +} |