changeset 565:44abf4d901f3

Rewrite dirtree so we don't need readdir, scandir, and fts.h. Rewrite ls (from scratch) to use new dirtree infrastructure. (This breaks everything else that currently uses dirtree.)
author Rob Landley <rob@landley.net>
date Sat, 14 Apr 2012 22:30:41 -0500
parents 9530899eee51
children 05617db1a337
files lib/dirtree.c lib/lib.c lib/lib.h toys/cp.c toys/ls.c toys/mke2fs.c
diffstat 6 files changed, 472 insertions(+), 274 deletions(-) [+]
line wrap: on
line diff
--- a/lib/dirtree.c	Sat Apr 14 21:43:24 2012 -0500
+++ b/lib/dirtree.c	Sat Apr 14 22:30:41 2012 -0500
@@ -6,85 +6,150 @@
 
 #include "toys.h"
 
-// NOTE: This uses toybuf.  Possibly it shouldn't do that.
+// Create a dirtree node from a path, with stat and symlink info.
 
-// Create a dirtree node from a path.
+struct dirtree *dirtree_add_node(int dirfd, char *name)
+{
+	struct dirtree *dt = NULL;
+	struct stat st;
+	char buf[4096];
+	int len = 0, linklen = 0;
 
-struct dirtree *dirtree_add_node(char *path)
-{
-	struct dirtree *dt;
-	char *name;
+	if (name) {
+		if (fstatat(dirfd, name, &st, AT_SYMLINK_NOFOLLOW)) goto error;
+		if (S_ISLNK(st.st_mode)) {
+			if (0>(linklen = readlinkat(dirfd, name, buf, 4095))) goto error;
+			buf[linklen++]=0;
+		}
+		len = strlen(name);
+	}
+   	dt = xzalloc((len = sizeof(struct dirtree)+len+1)+linklen);
+	if (name) {
+		memcpy(&(dt->st), &st, sizeof(struct stat));
+		strcpy(dt->name, name);
 
-	// Find last chunk of name.
-
-	for (;;) {
-		name = strrchr(path, '/');
-
-		if (!name) name = path;
-		else {
-			if (*(name+1)) name++;
-			else {
-				*name=0;
-				continue;
-			}
+		if (linklen) {
+			dt->symlink = memcpy(len+(char *)dt, buf, linklen);
+			dt->data = --linklen;
 		}
-		break;
 	}
 
-   	dt = xzalloc(sizeof(struct dirtree)+strlen(name)+1);
-	if (lstat(path, &(dt->st))) {
-		error_msg("Skipped '%s'",name);
-		free(dt);
-		return 0;
-	}
-	strcpy(dt->name, name);
+	return dt;
 
-	return dt;
+error:
+	perror_msg("%s",name);
+	free(dt);
+	return 0;
 }
 
-// Given a directory (in a writeable PATH_MAX buffer), recursively read in a
-// directory tree.
+// Return path to this node.
+
+char *dirtree_path(struct dirtree *node, int *plen)
+{
+	char *path;
+	int len;
+
+	if (!node || !node->name) return xmalloc(*plen);
+
+	len = (plen ? *plen : 0) + strlen(node->name)+1;
+	path = dirtree_path(node->parent, &len);
+	len = plen ? *plen : 0;
+	if (len) path[len++]='/';
+	strcpy(path+len, node->name);
+
+	return path;
+}
+
+// Default callback, filters out "." and "..".
+
+int dirtree_isdotdot(struct dirtree *catch)
+{
+	// Should we skip "." and ".."?
+	if (catch->name[0]=='.' && (!catch->name[1] ||
+			(catch->name[1]=='.' && !catch->name[2])))
+				return DIRTREE_NOSAVE|DIRTREE_NORECURSE;
+
+	return 0;
+}
+
+// Handle callback for a node in the tree. Returns saved node(s) or NULL.
 //
-// If callback==NULL, allocate tree of struct dirtree and
-// return root of tree.  Otherwise call callback(node) on each hit, free
+// By default, allocates a tree of struct dirtree, not following symlinks
+// If callback==NULL, or callback always returns 0, allocate tree of struct
+// dirtree and return root of tree.  Otherwise call callback(node) on each hit, free
 // structures after use, and return NULL.
+//
 
-struct dirtree *dirtree_read(char *path, struct dirtree *parent,
-					int (*callback)(char *path, struct dirtree *node))
+struct dirtree *handle_callback(struct dirtree *new,
+					int (*callback)(struct dirtree *node))
 {
-	struct dirtree *dtroot = NULL, *this, **ddt = &dtroot;
-	DIR *dir;
-	int len = strlen(path);
+	int flags;
 
-	if (!(dir = opendir(path))) perror_msg("No %s", path);
-	else for (;;) {
-		int norecurse = 0;
-		struct dirent *entry = readdir(dir);
-		if (!entry) {
-			closedir(dir);
-			break;
+	if (!callback) callback = dirtree_isdotdot;
+
+	flags = callback(new);
+	if (S_ISDIR(new->st.st_mode)) {
+		if (!(flags & DIRTREE_NORECURSE)) {
+			new->data = openat(new->data, new->name, 0);
+			dirtree_recurse(new, callback);
 		}
-
-		// Skip "." and ".."
-		if (entry->d_name[0]=='.') {
-			if (!entry->d_name[1]) continue;
-			if (entry->d_name[1]=='.' && !entry->d_name[2]) continue;
-		}
-
-		snprintf(path+len, sizeof(toybuf)-len, "/%s", entry->d_name);
-		*ddt = this = dirtree_add_node(path);
-		if (!this) continue;
-		this->parent = parent;
-		this->depth = parent ? parent->depth + 1 : 1;
-		if (callback) norecurse = callback(path, this);
-		if (!norecurse && S_ISDIR(this->st.st_mode))
-			this->child = dirtree_read(path, this, callback);
-		if (callback) free(this);
-		else ddt = &(this->next);
-		path[len]=0;
+		new->data = -1;
+		if (flags & DIRTREE_COMEAGAIN) flags = callback(new);
+	}
+	// If this had children, it was callback's job to free them already.
+	if (flags & DIRTREE_NOSAVE) {
+		free(new);
+		new = NULL;
 	}
 
-	return dtroot;
+	return (flags & DIRTREE_ABORT)==DIRTREE_ABORT ? DIRTREE_ABORTVAL : new;
 }
 
+// Recursively read/process children of directory node (with dirfd in data),
+// filtering through callback().
 
+void dirtree_recurse(struct dirtree *node,
+					int (*callback)(struct dirtree *node))
+{
+	struct dirtree *new, **ddt = &(node->child);
+	struct dirent *entry;
+	DIR *dir;
+	int dirfd;
+
+	if (!(dir = fdopendir(node->data))) {
+		char *path = dirtree_path(node, 0);
+		perror_msg("No %s", path);
+		free(path);
+		close(node->data);
+	}
+	// Dunno if I really need to do this, but the fdopendir man page insists
+	dirfd = xdup(node->data);
+
+	// The extra parentheses are to shut the stupid compiler up.
+	while ((entry = readdir(dir))) {
+		if (!(new = dirtree_add_node(dirfd, entry->d_name))) continue;
+		new->parent = node;
+		new = handle_callback(new, callback);
+		if (new == DIRTREE_ABORTVAL) break;
+		if (new) {
+			*ddt = new;
+			ddt = &((*ddt)->next);
+		}
+	}
+
+	closedir(dir);
+	close(dirfd);
+}
+
+// Create dirtree from path, using callback to filter nodes.
+// If callback == NULL allocate a tree of struct dirtree nodes and return
+// pointer to root node.
+
+struct dirtree *dirtree_read(char *path, int (*callback)(struct dirtree *node))
+{
+	int fd = open(".", 0);
+	struct dirtree *root = dirtree_add_node(fd, path);
+	root->data = fd;
+
+	return handle_callback(root, callback);
+}
--- a/lib/lib.c	Sat Apr 14 21:43:24 2012 -0500
+++ b/lib/lib.c	Sat Apr 14 22:30:41 2012 -0500
@@ -208,6 +208,13 @@
 	if (close(fd)) perror_exit("xclose");
 }
 
+int xdup(int fd)
+{
+	fd = dup(fd);
+	if (fd == -1) perror_exit("xdup");
+	return fd;
+}
+
 // Die unless we can open/create a file, returning FILE *.
 FILE *xfopen(char *path, char *mode)
 {
@@ -497,6 +504,16 @@
 	return val;
 }
 
+int numlen(long l)
+{
+    int len = 0;
+    while (l) {
+       l /= 10;
+       len++;
+    }
+    return len;
+}
+
 // Return how long the file at fd is, if there's any way to determine it.
 off_t fdlength(int fd)
 {
--- a/lib/lib.h	Sat Apr 14 21:43:24 2012 -0500
+++ b/lib/lib.h	Sat Apr 14 22:30:41 2012 -0500
@@ -17,6 +17,9 @@
 
 // llist.c
 
+// All these list types can be handled by the same code because first element
+// is always next pointer, so next = (mytype *)&struct.
+
 struct string_list {
 	struct string_list *next;
 	char str[0];
@@ -28,8 +31,7 @@
 };
 
 struct double_list {
-	struct double_list *next;
-	struct double_list *prev;
+	struct double_list *next, *prev;
 	char *data;
 };
 
@@ -42,16 +44,40 @@
 void get_optflags(void);
 
 // dirtree.c
+
+// Values returnable from callback function (bitfield, or them together)
+// Default with no callback is 0
+
+// Do not add this node to the tree
+#define DIRTREE_NOSAVE       1
+// Do not recurse into children
+#define DIRTREE_NORECURSE    2
+// Call again after handling all children (Directories only. Sets linklen = -1)
+#define DIRTREE_COMEAGAIN    4
+// Follow symlinks to directories
+#define DIRTREE_SYMFOLLOW    8
+// Abort recursive dirtree.  (Forces NOSAVE and NORECURSE on this entry.)
+#define DIRTREE_ABORT      (256|DIRTREE_NOSAVE|DIRTREE_NORECURSE)
+
+#define DIRTREE_ABORTVAL ((struct dirtree *)1)
+
 struct dirtree {
-	struct dirtree *next, *child, *parent;
+	struct dirtree *next, *parent, *child;
+	long extra; // place for user to store their stuff (can be pointer)
+	long data;  // dirfd for directory, linklen for symlink
 	struct stat st;
-	int depth;
+	char *symlink;
 	char name[];
 };
 
-struct dirtree *dirtree_add_node(char *path);
-struct dirtree *dirtree_read(char *path, struct dirtree *parent,
-                    int (*callback)(char *path, struct dirtree *node));
+struct dirtree *dirtree_add_node(int dirfd, char *name);
+char *dirtree_path(struct dirtree *node, int *plen);
+int dirtree_isdotdot(struct dirtree *catch);
+struct dirtree *handle_callback(struct dirtree *new,
+	int (*callback)(struct dirtree *node));
+void dirtree_recurse(struct dirtree *node,
+	int (*callback)(struct dirtree *node));
+struct dirtree *dirtree_read(char *path, int (*callback)(struct dirtree *node));
 
 // lib.c
 void xstrcpy(char *dest, char *src, size_t size);
@@ -76,6 +102,7 @@
 int xcreate(char *path, int flags, int mode);
 int xopen(char *path, int flags);
 void xclose(int fd);
+int xdup(int fd);
 FILE *xfopen(char *path, char *mode);
 ssize_t readall(int fd, void *buf, size_t len);
 ssize_t writeall(int fd, void *buf, size_t len);
@@ -97,6 +124,7 @@
 char *utoa(unsigned n);
 char *itoa(int n);
 long atolx(char *c);
+int numlen(long l);
 off_t fdlength(int fd);
 char *xreadlink(char *name);
 void loopfiles_rw(char **argv, int flags, int permissions, int failok,
--- a/toys/cp.c	Sat Apr 14 21:43:24 2012 -0500
+++ b/toys/cp.c	Sat Apr 14 22:30:41 2012 -0500
@@ -10,8 +10,8 @@
 USE_CP(NEWTOY(cp, "<2vslrR+rdpa+d+p+rHLPif", TOYFLAG_BIN))
 
 config CP
-	bool "cp"
-	default y
+	bool "cp (broken by dirtree changes)"
+	default n
 	help
 	  usage: cp -fiprdal SOURCE... DEST
 
@@ -128,8 +128,9 @@
 
 // Callback from dirtree_read() for each file/directory under a source dir.
 
-int cp_node(char *path, struct dirtree *node)
+int cp_node(struct dirtree *node)
 {
+	char *path = dirtree_path(node, 0); // TODO: use openat() instead
 	char *s = path+strlen(path);
 	struct dirtree *n;
 
@@ -148,6 +149,7 @@
 	s = xmsprintf("%s/%s", TT.destname, s);
 	cp_file(path, s, &(node->st));
 	free(s);
+	free(path); // redo this whole darn function.
 
 	return 0;
 }
@@ -209,7 +211,7 @@
 				TT.keep_symlinks++;
 				strncpy(toybuf, src, sizeof(toybuf)-1);
 				toybuf[sizeof(toybuf)-1]=0;
-				dirtree_read(toybuf, NULL, cp_node);
+				dirtree_read(toybuf, cp_node);
 			} else error_msg("Skipped dir '%s'", src);
 		} else cp_file(src, dst, &st);
 		if (TT.destisdir) free(dst);
--- a/toys/ls.c	Sat Apr 14 21:43:24 2012 -0500
+++ b/toys/ls.c	Sat Apr 14 22:30:41 2012 -0500
@@ -3,16 +3,17 @@
  * ls.c - list files
  *
  * Copyright 2012 Andre Renaud <andre@bluewatersys.com>
+ * Copyright 2012 Rob Landley <rob@landley.net>
  *
  * See http://pubs.opengroup.org/onlinepubs/9699919799/utilities/ls.html
 
-USE_LS(NEWTOY(ls, "AnRlF1a", TOYFLAG_BIN))
+USE_LS(NEWTOY(ls, "ACFHLRSacdfiklmnpqrstux1", TOYFLAG_BIN))
 
 config LS
 	bool "ls"
-	default n
+	default y
 	help
-	  usage: ls [-lFaA1] [directory...]
+	  usage: ls [-ACFHLRSacdfiklmnpqrstux1] [directory...]
 	  list files
 
           -1    list one file per line
@@ -24,209 +25,294 @@
 
 #include "toys.h"
 
-#define FLAG_a 1
-#define FLAG_1 2
-#define FLAG_F 4
-#define FLAG_l 8
-#define FLAG_R 16
-#define FLAG_n 32
-#define FLAG_A 64
+#define FLAG_1 (1<<0)
+//#define FLAG_x (1<<1)
+//#define FLAG_u (1<<2)
+//#define FLAG_t (1<<3)
+//#define FLAG_s (1<<4)
+//#define FLAG_r (1<<5)
+//#define FLAG_q (1<<6)
+#define FLAG_p (1<<7)
+//#define FLAG_n (1<<8)
+#define FLAG_m (1<<9)
+#define FLAG_l (1<<10)
+//#define FLAG_k (1<<11)
+#define FLAG_i (1<<12)
+#define FLAG_f (1<<13)
+#define FLAG_d (1<<14)
+//#define FLAG_c (1<<15)
+#define FLAG_a (1<<16)
+//#define FLAG_S (1<<17)
+#define FLAG_R (1<<18)
+//#define FLAG_L (1<<19)
+//#define FLAG_H (1<<20)
+#define FLAG_F (1<<21)
+//#define FLAG_C (1<<21)
+#define FLAG_A (1<<22)
 
-static int dir_filter(const struct dirent *d)
+// test sst output (suid/sticky in ls flaglist)
+
+// ls -lR starts .: then ./subdir:
+
+DEFINE_GLOBALS(
+  struct dirtree *files;
+
+  unsigned width;
+  int again;
+)
+
+#define TT this.ls
+
+void dlist_to_dirtree(struct dirtree *parent)
 {
-    /* Skip over all '.*' entries, unless -a is given */
-    if (!(toys.optflags & FLAG_a)) {
-        /* -A means show everything except the . & .. entries */
-        if (toys.optflags & FLAG_A) {
-            if (strcmp(d->d_name, ".") == 0 ||
-                strcmp(d->d_name, "..") == 0)
-                return 0;
-        } else if (d->d_name[0] == '.')
-            return 0;
-    }
-    return 1;
-}
-
-static void do_ls(int fd, char *name)
-{
-    struct dirent **entries;
-    int nentries;
-    int i;
-    int maxwidth = -1;
-    int ncolumns = 1;
-    struct dirent file_dirent;
-    struct dirent *file_direntp;
-
-    if (!name || strcmp(name, "-") == 0)
-        name = ".";
-
-    if (toys.optflags & FLAG_R)
-        xprintf("\n%s:\n", name);
-
-    /* Get all the files in this directory */
-    nentries = scandir(name, &entries, dir_filter, alphasort);
-    if (nentries < 0) {
-        /* We've just selected a single file, so create a single-length list */
-        /* FIXME: This means that ls *.x results in a whole bunch of single
-         * listings, not one combined listing.
-         */
-        if (errno == ENOTDIR) {
-            nentries = 1;
-            strcpy(file_dirent.d_name, name);
-            file_direntp = &file_dirent;
-            entries = &file_direntp;
-        } else 
-            perror_exit("ls: cannot access %s'", name);
-    }
-
-
-    /* Determine the widest entry so we can flow them properly */
-    if (!(toys.optflags & FLAG_1)) {
-        int columns;
-        char *columns_str;
-
-        for (i = 0; i < nentries; i++) {
-            struct dirent *ent = entries[i];
-            int width;
-
-            width = strlen(ent->d_name);
-            if (width > maxwidth)
-                maxwidth = width;
-        }
-        /* We always want at least a single space for each entry */
-        maxwidth++;
-        if (toys.optflags & FLAG_F)
-            maxwidth++;
-
-        columns_str = getenv("COLUMNS");
-        columns = columns_str ? atoi(columns_str) : 80;
-        ncolumns = maxwidth ? columns / maxwidth : 1;
-    }
-
-    for (i = 0; i < nentries; i++) {
-        struct dirent *ent = entries[i];
-        int len = strlen(ent->d_name);
-        struct stat st;
-        int stat_valid = 0;
-
-        sprintf(toybuf, "%s/%s", name, ent->d_name);
-
-        /* Provide the ls -l long output */
-        if (toys.optflags & FLAG_l) {
-            char type;
-            char timestamp[64];
-            struct tm mtime;
-
-            if (lstat(toybuf, &st))
-                perror_exit("Can't stat %s", toybuf);
-            stat_valid = 1;
-            if (S_ISDIR(st.st_mode))
-                type = 'd';
-            else if (S_ISCHR(st.st_mode))
-                type = 'c';
-            else if (S_ISBLK(st.st_mode))
-                type = 'b';
-            else if (S_ISLNK(st.st_mode))
-                type = 'l';
-            else
-                type = '-';
-
-            xprintf("%c%c%c%c%c%c%c%c%c%c ", type,
-                (st.st_mode & S_IRUSR) ? 'r' : '-',
-                (st.st_mode & S_IWUSR) ? 'w' : '-',
-                (st.st_mode & S_IXUSR) ? 'x' : '-',
-                (st.st_mode & S_IRGRP) ? 'r' : '-',
-                (st.st_mode & S_IWGRP) ? 'w' : '-',
-                (st.st_mode & S_IXGRP) ? 'x' : '-',
-                (st.st_mode & S_IROTH) ? 'r' : '-',
-                (st.st_mode & S_IWOTH) ? 'w' : '-',
-                (st.st_mode & S_IXOTH) ? 'x' : '-');
-
-            xprintf("%2d ", st.st_nlink);
-            if (toys.optflags & FLAG_n) {
-                xprintf("%4d ", st.st_uid);
-                xprintf("%4d ", st.st_gid);
-            } else {
-                struct passwd *pwd = getpwuid(st.st_uid);
-                struct group *grp = getgrgid(st.st_gid);
-                if (!pwd)
-                    xprintf("%4d ", st.st_uid);
-                else
-                    xprintf("%-10s ", pwd->pw_name);
-                if (!grp)
-                    xprintf("%4d ", st.st_gid);
-                else
-                    xprintf("%-10s ", grp->gr_name);
-            }
-            if (S_ISCHR(st.st_mode) || S_ISBLK(st.st_mode))
-                xprintf("%3d, %3d ", major(st.st_rdev), minor(st.st_rdev));
-            else
-                xprintf("%12lld ", st.st_size);
-
-            localtime_r(&st.st_mtime, &mtime);
-
-            strftime(timestamp, sizeof(timestamp), "%b %e %H:%M", &mtime);
-            xprintf("%s ", timestamp);
-        }
-
-        xprintf("%s", ent->d_name);
-
-        /* Append the file-type indicator character */
-        if (toys.optflags & FLAG_F) {
-            if (!stat_valid) {
-                if (lstat(toybuf, &st))
-                    perror_exit("Can't stat %s", toybuf);
-                stat_valid = 1;
-            }
-            if (S_ISDIR(st.st_mode)) {
-                xprintf("/");
-                len++;
-            } else if (S_ISREG(st.st_mode) &&
-                (st.st_mode & (S_IXUSR | S_IXGRP | S_IXOTH))) {
-                xprintf("*");
-                len++;
-            } else if (S_ISLNK(st.st_mode)) {
-                xprintf("@");
-                len++;
-            }
-        }
-        if (toys.optflags & FLAG_1) {
-            xprintf("\n");
-        } else {
-            if (i % ncolumns == ncolumns - 1)
-                xprintf("\n");
-            else
-                xprintf("%*s", maxwidth - len, "");
-        }
-    }
-    /* Make sure we put at a trailing new line in */
-    if (!(toys.optflags & FLAG_1) && (i % ncolumns))
-        xprintf("\n");
-
-    if (toys.optflags & FLAG_R) {
-        for (i = 0; i < nentries; i++) {
-            struct dirent *ent = entries[i];
-            struct stat st;
-            char dirname[PATH_MAX];
-
-            sprintf(dirname, "%s/%s", name, ent->d_name);
-            if (lstat(dirname, &st))
-                perror_exit("Can't stat %s", dirname);
-            if (S_ISDIR(st.st_mode))
-                do_ls(0, dirname);
+    // Turn double_list into dirtree
+    struct dirtree *dt = parent->child;
+    if (dt) {
+        dt->parent->next = NULL;
+        while (dt) {
+            dt->parent = parent;
+            dt = dt->next;
         }
     }
 }
 
+static char endtype(struct stat *st)
+{
+    mode_t mode = st->st_mode;
+    if ((toys.optflags&(FLAG_F|FLAG_p)) && S_ISDIR(mode)) return '/';
+    if (toys.optflags & FLAG_F) {
+        if (S_ISLNK(mode) && !(toys.optflags & FLAG_F)) return '@';
+        if (S_ISREG(mode) && (mode&0111)) return '*';
+        if (S_ISFIFO(mode)) return '|';
+        if (S_ISSOCK(mode)) return '=';
+    }
+    return 0;
+}
+
+static char *getusername(uid_t uid)
+{
+  struct passwd *pw = getpwuid(uid);
+  return pw ? pw->pw_name : utoa(uid);
+}
+
+static char *getgroupname(gid_t gid)
+{
+  struct group *gr = getgrgid(gid);
+  return gr ? gr->gr_name : utoa(gid);
+}
+
+// Figure out size of printable entry fields for display indent/wrap
+
+static void entrylen(struct dirtree *dt, unsigned *len)
+{
+    struct stat *st = &(dt->st);
+    unsigned flags = toys.optflags;
+
+    *len = strlen(dt->name);
+    if (endtype(st)) ++*len;
+    if (flags & FLAG_m) ++*len;
+
+    if (flags & FLAG_i) *len += (len[1] = numlen(st->st_ino));
+    if (flags & FLAG_l) {
+        len[2] = numlen(st->st_nlink);
+        len[3] = strlen(getusername(st->st_uid));
+        len[4] = strlen(getgroupname(st->st_gid));
+        len[5] = numlen(st->st_size);
+    }
+}
+
+static int compare(void *a, void *b)
+{
+    struct dirtree *dta = *(struct dirtree **)a;
+    struct dirtree *dtb = *(struct dirtree **)b;
+
+// TODO handle flags
+    return strcmp(dta->name, dtb->name);
+}
+
+static int filter(struct dirtree *new)
+{
+    int ret = DIRTREE_NORECURSE;
+
+// TODO -1f should print here to handle enormous dirs without runing out of mem.
+
+    if (!(toys.optflags & (FLAG_a|FLAG_A)) && new->name[0]=='.')
+        ret |= DIRTREE_NOSAVE;
+    else if (!(toys.optflags & FLAG_a)) ret |= dirtree_isdotdot(new);
+
+    return ret;
+}
+
+// Display a list of dirtree entries, according to current format
+// Output types -1, -l, -C, or stream
+
+static void listfiles(struct dirtree *indir)
+{
+    struct dirtree *dt, **sort = 0;
+    unsigned long dtlen = 0, ul = 0;
+    unsigned width, flags = toys.optflags, totals[6], len[6];
+    int showdirs = 1;
+
+    // Figure out if we should show directories and current directory name
+    if (indir == TT.files) showdirs = (flags & (FLAG_d|FLAG_R));
+    else if (indir->parent == TT.files && toys.optc <= 1 && !(flags&FLAG_R));
+    else {
+        char *path = dirtree_path(indir, 0);
+        if (TT.again++) xputc('\n');
+        xprintf("%s:\n", path);
+        free(path);
+    }
+
+
+    // Copy linked list to array and sort it. Directories go in array because
+    // we visit them in sorted order.
+
+    for (;;) {
+        for (dt = indir->child; dt; dt = dt->next) {
+            if (sort) sort[dtlen] = dt;
+            dtlen++;
+        }
+        if (sort) break;
+        sort = xmalloc(dtlen * sizeof(void *));
+        dtlen = 0;
+        continue;
+    }
+
+    if (flags & FLAG_l) xprintf("total %lu\n", dtlen);
+
+    if (!(flags & FLAG_f)) qsort(sort, dtlen, sizeof(void *), (void *)compare);
+
+    // Find largest entry in each field for everything but -1
+
+    memset(totals, 0, 6*sizeof(unsigned));
+    if ((flags & (FLAG_1|FLAG_l)) != FLAG_1) {
+        for (ul = 0; ul<dtlen; ul++) {
+            if (!showdirs && S_ISDIR(sort[ul]->st.st_mode)) continue;
+            entrylen(sort[ul], len);
+            if (flags & FLAG_l) {
+                for (width=0; width<6; width++)
+                    if (len[width] > totals[width]) totals[width] = len[width];
+//TODO            } else if (flags & FLAG_C) {
+            } else if (*len > *totals) *totals = *len;
+        }
+    }
+
+    // Loop through again to produce output.
+    width = 0;
+    memset(toybuf, ' ', 256);
+    for (ul = 0; ul<dtlen; ul++) {
+        struct stat *st = &(sort[ul]->st);
+        mode_t mode = st->st_mode;
+        char et = endtype(st);
+
+        if (S_ISDIR(mode) && !showdirs) continue;
+        entrylen(sort[ul], len);
+
+        if (ul) {
+            if (toys.optflags & FLAG_m) xputc(',');
+            if ((flags & FLAG_1) || width+1+*len > TT.width) {
+                xputc('\n');
+                width = 0;
+            } else {
+                xputc(' ');
+                width++;
+            }
+        }
+        width += *len;
+
+        if (flags & FLAG_i)
+            xprintf("% *lu ", len[1], (unsigned long)st->st_ino);
+
+        if (flags & FLAG_l) {
+            struct tm *tm;
+            char perm[11], thyme[64], c, d;
+            int i, bit;
+
+            perm[10]=0;
+            for (i=0; i<9; i++) {
+                bit = mode & (1<<i);
+                c = i%3;
+                if (!c && (mode & (1<<((d=i/3)+9)))) {
+                    c = "tss"[d];
+                    if (!bit) c &= 0x20;
+                } else c = bit ? "xwr"[c] : '-';
+                perm[9-i] = c;
+            }
+
+            if (S_ISDIR(mode)) c = 'd';
+            else if (S_ISBLK(mode)) c = 'b';
+            else if (S_ISCHR(mode)) c = 'c';
+            else if (S_ISLNK(mode)) c = 'l';
+            else if (S_ISFIFO(mode)) c = 'p';
+            else if (S_ISSOCK(mode)) c = 's';
+            else c = '-';
+            *perm = c;
+
+            tm = localtime(&(st->st_mtime));
+            strftime(thyme, sizeof(thyme), "%F %H:%M", tm);
+
+            xprintf("%s% *d %s%s%s%s% *d %s ", perm, totals[2]+1, st->st_nlink,
+                    getusername(st->st_uid), toybuf+255-(totals[3]-len[3]),
+                    getgroupname(st->st_gid), toybuf+256-(totals[4]-len[4]),
+                    totals[5]+1, st->st_size, thyme);
+        }
+
+        xprintf("%s", sort[ul]->name);
+        if ((flags & FLAG_l) && S_ISLNK(mode))
+            xprintf(" -> %s", sort[ul]->symlink);
+
+        if (et) xputc(et);
+    }
+
+    if (width) xputc('\n');
+
+    for (ul = 0; ul<dtlen; free(sort[ul++])) {
+// TODO follow symlinks when?
+        if (!S_ISDIR(sort[ul]->st.st_mode) || dirtree_isdotdot(sort[ul]))
+            continue;
+        if (indir == TT.files || (flags & FLAG_R)) {
+            sort[ul]->data = openat(indir->data, sort[ul]->name, 0);
+            dirtree_recurse(sort[ul], filter);
+            listfiles(sort[ul]);
+        }
+    }
+    free(sort);
+    close(indir->data);
+
+
+}
+
 void ls_main(void)
 {
-    /* If the output is not a TTY, then just do one-file per line
-     * This makes ls easier to use with other command line tools (grep/awk etc...)
-     */
-    if (!isatty(fileno(stdout)))
-        toys.optflags |= FLAG_1;
-    /* Long output must be one-file per line */
-    if (toys.optflags & FLAG_l)
-        toys.optflags |= FLAG_1;
-    loopfiles(toys.optargs, do_ls);
+    char **s, *noargs[] = {".", 0};
+
+    // Do we have an implied -1
+    if (!isatty(1) || (toys.optflags&FLAG_l)) toys.optflags |= FLAG_1;
+    else {
+        TT.width = 80;
+        terminal_size(&TT.width, NULL);
+    }
+
+    // Iterate through command line arguments, collecting directories and files.
+    // Non-absolute paths are relative to current directory.
+    TT.files = dirtree_add_node(0, 0);
+    TT.files->data =open(".", 0);
+    for (s = toys.optargs ? toys.optargs : noargs; *s; s++) {
+        struct dirtree *dt = dirtree_add_node(TT.files->data, *s);
+
+        if (!dt) {
+            toys.exitval = 1;
+            continue;
+        }
+
+        // Typecast means double_list->prev temporarirly goes in dirtree->parent
+        dlist_add_nomalloc((struct double_list **)&TT.files->child,
+                           (struct double_list *)dt);
+    }
+
+    // Turn double_list into dirtree
+    dlist_to_dirtree(TT.files);
+
+    // Display the files we collected
+    listfiles(TT.files);
 }
--- a/toys/mke2fs.c	Sat Apr 14 21:43:24 2012 -0500
+++ b/toys/mke2fs.c	Sat Apr 14 22:30:41 2012 -0500
@@ -10,7 +10,7 @@
 USE_MKE2FS(NEWTOY(mke2fs, "<1>2g:Fnqm#N#i#b#", TOYFLAG_SBIN))
 
 config MKE2FS
-	bool "mke2fs"
+	bool "mke2fs (unfinished and broken by dirtree changes)"
 	default n
 	help
 	  usage: mke2fs [-Fnq] [-b ###] [-N|i ###] [-m ###] device