bin/51151: du hardlinkmatching is slow - fix included

[David Schultz]

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

From: David Schultz <das at FreeBSD.org>
To: Peter van Dijk <peter at dataloss.nl>
Cc: FreeBSD-gnats-submit at 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 ==.