[WIP] lazy revlog index parsing

[Greg Ward]

On 21 March 2012, Isaac Jurado said:
> On Wed, Mar 21, 2012 at 7:34 PM, Matt Mackall <mpm at selenic.com> wrote:
> >
> > For the record, Wikipedia's idea of what a radix tree is is completely
> > different than mine. Mine is more like this:
> >
> > https://lwn.net/Articles/175432/
> >
> > In other words, take a binary tree and make it 16-way. Then given a
> > hash prefix like "abcde", we do at most 5 steps before we find a tree
> > leaf node, discover it's not present, or discover it's ambiguous.
> 
> Also for the record.  If I understood correctly, those are called tries:
> 
>     http://en.wikipedia.org/wiki/Trie
> 
> Radix trees (or PATRICIA tries) are an space optimization of tries.  The
> structure mentioned in the LWN article is just a trie with a 64 symbol
> alphabet.

I just checked my undergrad data structures text book. It has one
brief reference to radix tries in an exercise, and they are much
closer to what that lwn.net article describes (and presumably what
Linux implements).

That Wikipedia article sounds like a reasonable description of
PATRICIA tries as I dimly recall reading about them once, but PATRICIA
tries != radix trees. I just found an article from 1990 that says a
PATRICIA tree is "technically a binary radix tree with one-way
branching removed", FWIW. (See
http://ece.ut.ac.ir/classpages/F83/Advanced%20Computer%20Networks/PAPERS/LOOKUP/routing.pdf).

>From the references in that article, I'm guessing either Sedgick or
Knuth describe radix trees ... but apparently I didn't take
sufficiently advanced data structures courses in school, since I don't
own either one. *sigh*

Anyways... radix trees sound like just the ticket for mapping
changeset IDs to revnums. Huh. And here I thought hash tables were the
One Final Data Structure, the answer to every problem, the be-all and
the end-all. ;-)

        Greg
-- 
Greg Ward                                http://www.gerg.ca/
This quote intentionally left blank.