William Kurkian | ea86948 | 2019-04-09 15:16:11 -0400 | [diff] [blame] | 1 | package iradix |
| 2 | |
| 3 | import "bytes" |
| 4 | |
| 5 | // Iterator is used to iterate over a set of nodes |
| 6 | // in pre-order |
| 7 | type Iterator struct { |
| 8 | node *Node |
| 9 | stack []edges |
| 10 | } |
| 11 | |
| 12 | // SeekPrefixWatch is used to seek the iterator to a given prefix |
| 13 | // and returns the watch channel of the finest granularity |
| 14 | func (i *Iterator) SeekPrefixWatch(prefix []byte) (watch <-chan struct{}) { |
| 15 | // Wipe the stack |
| 16 | i.stack = nil |
| 17 | n := i.node |
| 18 | watch = n.mutateCh |
| 19 | search := prefix |
| 20 | for { |
| 21 | // Check for key exhaution |
| 22 | if len(search) == 0 { |
| 23 | i.node = n |
| 24 | return |
| 25 | } |
| 26 | |
| 27 | // Look for an edge |
| 28 | _, n = n.getEdge(search[0]) |
| 29 | if n == nil { |
| 30 | i.node = nil |
| 31 | return |
| 32 | } |
| 33 | |
| 34 | // Update to the finest granularity as the search makes progress |
| 35 | watch = n.mutateCh |
| 36 | |
| 37 | // Consume the search prefix |
| 38 | if bytes.HasPrefix(search, n.prefix) { |
| 39 | search = search[len(n.prefix):] |
| 40 | |
| 41 | } else if bytes.HasPrefix(n.prefix, search) { |
| 42 | i.node = n |
| 43 | return |
| 44 | } else { |
| 45 | i.node = nil |
| 46 | return |
| 47 | } |
| 48 | } |
| 49 | } |
| 50 | |
| 51 | // SeekPrefix is used to seek the iterator to a given prefix |
| 52 | func (i *Iterator) SeekPrefix(prefix []byte) { |
| 53 | i.SeekPrefixWatch(prefix) |
| 54 | } |
| 55 | |
| 56 | // Next returns the next node in order |
| 57 | func (i *Iterator) Next() ([]byte, interface{}, bool) { |
| 58 | // Initialize our stack if needed |
| 59 | if i.stack == nil && i.node != nil { |
| 60 | i.stack = []edges{ |
| 61 | edges{ |
| 62 | edge{node: i.node}, |
| 63 | }, |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | for len(i.stack) > 0 { |
| 68 | // Inspect the last element of the stack |
| 69 | n := len(i.stack) |
| 70 | last := i.stack[n-1] |
| 71 | elem := last[0].node |
| 72 | |
| 73 | // Update the stack |
| 74 | if len(last) > 1 { |
| 75 | i.stack[n-1] = last[1:] |
| 76 | } else { |
| 77 | i.stack = i.stack[:n-1] |
| 78 | } |
| 79 | |
| 80 | // Push the edges onto the frontier |
| 81 | if len(elem.edges) > 0 { |
| 82 | i.stack = append(i.stack, elem.edges) |
| 83 | } |
| 84 | |
| 85 | // Return the leaf values if any |
| 86 | if elem.leaf != nil { |
| 87 | return elem.leaf.key, elem.leaf.val, true |
| 88 | } |
| 89 | } |
| 90 | return nil, nil, false |
| 91 | } |