commit - 11624658e63b039ca9c172f4c2dca569f6b39bd0
commit + aaa0878e4df2825d2597e407b5015a0e663ec7f8
blob - /dev/null
blob + a9b72d3ee4624c553d9cb7e7dfcaa30e4360a5b2 (mode 644)
--- /dev/null
+++ lib/got_lib_pathset.h
+/*
+ * Copyright (c) 2019 Stefan Sperling <stsp@openbsd.org>
+ *
+ * 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
+/*
+ * Copyright (c) 2019 Stefan Sperling <stsp@openbsd.org>
+ *
+ * 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 <sys/tree.h>
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <limits.h>
+
+#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
-SUBDIR = cmdline delta idset repository worktree
+SUBDIR = cmdline delta idset pathset repository worktree
.include <bsd.subdir.mk>
blob - /dev/null
blob + 9727586cdfb5e786c91383b214228ee484459083 (mode 644)
--- /dev/null
+++ regress/pathset/Makefile
+.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 <bsd.regress.mk>
blob - /dev/null
blob + c003ce56c94d3d571813042a5f7fa377886226ee (mode 644)
--- /dev/null
+++ regress/pathset/pathset_test.c
+/*
+ * Copyright (c) 2019 Stefan Sperling <stsp@openbsd.org>
+ *
+ * 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 <stdarg.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <err.h>
+
+#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;
+}
