sauerbraten / radix Goto Github PK

Specifially meant towards @miekg: Since you forked it, I can make changes without asking now I guess? License will stay the same?

EDIT: Just saw he's no longer collaborator.

I think we should include a Get() method returning the actual value or nil, to simplify usage of the package as data storage. Right now you have to do Find(), then check that this did not return nil, and if it really is not nil, you can acces Value, else you get a nil pointer dereference.
Your thoughts on this?

Edit: Also maybe rename Find() to GetNode() or GetSubRadix() or something, because that's what it actually does. Find() to me would mean: returns a bool, true if key is included in radix.

What is the license for this code? I forked it and made (large) bunch of changes...

I noticed that each node uses byte to point to children nodes; any reason for byte over rune? With the current implementation, storing multi-byte characters will use more nodes.

Hi,

I've created an Iter() function, which I need in code using this radix tree, i.e I want to be able to "walk the tree" and do something with each node. See https://github.com/miekg/dns/blob/dev/zone.go for instance.

The problem I have now is that Iter() works and return *Radix, but each *Radix.key is only partial (that's the beauty of radix tree), but I need the full key... Any bright ideas on how to proceed? May a func (r *Radix) FullKey() function or something?

If this works, we can drop FindKey and let Find return an *Radix. Value needs to be exported again, so callers can see/modify it.

So as you can I added a Find benchmark to the test file. I also implemented a loop version of Find, didn't push it though (of course): http://pastie.org/private/ejdhtf1qhhey62ahwxteya. What I found is: the implementation are nearly the same speed, both around 200ns/op on my i5.

Now, for a copy-on-write tree, a loop implementation of Insert() would be more efficient anyway, provided that we do not want to have a pointer to the parent node and that we can efficiently record the path walking down the tree when using a loop.

I propose a cow branch that uses loop implementations, and we keep the current recursive version for now. If the copy-on-write version is satisfying, we can still merge back into master.

Hi,

I've added a FindPrefix. Are you happy with the impl?

To be really (really) useful a copy-on-write variant of radix would be nice. It will probably need a parental pointer in each node and ofcourse code that deals with the copy-on-write part.