diff -Nru golang-github-hashicorp-go-immutable-radix-1.0.0/CHANGELOG.md golang-github-hashicorp-go-immutable-radix-1.1.0/CHANGELOG.md --- golang-github-hashicorp-go-immutable-radix-1.0.0/CHANGELOG.md 1970-01-01 00:00:00.000000000 +0000 +++ golang-github-hashicorp-go-immutable-radix-1.1.0/CHANGELOG.md 2019-05-22 19:38:59.000000000 +0000 @@ -0,0 +1,9 @@ +# 1.1.0 (May 22nd, 2019) + +FEATURES + +* Add `SeekLowerBound` to allow for range scans. [[GH-24](https://github.com/hashicorp/go-immutable-radix/pull/24)] + +# 1.0.0 (August 30th, 2018) + +* go mod adopted diff -Nru golang-github-hashicorp-go-immutable-radix-1.0.0/debian/changelog golang-github-hashicorp-go-immutable-radix-1.1.0/debian/changelog --- golang-github-hashicorp-go-immutable-radix-1.0.0/debian/changelog 2018-12-20 06:37:05.000000000 +0000 +++ golang-github-hashicorp-go-immutable-radix-1.1.0/debian/changelog 2019-09-30 09:49:12.000000000 +0000 @@ -1,3 +1,11 @@ +golang-github-hashicorp-go-immutable-radix (1.1.0-1) unstable; urgency=medium + + * New upstream release. + * Standards-Version: 4.4.0. + * DH & compat to version 12. + + -- Dmitry Smirnov Mon, 30 Sep 2019 19:49:12 +1000 + golang-github-hashicorp-go-immutable-radix (1.0.0-1) unstable; urgency=medium [ Alexandre Viau ] diff -Nru golang-github-hashicorp-go-immutable-radix-1.0.0/debian/compat golang-github-hashicorp-go-immutable-radix-1.1.0/debian/compat --- golang-github-hashicorp-go-immutable-radix-1.0.0/debian/compat 2018-12-20 06:26:23.000000000 +0000 +++ golang-github-hashicorp-go-immutable-radix-1.1.0/debian/compat 2019-09-30 09:47:14.000000000 +0000 @@ -1 +1 @@ -11 +12 diff -Nru golang-github-hashicorp-go-immutable-radix-1.0.0/debian/control golang-github-hashicorp-go-immutable-radix-1.1.0/debian/control --- golang-github-hashicorp-go-immutable-radix-1.0.0/debian/control 2018-12-20 06:36:50.000000000 +0000 +++ golang-github-hashicorp-go-immutable-radix-1.1.0/debian/control 2019-09-30 09:47:12.000000000 +0000 @@ -6,12 +6,12 @@ Section: devel Testsuite: autopkgtest-pkg-go Priority: optional -Build-Depends: debhelper (>= 11~), +Standards-Version: 4.4.0 +Build-Depends: debhelper (>= 12~), dh-golang, golang-any, golang-github-hashicorp-go-uuid-dev (>= 1.0.0~), golang-github-hashicorp-golang-lru-dev (>= 0.5.0~) -Standards-Version: 4.2.1 Vcs-Browser: https://salsa.debian.org/go-team/packages/golang-github-hashicorp-go-immutable-radix Vcs-Git: https://salsa.debian.org/go-team/packages/golang-github-hashicorp-go-immutable-radix.git Homepage: https://github.com/hashicorp/go-immutable-radix diff -Nru golang-github-hashicorp-go-immutable-radix-1.0.0/iradix_test.go golang-github-hashicorp-go-immutable-radix-1.1.0/iradix_test.go --- golang-github-hashicorp-go-immutable-radix-1.0.0/iradix_test.go 2018-08-30 03:32:45.000000000 +0000 +++ golang-github-hashicorp-go-immutable-radix-1.1.0/iradix_test.go 2019-05-22 19:38:59.000000000 +0000 @@ -2,9 +2,11 @@ import ( "fmt" + "math/rand" "reflect" "sort" "testing" + "testing/quick" "github.com/hashicorp/go-uuid" ) @@ -1529,3 +1531,246 @@ t.Fatalf("tree len should be zero, got %d", r.Len()) } } + +func TestIterateLowerBound(t *testing.T) { + fixedLenKeys := []string{ + "00000", + "00001", + "00004", + "00010", + "00020", + "20020", + } + + mixedLenKeys := []string{ + "a1", + "abc", + "barbazboo", + "foo", + "found", + "zap", + "zip", + } + + type exp struct { + keys []string + search string + want []string + } + cases := []exp{ + exp{ + fixedLenKeys, + "00000", + fixedLenKeys, + }, exp{ + fixedLenKeys, + "00003", + []string{ + "00004", + "00010", + "00020", + "20020", + }, + }, exp{ + fixedLenKeys, + "00010", + []string{ + "00010", + "00020", + "20020", + }, + }, exp{ + fixedLenKeys, + "20000", + []string{ + "20020", + }, + }, exp{ + fixedLenKeys, + "20020", + []string{ + "20020", + }, + }, exp{ + fixedLenKeys, + "20022", + []string{}, + }, exp{ + mixedLenKeys, + "A", // before all lower case letters + mixedLenKeys, + }, exp{ + mixedLenKeys, + "a1", + mixedLenKeys, + }, exp{ + mixedLenKeys, + "b", + []string{ + "barbazboo", + "foo", + "found", + "zap", + "zip", + }, + }, exp{ + mixedLenKeys, + "bar", + []string{ + "barbazboo", + "foo", + "found", + "zap", + "zip", + }, + }, exp{ + mixedLenKeys, + "barbazboo0", + []string{ + "foo", + "found", + "zap", + "zip", + }, + }, exp{ + mixedLenKeys, + "zippy", + []string{}, + }, exp{ + mixedLenKeys, + "zi", + []string{ + "zip", + }, + }, + + // This is a case found by TestIterateLowerBoundFuzz simplified by hand. The + // lowest node should be the first, but it is split on the same char as the + // second char in the search string. My initial implementation didn't take + // that into account (i.e. propagate the fact that we already know we are + // greater than the input key into the recursion). This would skip the first + // result. + exp{ + []string{ + "bb", + "bc", + }, + "ac", + []string{"bb", "bc"}, + }, + + // This is a case found by TestIterateLowerBoundFuzz. + exp{ + []string{"aaaba", "aabaa", "aabab", "aabcb", "aacca", "abaaa", "abacb", "abbcb", "abcaa", "abcba", "abcbb", "acaaa", "acaab", "acaac", "acaca", "acacb", "acbaa", "acbbb", "acbcc", "accca", "babaa", "babcc", "bbaaa", "bbacc", "bbbab", "bbbac", "bbbcc", "bbcab", "bbcca", "bbccc", "bcaac", "bcbca", "bcbcc", "bccac", "bccbc", "bccca", "caaab", "caacc", "cabac", "cabbb", "cabbc", "cabcb", "cacac", "cacbc", "cacca", "cbaba", "cbabb", "cbabc", "cbbaa", "cbbab", "cbbbc", "cbcbb", "cbcbc", "cbcca", "ccaaa", "ccabc", "ccaca", "ccacc", "ccbac", "cccaa", "cccac", "cccca"}, + "cbacb", + []string{"cbbaa", "cbbab", "cbbbc", "cbcbb", "cbcbc", "cbcca", "ccaaa", "ccabc", "ccaca", "ccacc", "ccbac", "cccaa", "cccac", "cccca"}, + }, + } + + for idx, test := range cases { + t.Run(fmt.Sprintf("case%03d", idx), func(t *testing.T) { + r := New() + + // Insert keys + for _, k := range test.keys { + var ok bool + r, _, ok = r.Insert([]byte(k), nil) + if ok { + t.Fatalf("duplicate key %s in keys", k) + } + } + if r.Len() != len(test.keys) { + t.Fatal("failed adding keys") + } + // Get and seek iterator + root := r.Root() + iter := root.Iterator() + if test.search != "" { + iter.SeekLowerBound([]byte(test.search)) + } + + // Consume all the keys + out := []string{} + for { + key, _, ok := iter.Next() + if !ok { + break + } + out = append(out, string(key)) + } + if !reflect.DeepEqual(out, test.want) { + t.Fatalf("mis-match: key=%s\n got=%v\n want=%v", test.search, + out, test.want) + } + }) + } +} + +type readableString string + +func (s readableString) Generate(rand *rand.Rand, size int) reflect.Value { + // Pick a random string from a limited alphabet that makes it easy to read the + // failure cases. Also never includes a null byte as we don't support that. + const letters = "abcdefghijklmnopqrstuvwxyz/-_0123456789" + + b := make([]byte, size) + for i := range b { + b[i] = letters[rand.Intn(len(letters))] + } + return reflect.ValueOf(readableString(b)) +} + +func TestIterateLowerBoundFuzz(t *testing.T) { + r := New() + set := []string{} + + // This specifies a property where each call adds a new random key to the radix + // tree (with a null byte appended since our tree doesn't support one key + // being a prefix of another and treats null bytes specially). + // + // It also maintains a plain sorted list of the same set of keys and asserts + // that iterating from some random key to the end using LowerBound produces + // the same list as filtering all sorted keys that are lower. + + radixAddAndScan := func(newKey, searchKey readableString) []string { + // Append a null byte + key := []byte(newKey + "\x00") + r, _, _ = r.Insert(key, nil) + + // Now iterate the tree from searchKey to the end + it := r.Root().Iterator() + result := []string{} + it.SeekLowerBound([]byte(searchKey)) + for { + key, _, ok := it.Next() + if !ok { + break + } + // Strip the null byte and append to result set + result = append(result, string(key[0:len(key)-1])) + } + return result + } + + sliceAddSortAndFilter := func(newKey, searchKey readableString) []string { + // Append the key to the set and re-sort + set = append(set, string(newKey)) + sort.Strings(set) + + t.Logf("Current Set: %#v", set) + + result := []string{} + var prev string + for _, k := range set { + if k >= string(searchKey) && k != prev { + result = append(result, k) + } + prev = k + } + return result + } + + if err := quick.CheckEqual(radixAddAndScan, sliceAddSortAndFilter, nil); err != nil { + t.Error(err) + } +} diff -Nru golang-github-hashicorp-go-immutable-radix-1.0.0/iter.go golang-github-hashicorp-go-immutable-radix-1.1.0/iter.go --- golang-github-hashicorp-go-immutable-radix-1.0.0/iter.go 2018-08-30 03:32:45.000000000 +0000 +++ golang-github-hashicorp-go-immutable-radix-1.1.0/iter.go 2019-05-22 19:38:59.000000000 +0000 @@ -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 diff -Nru golang-github-hashicorp-go-immutable-radix-1.0.0/node.go golang-github-hashicorp-go-immutable-radix-1.1.0/node.go --- golang-github-hashicorp-go-immutable-radix-1.0.0/node.go 2018-08-30 03:32:45.000000000 +0000 +++ golang-github-hashicorp-go-immutable-radix-1.1.0/node.go 2019-05-22 19:38:59.000000000 +0000 @@ -79,6 +79,18 @@ return -1, nil } +func (n *Node) getLowerBoundEdge(label byte) (int, *Node) { + num := len(n.edges) + idx := sort.Search(num, func(i int) bool { + return n.edges[i].label >= label + }) + // we want lower bound behavior so return even if it's not an exact match + if idx < num { + return idx, n.edges[idx].node + } + return -1, nil +} + func (n *Node) delEdge(label byte) { num := len(n.edges) idx := sort.Search(num, func(i int) bool { diff -Nru golang-github-hashicorp-go-immutable-radix-1.0.0/README.md golang-github-hashicorp-go-immutable-radix-1.1.0/README.md --- golang-github-hashicorp-go-immutable-radix-1.0.0/README.md 2018-08-30 03:32:45.000000000 +0000 +++ golang-github-hashicorp-go-immutable-radix-1.1.0/README.md 2019-05-22 19:38:59.000000000 +0000 @@ -39,3 +39,28 @@ } ``` +Here is an example of performing a range scan of the keys. + +```go +// Create a tree +r := iradix.New() +r, _, _ = r.Insert([]byte("001"), 1) +r, _, _ = r.Insert([]byte("002"), 2) +r, _, _ = r.Insert([]byte("005"), 5) +r, _, _ = r.Insert([]byte("010"), 10) +r, _, _ = r.Insert([]byte("100"), 10) + +// Range scan over the keys that sort lexicographically between [003, 050) +it := r.Root().Iterator() +it.SeekLowerBound([]byte("003")) +for key, _, ok := it.Next(); ok; key, _, ok = it.Next() { + if key >= "050" { + break + } + fmt.Println(key) +} +// Output: +// 005 +// 010 +``` +