diff -Nru golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/changelog golang-github-armon-go-radix-1.0.0/debian/changelog --- golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/changelog 2017-08-08 14:06:29.000000000 +0000 +++ golang-github-armon-go-radix-1.0.0/debian/changelog 2018-09-27 08:13:02.000000000 +0000 @@ -1,3 +1,21 @@ +golang-github-armon-go-radix (1.0.0-1) unstable; urgency=medium + + * Team upload. + + [ Alexandre Viau ] + * Point Vcs-* urls to salsa.debian.org. + + [ Shengjing Zhu ] + * New upstream release 1.0.0. + * Update debhelper and compat to 11. + * Update team mail address to team+pkg-go@tracker.debian.org. + * Update Standards-Version to 4.2.1. + + Change Priority to optional. + + Use https form of the copyright-format URL. + * Add autopkgtest-pkg-go Testsuite. + + -- Shengjing Zhu Thu, 27 Sep 2018 16:13:02 +0800 + golang-github-armon-go-radix (0.0~git20150602.0.fbd82e8-2) unstable; urgency=medium [ Paul Tagliamonte ] diff -Nru golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/compat golang-github-armon-go-radix-1.0.0/debian/compat --- golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/compat 2017-08-08 14:00:56.000000000 +0000 +++ golang-github-armon-go-radix-1.0.0/debian/compat 2018-09-27 08:13:02.000000000 +0000 @@ -1 +1 @@ -9 +11 diff -Nru golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/control golang-github-armon-go-radix-1.0.0/debian/control --- golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/control 2017-08-08 14:05:57.000000000 +0000 +++ golang-github-armon-go-radix-1.0.0/debian/control 2018-09-27 08:13:02.000000000 +0000 @@ -1,18 +1,23 @@ Source: golang-github-armon-go-radix Section: devel -Priority: extra -Maintainer: Debian Go Packaging Team -Uploaders: Tianon Gravi , Tim Potter -Build-Depends: debhelper (>= 9), dh-golang, golang-any -Standards-Version: 3.9.6 +Priority: optional +Maintainer: Debian Go Packaging Team +Uploaders: Tianon Gravi , + Tim Potter , +Build-Depends: debhelper (>= 11), + dh-golang, + golang-any, +Standards-Version: 4.2.1 Homepage: https://github.com/armon/go-radix -Vcs-Browser: https://anonscm.debian.org/cgit/pkg-go/packages/golang-github-armon-go-radix.git -Vcs-Git: https://anonscm.debian.org/git/pkg-go/packages/golang-github-armon-go-radix.git +Vcs-Browser: https://salsa.debian.org/go-team/packages/golang-github-armon-go-radix +Vcs-Git: https://salsa.debian.org/go-team/packages/golang-github-armon-go-radix.git XS-Go-Import-Path: github.com/armon/go-radix +Testsuite: autopkgtest-pkg-go Package: golang-github-armon-go-radix-dev Architecture: all -Depends: ${misc:Depends}, ${shlibs:Depends} +Depends: ${misc:Depends}, + ${shlibs:Depends}, Description: Golang implementation of Radix trees Provides the radix package that implements a radix tree. The package only provides a single Tree implementation, optimized for sparse nodes. diff -Nru golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/copyright golang-github-armon-go-radix-1.0.0/debian/copyright --- golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/copyright 2017-08-08 14:00:56.000000000 +0000 +++ golang-github-armon-go-radix-1.0.0/debian/copyright 2018-09-27 08:13:02.000000000 +0000 @@ -1,4 +1,4 @@ -Format: http://www.debian.org/doc/packaging-manuals/copyright-format/1.0/ +Format: https://www.debian.org/doc/packaging-manuals/copyright-format/1.0/ Upstream-Name: go-radix Source: https://github.com/armon/go-radix diff -Nru golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/gbp.conf golang-github-armon-go-radix-1.0.0/debian/gbp.conf --- golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/gbp.conf 2017-08-08 14:00:56.000000000 +0000 +++ golang-github-armon-go-radix-1.0.0/debian/gbp.conf 2018-09-27 08:13:02.000000000 +0000 @@ -1,2 +1,2 @@ [DEFAULT] -pristine-tar = True +debian-branch = debian/sid diff -Nru golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/gitlab-ci.yml golang-github-armon-go-radix-1.0.0/debian/gitlab-ci.yml --- golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/debian/gitlab-ci.yml 1970-01-01 00:00:00.000000000 +0000 +++ golang-github-armon-go-radix-1.0.0/debian/gitlab-ci.yml 2018-09-27 08:13:02.000000000 +0000 @@ -0,0 +1,28 @@ + +# auto-generated, DO NOT MODIFY. +# The authoritative copy of this file lives at: +# https://salsa.debian.org/go-team/ci/blob/master/cmd/ci/gitlabciyml.go + +# TODO: publish under debian-go-team/ci +image: stapelberg/ci2 + +test_the_archive: + artifacts: + paths: + - before-applying-commit.json + - after-applying-commit.json + script: + # Create an overlay to discard writes to /srv/gopath/src after the build: + - "rm -rf /cache/overlay/{upper,work}" + - "mkdir -p /cache/overlay/{upper,work}" + - "mount -t overlay overlay -o lowerdir=/srv/gopath/src,upperdir=/cache/overlay/upper,workdir=/cache/overlay/work /srv/gopath/src" + - "export GOPATH=/srv/gopath" + - "export GOCACHE=/cache/go" + # Build the world as-is: + - "ci-build -exemptions=/var/lib/ci-build/exemptions.json > before-applying-commit.json" + # Copy this package into the overlay: + - "GBP_CONF_FILES=:debian/gbp.conf gbp buildpackage --git-no-pristine-tar --git-ignore-branch --git-ignore-new --git-export-dir=/tmp/export --git-no-overlay --git-tarball-dir=/nonexistant --git-cleaner=/bin/true --git-builder='dpkg-buildpackage -S -d --no-sign'" + - "pgt-gopath -dsc /tmp/export/*.dsc" + # Rebuild the world: + - "ci-build -exemptions=/var/lib/ci-build/exemptions.json > after-applying-commit.json" + - "ci-diff before-applying-commit.json after-applying-commit.json" diff -Nru golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/.gitignore golang-github-armon-go-radix-1.0.0/.gitignore --- golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/.gitignore 1970-01-01 00:00:00.000000000 +0000 +++ golang-github-armon-go-radix-1.0.0/.gitignore 2018-08-24 02:57:28.000000000 +0000 @@ -0,0 +1,22 @@ +# Compiled Object files, Static and Dynamic libs (Shared Objects) +*.o +*.a +*.so + +# Folders +_obj +_test + +# Architecture specific extensions/prefixes +*.[568vq] +[568vq].out + +*.cgo1.go +*.cgo2.c +_cgo_defun.c +_cgo_gotypes.go +_cgo_export.* + +_testmain.go + +*.exe diff -Nru golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/go.mod golang-github-armon-go-radix-1.0.0/go.mod --- golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/go.mod 1970-01-01 00:00:00.000000000 +0000 +++ golang-github-armon-go-radix-1.0.0/go.mod 2018-08-24 02:57:28.000000000 +0000 @@ -0,0 +1 @@ +module github.com/armon/go-radix diff -Nru golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/radix.go golang-github-armon-go-radix-1.0.0/radix.go --- golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/radix.go 2015-11-06 21:22:54.000000000 +0000 +++ golang-github-armon-go-radix-1.0.0/radix.go 2018-08-24 02:57:28.000000000 +0000 @@ -44,13 +44,13 @@ n.edges.Sort() } -func (n *node) replaceEdge(e edge) { +func (n *node) updateEdge(label byte, node *node) { num := len(n.edges) idx := sort.Search(num, func(i int) bool { - return n.edges[i].label >= e.label + return n.edges[i].label >= label }) - if idx < num && n.edges[idx].label == e.label { - n.edges[idx].node = e.node + if idx < num && n.edges[idx].label == label { + n.edges[idx].node = node return } panic("replacing missing edge") @@ -155,14 +155,14 @@ old := n.leaf.val n.leaf.val = v return old, true - } else { - n.leaf = &leafNode{ - key: s, - val: v, - } - t.size++ - return nil, false } + + n.leaf = &leafNode{ + key: s, + val: v, + } + t.size++ + return nil, false } // Look for the edge @@ -198,10 +198,7 @@ child := &node{ prefix: search[:commonPrefix], } - parent.replaceEdge(edge{ - label: search[0], - node: child, - }) + parent.updateEdge(search[0], child) // Restore the existing node child.addEdge(edge{ @@ -233,7 +230,6 @@ }) return nil, false } - return nil, false } // Delete is used to delete a key, returning the previous @@ -293,6 +289,53 @@ return leaf.val, true } +// DeletePrefix is used to delete the subtree under a prefix +// Returns how many nodes were deleted +// Use this to delete large subtrees efficiently +func (t *Tree) DeletePrefix(s string) int { + return t.deletePrefix(nil, t.root, s) +} + +// delete does a recursive deletion +func (t *Tree) deletePrefix(parent, n *node, prefix string) int { + // Check for key exhaustion + if len(prefix) == 0 { + // Remove the leaf node + subTreeSize := 0 + //recursively walk from all edges of the node to be deleted + recursiveWalk(n, func(s string, v interface{}) bool { + subTreeSize++ + return false + }) + if n.isLeaf() { + n.leaf = nil + } + n.edges = nil // deletes the entire subtree + + // Check if we should merge the parent's other child + if parent != nil && parent != t.root && len(parent.edges) == 1 && !parent.isLeaf() { + parent.mergeChild() + } + t.size -= subTreeSize + return subTreeSize + } + + // Look for an edge + label := prefix[0] + child := n.getEdge(label) + if child == nil || (!strings.HasPrefix(child.prefix, prefix) && !strings.HasPrefix(prefix, child.prefix)) { + return 0 + } + + // Consume the search prefix + if len(child.prefix) > len(prefix) { + prefix = prefix[len(prefix):] + } else { + prefix = prefix[len(child.prefix):] + } + return t.deletePrefix(n, child, prefix) +} + func (n *node) mergeChild() { e := n.edges[0] child := e.node @@ -393,9 +436,8 @@ } if n.isLeaf() { return n.leaf.key, n.leaf.val, true - } else { - break } + break } return "", nil, false } diff -Nru golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/radix_test.go golang-github-armon-go-radix-1.0.0/radix_test.go --- golang-github-armon-go-radix-0.0~git20150602.0.fbd82e8/radix_test.go 2015-11-06 21:22:54.000000000 +0000 +++ golang-github-armon-go-radix-1.0.0/radix_test.go 2018-08-24 02:57:28.000000000 +0000 @@ -104,6 +104,46 @@ } } +func TestDeletePrefix(t *testing.T) { + type exp struct { + inp []string + prefix string + out []string + numDeleted int + } + + cases := []exp{ + {[]string{"", "A", "AB", "ABC", "R", "S"}, "A", []string{"", "R", "S"}, 3}, + {[]string{"", "A", "AB", "ABC", "R", "S"}, "ABC", []string{"", "A", "AB", "R", "S"}, 1}, + {[]string{"", "A", "AB", "ABC", "R", "S"}, "", []string{}, 6}, + {[]string{"", "A", "AB", "ABC", "R", "S"}, "S", []string{"", "A", "AB", "ABC", "R"}, 1}, + {[]string{"", "A", "AB", "ABC", "R", "S"}, "SS", []string{"", "A", "AB", "ABC", "R", "S"}, 0}, + } + + for _, test := range cases { + r := New() + for _, ss := range test.inp { + r.Insert(ss, true) + } + + deleted := r.DeletePrefix(test.prefix) + if deleted != test.numDeleted { + t.Fatalf("Bad delete, expected %v to be deleted but got %v", test.numDeleted, deleted) + } + + out := []string{} + fn := func(s string, v interface{}) bool { + out = append(out, s) + return false + } + r.Walk(fn) + + if !reflect.DeepEqual(out, test.out) { + t.Fatalf("mis-match: %v %v", out, test.out) + } + } +} + func TestLongestPrefix(t *testing.T) { r := New() @@ -174,43 +214,43 @@ out []string } cases := []exp{ - exp{ + { "f", []string{"foobar", "foo/bar/baz", "foo/baz/bar", "foo/zip/zap"}, }, - exp{ + { "foo", []string{"foobar", "foo/bar/baz", "foo/baz/bar", "foo/zip/zap"}, }, - exp{ + { "foob", []string{"foobar"}, }, - exp{ + { "foo/", []string{"foo/bar/baz", "foo/baz/bar", "foo/zip/zap"}, }, - exp{ + { "foo/b", []string{"foo/bar/baz", "foo/baz/bar"}, }, - exp{ + { "foo/ba", []string{"foo/bar/baz", "foo/baz/bar"}, }, - exp{ + { "foo/bar", []string{"foo/bar/baz"}, }, - exp{ + { "foo/bar/baz", []string{"foo/bar/baz"}, }, - exp{ + { "foo/bar/bazoo", []string{}, }, - exp{ + { "z", []string{"zipzap"}, }, @@ -254,35 +294,35 @@ out []string } cases := []exp{ - exp{ + { "f", []string{}, }, - exp{ + { "foo", []string{"foo"}, }, - exp{ + { "foo/", []string{"foo"}, }, - exp{ + { "foo/ba", []string{"foo"}, }, - exp{ + { "foo/bar", []string{"foo", "foo/bar"}, }, - exp{ + { "foo/bar/baz", []string{"foo", "foo/bar", "foo/bar/baz"}, }, - exp{ + { "foo/bar/bazoo", []string{"foo", "foo/bar", "foo/bar/baz"}, }, - exp{ + { "z", []string{}, },