From owner-freebsd-bugs@FreeBSD.ORG  Sun Apr 20 03:00:32 2003
Return-Path: <owner-freebsd-bugs@FreeBSD.ORG>
Delivered-To: freebsd-bugs@hub.freebsd.org
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP id 9A38C37B401
	for <freebsd-bugs@hub.freebsd.org>;
	Sun, 20 Apr 2003 03:00:32 -0700 (PDT)
Received: from freefall.freebsd.org (freefall.freebsd.org [216.136.204.21])
	by mx1.FreeBSD.org (Postfix) with ESMTP id 423BC43FE0
	for <freebsd-bugs@hub.freebsd.org>;
	Sun, 20 Apr 2003 03:00:32 -0700 (PDT)
	(envelope-from gnats@FreeBSD.org)
Received: from freefall.freebsd.org (gnats@localhost [127.0.0.1])
	by freefall.freebsd.org (8.12.9/8.12.9) with ESMTP id h3KA0WUp023514
	for <freebsd-bugs@freefall.freebsd.org>;
	Sun, 20 Apr 2003 03:00:32 -0700 (PDT)
	(envelope-from gnats@freefall.freebsd.org)
Received: (from gnats@localhost)
	by freefall.freebsd.org (8.12.9/8.12.9/Submit) id h3KA0WYk023513;
	Sun, 20 Apr 2003 03:00:32 -0700 (PDT)
Date: Sun, 20 Apr 2003 03:00:32 -0700 (PDT)
Message-Id: <200304201000.h3KA0WYk023513@freefall.freebsd.org>
To: freebsd-bugs@FreeBSD.org
From: David Schultz <das@FreeBSD.org>
Subject: Re: bin/51151: du hardlinkmatching is slow - fix included
X-BeenThere: freebsd-bugs@freebsd.org
X-Mailman-Version: 2.1.1
Precedence: list
Reply-To: David Schultz <das@FreeBSD.org>
List-Id: Bug reports <freebsd-bugs.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-bugs>,
	<mailto:freebsd-bugs-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-bugs>
List-Post: <mailto:freebsd-bugs@freebsd.org>
List-Help: <mailto:freebsd-bugs-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-bugs>,
	<mailto:freebsd-bugs-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Sun, 20 Apr 2003 10:00:32 -0000

The following reply was made to PR bin/51151; it has been noted by GNATS.

From: David Schultz <das@FreeBSD.org>
To: Peter van Dijk <peter@dataloss.nl>
Cc: FreeBSD-gnats-submit@FreeBSD.org
Subject: Re: bin/51151: du hardlinkmatching is slow - fix included
Date: Sun, 20 Apr 2003 02:51:49 -0700

 On Sun, Apr 20, 2003, Peter van Dijk wrote:
 > On Sun, Apr 20, 2003 at 01:27:24AM -0700, David Schultz wrote:
 > > A hash table would be more appropriate here.  You could even
 > > preserve the original behavior of making infrequent calls to
 > > malloc() and most of the original code by using open addressing.
 > 
 > Yup, I'd prefer a hash too, but libc doesn't provide a suitable one,
 > so I figured giving this a shot was a viable option :)
 
 In libc, there are hcreate(3) and friends, which work nicely except
 for their limitation of one hash table per module.  That shouldn't
 be an issue here.  Alternatively, you could roll your own easily
 enough.  Here's some pseudocode using chaining:
 
 	hval = hash(ino, dev);
 	for (p = table[hval]; p != NULL; p = p->next)
 		if (p->ino == ino && p->dev == dev)
 			return (1);
 	p = malloc(sizeof(hashent));
 	p->next = table[hval];
 	p->ino = ino;
 	p->dev = dev;
 	talbe[hval] = p;
 
 > > If you would like to revise this patch, I would be happy to help
 > > you get it committed.  You might also want to take a look at
 > > style(9).
 
 At a glance, just the whitespace around = and ==.