tchap / go-patricia Goto Github PK

View Code? Open in Web Editor NEW

274.0 7.0 58.0 67 KB

A generic patricia trie (also called radix tree) implemented in Go (Golang)

License: MIT License

Go 100.00%

golang patricia-tree radix-tree data-structure

go-patricia's People

Contributors

Stargazers

Watchers

go-patricia's Issues

denseChildList.add case b < list.min broken

func Test_Dense_Preceeding_Insert(t *testing.T) {
    trie := patricia.NewTrie()
    start := byte(70)
    // create a dense node
    for i := 0; i <= patricia.MaxChildrenPerSparseNode; i++ {
        trie.Insert(patricia.Prefix([]byte{start + byte(i)}), true)
    }
    // insert some preceeding keys (b < list.min)
    trie.Insert(patricia.Prefix([]byte{start - 1}), true) // runtime error: slice bounds out of range
    trie.Insert(patricia.Prefix([]byte{start - 5}), true)
    trie.Insert(patricia.Prefix([]byte{start - 15}), true)
}

I may be able to take a look at fixing this soon.

Should keep track of size in a variable

My use case here is that I'm essentially using the 'trie' as a memory efficient "set" (I know it's not really a set but whatever).

TestTrie_IDLeakageDense test failing consistently

I was using docker v1.11 (which calls NewTrie on container creation) and observe a slow memory increase. I then ran a small test to create and immediately delete a container for thousands of times. The heap profile shows that github.com/tchap/go-patricia/patricia.NewTrie accumulates more memory over time even though the number of containers remains the same. I instrumented docker to make sure that the key is deleted from the Trie on container deletion, so the trie should remain a constant size over time.

I modified the TestTrie_IDLeakageDense test to use a UUID as a key (to be more consistent with how docker is using it), and change the test to perform insertion followed by deletion for 10 million times.

func genTestData() *testData {
        // generate a random hash as a key
        key, _ := uuid.NewUUID()
        return &testData{key: key.String(), value: "o", retVal: success}
}

        for i := 0; i < 10000000; i++ {
                if ok := trie.Insert(Prefix(v.key), v.value); ok != v.retVal {
                        t.Errorf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
                }

                if ok := trie.Delete([]byte(v.key)); ok != v.retVal {
                        t.Errorf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
                }
        }

The test consistently fails with increased heap usage, e.g.,

$ go test
--- FAIL: TestTrie_IDLeakageDense (11.70s)
    patricia_dense_test.go:60: Size=0, Total=1, Trie state:
         <nil>

    patricia_dense_test.go:61: Heap space leak, grew 79424 bytes (310016 to 389440)
FAIL
exit status 1
FAIL    github.com/tchap/go-patricia/patricia   11.735s

