Closes #14 Closes #12

In recursiveWalk called by Walk and WalkPrefix, we were iterating over the edges of a node. The edges as well as the current node object itself (when mergeChild is called) can be modified by calls to Delete.

This commit modifies the loop to handle modifications correctly and prevent a nil pointer dereference panic in the case detailed in TestWalkDelete.

carries https://github.com/armon/go-radix/pull/12 closes https://github.com/armon/go-radix/pull/12

relates to https://github.com/moby/libnetwork/pull/2581

The purpose of replaceEdge func is to redirect current edge to a new node with common prefix.

So pass label and node directly instead of creating a new edge structure.

Rewrite addEdge to use binary search to insert the element in the already sorted slice.

Benchmark for Insert:

name       old time/op    new time/op    delta
Insert-16     624ns ± 4%     523ns ± 3%  -16.29%  (p=0.029 n=4+4)

name       old alloc/op   new alloc/op   delta
Insert-16      169B ± 0%      137B ± 0%  -18.93%  (p=0.029 n=4+4)

name       old allocs/op  new allocs/op  delta
Insert-16      4.00 ± 0%      3.00 ± 0%  -25.00%  (p=0.029 n=4+4)

Closes #15

Sorry for the drive by. This is a useful package and I've made extensive changes to my version. There is an easy performance improvement. If you like it, you can take it, no attribution necessary. If not, feel free to close with no further comment.

The numbers I quoted in the header are for benchmarks when 10,000 entries are added to a tree. The order of insertions doesn't matter. They can be ordered, unordered, and even reverse ordered. Always 28% fewer allocations occur.

The package requires the edges are kept sorted. Currently the addEdge method performs a full sort after appending the new edge. Using the same binary search other parts of the package use, the insertion point can be found exactly. The binary search is much more efficient than the sort.

Replace

func (n *node) addEdge(e edge) {
	n.edges = append(n.edges, e)
	n.edges.Sort()
}

with

func (n *node) addEdge(e edge) {
	num := len(n.edges)
	idx := sort.Search(num, func(i int) bool {
		return n.edges[i].label >= e.label
	})

	n.edges = append(n.edges, edge{})
	copy(n.edges[idx+1:], n.edges[idx:])
	n.edges[idx] = e
}

If a node is deleted from within the walk function, currently the recursive walk will panic if it then tries to go down that branch. Instead, terminate walking that branch.

I see that the implementation is recursive, but this isn't exposed in the public API. For example it would be powerful to get a reference to a sub-tree and then to be able to query it the same as the root tree.

I don't have the time to deep dive into the implementation, so I was hoping you could answer this for me: Is there any technical reason why non-root Nodes can't be exposed and queried like the root Node? Is there some quirk in the implementation that prevents this, that requires all queries to be made from the root?

Just ran

gofmt -w .

on the project root. That's all.

https://blog.golang.org/go-fmt-your-code

I made this PR with a project going on over at https://github.com/rotblauer/gofmt-att, and it's definitely a work in progress. So if I got something wrong, or this is annoying at all, please file an issue over there and we'll sort it out.

Hi,

Before anything, great package :+1:

I'm creating an personal web framework and I need to route my routes :smile:. I'm studying and find a possible solution, use radix tree, and found this package.

But I've a problem, how to route the path if I catch a path with parameters ?

Ex.:

package main

import (
	"fmt"

	radix "github.com/armon/go-radix"
)

func main() {

	r := radix.New()

	r.Insert("/a/b/c/:d", 1)
	r.Insert("/a/b/n/:d", 2)
	r.Insert("/a/t/u/:i", 2)

	m, _, _ := r.LongestPrefix("/a/b/c/test")

	fmt.Println(m) // Don't match path

}

In this scene this code not match my path, but should. Can you help me, it is possible to do?

Tks

We should never merge into the root node since it's assumed to be the empty string.

We need to check for deleting this node from the parent before we have potentially merged the node and its child. If we check after we've merged, it might be the case that the merged node has no children (in which case we don't want to delete it from the parent, since it's still a valid entry.)

This patch includes tests to check that we're handling these cases.

Hi, I had added ppc64le(Linux on Power) support on travis-ci in the branch and looks like its been successfully added. I believe it is ready for the final review and merge. The travis ci build logs can be verified from the link below.

https://travis-ci.com/github/ujjwalsh/go-radix/builds/188880895 Please have a look.

Regards, ujjwal