commit e08cc72dc07ea915bb95484818f3be5847d6e556 from: Stefan Sperling date: Tue Feb 05 13:12:38 2019 UTC add a pathlist API commit - fc727cc52868117245ac2e264b3caf6fb06282ae commit + e08cc72dc07ea915bb95484818f3be5847d6e556 blob - ff7d21ebaf08b07c0fc13a54987d9d923c5432b4 blob + a3451ceb2cfc850c40fbd36a6bd24c8725de887f --- lib/got_lib_path.h +++ lib/got_lib_path.h @@ -60,3 +60,26 @@ int got_path_is_child(const char *, const char *, size * 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 @@ -15,6 +15,8 @@ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ +#include + #include #include #include @@ -166,24 +168,91 @@ got_path_cmp(const char *path1, const char *path2) 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 @@ -14,6 +14,9 @@ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ +#include + +#include #include #include #include @@ -56,15 +59,21 @@ path_cmp(void) { "/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 }, @@ -88,6 +97,112 @@ path_cmp(void) 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"); \ @@ -124,6 +239,8 @@ main(int argc, char *argv[]) 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; }