From a30b3f503bede87043262343ed26d6995b0a85d9 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Thu, 29 Aug 2019 23:45:45 -0400
Subject: darray: New dynamic array library
---
Makefile | 1 +
cmdline.h | 2 --
darray.c | 95 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
darray.h | 107 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
eval.c | 3 +-
parse.c | 21 +++---------
6 files changed, 210 insertions(+), 19 deletions(-)
create mode 100644 darray.c
create mode 100644 darray.h
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;
}
--
cgit v1.2.3