commit f5d3d7af6331314f863498d2e56cfefdf0143b07 from: Stefan Sperling date: Tue Feb 05 14:19:24 2019 UTC use path lists to sort dirent, tree object, and file index entries commit - 3d8df59c130064c8297bd34d0bacf021608eaf28 commit + f5d3d7af6331314f863498d2e56cfefdf0143b07 blob - ed60d5583a7b6f9135bbf8f7cf4acaee9e9e1fb6 blob + 266c84543cc2ab3f60caad3f5da7e8ead28697fb --- include/got_error.h +++ include/got_error.h @@ -71,6 +71,8 @@ #define GOT_ERR_ANCESTRY 55 #define GOT_ERR_FILEIDX_BAD 56 #define GOT_ERR_BAD_REF_DATA 57 +#define GOT_ERR_TREE_DUP_ENTRY 58 +#define GOT_ERR_DIR_DUP_ENTRY 59 static const struct got_error { int code; @@ -132,6 +134,8 @@ static const struct got_error { "the current branch" }, { GOT_ERR_FILEIDX_BAD, "file index is corrupt" }, { GOT_ERR_BAD_REF_DATA, "could not parse reference data" }, + { GOT_ERR_TREE_DUP_ENTRY,"duplicate entry in tree object" }, + { GOT_ERR_DIR_DUP_ENTRY,"duplicate entry in directory" }, }; /* blob - 49b86395ed04cc7cc8fdc01221790397b93c7057 blob + fecdb10fef1f1791b5e9c465db302bdf739c4a26 --- lib/fileindex.c +++ lib/fileindex.c @@ -696,27 +696,22 @@ static const struct got_error * diff_fileindex_dir(struct got_fileindex *, struct got_fileindex_entry **, DIR *, const char *, struct got_repository *, struct got_fileindex_diff_dir_cb *, void *); - -struct dirlist_entry { - SIMPLEQ_ENTRY(dirlist_entry) entry; - struct dirent *de; -}; -SIMPLEQ_HEAD(dirlist_head, dirlist_entry); static const struct got_error * -walk_dir(struct dirlist_entry **next, struct got_fileindex *fileindex, - struct got_fileindex_entry **ie, struct dirlist_entry *dle, +walk_dir(struct got_pathlist_entry **next, struct got_fileindex *fileindex, + struct got_fileindex_entry **ie, struct got_pathlist_entry *dle, const char *path, DIR *dir, struct got_repository *repo, struct got_fileindex_diff_dir_cb *cb, void *cb_arg) { const struct got_error *err = NULL; + struct dirent *de = dle->data; - if (dle->de->d_type == DT_DIR) { + if (de->d_type == DT_DIR) { char *subpath; DIR *subdir; if (asprintf(&subpath, "%s%s%s", path, - path[0] == '\0' ? "" : "/", dle->de->d_name) == -1) + path[0] == '\0' ? "" : "/", de->d_name) == -1) return got_error_from_errno(); subdir = opendir(subpath); @@ -733,45 +728,7 @@ walk_dir(struct dirlist_entry **next, struct got_filei return err; } - *next = SIMPLEQ_NEXT(dle, entry); - return NULL; -} - -static const struct got_error * -insert_dirent(struct dirlist_head *dirlist, struct dirent *de) -{ - struct dirlist_entry *dle, *prev = NULL; - - /* - * Keep dirents sorted in same order as used by file index. - * Git orders tree object entries based on length and then memcmp(). - */ - SIMPLEQ_FOREACH(dle, dirlist, entry) { - int cmp; - - if (dle->de->d_namlen > de->d_namlen) { - prev = dle; - continue; - } - - cmp = strcmp(dle->de->d_name, de->d_name); - if (cmp == 0) - return NULL; /* duplicate, should not happen */ - else if (cmp > 0) - break; - else - prev = dle; - } - - dle = malloc(sizeof(*dle)); - if (dle == NULL) - return got_error_from_errno(); - dle->de = de; - if (prev) - SIMPLEQ_INSERT_AFTER(dirlist, prev, dle, entry); - else - SIMPLEQ_INSERT_TAIL(dirlist, dle, entry); - + *next = TAILQ_NEXT(dle, entry); return NULL; } @@ -785,12 +742,14 @@ diff_fileindex_dir(struct got_fileindex *fileindex, struct dirent *de = NULL; size_t path_len = strlen(path); struct got_fileindex_entry *next; - struct dirlist_head dirlist; - struct dirlist_entry *dle; + struct got_pathlist_head dirlist; + struct got_pathlist_entry *dle; - SIMPLEQ_INIT(&dirlist); + TAILQ_INIT(&dirlist); while (1) { + struct got_pathlist_entry *new = NULL; + de = readdir(dir); if (de == NULL) break; @@ -801,17 +760,23 @@ diff_fileindex_dir(struct got_fileindex *fileindex, strcmp(de->d_name, GOT_WORKTREE_GOT_DIR) == 0)) continue; - insert_dirent(&dirlist, de); + err = got_pathlist_insert(&new, &dirlist, de->d_name, de); + if (err) + goto done; + if (new == NULL) { + err = got_error(GOT_ERR_DIR_DUP_ENTRY); + goto done; + } } - dle = SIMPLEQ_FIRST(&dirlist); + dle = TAILQ_FIRST(&dirlist); while ((*ie && got_path_is_child((*ie)->path, path, path_len)) || dle) { if (dle && *ie) { + de = dle->data; int cmp = cmp_entries((*ie)->path, path, path_len, - dle->de->d_name); + de->d_name); if (cmp == 0) { - err = cb->diff_old_new(cb_arg, *ie, dle->de, - path); + err = cb->diff_old_new(cb_arg, *ie, de, path); if (err) break; *ie = walk_fileindex(fileindex, *ie); @@ -824,7 +789,7 @@ diff_fileindex_dir(struct got_fileindex *fileindex, break; *ie = next; } else { - err = cb->diff_new(cb_arg, dle->de, path); + err = cb->diff_new(cb_arg, de, path); if (err) break; err = walk_dir(&dle, fileindex, ie, dle, path, @@ -839,7 +804,7 @@ diff_fileindex_dir(struct got_fileindex *fileindex, break; *ie = next; } else if (dle) { - err = cb->diff_new(cb_arg, dle->de, path); + err = cb->diff_new(cb_arg, de, path); if (err) break; err = walk_dir(&dle, fileindex, ie, dle, path, dir, @@ -848,13 +813,8 @@ diff_fileindex_dir(struct got_fileindex *fileindex, break; } } - - while (!SIMPLEQ_EMPTY(&dirlist)) { - dle = SIMPLEQ_FIRST(&dirlist); - SIMPLEQ_REMOVE_HEAD(&dirlist, entry); - free(dle); - } - +done: + got_pathlist_free(&dirlist); return err; } blob - 12d5ee251aa65405386153ccd88feb5b09106790 blob + f0befafd414a2ddcc56bb4f17a888939a7824d52 --- lib/got_lib_fileindex.h +++ lib/got_lib_fileindex.h @@ -78,7 +78,7 @@ static inline int got_fileindex_cmp(const struct got_fileindex_entry *e1, const struct got_fileindex_entry *e2) { - return strcmp(e1->path, e2->path); + return got_path_cmp(e1->path, e2->path); } RB_PROTOTYPE(got_fileindex_tree, got_fileindex_entry, entry, got_fileindex_cmp); blob - 330cbe4a0d85697ea7cce322aff8dab3bf12b118 blob + 9d4c4bb310991ee918bfcd5fe457e365678e92f0 --- lib/object_parse.c +++ lib/object_parse.c @@ -48,6 +48,7 @@ #include "got_lib_pack.h" #include "got_lib_privsep.h" #include "got_lib_repository.h" +#include "got_lib_path.h" #ifndef nitems #define nitems(_a) (sizeof(_a) / sizeof((_a)[0])) @@ -664,6 +665,10 @@ got_object_parse_tree(struct got_tree_object **tree, u { const struct got_error *err; size_t remain = len; + struct got_pathlist_head pathlist; + struct got_pathlist_entry *pe; + + TAILQ_INIT(&pathlist); *tree = calloc(1, sizeof(**tree)); if (*tree == NULL) @@ -673,13 +678,19 @@ got_object_parse_tree(struct got_tree_object **tree, u while (remain > 0) { struct got_tree_entry *te; + struct got_pathlist_entry *new = NULL; size_t elen; err = parse_tree_entry(&te, &elen, buf, remain); if (err) - return err; - (*tree)->entries.nentries++; - SIMPLEQ_INSERT_TAIL(&(*tree)->entries.head, te, entry); + goto done; + err = got_pathlist_insert(&new, &pathlist, te->name, te); + if (err) + goto done; + if (new == NULL) { + err = got_error(GOT_ERR_TREE_DUP_ENTRY); + goto done; + } buf += elen; remain -= elen; } @@ -687,10 +698,18 @@ got_object_parse_tree(struct got_tree_object **tree, u if (remain != 0) { got_object_tree_close(*tree); *tree = NULL; - return got_error(GOT_ERR_BAD_OBJ_DATA); + err = got_error(GOT_ERR_BAD_OBJ_DATA); + goto done; } - return NULL; + TAILQ_FOREACH(pe, &pathlist, entry) { + struct got_tree_entry *te = pe->data; + (*tree)->entries.nentries++; + SIMPLEQ_INSERT_TAIL(&(*tree)->entries.head, te, entry); + } +done: + got_pathlist_free(&pathlist); + return err; } void blob - 564acd4b5dec9e9f796f19fe13e4bb3e3e230610 blob + ad08409fc2e23e3dc1b5981b4e80df3ae5d993e2 --- libexec/got-read-blob/Makefile +++ libexec/got-read-blob/Makefile @@ -2,7 +2,7 @@ PROG= got-read-blob SRCS= got-read-blob.c delta.c error.c inflate.c object_parse.c \ - privsep.c sha1.c + path.c privsep.c sha1.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib LDADD = -lutil -lz blob - 1470f726d1eb6653e5953e61b6fe9f72ec633bdb blob + 2786410a5e3bf8c17f1cc1ed97f8d3a816d6019d --- libexec/got-read-commit/Makefile +++ libexec/got-read-commit/Makefile @@ -2,7 +2,7 @@ PROG= got-read-commit SRCS= got-read-commit.c delta.c error.c inflate.c object_parse.c \ - privsep.c sha1.c + path.c privsep.c sha1.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib LDADD = -lutil -lz blob - 9cb00e16eaaaf2f4b671b7c9b7f13730953e7bd8 blob + da7839de46ae66d80033b36e43ab1d71ef5cb5bd --- libexec/got-read-object/Makefile +++ libexec/got-read-object/Makefile @@ -2,7 +2,7 @@ PROG= got-read-object SRCS= got-read-object.c delta.c error.c inflate.c object_parse.c \ - privsep.c sha1.c + path.c privsep.c sha1.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib LDADD = -lutil -lz blob - 64fb2efe9db9a053c27290631e9ae5d09db1a820 blob + 3526b16aa7afcffb537e6b7d1110a318df7d1e9e --- libexec/got-read-tag/Makefile +++ libexec/got-read-tag/Makefile @@ -2,7 +2,7 @@ PROG= got-read-tag SRCS= got-read-tag.c delta.c error.c inflate.c object_parse.c \ - privsep.c sha1.c + path.c privsep.c sha1.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib LDADD = -lutil -lz blob - 600541da63b37f6061f6c39a8eb70d6288cc0e11 blob + 2d7e641e43c40642e073f9c044684b8c07e674c3 --- libexec/got-read-tree/Makefile +++ libexec/got-read-tree/Makefile @@ -2,7 +2,7 @@ PROG= got-read-tree SRCS= got-read-tree.c delta.c error.c inflate.c object_parse.c \ - privsep.c sha1.c + path.c privsep.c sha1.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib LDADD = -lutil -lz blob - 1e8b968d3584fd3c55b1c2217c8bedc4f7cfc108 blob + 32c4c6ac4ab75a05b1469c969541296100c928ae --- regress/cmdline/update.sh +++ regress/cmdline/update.sh @@ -317,8 +317,8 @@ function test_update_dir_with_dot_sibling { echo change > $testroot/repo/epsilon/zeta git_commit $testroot/repo -m "changing epsilon/zeta" - echo "A epsilon.txt" > $testroot/stdout.expected - echo "U epsilon/zeta" >> $testroot/stdout.expected + echo "U epsilon/zeta" > $testroot/stdout.expected + echo "A epsilon.txt" >> $testroot/stdout.expected echo -n "Updated to commit " >> $testroot/stdout.expected git_show_head $testroot/repo >> $testroot/stdout.expected echo >> $testroot/stdout.expected @@ -432,10 +432,10 @@ function test_update_moves_files_to_new_dir { (cd $testroot/repo && git mv epsilon/psi/chi/tau epsilon-new/psi/tau) git_commit $testroot/repo -m "moving files upwards" - echo "A epsilon-new/mu" > $testroot/stdout.expected - echo "A epsilon-new/psi/tau" >> $testroot/stdout.expected - echo "D epsilon/psi/chi/tau" >> $testroot/stdout.expected + echo "D epsilon/psi/chi/tau" > $testroot/stdout.expected echo "D epsilon/psi/mu" >> $testroot/stdout.expected + echo "A epsilon-new/mu" >> $testroot/stdout.expected + echo "A epsilon-new/psi/tau" >> $testroot/stdout.expected echo -n "Updated to commit " >> $testroot/stdout.expected git_show_head $testroot/repo >> $testroot/stdout.expected echo >> $testroot/stdout.expected