Re: cvs commit: src/sys/dev/misc/streams streams.c src/sys/kern init_main.c kern_descrip.c sys_pipe.c uipc_syscalls.c vfs_syscalls.c src/sys/sys filedesc.h

[Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>]

:Lately Jeffrey Hsu <hsu@xxxxxxxxxxxxxxxxxxxxxxx> said:
:>   Modified files:
:>     sys/dev/misc/streams streams.c=20
:>     sys/kern             init_main.c kern_descrip.c sys_pipe.c=20
:>                          uipc_syscalls.c vfs_syscalls.c=20
:>     sys/sys              filedesc.h=20
:>   Log:
:>   Replace the linear search in file descriptor allocation with an O(log N)
:>   algorithm based on full in-place binary search trees augmented with
:>   subtree free file descriptor counts.
:
:yay! as i already said, very slick! yet, i think there could be more
:comments on how it works, i guess it's hard to grok the first time you
:look at the code...
:
:cheers
:  simon

    I gotta say this is a *very* slick algorithm, assuming the free file
    descriptor counts were implemented properly!  It would be nice if someone
    could write a file descriptor tester program which uses open(), close(),
    and dup2() to randomly populate and depopulate the file descriptor table,
    and makes sure that new open() calls actually do allocate the lowest
    numbered available file descriptor.

    It's not even N log N.  It's just log N.  Slick!  It is a far better
    algorithm then anything we or FreeBSD thought up before.

						-Matt