DragonFly commits List (threaded) for 2005-06
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
: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
:> 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...
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.