From a30b3f503bede87043262343ed26d6995b0a85d9 Mon Sep 17 00:00:00 2001 From: Tavian Barnes 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 * + * * + * 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 +#include + +/** + * 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 * + * * + * 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 + +/** + * 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