RE: On PATH_MAX

[Christopher Nelson]

> 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}=-