I noticed that the test has a constant overhead set to 25000 byte (introduced in #20). Why is that and is an increase in memory usuage expected for the test?

Removing a child from node that was compacted panics

@tchap we ran into the following panic situation

$ go test 3debug_patricia_test.go 
--- FAIL: Test_DebugCrash (0.00s)
panic: removing non-existent child [recovered]
    panic: removing non-existent child

goroutine 5 [running]:
testing.func·006()
    /usr/local/go/src/testing/testing.go:441 +0x149
github.com/tchap/go-patricia/patricia.(*sparseChildList).remove(0x10362df0, 0x103afcb0)
    /Users/bishan/go/src/github.com/tchap/go-patricia/patricia/children.go:90 +0x25c
github.com/tchap/go-patricia/patricia.(*Trie).Delete(0x10356150, 0x10419d20, 0x18, 0x20, 0x20)
    /Users/bishan/go/src/github.com/tchap/go-patricia/patricia/patricia.go:270 +0x169
command-line-arguments.Test_DebugCrash(0x1034c0c0)
    /Users/bishan/go/src/bishan/3debug_patricia_test.go:3382 +0x20d
testing.tRunner(0x1034c0c0, 0x1db498)
    /usr/local/go/src/testing/testing.go:447 +0xab
created by testing.RunTests
    /usr/local/go/src/testing/testing.go:555 +0x85d

goroutine 1 [chan receive]:
testing.RunTests(0x1655a4, 0x1db498, 0x1, 0x1, 0x10350001)
    /usr/local/go/src/testing/testing.go:556 +0x899
testing.(*M).Run(0x10356090, 0x1e3860)
    /usr/local/go/src/testing/testing.go:485 +0x58
main.main()
    command-line-arguments/_test/_testmain.go:52 +0x171
FAIL    command-line-arguments  0.007s

I can pass on the test case privately if you need. I could not prune the test to a small enough size and I believe I might have some sensitive data there.

The bug seems to be in the following flow:

delete the node
https://github.com/tchap/go-patricia/blob/master/patricia/patricia.go#L252
compact the node
https://github.com/tchap/go-patricia/blob/master/patricia/patricia.go#L255
remove children from the compacted node
https://github.com/tchap/go-patricia/blob/master/patricia/patricia.go#L270

In our debugging we found that the node is already not in the tree and we are attempting to remove it, causing a panic here:
https://github.com/tchap/go-patricia/blob/master/patricia/children.go#L90

Order of inserts affects the retrieval of substrings

Thanks for the quick turnaround on the previous bug. I've got another one for you.

The order of inserts seem to affect whether or not a match is found.

For example, when you insert the prefix "by week" and then "by", the trie is unable to find the "by".
However, when you insert prefix "by" and then "by week", the trie successfully retrieves the "by".

    trie1 := patricia.NewTrie()
    trie1.Insert(patricia.Prefix("by week"), 2)
    trie1.Insert(patricia.Prefix("by"), 1)

    trie2 := patricia.NewTrie()
    trie2.Insert(patricia.Prefix("by"), 1)
    trie2.Insert(patricia.Prefix("by week"), 2)

    resultMatch1 := trie1.Match(patricia.Prefix("by"))
    resultMatch2 := trie2.Match(patricia.Prefix("by"))

    fmt.Printf("resultMatch1=%t\nresultMatch2=%t\n", resultMatch1, resultMatch2)

got:
resultMatch1=false
resultMatch2=true

want:
resultMatch1=true
resultMatch2=true

The leak test is failing occasionally

Not too cool, the tests should always return the same results.

$ go test
PASS
ok      github.com/tchap/go-patricia/patricia   4.871s
$ go test
PASS
ok      github.com/tchap/go-patricia/patricia   4.646s
$ go test
PASS
ok      github.com/tchap/go-patricia/patricia   4.584s
$ go test
PASS
ok      github.com/tchap/go-patricia/patricia   5.005s
$ go test
--- FAIL: TestTrie_DeleteLeakageDense (0.00s)
    patricia_dense_test.go:213: Size=0, Total=1, Trie state:
        ab <nil>

    patricia_dense_test.go:214: Heap space leak, grew from 106576 to 108672 bytes
FAIL
exit status 1
FAIL    github.com/tchap/go-patricia/patricia   4.463s

Possible to access/query sub-tries?

I'm making use of go-patricia in a proposed new version of Hugo. I noticed that the Trie structure is recursive, but that fact isn't exposed to the public API. For example it would be powerful to be able to query a sub-Trie in the say way you can query the root Trie.

I don't have the time to deep dive into go-patricia's implementation, so I was hoping you could answer this for me: Is there any technical reason why sub-Trie's can't be exposed publically? Is there something about the implementation (e.g. the way the prefixes are represented) that requires all queries to be made from the root?

"module declares its path as" problem

Hello!
When i've try do import:
import "github.com/projectcalico/libcalico-go/lib/client"

>go mod tidy
go: finding module for package github.com/projectcalico/libcalico-go/lib/client
go: found github.com/projectcalico/libcalico-go/lib/client in github.com/projectcalico/libcalico-go v1.7.3
go: finding module for package github.com/kelseyhightower/envconfig
go: finding module for package github.com/sirupsen/logrus
go: finding module for package github.com/projectcalico/go-yaml-wrapper
go: finding module for package github.com/satori/go.uuid
go: finding module for package github.com/onsi/ginkgo/extensions/table
go: finding module for package github.com/onsi/ginkgo
go: finding module for package gopkg.in/go-playground/validator.v8
go: finding module for package github.com/onsi/gomega
go: finding module for package github.com/coreos/etcd/client
go: finding module for package github.com/coreos/etcd/pkg/transport
go: finding module for package golang.org/x/net/context
go: finding module for package k8s.io/apimachinery/pkg/apis/meta/v1
go: finding module for package k8s.io/apimachinery/pkg/fields
go: finding module for package k8s.io/apimachinery/pkg/runtime
go: finding module for package k8s.io/apimachinery/pkg/runtime/schema
go: finding module for package k8s.io/apimachinery/pkg/runtime/serializer
go: finding module for package k8s.io/apimachinery/pkg/util/intstr
go: finding module for package k8s.io/apimachinery/pkg/util/wait
go: finding module for package k8s.io/apimachinery/pkg/watch
go: finding module for package k8s.io/client-go/kubernetes
go: finding module for package k8s.io/client-go/pkg/api
go: finding module for package k8s.io/client-go/pkg/api/v1
go: finding module for package k8s.io/client-go/plugin/pkg/client/auth
go: finding module for package k8s.io/client-go/rest
go: finding module for package k8s.io/client-go/tools/cache
go: finding module for package k8s.io/client-go/tools/clientcmd
go: finding module for package gopkg.in/tchap/go-patricia.v2/patricia
go: finding module for package k8s.io/apimachinery/pkg/api/errors
go: found github.com/kelseyhightower/envconfig in github.com/kelseyhightower/envconfig v1.4.0
go: found github.com/projectcalico/go-yaml-wrapper in github.com/projectcalico/go-yaml-wrapper v0.0.0-20191112210931-090425220c54
go: found github.com/satori/go.uuid in github.com/satori/go.uuid v1.2.0
go: found github.com/sirupsen/logrus in github.com/sirupsen/logrus v1.8.1
go: found gopkg.in/go-playground/validator.v8 in gopkg.in/go-playground/validator.v8 v8.18.2
go: found github.com/onsi/ginkgo in github.com/onsi/ginkgo v1.16.4
go: found github.com/onsi/ginkgo/extensions/table in github.com/onsi/ginkgo v1.16.4
go: found github.com/onsi/gomega in github.com/onsi/gomega v1.13.0
go: found github.com/coreos/etcd/client in github.com/coreos/etcd v3.3.25+incompatible
go: found github.com/coreos/etcd/pkg/transport in github.com/coreos/etcd v3.3.25+incompatible
go: found golang.org/x/net/context in golang.org/x/net v0.0.0-20210614182718-04defd469f4e
go: found k8s.io/apimachinery/pkg/apis/meta/v1 in k8s.io/apimachinery v0.21.1
go: found k8s.io/apimachinery/pkg/fields in k8s.io/apimachinery v0.21.1
go: found k8s.io/apimachinery/pkg/runtime in k8s.io/apimachinery v0.21.1
go: found k8s.io/apimachinery/pkg/runtime/schema in k8s.io/apimachinery v0.21.1
go: found k8s.io/apimachinery/pkg/runtime/serializer in k8s.io/apimachinery v0.21.1
go: found k8s.io/apimachinery/pkg/util/intstr in k8s.io/apimachinery v0.21.1
go: found k8s.io/apimachinery/pkg/util/wait in k8s.io/apimachinery v0.21.1
go: found k8s.io/apimachinery/pkg/watch in k8s.io/apimachinery v0.21.1
go: found k8s.io/client-go/kubernetes in k8s.io/client-go v0.21.1
go: found k8s.io/client-go/plugin/pkg/client/auth in k8s.io/client-go v0.21.1
go: found k8s.io/client-go/rest in k8s.io/client-go v0.21.1
go: found k8s.io/client-go/tools/cache in k8s.io/client-go v0.21.1
go: found k8s.io/client-go/tools/clientcmd in k8s.io/client-go v0.21.1
go: found gopkg.in/tchap/go-patricia.v2/patricia in gopkg.in/tchap/go-patricia.v2 v2.3.1
go: found k8s.io/apimachinery/pkg/api/errors in k8s.io/apimachinery v0.21.1
go: calicoget imports
        github.com/projectcalico/libcalico-go/lib/client imports
        github.com/projectcalico/libcalico-go/lib/backend imports
        github.com/projectcalico/libcalico-go/lib/backend/etcd imports
        github.com/projectcalico/libcalico-go/lib/hwm imports
        gopkg.in/tchap/go-patricia.v2/patricia: gopkg.in/tchap/[email protected]: parsing go.mod:
        module declares its path as: github.com/tchap/go-patricia/v2
                but was required as: gopkg.in/tchap/go-patricia.v2

Look like some problems with import module. TY

put function should copy Prefix

Prefix is a named type of []byte, so passing it to put function (called by Set and Insert) passes a reference to the slice value. put should make a copy of the key:

    t := patricia.NewTrie()

    key := patricia.Prefix("foo")
    t.Insert(key, true)

    // alter the key slice
    key[0] = 'b'

    fmt.Println("boo key: ", t.Get(patricia.Prefix("boo")))
    fmt.Println("foo key: ", t.Get(patricia.Prefix("foo")))

Output:

    boo key:  true
    foo key:  <nil>

Sending a pull request for a fix.

possible to make this into an lru cache with fixed size? so that it can automatically remove items based on fifo

possible to make this into an lru cache with fixed size? so that it can automatically remove items based on fifo
how does this compare with art?
https://github.com/plar/go-adaptive-radix-tree
any benchmarks on speed and mem storage size used?

The gopkg.in import path is incorretct

The readme says: to import the "gopkg.in/tchap/go-patricia.v2/patricia" but the go.mod declares the package as "github.com/tchap/go-patricia/v2". When using this module as a dependency and doing go mod tidy, I get this error:

go: github.com/monzo/calico-accountant/watch imports
	github.com/projectcalico/libcalico-go/lib/client imports
	github.com/projectcalico/libcalico-go/lib/backend imports
	github.com/projectcalico/libcalico-go/lib/backend/etcd imports
	github.com/projectcalico/libcalico-go/lib/hwm imports
	gopkg.in/tchap/go-patricia.v2/patricia: gopkg.in/tchap/[email protected]: parsing go.mod:
	module declares its path as: github.com/tchap/go-patricia/v2
	        but was required as: gopkg.in/tchap/go-patricia.v2

Either remove the go.mod or provide proper instructions to require the v2.x.x version.

Build Status badge broken in the project main page

https://drone.io/ says "Coming Soon" - maybe for now just delete the badge? Or would it be possible to replace drone.io with travis-ci.org?

Tag v1.0.1

Hi again, would you mind to set tag v1.0.1 on last commit? :)

