> On Tue, 2005-11-08 at 12:09 -0700, Christopher Nelson wrote:
> > >
> > > On Tue, 2005-11-08 at 19:20 +0100, Michal Suchanek wrote:
> > >
> > > > Even if the compare operation is bound (ie there is a
> limit on the
> > > > length of the filename) I do not see how the EROS solution
> > > guaratees
> > > > any latency constraint. Searching a directory with 4G
> > > files can take
> > > > quite long.
> > >
> > > Not if you choose appropriate data structures for storage.
> >
> > For example, a balanced binary tree can reduce this to about 32
> > operations, max.
>
> Or a properly designed single-probe hash can reduce it to
> O(1). This is one of those cases where the binary tree isn't
> the right choice because of paging behavior.
>
Do you use a growing hash table that expands on collision? Otherwise I
find it hard to see how you can get an optimal hashing algorithm for
arbitrary strings... Any pointers to relevant information would be
great.
-={C}=-
_______________________________________________
L4-hurd mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/l4-hurd
