RE: On PATH_MAX

[Jonathan S. Shapiro]

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.