Re: you are in an fs with millions of small files

On Wed, 2005-Jun-08 11:27:27 +0300, Giorgos Keramidas wrote:
>On 2005-06-08 11:03, Giorgos Keramidas <keramida_at_freebsd.org> wrote:
>>> The comparison function is known at the time the directory entries are
>>> read, so it should be a simple matter to read them into a red-black
>>> tree instead of a singly- linked list.  I'm working on a patch.
>>
>> Thanks :)
>
>This would require updates/changes to all the users of fts.h too?

That would seem to depend on how public the innards of FTS and FTSENT
are supposed to be.  Whilst <fts.h> refers to singly linked lists and
pointers to arrays, consumers are not supposed to allocate either
structure themselves and only traverse the list via fts_read() or
fts_children() - and only ls(1), mtree(8) and ctm_dequeue(1) use
fts_children().

At first glance, it should be fairly easy to change the underlying
representation from a linked list to a red-black tree without
affecting the API at all.

-- 
Peter Jeremy