Testsuite fails with gccgo 6.1

The s390x (Mainframe) Docker CI runs with gccgo 6.1. Currently it fails because Docker updated its go-patricia from v2.1.0 to v2.2.4 (see issue moby/moby#25360).

While investigating the problem I found out that the go-patricia testsuite does not run for version 2.2.4 with gccgo 6.1 also on amd64:

Start gcc:6.1 image and get go-patricia code:

$ docker run -ti --rm gcc:6.1 bash
root@a0f013b0c10a:~# mkdir -p /root/go/src
root@a0f013b0c10a:~# cd /root/go/src
root@a0f013b0c10a:~/go/src# export GOPATH=/root/go
root@a0f013b0c10a:~/go/src# go get github.com/satori/go.uuid
root@a0f013b0c10a:~/go/src# git clone https://github.com/tchap/go-patricia.git github.com/tchap/go-patricia

Try with version 2.1.0 (works):

root@a0f013b0c10a:~/go/src# cd github.com/tchap/go-patricia/patricia && git checkout v2.1.0 && cd -
HEAD is now at d87fea6... Merge pull request #14 from ishidawataru/fix_walk
root@a0f013b0c10a:~/go/src# go test github.com/tchap/go-patricia/patricia
ok      github.com/tchap/go-patricia/patricia   4.646s

Try with version 2.2.4 (fails):

root@a0f013b0c10a:~/go/src# cd github.com/tchap/go-patricia/patricia && git checkout v2.2.4 && cd -
HEAD is now at 0d76659... Fix Delete memory leak and other bugs found
root@a0f013b0c10a:~# go test github.com/tchap/go-patricia/patricia

--- FAIL: TestTrie_DeleteLeakageDense (0.00s)
panic: runtime error: index out of range [recovered]
        panic: runtime error: index out of range


        :0

        :0

github_com_tchap_go_patricia_patricia.remove.pN53_github_com_tchap_go_patricia_patricia.sparseChildList
        /root/go/src/github.com/tchap/go-patricia/patricia/children.go:73
github_com_tchap_go_patricia_patricia.Delete.pN42_github_com_tchap_go_patricia_patricia.Trie
        /root/go/src/github.com/tchap/go-patricia/patricia/patricia.go:302
github_com_tchap_go_patricia_patricia.TestTrie_DeleteLeakageDense
        /root/go/src/github.com/tchap/go-patricia/patricia/patricia_dense_test.go:196

        :0

goroutine 16 [chan receive]:

        :0


created by main
        /usr/src/gcc/libgo/runtime/go-main.c:54

        :0

        :0

goroutine 17 [syscall]:
        goroutine in C code; stack unavailable

goroutine 18 [finalizer wait]:

goroutine 19 [GC sweep wait]:
        :0

        :0
FAIL    github.com/tchap/go-patricia/patricia   0.044s

The testsuite runs well with golang 1.7rc5.

I am not sure if this is a gccgo or patricia problem. Could you verify that there is no "index out of range" problem in children.go:73?

Version tag

Hi, would you mind to create version tag?
It provides your package to http://labix.org/gopkg.in, which is so cool for version fixing.

MatchSubtree and Match return different results when searching for non-existent data

First of all, thank you for this implementation. It really does 90% of what I'm looking for.

I have found that Match and MatchSubtree return different results. For example, if you have a trie that only has the value "A" and you try to search for "A extra", you would expect that no matter how you search, the result would be false. This is the case for MatchSubtree; it correctly returns false.

However, Match returns true! The trouble originates with Get (which is what Match is based on). If you try to Get("A extra") you will actually get back "A".

    trie := patricia.NewTrie()
    trie.Insert(patricia.Prefix("A"), 1)

    resultMatchSubtree := trie.MatchSubtree(patricia.Prefix("A extra"))
    resultMatch := trie.Match(patricia.Prefix("A extra"))

    fmt.Printf("resultMatch=%t, resultMatchSubtree=%t", resultMatch, resultMatchSubtree)

got:
resultMatch=true, resultMatchSubtree=false
want:
resultMatch=false, resultMatchSubtree=false

Is this expected behavior?

Trie seems to be completely broken when dense tries are needed

I did some debugging and started correcting some mistakes, but it seems like the implementation using dense tries might just be incomplete. I didn't want to spend too much time on the issue if that was the case (perhaps you have an uncommitted/unpushed working version on your HD).

Here is some input that will cause it to break (for me). Adding each string, line by line, to the trie, it breaks on the last line: http://pastebin.com/d7FUzqDi

tchap / go-patricia Goto Github PK

go-patricia's People

Contributors

Stargazers

Watchers

Forkers

go-patricia's Issues

Recommend Projects

Recommend Topics

Recommend Org