Date: Sun, 20 Apr 2003 03:00:32 -0700 (PDT) From: David Schultz <das@FreeBSD.org> To: freebsd-bugs@FreeBSD.org Subject: Re: bin/51151: du hardlinkmatching is slow - fix included Message-ID: <200304201000.h3KA0WYk023513@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
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 ==.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200304201000.h3KA0WYk023513>