commit - fc727cc52868117245ac2e264b3caf6fb06282ae
commit + e08cc72dc07ea915bb95484818f3be5847d6e556
blob - ff7d21ebaf08b07c0fc13a54987d9d923c5432b4
blob + a3451ceb2cfc850c40fbd36a6bd24c8725de887f
--- lib/got_lib_path.h
+++ lib/got_lib_path.h
* their parents.
*/
int got_path_cmp(const char *, const char *);
+
+/*
+ * Path lists allow for predictable concurrent iteration over multiple lists
+ * of paths obtained from disparate sources which don't all provide the same
+ * ordering guarantees (e.g. git trees, file index, and on-disk directories).
+ */
+struct got_pathlist_entry {
+ TAILQ_ENTRY(got_pathlist_entry) entry;
+ const char *path;
+};
+TAILQ_HEAD(got_pathlist_head, got_pathlist_entry);
+
+/*
+ * Insert a path into the list of paths in a predictable order.
+ * The caller should already have initialized the list head. This list stores
+ * the pointer to the path as-is, i.e. the path is not copied internally and
+ * must remain available until the list is freed with got_pathlist_free().
+ */
+const struct got_error *got_pathlist_insert(struct got_pathlist_head *,
+ const char *);
+
+/* Free resources allocated for a path list. */
+void got_pathlist_free(struct got_pathlist_head *);
blob - 4878d3be7482827add298d0f4e7ccbefc6168540
blob + cc15eae49b0e361ae325d2e6c1fda427850d2591
--- lib/path.c
+++ lib/path.c
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
+#include <sys/queue.h>
+
#include <limits.h>
#include <stdlib.h>
#include <unistd.h>
size_t min_len = MIN(len1, len2);
size_t i = 0;
+ /* Leading directory separators are insignificant. */
+ while (path1[0] == '/')
+ path1++;
+ while (path2[0] == '/')
+ path2++;
+
+ len1 = strlen(path1);
+ len2 = strlen(path2);
+ min_len = MIN(len1, len2);
+
/* Skip over common prefix. */
while (i < min_len && path1[i] == path2[i])
i++;
- /* Are the paths exactly equal? */
+ /* Are the paths exactly equal (besides path separators)? */
if (len1 == len2 && i >= min_len)
return 0;
+ /* Skip over redundant trailing path seperators. */
+ while (path1[i] == '/' && path1[i + 1] == '/')
+ path1++;
+ while (path2[i] == '/' && path2[i + 1] == '/')
+ path2++;
+
+ /* Trailing path separators are insignificant. */
+ if (path1[i] == '/' && path1[i + 1] == '\0' && path2[i] == '\0')
+ return 0;
+ if (path2[i] == '/' && path2[i + 1] == '\0' && path1[i] == '\0')
+ return 0;
+
/* Order children in subdirectories directly after their parents. */
if (path1[i] == '/' && path2[i] == '\0')
return 1;
if (path2[i] == '/' && path1[i] == '\0')
return -1;
- if (path1[i] == '/')
+ if (path1[i] == '/' && path2[i] != '\0')
return -1;
- if (path2[i] == '/')
+ if (path2[i] == '/' && path1[i] != '\0')
return 1;
/* Next character following the common prefix determines order. */
return (unsigned char)path1[i] < (unsigned char)path2[i] ? -1 : 1;
}
+
+const struct got_error *
+got_pathlist_insert(struct got_pathlist_head *pathlist, const char *path)
+{
+ struct got_pathlist_entry *new, *pe;
+
+ new = malloc(sizeof(*new));
+ if (new == NULL)
+ return got_error_from_errno();
+ new->path = path;
+
+ /*
+ * Many callers will provide paths in a somewhat sorted order while
+ * constructing a path list from inputs such as tree objects or
+ * dirents. Iterating backwards from the tail of the list should
+ * be more efficient than traversing through the entire list each
+ * time an element is inserted.
+ */
+ pe = TAILQ_LAST(pathlist, got_pathlist_head);
+ while (pe) {
+ int cmp = got_path_cmp(pe->path, path);
+ if (cmp == 0) {
+ free(new); /* duplicate */
+ return NULL;
+ } else if (cmp < 0) {
+ TAILQ_INSERT_AFTER(pathlist, pe, new, entry);
+ return NULL;
+ }
+ pe = TAILQ_PREV(pe, got_pathlist_head, entry);
+ }
+
+ TAILQ_INSERT_HEAD(pathlist, new, entry);
+ return NULL;
+}
+
+void
+got_pathlist_free(struct got_pathlist_head *pathlist)
+{
+ struct got_pathlist_entry *pe;
+
+ while ((pe = TAILQ_FIRST(pathlist)) != NULL) {
+ TAILQ_REMOVE(pathlist, pe, entry);
+ free(pe);
+ }
+}
blob - e8ede9f6ecab9e64f288f5a139703c1c8589727d
blob + 24bfb418705d1482e271f5d2f70ebcdd3a95243b
--- regress/path/path_test.c
+++ regress/path/path_test.c
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
+#include <sys/queue.h>
+
+#include <string.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stdio.h>
{ "/a", "/b", -1 },
{ "x/a", "x.a", -1 },
{ "x.a", "x/a", 1 },
- { "//foo", "/bar", -1 },
+ { "//foo", "/bar", 1 },
{ "/foo", "/bar", 1 },
+ { "foo", "bar", 1 },
{ "/foo/sub", "/bar", 1 },
{ "/foo", "/bar/sub", 1 },
{ "/foo/", "/bar", 1 },
{ "/foo", "/bar/", 1 },
{ "/foo/", "/bar/", 1 },
{ "/bar/", "/bar/", 0 },
+ { "/bar/", "/bar", 0 },
+ { "//bar//", "/bar/", 0 },
+ { "//bar//", "/bar////", 0 },
+ { "/bar/sub", "/bar.", -1 },
{ "/bar/sub", "/bar/", 1 },
+ { "/bar/sub/", "/bar///", 1 },
{ "/bar/sub/sub2", "/bar/", 1 },
{ "/bar/sub/sub2", "/bar", 1 },
{ "/bar.sub.sub2", "/bar", 1 },
return 1;
}
+const char *path_list_input[] = {
+ "", "/", "a", "/b", "/bar", "bar/sub", "/bar/sub", "/bar/",
+ "/bar.c", "/bar/sub/sub2", "/bar.sub.sub2", "/foo",
+ "/foo/sub", "/foo/", "/foo/", "x/a",
+};
+const char *path_list_expected[] = {
+ "",
+ "a",
+ "/b",
+ "/bar",
+ "bar/sub",
+ "/bar/sub/sub2",
+ "/bar.c",
+ "/bar.sub.sub2",
+ "/foo",
+ "/foo/sub",
+ "x/a",
+};
+
+/* If inserting pathlist_input in reverse the result is slightly different. */
+const char *path_list_expected_reverse[] = {
+ "/",
+ "a",
+ "/b",
+ "/bar/",
+ "/bar/sub",
+ "/bar/sub/sub2",
+ "/bar.c",
+ "/bar.sub.sub2",
+ "/foo/",
+ "/foo/sub",
+ "x/a",
+};
+
+
+static int
+path_list(void)
+{
+ const struct got_error *err = NULL;
+ struct got_pathlist_head paths;
+ struct got_pathlist_entry *pe;
+ int i;
+
+ TAILQ_INIT(&paths);
+ for (i = 0; i < nitems(path_list_input); i++) {
+ err = got_pathlist_insert(&paths, path_list_input[i]);
+ if (err) {
+ test_printf("%s\n", __func__, err->msg);
+ return 0;
+ }
+ }
+
+ i = 0;
+ TAILQ_FOREACH(pe, &paths, entry) {
+ test_printf("'%s' -- '%s'\n", pe->path, path_list_expected[i]);
+ if (i >= nitems(path_list_expected)) {
+ test_printf("too many elements on list\n");
+ return 0;
+ }
+ if (strcmp(pe->path, path_list_expected[i]) != 0) {
+ test_printf("unordered elements on list\n");
+ return 0;
+ }
+ i++;
+ }
+
+ got_pathlist_free(&paths);
+ return 1;
+}
+
+static int
+path_list_reverse_input(void)
+{
+ const struct got_error *err = NULL;
+ struct got_pathlist_head paths;
+ struct got_pathlist_entry *pe;
+ int i;
+
+ TAILQ_INIT(&paths);
+ for (i = nitems(path_list_input) - 1; i >= 0; i--) {
+ err = got_pathlist_insert(&paths, path_list_input[i]);
+ if (err) {
+ test_printf("%s\n", __func__, err->msg);
+ return 0;
+ }
+ }
+
+ i = 0;
+ TAILQ_FOREACH(pe, &paths, entry) {
+ test_printf("'%s' -- '%s'\n", pe->path,
+ path_list_expected_reverse[i]);
+ if (i >= nitems(path_list_expected_reverse)) {
+ test_printf("too many elements on list\n");
+ return 0;
+ }
+ if (strcmp(pe->path, path_list_expected_reverse[i]) != 0) {
+ test_printf("unordered elements on list\n");
+ return 0;
+ }
+ i++;
+ }
+
+ got_pathlist_free(&paths);
+ return 1;
+}
+
#define RUN_TEST(expr, name) \
{ test_ok = (expr); \
printf("test_%s %s\n", (name), test_ok ? "ok" : "failed"); \
argv += optind;
RUN_TEST(path_cmp(), "path_cmp");
+ RUN_TEST(path_list(), "path_list");
+ RUN_TEST(path_list_reverse_input(), "path_list_reverse_input");
return failure ? 1 : 0;
}
