summaryrefslogtreecommitdiff
path: root/usr.bin/du
diff options
context:
space:
mode:
Diffstat (limited to 'usr.bin/du')
-rw-r--r--usr.bin/du/Makefile4
-rw-r--r--usr.bin/du/du.c197
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);
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-04 14:32:25 +0000