darray: New dynamic array library

6 files changed, 210 insertions, 19 deletions

diff --git a/Makefile b/Makefile
index 63ac559..a079c08 100644
--- a/Makefile
+++ b/Makefile
@@ -72,6 +72,7 @@ all: bfs tests/mksock
 bfs: \
     bftw.o \
     color.o \
+    darray.o \
     diag.o \
     dstring.o \
     eval.o \
diff --git a/cmdline.h b/cmdline.h
index 29c8d25..6670696 100644
--- a/cmdline.h
+++ b/cmdline.h
@@ -55,8 +55,6 @@ struct cmdline {
 
 	/** The root paths. */
 	const char **paths;
-	/** The number of root paths. */
-	size_t npaths;
 
 	/** Color data. */
 	struct colors *colors;
diff --git a/darray.c b/darray.c
new file mode 100644
index 0000000..459eb4d
--- /dev/null
+++ b/darray.c
@@ -0,0 +1,95 @@
+/****************************************************************************
+ * bfs                                                                      *
+ * Copyright (C) 2019 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 "darray.h"
+#include <stdlib.h>
+#include <string.h>
+
+/**
+ * The darray header.
+ */
+struct darray {
+	size_t capacity;
+	size_t length;
+};
+
+/** Get the header for a darray. */
+static struct darray *darray_header(const void *da) {
+	return (struct darray *)da - 1;
+}
+
+/** Get the array from a darray header. */
+static char *darray_data(struct darray *header) {
+	return (char *)(header + 1);
+}
+
+size_t darray_length(const void *da) {
+	if (da) {
+		return darray_header(da)->length;
+	} else {
+		return 0;
+	}
+}
+
+void *darray_push(void *da, const void *item, size_t size) {
+	struct darray *header;
+	if (da) {
+		header = darray_header(da);
+	} else {
+		header = malloc(sizeof(*header) + size);
+		if (!header) {
+			return NULL;
+		}
+		header->capacity = 1;
+		header->length = 0;
+	}
+
+	size_t capacity = header->capacity;
+	size_t i = header->length++;
+	if (i >= capacity) {
+		capacity *= 2;
+		header = realloc(header, sizeof(*header) + capacity*size);
+		if (!header) {
+			// This failure will be detected by darray_check()
+			return da;
+		}
+		header->capacity = capacity;
+	}
+
+	char *data = darray_data(header);
+	memcpy(data + i*size, item, size);
+	return data;
+}
+
+int darray_check(void *da) {
+	if (!da) {
+		return -1;
+	}
+
+	struct darray *header = darray_header(da);
+	if (header->length <= header->capacity) {
+		return 0;
+	} else {
+		header->length = header->capacity;
+		return -1;
+	}
+}
+
+void darray_free(void *da) {
+	if (da) {
+		free(darray_header(da));
+	}
+}
diff --git a/darray.h b/darray.h
new file mode 100644
index 0000000..22e4c68
--- /dev/null
+++ b/darray.h
@@ -0,0 +1,107 @@
+/****************************************************************************
+ * bfs                                                                      *
+ * Copyright (C) 2019 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 dynamic array library.
+ *
+ *     int ret = 0;
+ *     int *array = NULL;
+ *
+ *     int e = 1;
+ *     if (DARRAY_PUSH(&array, &e) != 0) {
+ *             goto fail;
+ *     }
+ *
+ *     e = 2;
+ *     if (DARRAY_PUSH(&array, &e) != 0) {
+ *             goto fail;
+ *     }
+ *
+ *     for (size_t i = 0; i < darray_length(array); ++i) {
+ *             assert(array[i] == i + 1);
+ *     }
+ *
+ *     ret = 0;
+ *     fail:
+ *     darray_free(array);
+ *     return ret;
+ */
+
+#ifndef BFS_DARRAY_H
+#define BFS_DARRAY_H
+
+#include <stddef.h>
+
+/**
+ * Get the length of a darray.
+ *
+ * @param da
+ *         The array in question.
+ * @return
+ *         The length of the array.
+ */
+size_t darray_length(const void *da);
+
+/**
+ * @internal Use DARRAY_PUSH().
+ *
+ * Push an element into a darray.
+ *
+ * @param da
+ *         The array to append to.
+ * @param item
+ *         The item to append.
+ * @param size
+ *         The size of the item.
+ * @return
+ *         The (new) location of the array.
+ */
+void *darray_push(void *da, const void *item, size_t size);
+
+/**
+ * @internal Use DARRAY_PUSH().
+ *
+ * Check if the last darray_push() call failed.
+ *
+ * @param da
+ *         The darray to check.
+ * @return
+ *         0 on success, -1 on failure.
+ */
+int darray_check(void *da);
+
+/**
+ * Free a darray.
+ *
+ * @param da
+ *         The darray to free.
+ */
+void darray_free(void *da);
+
+/**
+ * Push an item into a darray.
+ *
+ * @param da
+ *         The array to append to.
+ * @param item
+ *         A pointer to the item to append.
+ * @return
+ *         0 on success, -1 on failure.
+ */
+#define DARRAY_PUSH(da, item) \
+	(darray_check(*(da) = darray_push(*(da), (item), sizeof(**(da) = *(item)))))
+
+#endif // BFS_DARRAY_H
diff --git a/eval.c b/eval.c
index e2690c0..1b3d211 100644
--- a/eval.c
+++ b/eval.c
@@ -22,6 +22,7 @@
 #include "bftw.h"
 #include "cmdline.h"
 #include "color.h"
+#include "darray.h"
 #include "diag.h"
 #include "dstring.h"
 #include "exec.h"
@@ -1339,7 +1340,7 @@ int eval_cmdline(const struct cmdline *cmdline) {
 
 	struct bftw_args bftw_args = {
 		.paths = cmdline->paths,
-		.npaths = cmdline->npaths,
+		.npaths = darray_length(cmdline->paths),
 		.callback = cmdline_callback,
 		.ptr = &args,
 		.nopenfd = infer_fdlimit(cmdline),
diff --git a/parse.c b/parse.c
index 6a81fa7..b0b8167 100644
--- a/parse.c
+++ b/parse.c
@@ -23,6 +23,7 @@
 
 #include "bfs.h"
 #include "cmdline.h"
+#include "darray.h"
 #include "diag.h"
 #include "dstring.h"
 #include "eval.h"
@@ -292,7 +293,7 @@ int free_cmdline(struct cmdline *cmdline) {
 		cfclose(cerr);
 
 		free_colors(cmdline->colors);
-		free(cmdline->paths);
+		darray_free(cmdline->paths);
 		free(cmdline->argv);
 		free(cmdline);
 	}
@@ -505,18 +506,7 @@ static char **parser_advance(struct parser_state *state, enum token_type type, s
  */
 static int parse_root(struct parser_state *state, const char *path) {
 	struct cmdline *cmdline = state->cmdline;
-	size_t i = cmdline->npaths;
-	if ((i & (i + 1)) == 0) {
-		const char **paths = realloc(cmdline->paths, 2*(i + 1)*sizeof(*paths));
-		if (!paths) {
-			return -1;
-		}
-		cmdline->paths = paths;
-	}
-
-	cmdline->paths[i] = path;
-	cmdline->npaths = i + 1;
-	return 0;
+	return DARRAY_PUSH(&cmdline->paths, &path);
 }
 
 /**
@@ -3276,7 +3266,7 @@ void dump_cmdline(const struct cmdline *cmdline, bool verbose) {
 		cfprintf(cerr, " ");
 	}
 
-	for (size_t i = 0; i < cmdline->npaths; ++i) {
+	for (size_t i = 0; i < darray_length(cmdline->paths); ++i) {
 		const char *path = cmdline->paths[i];
 		char c = path[0];
 		if (c == '-' || c == '(' || c == ')' || c == '!' || c == ',') {
@@ -3361,7 +3351,6 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) {
 
 	cmdline->argv = NULL;
 	cmdline->paths = NULL;
-	cmdline->npaths = 0;
 	cmdline->colors = NULL;
 	cmdline->cout = NULL;
 	cmdline->cerr = NULL;
@@ -3460,7 +3449,7 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) {
 		goto fail;
 	}
 
-	if (cmdline->npaths == 0) {
+	if (darray_length(cmdline->paths) == 0) {
 		if (parse_root(&state, ".") != 0) {
 			goto fail;
 		}