thodg/got

diff --git a/lib/got_lib_pathset.h b/lib/got_lib_pathset.h
new file mode 100644
index 0000000..a9b72d3
--- /dev/null
+++ b/lib/got_lib_pathset.h
@@ -0,0 +1,31 @@
+/*
+ * 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 *);
diff --git a/lib/pathset.c b/lib/pathset.c
new file mode 100644
index 0000000..2ba5c86
--- /dev/null
+++ b/lib/pathset.c
@@ -0,0 +1,208 @@
+/*
+ * 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);
diff --git a/regress/Makefile b/regress/Makefile
index bd68cd5..f4dda9c 100644
--- a/regress/Makefile
+++ b/regress/Makefile
@@ -1,3 +1,3 @@
-SUBDIR = cmdline delta idset repository worktree
+SUBDIR = cmdline delta idset pathset repository worktree
 
 .include <bsd.subdir.mk>
diff --git a/regress/pathset/Makefile b/regress/pathset/Makefile
new file mode 100644
index 0000000..9727586
--- /dev/null
+++ b/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 <bsd.regress.mk>
diff --git a/regress/pathset/pathset_test.c b/regress/pathset/pathset_test.c
new file mode 100644
index 0000000..c003ce5
--- /dev/null
+++ b/regress/pathset/pathset_test.c
@@ -0,0 +1,235 @@
+/*
+ * 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;
+}