From owner-cvs-src@FreeBSD.ORG  Fri Apr 30 19:46:34 2004
Return-Path: <owner-cvs-src@FreeBSD.ORG>
Delivered-To: cvs-src@freebsd.org
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP
	id C697916A4CE; Fri, 30 Apr 2004 19:46:34 -0700 (PDT)
Received: from VARK.homeunix.com (adsl-68-121-163-250.dsl.pltn13.pacbell.net
	[68.121.163.250])	by mx1.FreeBSD.org (Postfix) with ESMTP
	id 9831E43D45; Fri, 30 Apr 2004 19:46:34 -0700 (PDT)
	(envelope-from das@FreeBSD.ORG)
Received: from VARK.homeunix.com (localhost [127.0.0.1])
	by VARK.homeunix.com (8.12.10/8.12.10) with ESMTP id i412kLnx065198;
	Fri, 30 Apr 2004 19:46:21 -0700 (PDT)
	(envelope-from das@FreeBSD.ORG)
Received: (from das@localhost)
	by VARK.homeunix.com (8.12.10/8.12.10/Submit) id i412kKiV065197;
	Fri, 30 Apr 2004 19:46:20 -0700 (PDT)
	(envelope-from das@FreeBSD.ORG)
Date: Fri, 30 Apr 2004 19:46:15 -0700
From: David Schultz <das@FreeBSD.ORG>
To: "Dag-Erling =?us-ascii:iso-8859-1?Q?Sm=F8rgrav?=" <des@des.no>
Message-ID: <20040501024615.GC65015@VARK.homeunix.com>
Mail-Followup-To: "Dag-Erling =?us-ascii:iso-8859-1?Q?Sm=F8rgrav?="
	<des@des.no>,
	Tim Kientzle <kientzle@FreeBSD.ORG>, src-committers@FreeBSD.ORG,
	cvs-src@FreeBSD.ORG, cvs-all@FreeBSD.ORG
References: <200404301817.i3UIHprY005219@repoman.freebsd.org>
	<xzpfzal81nj.fsf@dwp.des.no>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <xzpfzal81nj.fsf@dwp.des.no>
cc: cvs-src@FreeBSD.ORG
cc: Tim Kientzle <kientzle@FreeBSD.ORG>
cc: src-committers@FreeBSD.ORG
cc: cvs-all@FreeBSD.ORG
Subject: Re: cvs commit: src/usr.bin/du du.c
X-BeenThere: cvs-src@freebsd.org
X-Mailman-Version: 2.1.1
Precedence: list
List-Id: CVS commit messages for the src tree <cvs-src.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/cvs-src>,
	<mailto:cvs-src-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/cvs-src>
List-Post: <mailto:cvs-src@freebsd.org>
List-Help: <mailto:cvs-src-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/cvs-src>,
	<mailto:cvs-src-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Sat, 01 May 2004 02:46:34 -0000

On Sat, May 01, 2004, Dag-Erling Smrgrav wrote:
> Tim Kientzle <kientzle@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.