sauerbraten / radix Goto Github PK
View Code? Open in Web Editor NEWAn implementation of the radix tree data structure (http://en.wikipedia.org/wiki/Radix_tree).
An implementation of the radix tree data structure (http://en.wikipedia.org/wiki/Radix_tree).
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.
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.
What is the license for this code? I forked it and made (large) bunch of changes...
Hi,
I've added a FindPrefix. Are you happy with the impl?
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.
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.
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.
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.