dstring: Split out the dynamic string logic.

4 files changed, 213 insertions, 69 deletions

diff --git a/Makefile b/Makefile
index 01aec38..84bf484 100644
--- a/Makefile
+++ b/Makefile
@@ -34,7 +34,7 @@ ALL_LDFLAGS = $(ALL_CFLAGS) $(LDFLAGS)
 
 all: bfs
 
-bfs: bftw.o color.o eval.o main.o parse.o
+bfs: bftw.o color.o dstring.o eval.o main.o parse.o
 	$(CC) $(ALL_LDFLAGS) $^ -o $@
 
 release: CFLAGS := -O3 -flto -Wall -DNDEBUG
diff --git a/bftw.c b/bftw.c
index b4a2e99..8f6492e 100644
--- a/bftw.c
+++ b/bftw.c
@@ -21,6 +21,7 @@
  */
 
 #include "bftw.h"
+#include "dstring.h"
 #include <assert.h>
 #include <dirent.h>
 #include <errno.h>
@@ -35,56 +36,6 @@
 #include <unistd.h>
 
 /**
- * Simple dynamically-sized string type.
- */
-struct dynstr {
-	char *str;
-	size_t length;
-	size_t capacity;
-};
-
-/** Initialize a dynstr. */
-static void dynstr_init(struct dynstr *dstr) {
-	dstr->str = NULL;
-	dstr->length = 0;
-	dstr->capacity = 0;
-}
-
-/** Grow a dynstr to the given capacity if necessary. */
-static int dynstr_grow(struct dynstr *dstr, size_t length) {
-	if (length >= dstr->capacity) {
-		size_t new_capacity = 3*(length + 1)/2;
-		char *new_str = realloc(dstr->str, new_capacity);
-		if (!new_str) {
-			return -1;
-		}
-
-		dstr->str = new_str;
-		dstr->capacity = new_capacity;
-	}
-
-	return 0;
-}
-
-/** Concatenate a string to a dynstr at the given position. */
-static int dynstr_concat(struct dynstr *dstr, size_t pos, const char *more) {
-	size_t morelen = strlen(more);
-	size_t length = pos + morelen;
-	if (dynstr_grow(dstr, length) != 0) {
-		return -1;
-	}
-
-	memcpy(dstr->str + pos, more, morelen + 1);
-	dstr->length = length;
-	return 0;
-}
-
-/** Free a dynstr. */
-static void dynstr_free(struct dynstr *dstr) {
-	free(dstr->str);
-}
-
-/**
  * A single entry in the dircache.
  */
 struct dircache_entry {
@@ -292,20 +243,17 @@ static struct dircache_entry *dircache_add(struct dircache *cache, struct dircac
  * @param[out] path
  *         Will hold the full path to the entry, with a trailing '/'.
  */
-static int dircache_entry_path(const struct dircache_entry *entry, struct dynstr *path) {
+static int dircache_entry_path(const struct dircache_entry *entry, char **path) {
 	size_t namelen = entry->namelen;
 	size_t pathlen = entry->nameoff + namelen;
 
-	if (dynstr_grow(path, pathlen) != 0) {
+	if (dstresize(path, pathlen) != 0) {
 		return -1;
 	}
-	path->length = pathlen;
 
 	// Build the path backwards
-	path->str[pathlen] = '\0';
-
 	do {
-		char *segment = path->str + entry->nameoff;
+		char *segment = *path + entry->nameoff;
 		namelen = entry->namelen;
 		memcpy(segment, entry->name, namelen);
 		entry = entry->parent;
@@ -628,7 +576,7 @@ struct bftw_state {
 	enum bftw_status status;
 
 	/** The current path being explored. */
-	struct dynstr path;
+	char *path;
 
 	/** Extra data about the current file. */
 	struct BFTW ftwbuf;
@@ -653,20 +601,29 @@ static int bftw_state_init(struct bftw_state *state, bftw_fn *fn, int nopenfd, i
 
 	// -1 to account for dup()
 	if (dircache_init(&state->cache, nopenfd - 1) != 0) {
-		return -1;
+		goto err;
 	}
 
 	if (dirqueue_init(&state->queue) != 0) {
-		dircache_free(&state->cache);
-		return -1;
+		goto err_cache;
 	}
 
 	state->current = NULL;
 	state->status = BFTW_CURRENT;
 
-	dynstr_init(&state->path);
+	state->path = dstralloc(0);
+	if (!state->path) {
+		goto err_queue;
+	}
 
 	return 0;
+
+err_queue:
+	dirqueue_free(&state->queue);
+err_cache:
+	dircache_free(&state->cache);
+err:
+	return -1;
 }
 
 /**
@@ -682,7 +639,7 @@ static int bftw_path_concat(struct bftw_state *state, const char *subpath) {
 
 	state->status = BFTW_CHILD;
 
-	return dynstr_concat(&state->path, nameoff, subpath);
+	return dstrcatat(&state->path, nameoff, subpath);
 }
 
 /**
@@ -714,7 +671,7 @@ static size_t basename_offset(const char *path) {
  */
 static void bftw_init_buffers(struct bftw_state *state, const struct dirent *de) {
 	struct BFTW *ftwbuf = &state->ftwbuf;
-	ftwbuf->path = state->path.str;
+	ftwbuf->path = state->path;
 	ftwbuf->error = 0;
 	ftwbuf->visit = (state->status == BFTW_GC ? BFTW_POST : BFTW_PRE);
 	ftwbuf->statbuf = NULL;
@@ -873,12 +830,12 @@ static int bftw_pop(struct bftw_state *state, bool invoke_callback) {
 		}
 
 		if (invoke_callback) {
-			size_t offset = current->nameoff + current->namelen;
-			state->path.str[offset] = '\0';
+			size_t length = current->nameoff + current->namelen;
 			if (current->namelen > 1) {
 				// Trim the trailing slash
-				state->path.str[offset - 1] = '\0';
+				--length;
 			}
+			dstresize(&state->path, length);
 
 			state->current = current;
 			bftw_init_buffers(state, NULL);
@@ -918,7 +875,7 @@ static void bftw_state_free(struct bftw_state *state) {
 
 	dircache_free(&state->cache);
 
-	dynstr_free(&state->path);
+	dstrfree(state->path);
 }
 
 int bftw(const char *path, bftw_fn *fn, int nopenfd, enum bftw_flags flags, void *ptr) {
@@ -966,7 +923,7 @@ int bftw(const char *path, bftw_fn *fn, int nopenfd, enum bftw_flags flags, void
 			goto fail;
 		}
 
-		DIR *dir = dircache_entry_open(&state.cache, state.current, state.path.str);
+		DIR *dir = dircache_entry_open(&state.cache, state.current, state.path);
 		if (!dir) {
 			int error = errno;
 
diff --git a/dstring.c b/dstring.c
new file mode 100644
index 0000000..9c65757
--- /dev/null
+++ b/dstring.c
@@ -0,0 +1,99 @@
+/*********************************************************************
+ * bfs                                                               *
+ * Copyright (C) 2016 Tavian Barnes <tavianator@tavianator.com>      *
+ *                                                                   *
+ * This program is free software. It comes without any warranty, to  *
+ * the extent permitted by applicable law. You can redistribute it   *
+ * and/or modify it under the terms of the Do What The Fuck You Want *
+ * To Public License, Version 2, as published by Sam Hocevar. See    *
+ * the COPYING file or http://www.wtfpl.net/ for more details.       *
+ *********************************************************************/
+
+#include "dstring.h"
+#include <stdlib.h>
+#include <string.h>
+
+/**
+ * The memory representation of a dynamic string.  Users get a pointer to data.
+ */
+struct dstring {
+	size_t capacity;
+	size_t length;
+	char data[];
+};
+
+static struct dstring *dstrheader(const char *dstr) {
+	return (struct dstring *)(dstr - offsetof(struct dstring, data));
+}
+
+static size_t dstrsize(size_t capacity) {
+	return sizeof(struct dstring) + capacity + 1;
+}
+
+char *dstralloc(size_t capacity) {
+	struct dstring *header = malloc(dstrsize(capacity));
+	if (!header) {
+		return NULL;
+	}
+
+	header->capacity = capacity;
+	header->length = 0;
+	return header->data;
+}
+
+size_t dstrlen(const char *dstr) {
+	return dstrheader(dstr)->length;
+}
+
+int dstreserve(char **dstr, size_t capacity) {
+	struct dstring *header = dstrheader(*dstr);
+
+	if (capacity > header->capacity) {
+		capacity *= 2;
+
+		header = realloc(header, dstrsize(capacity));
+		if (!header) {
+			return -1;
+		}
+		header->capacity = capacity;
+
+		*dstr = header->data;
+	}
+
+	return 0;
+}
+
+int dstresize(char **dstr, size_t length) {
+	if (dstreserve(dstr, length) != 0) {
+		return -1;
+	}
+
+	struct dstring *header = dstrheader(*dstr);
+	header->length = length;
+	header->data[length] = '\0';
+
+	return 0;
+}
+
+int dstrcat(char **dest, const char *src) {
+	struct dstring *header = dstrheader(*dest);
+	return dstrcatat(dest, header->length, src);
+}
+
+int dstrcatat(char **dest, size_t pos, const char *src) {
+	size_t srclen = strlen(src);
+	size_t destlen = pos + srclen;
+
+	if (dstresize(dest, destlen) != 0) {
+		return -1;
+	}
+
+	memcpy(*dest + pos, src, srclen);
+	return 0;
+}
+
+void dstrfree(char *dstr) {
+	if (dstr) {
+		free(dstrheader(dstr));
+	}
+}
diff --git a/dstring.h b/dstring.h
new file mode 100644
index 0000000..7e46da8
--- /dev/null
+++ b/dstring.h
@@ -0,0 +1,88 @@
+/*********************************************************************
+ * bfs                                                               *
+ * Copyright (C) 2016 Tavian Barnes <tavianator@tavianator.com>      *
+ *                                                                   *
+ * This program is free software. It comes without any warranty, to  *
+ * the extent permitted by applicable law. You can redistribute it   *
+ * and/or modify it under the terms of the Do What The Fuck You Want *
+ * To Public License, Version 2, as published by Sam Hocevar. See    *
+ * the COPYING file or http://www.wtfpl.net/ for more details.       *
+ *********************************************************************/
+
+#ifndef BFS_DSTRING_H
+#define BFS_DSTRING_H
+
+#include <stddef.h>
+
+/**
+ * Allocate a dynamic string.
+ *
+ * @param capacity
+ *         The initial capacity of the string.
+ */
+char *dstralloc(size_t capacity);
+
+/**
+ * Get a dynamic string's length.
+ *
+ * @param dstr
+ *         The string to measure.
+ * @return The length of dstr.
+ */
+size_t dstrlen(const char *dstr);
+
+/**
+ * Reserve some capacity in a dynamic string.
+ *
+ * @param dstr
+ *         The dynamic string to preallocate.
+ * @param capacity
+ *         The new capacity for the string.
+ * @return 0 on success, -1 on failure.
+ */
+int dstreserve(char **dstr, size_t capacity);
+
+/**
+ * Resize a dynamic string.
+ *
+ * @param dstr
+ *         The dynamic string to resize.
+ * @param length
+ *         The new length for the dynamic string.
+ * @return 0 on success, -1 on failure.
+ */
+int dstresize(char **dstr, size_t length);
+
+/**
+ * Append to a dynamic string.
+ *
+ * @param dest
+ *         The destination dynamic string.
+ * @param src
+ *         The string to append.
+ * @return 0 on success, -1 on failure.
+ */
+int dstrcat(char **dest, const char *src);
+
+/**
+ * Append to a dynamic string at a particular offset.
+ *
+ * @param dest
+ *         The destination dynamic string.
+ * @param pos
+ *         The offset at which to append.
+ * @param src
+ *         The string to append.
+ * @return 0 on success, -1 on failure.
+ */
+int dstrcatat(char **dest, size_t pos, const char *src);
+
+/**
+ * Free a dynamic string.
+ *
+ * @param dstr
+ *         The string to free.
+ */
+void dstrfree(char *dstr);
+
+#endif // BFS_DSTRING_H