commit aaa0878e4df2825d2597e407b5015a0e663ec7f8 from: Stefan Sperling date: Tue Jan 08 18:44:25 2019 UTC add got_pathset API which manages a tree of paths commit - 11624658e63b039ca9c172f4c2dca569f6b39bd0 commit + aaa0878e4df2825d2597e407b5015a0e663ec7f8 blob - /dev/null blob + a9b72d3ee4624c553d9cb7e7dfcaa30e4360a5b2 (mode 644) --- /dev/null +++ lib/got_lib_pathset.h @@ -0,0 +1,31 @@ +/* + * Copyright (c) 2019 Stefan Sperling + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * 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. + */ + +struct got_pathset; + +struct got_pathset *got_pathset_alloc(void); +void got_pathset_free(struct got_pathset *); + +const struct got_error *got_pathset_add(struct got_pathset *, const char *, + void *); +void *got_pathset_get(struct got_pathset *, const char *); +const struct got_error *got_pathset_remove(void **, struct got_pathset *, + const char *); +int got_pathset_contains(struct got_pathset *, const char *); +const struct got_error *got_pathset_for_each(struct got_pathset *, + const struct got_error *(*cb)(const char *, void *, void *), + void *); +int got_pathset_num_elements(struct got_pathset *); blob - /dev/null blob + 2ba5c863e4fd65416044b32696705d6ff47fb160 (mode 644) --- /dev/null +++ lib/pathset.c @@ -0,0 +1,208 @@ +/* + * Copyright (c) 2019 Stefan Sperling + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * 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 + +#include +#include +#include +#include + +#include "got_error.h" +#include "got_lib_pathset.h" + +#ifndef MIN +#define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b)) +#endif + +struct got_pathset_element { + RB_ENTRY(got_pathset_element) entry; + char *path; + void *data; /* API user data */ +}; + +RB_HEAD(got_pathset_tree, got_pathset_element); + +static int +cmp_elements(const struct got_pathset_element *e1, + const struct got_pathset_element *e2) +{ + size_t len1 = strlen(e1->path); + size_t len2 = strlen(e2->path); + size_t min_len = MIN(len1, len2); + size_t i = 0; + + /* Skip over common prefix. */ + while (i < min_len && e1->path[i] == e2->path[i]) + i++; + + /* Are the paths exactly equal? */ + if (len1 == len2 && i >= min_len) + return 0; + + /* Order children in subdirectories directly after their parents. */ + if (e1->path[i] == '/' && e2->path[i] == '\0') + return 1; + if (e2->path[i] == '/' && e1->path[i] == '\0') + return -1; + if (e1->path[i] == '/') + return -1; + if (e2->path[i] == '/') + return 1; + + /* Next character following the common prefix determines order. */ + return (unsigned char)e1->path[i] < (unsigned char)e2->path[i] ? -1 : 1; +} + +RB_PROTOTYPE(got_pathset_tree, got_pathset_element, entry, cmp_elements); + +struct got_pathset { + struct got_pathset_tree entries; + int totelem; +#define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX +}; + +struct got_pathset * +got_pathset_alloc(void) +{ + struct got_pathset *set; + + set = malloc(sizeof(*set)); + if (set == NULL) + return NULL; + + RB_INIT(&set->entries); + set->totelem = 0; + + return set; +} + +static void +free_element(struct got_pathset_element *entry) +{ + free(entry->path); + free(entry); +} + +void +got_pathset_free(struct got_pathset *set) +{ + struct got_pathset_element *entry; + + while ((entry = RB_MIN(got_pathset_tree, &set->entries))) { + RB_REMOVE(got_pathset_tree, &set->entries, entry); + /* User data should be freed by caller. */ + free_element(entry); + } + + free(set); +} + +const struct got_error * +got_pathset_add(struct got_pathset *set, const char *path, void *data) +{ + struct got_pathset_element *new; + + if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM) + return got_error(GOT_ERR_NO_SPACE); + + new = malloc(sizeof(*new)); + if (new == NULL) + return got_error_from_errno(); + + new->path = strdup(path); + if (new->path == NULL) + return got_error_from_errno(); + + new->data = data; + + RB_INSERT(got_pathset_tree, &set->entries, new); + set->totelem++; + return NULL; +} + +static struct got_pathset_element * +find_element(struct got_pathset *set, const char *path) +{ + struct got_pathset_element key, *entry; + key.path = strdup(path); + entry = RB_FIND(got_pathset_tree, &set->entries, &key); + free(key.path); + return entry; +} + +void * +got_pathset_get(struct got_pathset *set, const char *path) +{ + struct got_pathset_element *entry = find_element(set, path); + return entry ? entry->data : NULL; +} + +const struct got_error * +got_pathset_remove(void **data, struct got_pathset *set, const char *path) +{ + struct got_pathset_element *entry; + + if (data) + *data = NULL; + + if (set->totelem == 0) + return got_error(GOT_ERR_NO_OBJ); + + if (path == NULL) + entry = RB_ROOT(&set->entries); + else + entry = find_element(set, path); + if (entry == NULL) + return got_error(GOT_ERR_NO_OBJ); + + RB_REMOVE(got_pathset_tree, &set->entries, entry); + if (data) + *data = entry->data; + free_element(entry); + set->totelem--; + return NULL; +} + +int +got_pathset_contains(struct got_pathset *set, const char *path) +{ + struct got_pathset_element *entry = find_element(set, path); + return entry ? 1 : 0; +} + +const struct got_error * +got_pathset_for_each(struct got_pathset *set, + const struct got_error *(*cb)(const char *, void *, void *), void *arg) +{ + const struct got_error *err; + struct got_pathset_element *entry, *tmp; + + RB_FOREACH_SAFE(entry, got_pathset_tree, &set->entries, tmp) { + err = (*cb)(entry->path, entry->data, arg); + if (err) + return err; + } + return NULL; +} + +int +got_pathset_num_elements(struct got_pathset *set) +{ + return set->totelem; +} + +RB_GENERATE(got_pathset_tree, got_pathset_element, entry, cmp_elements); blob - bd68cd59dd3fc57df8b43aee72ba61e5cda697d3 blob + f4dda9c1107a2a59b5d7c6f3878b068ca3075b96 --- regress/Makefile +++ regress/Makefile @@ -1,3 +1,3 @@ -SUBDIR = cmdline delta idset repository worktree +SUBDIR = cmdline delta idset pathset repository worktree .include blob - /dev/null blob + 9727586cdfb5e786c91383b214228ee484459083 (mode 644) --- /dev/null +++ regress/pathset/Makefile @@ -0,0 +1,11 @@ +.PATH:${.CURDIR}/../../lib + +PROG = pathset_test +SRCS = error.c sha1.c pathset.c pathset_test.c + +CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib +LDADD = + +NOMAN = yes + +.include blob - /dev/null blob + c003ce56c94d3d571813042a5f7fa377886226ee (mode 644) --- /dev/null +++ regress/pathset/pathset_test.c @@ -0,0 +1,235 @@ +/* + * Copyright (c) 2019 Stefan Sperling + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * 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 +#include +#include +#include +#include +#include + +#include "got_error.h" + +#include "got_lib_pathset.h" + +static int verbose; + +void +test_printf(char *fmt, ...) +{ + va_list ap; + + if (!verbose) + return; + + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); +} + +static const char *path1 = "/", *path2 = "/usr", *path3 = "/usr/bin"; +static const char *data1 = "data1", *data2 = "data2", *data3 = "data3"; + +static const struct got_error * +pathset_add_remove_iter_cb(const char *path, void *data, void *arg) { + test_printf("%s\n", path); + if ((strcmp(path, path1) == 0 && data == (void *)data1) || + (strcmp(path, path3) == 0 && data == (void *)data3)) + return NULL; + abort(); + return NULL; /* not reached */ +} + +static int +pathset_add_remove_iter(void) +{ + const struct got_error *err = NULL; + struct got_pathset *set; + + set = got_pathset_alloc(); + if (set == NULL) { + err = got_error_from_errno(); + goto done; + } + if (got_pathset_num_elements(set) != 0) { + err = got_error(GOT_ERR_BAD_PATH); + goto done; + } + + + err = got_pathset_add(set, path1, (void *)data1); + if (err) + goto done; + if (got_pathset_num_elements(set) != 1) { + err = got_error(GOT_ERR_BAD_PATH); + goto done; + } + + if (!got_pathset_contains(set, path1)) { + err = got_error(GOT_ERR_BAD_PATH); + goto done; + } + + err = got_pathset_add(set, path2, (void *)data2); + if (err) + goto done; + if (!got_pathset_contains(set, path2)) { + err = got_error(GOT_ERR_BAD_PATH); + goto done; + } + if (got_pathset_num_elements(set) != 2) { + err = got_error(GOT_ERR_BAD_PATH); + goto done; + } + + err = got_pathset_add(set, path3, (void *)data3); + if (err) + goto done; + if (got_pathset_get(set, path3) != (void *)data3) { + err = got_error(GOT_ERR_BAD_PATH); + goto done; + } + if (got_pathset_num_elements(set) != 3) { + err = got_error(GOT_ERR_BAD_PATH); + goto done; + } + + err = got_pathset_remove(NULL, set, path2); + if (err) + goto done; + if (got_pathset_num_elements(set) != 2) { + err = got_error(GOT_ERR_BAD_PATH); + goto done; + } + if (got_pathset_contains(set, path2)) { + err = got_error(GOT_ERR_BAD_PATH); + goto done; + } + if (got_pathset_get(set, path2) != NULL) { + err = got_error(GOT_ERR_BAD_PATH); + goto done; + } + + got_pathset_for_each(set, pathset_add_remove_iter_cb, NULL); +done: + got_pathset_free(set); + return (err == NULL); +} + +static const struct got_error * +pathset_iter_ordering_cb(const char *path, void *data, void *arg) { + static int i; + test_printf("%s\n", path); + if (i == 0 && strcmp(path, "/") != 0) + abort(); + if (i == 1 && strcmp(path, "/usr.bin") != 0) + abort(); + if (i == 2 && strcmp(path, "/usr.bin/vi") != 0) + abort(); + if (i == 3 && strcmp(path, "/usr.sbin") != 0) + abort(); + if (i == 4 && strcmp(path, "/usr.sbin/unbound") != 0) + abort(); + if (i == 5 && strcmp(path, "/usr.sbin/zic") != 0) + abort(); + if (i > 5) + abort(); + i++; + return NULL; +} + +static int +pathset_iter_ordering(void) +{ + const struct got_error *err = NULL; + struct got_pathset *set; + + set = got_pathset_alloc(); + if (set == NULL) { + err = got_error_from_errno(); + goto done; + } + if (got_pathset_num_elements(set) != 0) { + err = got_error(GOT_ERR_BAD_PATH); + goto done; + } + + + err = got_pathset_add(set, "/usr.bin", (void *)data1); + if (err) + goto done; + err = got_pathset_add(set, "/usr.sbin/unbound", (void *)data1); + if (err) + goto done; + err = got_pathset_add(set, "/usr.bin/vi", (void *)data1); + if (err) + goto done; + err = got_pathset_add(set, "/", (void *)data1); + if (err) + goto done; + err = got_pathset_add(set, "/usr.sbin/zic", (void *)data1); + if (err) + goto done; + err = got_pathset_add(set, "/usr.sbin", (void *)data1); + if (err) + goto done; + + got_pathset_for_each(set, pathset_iter_ordering_cb, NULL); +done: + got_pathset_free(set); + return (err == NULL); +} + +#define RUN_TEST(expr, name) \ + { test_ok = (expr); \ + printf("test_%s %s\n", (name), test_ok ? "ok" : "failed"); \ + failure = (failure || !test_ok); } + +void +usage(void) +{ + fprintf(stderr, "usage: pathset_test [-v]\n"); +} + +int +main(int argc, char *argv[]) +{ + int test_ok = 0, failure = 0; + int ch; + +#ifndef PROFILE + if (pledge("stdio", NULL) == -1) + err(1, "pledge"); +#endif + + while ((ch = getopt(argc, argv, "v")) != -1) { + switch (ch) { + case 'v': + verbose = 1; + break; + default: + usage(); + return 1; + } + } + argc -= optind; + argv += optind; + + RUN_TEST(pathset_add_remove_iter(), "pathset_add_remove_iter"); + RUN_TEST(pathset_iter_ordering(), "pathset_iter_ordering"); + + return failure ? 1 : 0; +}