On Thu, 8 Sep 2005, Chuck Lever wrote:
> >
> > Btw, in the sparse project, we have this really smart "pointer list" data
> > structure, which is extremely space- and time-efficient. It ends up
> > _looking_ like a linked list, but it batches things up in hunks of 29
> > entries (29 pointers plus overhead gives you blocks of 32 longwords, which
> > is the allocation size) and thus gives basically a cache-friendly
> > doubly-linked list. It knows how to do insertions, traversals etc very
> > efficiently.
> >
> > Any interest?
>
> i'm not married to splay trees. i think we should explore several
> different data structures before picking one, and this one sounds
> reasonable to try.
Actually, I just realized that one of the issues is just plain looking up
a name (ie "pos = cache_name_pos(..)", and the sparse list don't make that
very efficient unless you have a good starting point.
So a splay tree is probably more appropriate.
Linus
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
