Source / Include Folder (#88)

Moved Source Files Into `src` Folder

49 files changed, 19165 insertions, 0 deletions

diff --git a/src/bar.c b/src/bar.c
new file mode 100644
index 0000000..b0e595e
--- /dev/null
+++ b/src/bar.c
@@ -0,0 +1,248 @@
+/****************************************************************************
+ * bfs                                                                      *
+ * Copyright (C) 2020-2022 Tavian Barnes <tavianator@tavianator.com>        *
+ *                                                                          *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted.                           *
+ *                                                                          *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
+ ****************************************************************************/
+
+#include "bar.h"
+#include "dstring.h"
+#include "util.h"
+#include <errno.h>
+#include <fcntl.h>
+#include <limits.h>
+#include <signal.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/ioctl.h>
+#include <unistd.h>
+
+struct bfs_bar {
+	int fd;
+	volatile sig_atomic_t width;
+	volatile sig_atomic_t height;
+};
+
+/** The global status bar instance. */
+static struct bfs_bar the_bar = {
+	.fd = -1,
+};
+
+/** Get the terminal size, if possible. */
+static int bfs_bar_getsize(struct bfs_bar *bar) {
+#ifdef TIOCGWINSZ
+	struct winsize ws;
+	if (ioctl(bar->fd, TIOCGWINSZ, &ws) != 0) {
+		return -1;
+	}
+
+	bar->width = ws.ws_col;
+	bar->height = ws.ws_row;
+	return 0;
+#else
+	errno = ENOTSUP;
+	return -1;
+#endif
+}
+
+/** Async Signal Safe puts(). */
+static int ass_puts(int fd, const char *str) {
+	size_t len = strlen(str);
+	return xwrite(fd, str, len) == len ? 0 : -1;
+}
+
+/** Number of decimal digits needed for terminal sizes. */
+#define ITOA_DIGITS ((sizeof(unsigned short) * CHAR_BIT + 2) / 3)
+
+/** Async Signal Safe itoa(). */
+static char *ass_itoa(char *str, unsigned int n) {
+	char *end = str + ITOA_DIGITS;
+	*end = '\0';
+
+	char *c = end;
+	do {
+		*--c = '0' + (n % 10);
+		n /= 10;
+	} while (n);
+
+	size_t len = end - c;
+	memmove(str, c, len + 1);
+	return str + len;
+}
+
+/** Update the size of the scrollable region. */
+static int bfs_bar_resize(struct bfs_bar *bar) {
+	char esc_seq[12 + ITOA_DIGITS] =
+		"\0337"   // DECSC: Save cursor
+		"\033[;"; // DECSTBM: Set scrollable region
+
+	// DECSTBM takes the height as the second argument
+	char *ptr = esc_seq + strlen(esc_seq);
+	ptr = ass_itoa(ptr, bar->height - 1);
+
+	strcpy(ptr,
+		"r"      // DECSTBM
+		"\0338"  // DECRC: Restore the cursor
+		"\033[J" // ED: Erase display from cursor to end
+	);
+
+	return ass_puts(bar->fd, esc_seq);
+}
+
+#ifdef SIGWINCH
+/** SIGWINCH handler. */
+static void sighand_winch(int sig) {
+	int error = errno;
+
+	bfs_bar_getsize(&the_bar);
+	bfs_bar_resize(&the_bar);
+
+	errno = error;
+}
+#endif
+
+/** Reset the scrollable region and hide the bar. */
+static int bfs_bar_reset(struct bfs_bar *bar) {
+	return ass_puts(bar->fd,
+		"\0337"  // DECSC: Save cursor
+		"\033[r" // DECSTBM: Reset scrollable region
+		"\0338"  // DECRC: Restore cursor
+		"\033[J" // ED: Erase display from cursor to end
+	);
+}
+
+/** Signal handler for process-terminating signals. */
+static void sighand_reset(int sig) {
+	bfs_bar_reset(&the_bar);
+	raise(sig);
+}
+
+/** Register sighand_reset() for a signal. */
+static void reset_before_death_by(int sig) {
+	struct sigaction sa = {
+		.sa_handler = sighand_reset,
+		.sa_flags = SA_RESETHAND,
+	};
+	sigemptyset(&sa.sa_mask);
+	sigaction(sig, &sa, NULL);
+}
+
+/** printf() to the status bar with a single write(). */
+BFS_FORMATTER(2, 3)
+static int bfs_bar_printf(struct bfs_bar *bar, const char *format, ...) {
+	va_list args;
+	va_start(args, format);
+	char *str = dstrvprintf(format, args);
+	va_end(args);
+
+	if (!str) {
+		return -1;
+	}
+
+	int ret = ass_puts(bar->fd, str);
+	dstrfree(str);
+	return ret;
+}
+
+struct bfs_bar *bfs_bar_show(void) {
+	if (the_bar.fd >= 0) {
+		errno = EBUSY;
+		goto fail;
+	}
+
+	char term[L_ctermid];
+	ctermid(term);
+	if (strlen(term) == 0) {
+		errno = ENOTTY;
+		goto fail;
+	}
+
+	the_bar.fd = open(term, O_RDWR | O_CLOEXEC);
+	if (the_bar.fd < 0) {
+		goto fail;
+	}
+
+	if (bfs_bar_getsize(&the_bar) != 0) {
+		goto fail_close;
+	}
+
+	reset_before_death_by(SIGABRT);
+	reset_before_death_by(SIGINT);
+	reset_before_death_by(SIGPIPE);
+	reset_before_death_by(SIGQUIT);
+	reset_before_death_by(SIGTERM);
+
+#ifdef SIGWINCH
+	struct sigaction sa = {
+		.sa_handler = sighand_winch,
+		.sa_flags = SA_RESTART,
+	};
+	sigemptyset(&sa.sa_mask);
+	sigaction(SIGWINCH, &sa, NULL);
+#endif
+
+	bfs_bar_printf(&the_bar,
+		"\n"        // Make space for the bar
+		"\0337"     // DECSC: Save cursor
+		"\033[;%ur" // DECSTBM: Set scrollable region
+		"\0338"     // DECRC: Restore cursor
+		"\033[1A",  // CUU: Move cursor up 1 row
+		(unsigned int)(the_bar.height - 1)
+	);
+
+	return &the_bar;
+
+fail_close:
+	close_quietly(the_bar.fd);
+	the_bar.fd = -1;
+fail:
+	return NULL;
+}
+
+unsigned int bfs_bar_width(const struct bfs_bar *bar) {
+	return bar->width;
+}
+
+int bfs_bar_update(struct bfs_bar *bar, const char *str) {
+	return bfs_bar_printf(bar,
+		"\0337"      // DECSC: Save cursor
+		"\033[%u;0f" // HVP: Move cursor to row, column
+		"\033[K"     // EL: Erase line
+		"\033[7m"    // SGR reverse video
+		"%s"
+		"\033[27m"   // SGR reverse video off
+		"\0338",     // DECRC: Restore cursor
+		(unsigned int)bar->height,
+		str
+	);
+}
+
+void bfs_bar_hide(struct bfs_bar *bar) {
+	if (!bar) {
+		return;
+	}
+
+	signal(SIGABRT, SIG_DFL);
+	signal(SIGINT, SIG_DFL);
+	signal(SIGPIPE, SIG_DFL);
+	signal(SIGQUIT, SIG_DFL);
+	signal(SIGTERM, SIG_DFL);
+#ifdef SIGWINCH
+	signal(SIGWINCH, SIG_DFL);
+#endif
+
+	bfs_bar_reset(bar);
+
+	xclose(bar->fd);
+	bar->fd = -1;
+}
diff --git a/src/bar.h b/src/bar.h
new file mode 100644
index 0000000..3e509d6
--- /dev/null
+++ b/src/bar.h
@@ -0,0 +1,57 @@
+/****************************************************************************
+ * bfs                                                                      *
+ * Copyright (C) 2020 Tavian Barnes <tavianator@tavianator.com>             *
+ *                                                                          *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted.                           *
+ *                                                                          *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
+ ****************************************************************************/
+
+/**
+ * A terminal status bar.
+ */
+
+#ifndef BFS_BAR_H
+#define BFS_BAR_H
+
+/** A terminal status bar. */
+struct bfs_bar;
+
+/**
+ * Create a terminal status bar.  Only one status bar is supported at a time.
+ *
+ * @return
+ *         A pointer to the new status bar, or NULL on failure.
+ */
+struct bfs_bar *bfs_bar_show(void);
+
+/**
+ * Get the width of the status bar.
+ */
+unsigned int bfs_bar_width(const struct bfs_bar *bar);
+
+/**
+ * Update the status bar message.
+ *
+ * @param bar
+ *         The status bar to update.
+ * @param str
+ *         The string to display.
+ * @return
+ *         0 on success, -1 on failure.
+ */
+int bfs_bar_update(struct bfs_bar *bar, const char *str);
+
+/**
+ * Hide the status bar.
+ */
+void bfs_bar_hide(struct bfs_bar *status);
+
+#endif // BFS_BAR_H
diff --git a/src/bfs.h b/src/bfs.h
new file mode 100644
index 0000000..93d8d79
--- /dev/null
+++ b/src/bfs.h
@@ -0,0 +1,32 @@
+/****************************************************************************
+ * bfs                                                                      *
+ * Copyright (C) 2015-2021 Tavian Barnes <tavianator@tavianator.com>        *
+ *                                                                          *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted.                           *
+ *                                                                          *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
+ ****************************************************************************/
+
+/**
+ * Constants about the bfs program itself.
+ */
+
+#ifndef BFS_H
+#define BFS_H
+
+#ifndef BFS_VERSION
+#	define BFS_VERSION "2.5"
+#endif
+
+#ifndef BFS_HOMEPAGE
+#	define BFS_HOMEPAGE "https://tavianator.com/projects/bfs.html"
+#endif
+
+#endif // BFS_H
diff --git a/src/bftw.c b/src/bftw.c
new file mode 100644
index 0000000..6f97bf6
--- /dev/null
+++ b/src/bftw.c
@@ -0,0 +1,1494 @@
+/****************************************************************************
+ * bfs                                                                      *
+ * Copyright (C) 2015-2022 Tavian Barnes <tavianator@tavianator.com>        *
+ *                                                                          *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted.                           *
+ *                                                                          *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
+ ****************************************************************************/
+
+/**
+ * The bftw() implementation consists of the following components:
+ *
+ * - struct bftw_file: A file that has been encountered during the traversal.
+ *   They have reference-counted links to their parents in the directory tree.
+ *
+ * - struct bftw_cache: An LRU list of bftw_file's with open file descriptors,
+ *   used for openat() to minimize the amount of path re-traversals.
+ *
+ * - struct bftw_queue: The queue of bftw_file's left to explore.  Implemented
+ *   as a simple circular buffer.
+ *
+ * - struct bftw_state: Represents the current state of the traversal, allowing
+ *   various helper functions to take fewer parameters.
+ */
+
+#include "bftw.h"
+#include "dir.h"
+#include "darray.h"
+#include "dstring.h"
+#include "mtab.h"
+#include "stat.h"
+#include "trie.h"
+#include "util.h"
+#include <assert.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+/**
+ * A file.
+ */
+struct bftw_file {
+	/** The parent directory, if any. */
+	struct bftw_file *parent;
+	/** The root under which this file was found. */
+	struct bftw_file *root;
+	/** The next file in the queue, if any. */
+	struct bftw_file *next;
+
+	/** The previous file in the LRU list. */
+	struct bftw_file *lru_prev;
+	/** The next file in the LRU list. */
+	struct bftw_file *lru_next;
+
+	/** This file's depth in the walk. */
+	size_t depth;
+	/** Reference count. */
+	size_t refcount;
+
+	/** An open descriptor to this file, or -1. */
+	int fd;
+
+	/** This file's type, if known. */
+	enum bfs_type type;
+	/** The device number, for cycle detection. */
+	dev_t dev;
+	/** The inode number, for cycle detection. */
+	ino_t ino;
+
+	/** The offset of this file in the full path. */
+	size_t nameoff;
+	/** The length of the file's name. */
+	size_t namelen;
+	/** The file's name. */
+	char name[];
+};
+
+/**
+ * A cache of open directories.
+ */
+struct bftw_cache {
+	/** The head of the LRU list. */
+	struct bftw_file *head;
+	/** The insertion target for the LRU list. */
+	struct bftw_file *target;
+	/** The tail of the LRU list. */
+	struct bftw_file *tail;
+	/** The remaining capacity of the LRU list. */
+	size_t capacity;
+};
+
+/** Initialize a cache. */
+static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
+	cache->head = NULL;
+	cache->target = NULL;
+	cache->tail = NULL;
+	cache->capacity = capacity;
+}
+
+/** Destroy a cache. */
+static void bftw_cache_destroy(struct bftw_cache *cache) {
+	assert(!cache->tail);
+	assert(!cache->target);
+	assert(!cache->head);
+}
+
+/** Add a bftw_file to the cache. */
+static void bftw_cache_add(struct bftw_cache *cache, struct bftw_file *file) {
+	assert(cache->capacity > 0);
+	assert(file->fd >= 0);
+	assert(!file->lru_prev);
+	assert(!file->lru_next);
+
+	if (cache->target) {
+		file->lru_prev = cache->target;
+		file->lru_next = cache->target->lru_next;
+	} else {
+		file->lru_next = cache->head;
+	}
+
+	if (file->lru_prev) {
+		file->lru_prev->lru_next = file;
+	} else {
+		cache->head = file;
+	}
+
+	if (file->lru_next) {
+		file->lru_next->lru_prev = file;
+	} else {
+		cache->tail = file;
+	}
+
+	// Prefer to keep the root paths open by keeping them at the head of the list
+	if (file->depth == 0) {
+		cache->target = file;
+	}
+
+	--cache->capacity;
+}
+
+/** Remove a bftw_file from the cache. */
+static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file) {
+	if (cache->target == file) {
+		cache->target = file->lru_prev;
+	}
+
+	if (file->lru_prev) {
+		assert(cache->head != file);
+		file->lru_prev->lru_next = file->lru_next;
+	} else {
+		assert(cache->head == file);
+		cache->head = file->lru_next;
+	}
+
+	if (file->lru_next) {
+		assert(cache->tail != file);
+		file->lru_next->lru_prev = file->lru_prev;
+	} else {
+		assert(cache->tail == file);
+		cache->tail = file->lru_prev;
+	}
+
+	file->lru_prev = NULL;
+	file->lru_next = NULL;
+	++cache->capacity;
+}
+
+/** Mark a cache entry as recently used. */
+static void bftw_cache_use(struct bftw_cache *cache, struct bftw_file *file) {
+	bftw_cache_remove(cache, file);
+	bftw_cache_add(cache, file);
+}
+
+/** Close a bftw_file. */
+static void bftw_file_close(struct bftw_cache *cache, struct bftw_file *file) {
+	assert(file->fd >= 0);
+
+	bftw_cache_remove(cache, file);
+
+	xclose(file->fd);
+	file->fd = -1;
+}
+
+/** Pop a directory from the cache. */
+static void bftw_cache_pop(struct bftw_cache *cache) {
+	assert(cache->tail);
+	bftw_file_close(cache, cache->tail);
+}
+
+/**
+ * Shrink the cache, to recover from EMFILE.
+ *
+ * @param cache
+ *         The cache in question.
+ * @param saved
+ *         A bftw_file that must be preserved.
+ * @return
+ *         0 if successfully shrunk, otherwise -1.
+ */
+static int bftw_cache_shrink(struct bftw_cache *cache, const struct bftw_file *saved) {
+	struct bftw_file *file = cache->tail;
+	if (!file) {
+		return -1;
+	}
+
+	if (file == saved) {
+		file = file->lru_prev;
+		if (!file) {
+			return -1;
+		}
+	}
+
+	bftw_file_close(cache, file);
+	cache->capacity = 0;
+	return 0;
+}
+
+/** Compute the name offset of a child path. */
+static size_t bftw_child_nameoff(const struct bftw_file *parent) {
+	size_t ret = parent->nameoff + parent->namelen;
+	if (parent->name[parent->namelen - 1] != '/') {
+		++ret;
+	}
+	return ret;
+}
+
+/** Create a new bftw_file. */
+static struct bftw_file *bftw_file_new(struct bftw_file *parent, const char *name) {
+	size_t namelen = strlen(name);
+	size_t size = BFS_FLEX_SIZEOF(struct bftw_file, name, namelen + 1);
+
+	struct bftw_file *file = malloc(size);
+	if (!file) {
+		return NULL;
+	}
+
+	file->parent = parent;
+
+	if (parent) {
+		file->root = parent->root;
+		file->depth = parent->depth + 1;
+		file->nameoff = bftw_child_nameoff(parent);
+		++parent->refcount;
+	} else {
+		file->root = file;
+		file->depth = 0;
+		file->nameoff = 0;
+	}
+
+	file->next = NULL;
+
+	file->lru_prev = NULL;
+	file->lru_next = NULL;
+
+	file->refcount = 1;
+	file->fd = -1;
+
+	file->type = BFS_UNKNOWN;
+	file->dev = -1;
+	file->ino = -1;
+
+	file->namelen = namelen;
+	memcpy(file->name, name, namelen + 1);
+
+	return file;
+}
+
+/**
+ * Open a bftw_file relative to another one.
+ *
+ * @param cache
+ *         The cache to hold the file.
+ * @param file
+ *         The file to open.
+ * @param base
+ *         The base directory for the relative path (may be NULL).
+ * @param at_fd
+ *         The base file descriptor, AT_FDCWD if base == NULL.
+ * @param at_path
+ *         The relative path to the file.
+ * @return
+ *         The opened file descriptor, or negative on error.
+ */
+static int bftw_file_openat(struct bftw_cache *cache, struct bftw_file *file, struct bftw_file *base, const char *at_path) {
+	assert(file->fd < 0);
+
+	int at_fd = AT_FDCWD;
+	if (base) {
+		bftw_cache_use(cache, base);
+		at_fd = base->fd;
+	}
+
+	int flags = O_RDONLY | O_CLOEXEC | O_DIRECTORY;
+	int fd = openat(at_fd, at_path, flags);
+
+	if (fd < 0 && errno == EMFILE) {
+		if (bftw_cache_shrink(cache, base) == 0) {
+			fd = openat(at_fd, at_path, flags);
+		}
+	}
+
+	if (fd >= 0) {
+		if (cache->capacity == 0) {
+			bftw_cache_pop(cache);
+		}
+
+		file->fd = fd;
+		bftw_cache_add(cache, file);
+	}
+
+	return fd;
+}
+
+/**
+ * Open a bftw_file.
+ *
+ * @param cache
+ *         The cache to hold the file.
+ * @param file
+ *         The file to open.
+ * @param path
+ *         The full path to the file.
+ * @return
+ *         The opened file descriptor, or negative on error.
+ */
+static int bftw_file_open(struct bftw_cache *cache, struct bftw_file *file, const char *path) {
+	// Find the nearest open ancestor
+	struct bftw_file *base = file;
+	do {
+		base = base->parent;
+	} while (base && base->fd < 0);
+
+	const char *at_path = path;
+	if (base) {
+		at_path += bftw_child_nameoff(base);
+	}
+
+	int fd = bftw_file_openat(cache, file, base, at_path);
+	if (fd >= 0 || errno != ENAMETOOLONG) {
+		return fd;
+	}
+
+	// Handle ENAMETOOLONG by manually traversing the path component-by-component
+
+	// Use the ->next linked list to temporarily hold the reversed parent
+	// chain between base and file
+	struct bftw_file *cur;
+	for (cur = file; cur->parent != base; cur = cur->parent) {
+		cur->parent->next = cur;
+	}
+
+	// Open the files in the chain one by one
+	for (base = cur; base; base = base->next) {
+		fd = bftw_file_openat(cache, base, base->parent, base->name);
+		if (fd < 0 || base == file) {
+			break;
+		}
+	}
+
+	// Clear out the linked list
+	for (struct bftw_file *next = cur->next; cur != file; cur = next, next = next->next) {
+		cur->next = NULL;
+	}
+
+	return fd;
+}
+
+/**
+ * Open a bftw_file as a directory.
+ *
+ * @param cache
+ *         The cache to hold the file.
+ * @param file
+ *         The directory to open.
+ * @param path
+ *         The full path to the directory.
+ * @return
+ *         The opened directory, or NULL on error.
+ */
+static struct bfs_dir *bftw_file_opendir(struct bftw_cache *cache, struct bftw_file *file, const char *path) {
+	int fd = bftw_file_open(cache, file, path);
+	if (fd < 0) {
+		return NULL;
+	}
+
+	return bfs_opendir(fd, NULL);
+}
+
+/** Free a bftw_file. */
+static void bftw_file_free(struct bftw_cache *cache, struct bftw_file *file) {
+	assert(file->refcount == 0);
+
+	if (file->fd >= 0) {
+		bftw_file_close(cache, file);
+	}
+
+	free(file);
+}
+
+/**
+ * A queue of bftw_file's to examine.
+ */
+struct bftw_queue {
+	/** The head of the queue. */
+	struct bftw_file *head;
+	/** The insertion target. */
+	struct bftw_file **target;
+};
+
+/** Initialize a bftw_queue. */
+static void bftw_queue_init(struct bftw_queue *queue) {
+	queue->head = NULL;
+	queue->target = &queue->head;
+}
+
+/** Add a file to a bftw_queue. */
+static void bftw_queue_push(struct bftw_queue *queue, struct bftw_file *file) {
+	assert(file->next == NULL);
+
+	file->next = *queue->target;
+	*queue->target = file;
+	queue->target = &file->next;
+}
+
+/** Pop the next file from the head of the queue. */
+static struct bftw_file *bftw_queue_pop(struct bftw_queue *queue) {
+	struct bftw_file *file = queue->head;
+	queue->head = file->next;
+	file->next = NULL;
+	if (queue->target == &file->next) {
+		queue->target = &queue->head;
+	}
+	return file;
+}
+
+/** The split phase of mergesort. */
+static struct bftw_file **bftw_sort_split(struct bftw_file **head, struct bftw_file **tail) {
+	struct