- use fmt_scaled(3) instead of home grown function to print -h numbers

- do not use a linear list to keep track of inodes with link count > 2,
  use a red & black tree. Based on freebsd code that uses auto-sizing
  hash maps; this tree version by canacar@.

ok millert@ canacar@

2 files changed, 133 insertions, 68 deletions

diff --git a/usr.bin/du/Makefile b/usr.bin/du/Makefile
index 2cf1ff724eb..feb644de139 100644
--- a/usr.bin/du/Makefile
+++ b/usr.bin/du/Makefile
@@ -1,5 +1,7 @@
-#	$OpenBSD: Makefile,v 1.3 1997/09/21 11:48:54 deraadt Exp $
+#	$OpenBSD: Makefile,v 1.4 2004/06/14 18:21:31 otto Exp $
 
 PROG=	du
+DPADD= ${LIBUTIL}
+LDADD= -lutil
 
 .include <bsd.prog.mk>
diff --git a/usr.bin/du/du.c b/usr.bin/du/du.c
index 433bb896159..a59a191eff8 100644
--- a/usr.bin/du/du.c
+++ b/usr.bin/du/du.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: du.c,v 1.15 2004/06/02 14:58:46 tom Exp $	*/
+/*	$OpenBSD: du.c,v 1.16 2004/06/14 18:21:31 otto Exp $	*/
 /*	$NetBSD: du.c,v 1.11 1996/10/18 07:20:35 thorpej Exp $	*/
 
 /*
@@ -43,7 +43,7 @@ static char copyright[] =
 #if 0
 static char sccsid[] = "@(#)du.c	8.5 (Berkeley) 5/4/95";
 #else
-static char rcsid[] = "$OpenBSD: du.c,v 1.15 2004/06/02 14:58:46 tom Exp $";
+static char rcsid[] = "$OpenBSD: du.c,v 1.16 2004/06/14 18:21:31 otto Exp $";
 #endif
 #endif /* not lint */
 
@@ -54,18 +54,16 @@ static char rcsid[] = "$OpenBSD: du.c,v 1.15 2004/06/02 14:58:46 tom Exp $";
 #include <err.h>
 #include <errno.h>
 #include <fts.h>
-#include <math.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
+#include <util.h>
 
-typedef enum { NONE = 0, KILO, MEGA, GIGA, TERA, PETA /* , EXA */ } unit_t;
 
 int	 linkchk(FTSENT *);
 void	 prtout(quad_t, char *, int);
 void	 usage(void);
-unit_t	 unit_adjust(double *);
 
 int
 main(int argc, char *argv[])
@@ -219,87 +217,152 @@ main(int argc, char *argv[])
 	exit(rval);
 }
 
-typedef struct _ID {
-	dev_t	dev;
-	ino_t	inode;
-} ID;
-
 int
 linkchk(FTSENT *p)
 {
-	static ID *files;
-	static int maxfiles, nfiles;
-	ID *fp, *start;
-	ino_t ino;
-	dev_t dev;
+	struct links_entry {
+		struct links_entry *next;
+		struct links_entry *previous;
+		int	 links;
+		dev_t	 dev;
+		ino_t	 ino;
+	};
+	static const size_t links_hash_initial_size = 8192;
+	static struct links_entry **buckets;
+	static struct links_entry *free_list;
+	static size_t number_buckets;
+	static unsigned long number_entries;
+	static char stop_allocating;
+	struct links_entry *le, **new_buckets;
+	struct stat *st;
+	size_t i, new_size;
+	int count, hash;
 
-	ino = p->fts_statp->st_ino;
-	dev = p->fts_statp->st_dev;
-	if ((start = files) != NULL)
-		for (fp = start + nfiles - 1; fp >= start; --fp)
-			if (ino == fp->inode && dev == fp->dev)
-				return (1);
+	st = p->fts_statp;
 
-	if (nfiles == maxfiles && (files = realloc((char *)files,
-	    (u_int)(sizeof(ID) * (maxfiles += 128)))) == NULL)
-		err(1, NULL);
-	files[nfiles].inode = ino;
-	files[nfiles].dev = dev;
-	++nfiles;
-	return (0);
-}
+	/* If necessary, initialize the hash table. */
+	if (buckets == NULL) {
+		number_buckets = links_hash_initial_size;
+		buckets = malloc(number_buckets * sizeof(buckets[0]));
+		if (buckets == NULL)
+			errx(1, "No memory for hardlink detection");
+		for (i = 0; i < number_buckets; i++)
+			buckets[i] = NULL;
+	}
 
