cvs commit: src/usr.bin/du du.c

[David Schultz]

On Sat, May 01, 2004, Dag-Erling Smrgrav wrote:
> Tim Kientzle <kientzle at FreeBSD.org> writes:
> >   Log:
> >   Speed up hardlink detection by using a self-sizing hash
> >   table rather than the old linear list search.
> 
> You know, this would be a lot easier with a plain old red-black tree.

...especially if we had a good red-black tree implementation in a
library (hint, hint).  At one of my former employers, virtually
nobody used AVL trees until one day when someone committed a
generic AVL tree implementation.  Within a few weeks after that,
people had found dozens of optimizations that involved replacing
linked lists with AVL trees.