-/*
- * "human-readable" output: use 3 digits max.--put unit suffixes at
- * the end.  Makes output compact and easy-to-read. 
- */
+	/* If the hash table is getting too full, enlarge it. */
+	if (number_entries > number_buckets * 10 && !stop_allocating) {
+		new_size = number_buckets * 2;
+		new_buckets = malloc(new_size * sizeof(struct links_entry *));
+		count = 0;
 
-unit_t
-unit_adjust(double *val)
-{
-	double abval;
-	unit_t unit;
+		/* Try releasing the free list to see if that helps. */
+		if (new_buckets == NULL && free_list != NULL) {
+			while (free_list != NULL) {
+				le = free_list;
+				free_list = le->next;
+				free(le);
+			}
+			new_buckets = malloc(new_size * sizeof(new_buckets[0]));
+		}
+
+		if (new_buckets == NULL) {
+			stop_allocating = 1;
+			warnx("No more memory for tracking hard links");
+		} else {
+			memset(new_buckets, 0,
+			    new_size * sizeof(struct links_entry *));
+			for (i = 0; i < number_buckets; i++) {
+				while (buckets[i] != NULL) {
+					/* Remove entry from old bucket. */
+					le = buckets[i];
+					buckets[i] = le->next;
 
-	abval = fabs(*val);
-	if (abval < 1024)
-		unit = NONE;
-	else if (abval < 1048576ULL) {
-		unit = KILO;
-		*val /= 1024;
-	} else if (abval < 1073741824ULL) {
-		unit = MEGA;
-		*val /= 1048576;
-	} else if (abval < 1099511627776ULL) {
-		unit = GIGA;
-		*val /= 1073741824ULL;
-	} else if (abval < 1125899906842624ULL) {
-		unit = TERA;
-		*val /= 1099511627776ULL;
-	} else /* if (abval < 1152921504606846976ULL) */ {
-		unit = PETA;
-		*val /= 1125899906842624ULL;
+					/* Add entry to new bucket. */
+					hash = (le->dev ^ le->ino) % new_size;
+
+					if (new_buckets[hash] != NULL)
+						new_buckets[hash]->previous =
+						    le;
+					le->next = new_buckets[hash];
+					le->previous = NULL;
+					new_buckets[hash] = le;
+				}
+			}
+			free(buckets);
+			buckets = new_buckets;
+			number_buckets = new_size;
+		}
 	}
-	return (unit);
+
+	/* Try to locate this entry in the hash table. */
+	hash = ( st->st_dev ^ st->st_ino ) % number_buckets;
+	for (le = buckets[hash]; le != NULL; le = le->next) {
+		if (le->dev == st->st_dev && le->ino == st->st_ino) {
+			/*
+			 * Save memory by releasing an entry when we've seen
+			 * all of it's links.
+			 */
+			if (--le->links <= 0) {
+				if (le->previous != NULL)
+					le->previous->next = le->next;
+				if (le->next != NULL)
+					le->next->previous = le->previous;
+				if (buckets[hash] == le)
+					buckets[hash] = le->next;
+				number_entries--;
+				/* Recycle this node through the free list */
+				if (stop_allocating) {
+					free(le);
+				} else {
+					le->next = free_list;
+					free_list = le;
+				}
+			}
+			return (1);
+		}
+	}
+
+	if (stop_allocating)
+		return (0);
+
+	/* Add this entry to the links cache. */
+	if (free_list != NULL) {
+		/* Pull a node from the free list if we can. */
+		le = free_list;
+		free_list = le->next;
+	} else
+		/* Malloc one if we have to. */
+		le = malloc(sizeof(struct links_entry));
+	if (le == NULL) {
+		stop_allocating = 1;
+		warnx("No more memory for tracking hard links");
+		return (0);
+	}
+	le->dev = st->st_dev;
+	le->ino = st->st_ino;
+	le->links = st->st_nlink - 1;
+	number_entries++;
+	le->next = buckets[hash];
+	le->previous = NULL;
+	if (buckets[hash] != NULL)
+		buckets[hash]->previous = le;
+	buckets[hash] = le;
+	return (0);
 }
 
 void
 prtout(quad_t size, char *path, int hflag)
 {
-	unit_t unit;
-	double bytes;
-
 	if (!hflag)
 		(void)printf("%lld\t%s\n", (long long)size, path);
 	else {
-		bytes = (double)size * 512.0;
-		unit = unit_adjust(&bytes);
+		char buf[FMT_SCALED_STRSIZE];
 
-		if (bytes == 0)
-			(void)printf("0B\t%s\n", path);
-		else if (bytes > 10)
-			(void)printf("%.0f%c\t%s\n", bytes, "BKMGTPE"[unit], path);
+		if (fmt_scaled(size * 512, buf) == 0)
+			(void)printf("%s\t%s\n", buf, path);
 		else
-			(void)printf("%.1f%c\t%s\n", bytes, "BKMGTPE"[unit], path);
+			(void)printf("%lld\t%s\n", (long long)size, path);
 	}
 }