convert tree entries to an array

Tree traversals cause a huge amount of malloc/free calls. Currently each tree entry is individually allocated; with this diff the tree and its entries are allocated together, so freeing a tree can be doen with a single free call. This slightly improves performance of 'got blame'. $ time got blame sys/kern/kern_tc.c Before: 0m33.01s real 0m30.49s user 0m06.35s system 0m35.31s real 0m31.84s user 0m06.54s system 0m33.37s real 0m30.79s user 0m06.22s system After: 0m28.99s real 0m25.34s user 0m06.83s system 0m27.43s real 0m24.56s user 0m05.90s system 0m28.79s real 0m25.94s user 0m06.15s system This is a rather large diff. I don't see a good way to split it up since tree entries are used all over the place. The regress tests are passing and manual testing of tog suggests that nothing breaks, though I may have missed something. The only downside is that we no longer support tree entry names longer than NAME_MAX; however such names would already cause problems elsewhere even in the current implementation. Also each tree entry name now consumes NAME_MAX bytes instead of the actual string length, but that shouldn't be a problem. ok? diff refs/heads/master refs/heads/tree-entry-array blob - 776fb4c2ed06b1f5eaa6573a02ff26a086f3701b blob + 11985c8258e8f18f46f3706d26b1ed1c1ae06dec --- got/got.c +++ got/got.c @@ -2723,6 +2723,7 @@ print_entry(struct got_tree_entry *te, const char *id, { int is_root_path = (strcmp(path, root_path) == 0); const char *modestr = ""; + mode_t mode = got_tree_entry_get_mode(te); path += strlen(root_path); while (path[0] == '/') @@ -2730,15 +2731,15 @@ print_entry(struct got_tree_entry *te, const char *id, if (got_object_tree_entry_is_submodule(te)) modestr = "$"; - else if (S_ISLNK(te->mode)) + else if (S_ISLNK(mode)) modestr = "@"; - else if (S_ISDIR(te->mode)) + else if (S_ISDIR(mode)) modestr = "/"; - else if (te->mode & S_IXUSR) + else if (mode & S_IXUSR) modestr = "*"; printf("%s%s%s%s%s\n", id ? id : "", path, - is_root_path ? "" : "/", te->name, modestr); + is_root_path ? "" : "/", got_tree_entry_get_name(te), modestr); } static const struct got_error * @@ -2749,8 +2750,7 @@ print_tree(const char *path, struct got_object_id *com const struct got_error *err = NULL; struct got_object_id *tree_id = NULL; struct got_tree_object *tree = NULL; - const struct got_tree_entries *entries; - struct got_tree_entry *te; + int nentries, i; err = got_object_id_by_path(&tree_id, repo, commit_id, path); if (err) @@ -2759,17 +2759,19 @@ print_tree(const char *path, struct got_object_id *com err = got_object_open_as_tree(&tree, repo, tree_id); if (err) goto done; - entries = got_object_tree_get_entries(tree); - te = SIMPLEQ_FIRST(&entries->head); - while (te) { + nentries = got_object_tree_get_nentries(tree); + for (i = 0; i < nentries; i++) { + struct got_tree_entry *te; char *id = NULL; if (sigint_received || sigpipe_received) break; + te = got_object_tree_get_entry(tree, i); if (show_ids) { char *id_str; - err = got_object_id_str(&id_str, te->id); + err = got_object_id_str(&id_str, + got_tree_entry_get_id(te)); if (err) goto done; if (asprintf(&id, "%s ", id_str) == -1) { @@ -2782,11 +2784,11 @@ print_tree(const char *path, struct got_object_id *com print_entry(te, id, path, root_path); free(id); - if (recurse && S_ISDIR(te->mode)) { + if (recurse && S_ISDIR(got_tree_entry_get_mode(te))) { char *child_path; if (asprintf(&child_path, "%s%s%s", path, path[0] == '/' && path[1] == '\0' ? "" : "/", - te->name) == -1) { + got_tree_entry_get_name(te)) == -1) { err = got_error_from_errno("asprintf"); goto done; } @@ -2796,8 +2798,6 @@ print_tree(const char *path, struct got_object_id *com if (err) goto done; } - - te = SIMPLEQ_NEXT(te, entry); } done: if (tree) @@ -6975,25 +6975,26 @@ cat_tree(struct got_object_id *id, struct got_reposito { const struct got_error *err; struct got_tree_object *tree; - const struct got_tree_entries *entries; - struct got_tree_entry *te; + int nentries, i; err = got_object_open_as_tree(&tree, repo, id); if (err) return err; - entries = got_object_tree_get_entries(tree); - te = SIMPLEQ_FIRST(&entries->head); - while (te) { + nentries = got_object_tree_get_nentries(tree); + for (i = 0; i < nentries; i++) { + struct got_tree_entry *te; char *id_str; if (sigint_received || sigpipe_received) break; - err = got_object_id_str(&id_str, te->id); + te = got_object_tree_get_entry(tree, i); + err = got_object_id_str(&id_str, got_tree_entry_get_id(te)); if (err) break; - fprintf(outfile, "%s %.7o %s\n", id_str, te->mode, te->name); + fprintf(outfile, "%s %.7o %s\n", id_str, + got_tree_entry_get_mode(te), + got_tree_entry_get_name(te)); free(id_str); - te = SIMPLEQ_NEXT(te, entry); } got_object_tree_close(tree); blob - 8063afe6c8c64dee5df429c78330e6af4c4deb3b blob + 461975117c98f1bb74df15d9317223d1940e4c6d --- include/got_object.h +++ include/got_object.h @@ -18,23 +18,10 @@ struct got_object_id; struct got_blob_object; struct got_tree_object; +struct got_tree_entry; struct got_tag_object; struct got_commit_object; -struct got_tree_entry { - SIMPLEQ_ENTRY(got_tree_entry) entry; - mode_t mode; - char *name; - struct got_object_id *id; -}; - -SIMPLEQ_HEAD(got_tree_entries_queue, got_tree_entry); - -struct got_tree_entries { - int nentries; - struct got_tree_entries_queue head; -}; - struct got_object_qid { SIMPLEQ_ENTRY(got_object_qid) entry; struct got_object_id *id; @@ -178,16 +165,45 @@ const struct got_error *got_object_open_as_tree(struct /* Dispose of a tree object. */ void got_object_tree_close(struct got_tree_object *); -/* Get the entries of a tree object. */ -const struct got_tree_entries *got_object_tree_get_entries( - struct got_tree_object *); +/* Get the number of entries in this tree object. */ +int got_object_tree_get_nentries(struct got_tree_object *); -/* Find a particular entry in a tree. */ -const struct got_tree_entry *got_object_tree_find_entry( +/* Get the first tree entry from a tree, or NULL if there is none. */ +struct got_tree_entry *got_object_tree_get_first_entry(struct got_tree_object *); + +/* Get the last tree entry from a tree, or NULL if there is none. */ +struct got_tree_entry *got_object_tree_get_last_entry(struct got_tree_object *); + +/* Get the entry with the specified index from a tree object. */ +struct got_tree_entry *got_object_tree_get_entry( + struct got_tree_object *, int); + +/* Find a particular entry in a tree by name. */ +struct got_tree_entry *got_object_tree_find_entry( struct got_tree_object *, const char *); +/* Get the file permission mode of a tree entry. */ +mode_t got_tree_entry_get_mode(struct got_tree_entry *); + +/* Get the name of a tree entry. */ +const char *got_tree_entry_get_name(struct got_tree_entry *); + +/* Get the object ID of a tree entry. */ +struct got_object_id *got_tree_entry_get_id(struct got_tree_entry *); + +/* Get the index of a tree entry. */ +int got_tree_entry_get_index(struct got_tree_entry *); + +/* Get the next tree entry from a tree, or NULL if there is none. */ +struct got_tree_entry *got_tree_entry_get_next(struct got_tree_object *, + struct got_tree_entry *); + +/* Get the previous tree entry from a tree, or NULL if there is none. */ +struct got_tree_entry *got_tree_entry_get_prev(struct got_tree_object *, + struct got_tree_entry *); + /* Return non-zero if the specified tree entry is a Git submodule. */ -int got_object_tree_entry_is_submodule(const struct got_tree_entry *); +int got_object_tree_entry_is_submodule(struct got_tree_entry *); /* * Compare two trees and indicate whether the entry at the specified path blob - a602d0a3605f055369bf85a999e52e7399ff2c86 blob + a21b3cf85babdf6fe5b6c2dcc4ef02419742dfc6 --- lib/blame.c +++ lib/blame.c @@ -22,6 +22,7 @@ #include <stdio.h> #include <stdlib.h> #include <time.h> +#include <limits.h> #include <util.h> #include <zlib.h> blob - 51eb77382cd5c58ba7622c58006aa44e64287c35 blob + 899ed14bbc2aac2a8d0b0ce342ae94aff600f7ff --- lib/commit_graph.c +++ lib/commit_graph.c @@ -19,6 +19,7 @@ #include <sys/queue.h> #include <sys/stdint.h> +#include <limits.h> #include <stdio.h> #include <stdlib.h> #include <string.h> blob - 9abb0d4dc56c7c09ebf32461a9eb717f79cbca05 blob + 194fedc8fa1abc94fee0ebebe9c8a693426b89c2 --- lib/delta.c +++ lib/delta.c @@ -20,6 +20,7 @@ #include <stdlib.h> #include <stdint.h> #include <string.h> +#include <limits.h> #include <zlib.h> #include <sha1.h> #include <time.h> blob - c98502c82d7d8b1ed38dfe6ab2fbf0b1fbb5d095 blob + 7874be93a5e85387f051461ac0865dfb7e514500 --- lib/diff.c +++ lib/diff.c @@ -516,8 +516,8 @@ diff_kind_mismatch(struct got_object_id *id1, struct g } static const struct got_error * -diff_entry_old_new(const struct got_tree_entry *te1, - const struct got_tree_entry *te2, const char *label1, const char *label2, +diff_entry_old_new(struct got_tree_entry *te1, + struct got_tree_entry *te2, const char *label1, const char *label2, struct got_repository *repo, got_diff_blob_cb cb, void *cb_arg, int diff_content) { @@ -529,35 +529,35 @@ diff_entry_old_new(const struct got_tree_entry *te1, if (te2 == NULL) { if (S_ISDIR(te1->mode)) - err = diff_deleted_tree(te1->id, label1, repo, + err = diff_deleted_tree(&te1->id, label1, repo, cb, cb_arg, diff_content); else { if (diff_content) - err = diff_deleted_blob(te1->id, label1, + err = diff_deleted_blob(&te1->id, label1, te1->mode, repo, cb, cb_arg); else - err = cb(cb_arg, NULL, NULL, te1->id, NULL, + err = cb(cb_arg, NULL, NULL, &te1->id, NULL, label1, NULL, te1->mode, 0, repo); } return err; } else if (got_object_tree_entry_is_submodule(te2)) return NULL; - id_match = (got_object_id_cmp(te1->id, te2->id) == 0); + id_match = (got_object_id_cmp(&te1->id, &te2->id) == 0); if (S_ISDIR(te1->mode) && S_ISDIR(te2->mode)) { if (!id_match) - return diff_modified_tree(te1->id, te2->id, + return diff_modified_tree(&te1->id, &te2->id, label1, label2, repo, cb, cb_arg, diff_content); } else if (S_ISREG(te1->mode) && S_ISREG(te2->mode)) { if (!id_match || (te1->mode & S_IXUSR) != (te2->mode & S_IXUSR)) { if (diff_content) - return diff_modified_blob(te1->id, te2->id, + return diff_modified_blob(&te1->id, &te2->id, label1, label2, te1->mode, te2->mode, repo, cb, cb_arg); else - return cb(cb_arg, NULL, NULL, te1->id, - te2->id, label1, label2, te1->mode, + return cb(cb_arg, NULL, NULL, &te1->id, + &te2->id, label1, label2, te1->mode, te2->mode, repo); } } @@ -565,13 +565,13 @@ diff_entry_old_new(const struct got_tree_entry *te1, if (id_match) return NULL; - return diff_kind_mismatch(te1->id, te2->id, label1, label2, repo, + return diff_kind_mismatch(&te1->id, &te2->id, label1, label2, repo, cb, cb_arg); } static const struct got_error * -diff_entry_new_old(const struct got_tree_entry *te2, - const struct got_tree_entry *te1, const char *label2, +diff_entry_new_old(struct got_tree_entry *te2, + struct got_tree_entry *te1, const char *label2, struct got_repository *repo, got_diff_blob_cb cb, void *cb_arg, int diff_content) { @@ -582,14 +582,14 @@ diff_entry_new_old(const struct got_tree_entry *te2, return NULL; if (S_ISDIR(te2->mode)) - return diff_added_tree(te2->id, label2, repo, cb, cb_arg, + return diff_added_tree(&te2->id, label2, repo, cb, cb_arg, diff_content); if (diff_content) - return diff_added_blob(te2->id, label2, te2->mode, repo, cb, + return diff_added_blob(&te2->id, label2, te2->mode, repo, cb, cb_arg); - return cb(cb_arg, NULL, NULL, NULL, te2->id, NULL, label2, 0, + return cb(cb_arg, NULL, NULL, NULL, &te2->id, NULL, label2, 0, te2->mode, repo); } @@ -602,19 +602,16 @@ got_diff_tree(struct got_tree_object *tree1, struct go struct got_tree_entry *te1 = NULL; struct got_tree_entry *te2 = NULL; char *l1 = NULL, *l2 = NULL; + int tidx1 = 0, tidx2 = 0; if (tree1) { - const struct got_tree_entries *entries; - entries = got_object_tree_get_entries(tree1); - te1 = SIMPLEQ_FIRST(&entries->head); + te1 = got_object_tree_get_entry(tree1, 0); if (te1 && asprintf(&l1, "%s%s%s", label1, label1[0] ? "/" : "", te1->name) == -1) return got_error_from_errno("asprintf"); } if (tree2) { - const struct got_tree_entries *entries; - entries = got_object_tree_get_entries(tree2); - te2 = SIMPLEQ_FIRST(&entries->head); + te2 = got_object_tree_get_entry(tree2, 0); if (te2 && asprintf(&l2, "%s%s%s", label2, label2[0] ? "/" : "", te2->name) == -1) return got_error_from_errno("asprintf"); @@ -622,7 +619,7 @@ got_diff_tree(struct got_tree_object *tree1, struct go do { if (te1) { - const struct got_tree_entry *te = NULL; + struct got_tree_entry *te = NULL; if (tree2) te = got_object_tree_find_entry(tree2, te1->name); @@ -641,7 +638,7 @@ got_diff_tree(struct got_tree_object *tree1, struct go } if (te2) { - const struct got_tree_entry *te = NULL; + struct got_tree_entry *te = NULL; if (tree1) te = got_object_tree_find_entry(tree1, te2->name); @@ -666,7 +663,8 @@ got_diff_tree(struct got_tree_object *tree1, struct go free(l1); l1 = NULL; if (te1) { - te1 = SIMPLEQ_NEXT(te1, entry); + tidx1++; + te1 = got_object_tree_get_entry(tree1, tidx1); if (te1 && asprintf(&l1, "%s%s%s", label1, label1[0] ? "/" : "", te1->name) == -1) @@ -675,7 +673,8 @@ got_diff_tree(struct got_tree_object *tree1, struct go free(l2); l2 = NULL; if (te2) { - te2 = SIMPLEQ_NEXT(te2, entry); + tidx2++; + te2 = got_object_tree_get_entry(tree2, tidx2); if (te2 && asprintf(&l2, "%s%s%s", label2, label2[0] ? "/" : "", te2->name) == -1) blob - 1db1d7561b93f5dfbf11def07d7ef437d2da324c blob + a41a89c62ebf12fa26c7ef903d7d2fbd4f491499 --- lib/fileindex.c +++ lib/fileindex.c @@ -692,48 +692,52 @@ walk_fileindex(struct got_fileindex *fileindex, struct } static const struct got_error * -diff_fileindex_tree(struct got_fileindex *, struct got_fileindex_entry **, - const struct got_tree_entries *, const char *, const char *, +diff_fileindex_tree(struct got_fileindex *, struct got_fileindex_entry **ie, + struct got_tree_object *tree, const char *, const char *, struct got_repository *, struct got_fileindex_diff_tree_cb *, void *); static const struct got_error * walk_tree(struct got_tree_entry **next, struct got_fileindex *fileindex, - struct got_fileindex_entry **ie, struct got_tree_entry *te, + struct got_fileindex_entry **ie, struct got_tree_object *tree, int *tidx, const char *path, const char *entry_name, struct got_repository *repo, struct got_fileindex_diff_tree_cb *cb, void *cb_arg) { const struct got_error *err = NULL; + struct got_tree_entry *te = got_object_tree_get_entry(tree, *tidx); - if (!got_object_tree_entry_is_submodule(te) && S_ISDIR(te->mode)) { + if (!got_object_tree_entry_is_submodule(te) && + S_ISDIR(got_tree_entry_get_mode(te))) { char *subpath; struct got_tree_object *subtree; if (asprintf(&subpath, "%s%s%s", path, - path[0] == '\0' ? "" : "/", te->name) == -1) + path[0] == '\0' ? "" : "/", + got_tree_entry_get_name(te)) == -1) return got_error_from_errno("asprintf"); - err = got_object_open_as_tree(&subtree, repo, te->id); + err = got_object_open_as_tree(&subtree, repo, + got_tree_entry_get_id(te)); if (err) { free(subpath); return err; } - err = diff_fileindex_tree(fileindex, ie, - got_object_tree_get_entries(subtree), subpath, entry_name, - repo, cb, cb_arg); + err = diff_fileindex_tree(fileindex, ie, subtree, subpath, + entry_name, repo, cb, cb_arg); free(subpath); got_object_tree_close(subtree); if (err) return err; } - *next = SIMPLEQ_NEXT(te, entry); + (*tidx)++; + *next = got_object_tree_get_entry(tree, *tidx); return NULL; } static const struct got_error * diff_fileindex_tree(struct got_fileindex *fileindex, - struct got_fileindex_entry **ie, const struct got_tree_entries *entries, + struct got_fileindex_entry **ie, struct got_tree_object *tree, const char *path, const char *entry_name, struct got_repository *repo, struct got_fileindex_diff_tree_cb *cb, void *cb_arg) { @@ -741,13 +745,15 @@ diff_fileindex_tree(struct got_fileindex *fileindex, struct got_tree_entry *te = NULL; size_t path_len = strlen(path); struct got_fileindex_entry *next; + int tidx = 0; - te = SIMPLEQ_FIRST(&entries->head); + te = got_object_tree_get_entry(tree, tidx); while ((*ie && got_path_is_child((*ie)->path, path, path_len)) || te) { if (te && *ie) { char *te_path; + const char *te_name = got_tree_entry_get_name(te); int cmp; - if (asprintf(&te_path, "%s/%s", path, te->name) == -1) { + if (asprintf(&te_path, "%s/%s", path, te_name) == -1) { err = got_error_from_errno("asprintf"); break; } @@ -759,20 +765,20 @@ diff_fileindex_tree(struct got_fileindex *fileindex, path_len) && !got_object_tree_entry_is_submodule(te) && (entry_name == NULL || - strcmp(te->name, entry_name) == 0)) { + strcmp(te_name, entry_name) == 0)) { err = cb->diff_old_new(cb_arg, *ie, te, path); if (err || entry_name) break; } *ie = walk_fileindex(fileindex, *ie); - err = walk_tree(&te, fileindex, ie, te, + err = walk_tree(&te, fileindex, ie, tree, &tidx, path, entry_name, repo, cb, cb_arg); } else if (cmp < 0) { next = walk_fileindex(fileindex, *ie); if (got_path_is_child((*ie)->path, path, path_len) && (entry_name == NULL || - strcmp(te->name, entry_name) == 0)) { + strcmp(te_name, entry_name) == 0)) { err = cb->diff_old(cb_arg, *ie, path); if (err || entry_name) break; @@ -780,12 +786,12 @@ diff_fileindex_tree(struct got_fileindex *fileindex, *ie = next; } else { if ((entry_name == NULL || - strcmp(te->name, entry_name) == 0)) { + strcmp(te_name, entry_name) == 0)) { err = cb->diff_new(cb_arg, te, path); if (err || entry_name) break; } - err = walk_tree(&te, fileindex, ie, te, + err = walk_tree(&te, fileindex, ie, tree, &tidx, path, entry_name, repo, cb, cb_arg); } if (err) @@ -794,7 +800,8 @@ diff_fileindex_tree(struct got_fileindex *fileindex, next = walk_fileindex(fileindex, *ie); if (got_path_is_child((*ie)->path, path, path_len) && (entry_name == NULL || - (te && strcmp(te->name, entry_name) == 0))) { + (te && strcmp(got_tree_entry_get_name(te), + entry_name) == 0))) { err = cb->diff_old(cb_arg, *ie, path); if (err || entry_name) break; @@ -803,12 +810,13 @@ diff_fileindex_tree(struct got_fileindex *fileindex, } else if (te) { if (!got_object_tree_entry_is_submodule(te) && (entry_name == NULL || - strcmp(te->name, entry_name) == 0)) { + strcmp(got_tree_entry_get_name(te), entry_name) + == 0)) { err = cb->diff_new(cb_arg, te, path); if (err || entry_name) break; } - err = walk_tree(&te, fileindex, ie, te, path, + err = walk_tree(&te, fileindex, ie, tree, &tidx, path, entry_name, repo, cb, cb_arg); if (err) break; @@ -828,8 +836,7 @@ got_fileindex_diff_tree(struct got_fileindex *fileinde ie = RB_MIN(got_fileindex_tree, &fileindex->entries); while (ie && !got_path_is_child(ie->path, path, strlen(path))) ie = walk_fileindex(fileindex, ie); - return diff_fileindex_tree(fileindex, &ie, - got_object_tree_get_entries(tree), path, entry_name, repo, + return diff_fileindex_tree(fileindex, &ie, tree, path, entry_name, repo, cb, cb_arg); } blob - f09d092331780e3ebd0811893a864ed717f20689 blob + 9e91fb7c01c462fc3a6e27bac48b485f25480eb4 --- lib/got_lib_object.h +++ lib/got_lib_object.h @@ -50,8 +50,16 @@ struct got_commit_object { int refcnt; /* > 0 if open and/or cached */ }; +struct got_tree_entry { + mode_t mode; + char name[NAME_MAX]; + struct got_object_id id; + int idx; +}; + struct got_tree_object { - struct got_tree_entries entries; + int nentries; + struct got_tree_entry *entries; int refcnt; }; blob - 011e79e1b6f5f62d4fdb6d0658db9c490498352a blob + 899d18ef5efa99dada375165674b485b6bf60311 --- lib/got_lib_object_create.h +++ lib/got_lib_object_create.h @@ -16,8 +16,10 @@ const struct got_error *got_object_blob_create(struct got_object_id **, const char *, struct got_repository *); + const struct got_error *got_object_tree_create(struct got_object_id **, - struct got_tree_entries *, struct got_repository *); + struct got_pathlist_head *, int, struct got_repository *); + const struct got_error *got_object_commit_create(struct got_object_id **, struct got_object_id *, struct got_object_id_queue *, int, const char *, time_t, const char *, time_t, const char *, blob - cea99150c7215d78de30a954486bf415f2000bb2 blob + 08660f26facc1d87231e58e9db7d096e06d4897a --- lib/got_lib_object_parse.h +++ lib/got_lib_object_parse.h @@ -39,9 +39,6 @@ const struct got_error *got_object_parse_tag(struct go uint8_t *, size_t); const struct got_error *got_read_file_to_mem(uint8_t **, size_t *, FILE *); -void got_object_tree_entry_close(struct got_tree_entry *); -void got_object_tree_entries_close(struct got_tree_entries *); - struct got_pack; struct got_packidx; blob - c6bef75ef4884567711056ca5c12f1bb477c78b1 blob + 676299fa284382a424d9a816b30a8418dc0cca02 --- lib/object.c +++ lib/object.c @@ -832,12 +832,70 @@ got_object_tree_open(struct got_tree_object **tree, return open_tree(tree, repo, got_object_get_id(obj), 1); } -const struct got_tree_entries * -got_object_tree_get_entries(struct got_tree_object *tree) +int +got_object_tree_get_nentries(struct got_tree_object *tree) { - return &tree->entries; + return tree->nentries; } +struct got_tree_entry * +got_object_tree_get_first_entry(struct got_tree_object *tree) +{ + return got_object_tree_get_entry(tree, 0); +} + +struct got_tree_entry * +got_object_tree_get_last_entry(struct got_tree_object *tree) +{ + return got_object_tree_get_entry(tree, tree->nentries - 1); +} + +struct got_tree_entry * +got_object_tree_get_entry(struct got_tree_object *tree, int i) +{ + if (i < 0 || i >= tree->nentries) + return NULL; + return &tree->entries[i]; +} + +mode_t +got_tree_entry_get_mode(struct got_tree_entry *te) +{ + return te->mode; +} + +const char * +got_tree_entry_get_name(struct got_tree_entry *te) +{ + return &te->name[0]; +} + +struct got_object_id * +got_tree_entry_get_id(struct got_tree_entry *te) +{ + return &te->id; +} + +int +got_tree_entry_get_index(struct got_tree_entry *te) +{ + return te->idx; +} + +struct got_tree_entry * +got_tree_entry_get_next(struct got_tree_object *tree, + struct got_tree_entry *te) +{ + return got_object_tree_get_entry(tree, te->idx + 1); +} + +struct got_tree_entry * +got_tree_entry_get_prev(struct got_tree_object *tree, + struct got_tree_entry *te) +{ + return got_object_tree_get_entry(tree, te->idx - 1); +} + static const struct got_error * request_packed_blob(uint8_t **outbuf, size_t *size, size_t *hdrlen, int outfd, struct got_pack *pack, struct got_packidx *packidx, int idx, @@ -1477,10 +1535,11 @@ got_object_tag_get_message(struct got_tag_object *tag) static struct got_tree_entry * find_entry_by_name(struct got_tree_object *tree, const char *name, size_t len) { - struct got_tree_entry *te; + int i; /* Note that tree entries are sorted in strncmp() order. */ - SIMPLEQ_FOREACH(te, &tree->entries.head, entry) { + for (i = 0; i < tree->nentries; i++) { + struct got_tree_entry *te = &tree->entries[i]; int cmp = strncmp(te->name, name, len); if (cmp < 0) continue; @@ -1492,7 +1551,7 @@ find_entry_by_name(struct got_tree_object *tree, const return NULL; } -const struct got_tree_entry * +struct got_tree_entry * got_object_tree_find_entry(struct got_tree_object *tree, const char *name) { return find_entry_by_name(tree, name, strlen(name)); @@ -1556,7 +1615,7 @@ got_object_id_by_path(struct got_object_id **id, struc s++; if (*s) { err = got_object_open_as_tree(&next_tree, repo, - te->id); + &te->id); te = NULL; if (err) goto done; @@ -1566,7 +1625,7 @@ got_object_id_by_path(struct got_object_id **id, struc } if (te) { - *id = got_object_id_dup(te->id); + *id = got_object_id_dup(&te->id); if (*id == NULL) return got_error_from_errno("got_object_id_dup"); } else @@ -1633,7 +1692,7 @@ got_object_tree_path_changed(int *changed, goto done; } - if (got_object_id_cmp(te1->id, te2->id) == 0) { + if (got_object_id_cmp(&te1->id, &te2->id) == 0) { *changed = 0; goto done; } @@ -1648,7 +1707,7 @@ got_object_tree_path_changed(int *changed, seglen = 0; if (*s) { err = got_object_open_as_tree(&next_tree1, repo, - te1->id); + &te1->id); te1 = NULL; if (err) goto done; @@ -1657,7 +1716,7 @@ got_object_tree_path_changed(int *changed, tree1 = next_tree1; err = got_object_open_as_tree(&next_tree2, repo, - te2->id); + &te2->id); te2 = NULL; if (err) goto done; @@ -1685,27 +1744,13 @@ got_object_tree_entry_dup(struct got_tree_entry **new_ return got_error_from_errno("calloc"); (*new_te)->mode = te->mode; - (*new_te)->name = strdup(te->name); - if ((*new_te)->name == NULL) { - err = got_error_from_errno("strdup"); - goto done; - } - - (*new_te)->id = got_object_id_dup(te->id); - if ((*new_te)->id == NULL) { - err = got_error_from_errno("got_object_id_dup"); - goto done; - } -done: - if (err) { - got_object_tree_entry_close(*new_te); - *new_te = NULL; - } + memcpy((*new_te)->name, te->name, sizeof((*new_te)->name)); + memcpy(&(*new_te)->id, &te->id, sizeof((*new_te)->id)); return err; } int -got_object_tree_entry_is_submodule(const struct got_tree_entry *te) +got_object_tree_entry_is_submodule(struct got_tree_entry *te) { return (te->mode & S_IFMT) == (S_IFDIR | S_IFLNK); } blob - c67ff751c1fbd694ef012e6ec8f54283f24acdf3 blob + 951d94e90b1a71e5c4b380a8b730e85ebc13f628 --- lib/object_cache.c +++ lib/object_cache.c @@ -21,6 +21,7 @@ #include <stdlib.h> #include <stdint.h> #include <string.h> +#include <limits.h> #include <sha1.h> #include <zlib.h> @@ -96,14 +97,8 @@ size_t get_size_tree(struct got_tree_object *tree) { size_t size = sizeof(*tree); - struct got_tree_entry *te; - SIMPLEQ_FOREACH(te, &tree->entries.head, entry) { - size += sizeof(*te); - size += strlen(te->name); - size += sizeof(*te->id); - } - + size += sizeof(struct got_tree_entry) * tree->nentries; return size; } blob - 0f37c4e073eac150d17ee0bcb78a15d01f27dce6 blob + cd56ee24ad04cda9b35ed84a84df1615626c2929 --- lib/object_create.c +++ lib/object_create.c @@ -21,6 +21,7 @@ #include <ctype.h> #include <errno.h> #include <fcntl.h> +#include <limits.h> #include <stdio.h> #include <stdlib.h> #include <string.h> @@ -210,117 +211,32 @@ mode2str(char *buf, size_t len, mode_t mode) return NULL; } - -static const struct got_error * -te_git_name(char **name, struct got_tree_entry *te) -{ - const struct got_error *err = NULL; - - if (S_ISDIR(te->mode)) { - if (asprintf(name, "%s/", te->name) == -1) - err = got_error_from_errno("asprintf"); - } else { - *name = strdup(te->name); - if (*name == NULL) - err = got_error_from_errno("strdup"); - } - return err; -} - -static const struct got_error * -insert_tree_entry(struct got_tree_entries *sorted, struct got_tree_entry *new) -{ - const struct got_error *err = NULL; - struct got_tree_entry *te = NULL, *prev = NULL; - char *name; - int cmp; - - if (SIMPLEQ_EMPTY(&sorted->head)) { - SIMPLEQ_INSERT_HEAD(&sorted->head, new, entry); - sorted->nentries++; - return NULL; - } - - err = te_git_name(&name, new); - if (err) - return err; - - te = SIMPLEQ_FIRST(&sorted->head); - while (te) { - char *te_name; - if (prev == NULL) { - prev = te; - te = SIMPLEQ_NEXT(te, entry); - continue; - } - err = te_git_name(&te_name, te); - if (err) - goto done; - cmp = strcmp(te_name, name); - free(te_name); - if (cmp == 0) { - err = got_error(GOT_ERR_TREE_DUP_ENTRY); - goto done; - } - if (cmp > 0) { - SIMPLEQ_INSERT_AFTER(&sorted->head, prev, new, entry); - sorted->nentries++; - break; - } - prev = te; - te = SIMPLEQ_NEXT(te, entry); - } - - if (te == NULL) { - SIMPLEQ_INSERT_TAIL(&sorted->head, new, entry); - sorted->nentries++; - } -done: - free(name); - return err; -} - /* * Git expects directory tree entries to be sorted with an imaginary slash * appended to their name, and will break otherwise. Let's be nice. + * This function is intended to be used with mergesort(3) to sort an + * array of pointers to struct got_tree_entry objects. */ -static const struct got_error * -sort_tree_entries_the_way_git_likes_it(struct got_tree_entries **sorted, - struct got_tree_entries *tree_entries) +static int +sort_tree_entries_the_way_git_likes_it(const void *arg1, const void *arg2) { - const struct got_error *err = NULL; - struct got_tree_entry *te; + struct got_tree_entry * const *te1 = arg1; + struct got_tree_entry * const *te2 = arg2; + char name1[NAME_MAX + 1]; + char name2[NAME_MAX + 1]; - *sorted = malloc(sizeof(**sorted)); - if (*sorted == NULL) - return got_error_from_errno("malloc"); - - (*sorted)->nentries = 0; - SIMPLEQ_INIT(&(*sorted)->head); - - SIMPLEQ_FOREACH(te, &tree_entries->head, entry) { - struct got_tree_entry *new; - err = got_object_tree_entry_dup(&new, te); - if (err) - break; - err = insert_tree_entry(*sorted, new); - if (err) { - got_object_tree_entry_close(new); - break; - } - } - - if (err) { - free(*sorted); - *sorted = NULL; - } - - return err; + strlcpy(name1, (*te1)->name, sizeof(name1)); + strlcpy(name2, (*te2)->name, sizeof(name2)); + if (S_ISDIR((*te1)->mode)) + strlcat(name1, "/", sizeof(name1)); + if (S_ISDIR((*te2)->mode)) + strlcat(name2, "/", sizeof(name2)); + return strcmp(name1, name2); } const struct got_error * got_object_tree_create(struct got_object_id **id, - struct got_tree_entries *tree_entries, struct got_repository *repo) + struct got_pathlist_head *paths, int nentries, struct got_repository *repo) { const struct got_error *err = NULL; char modebuf[sizeof("100644 ")]; @@ -328,18 +244,27 @@ got_object_tree_create(struct got_object_id **id, char *header = NULL; size_t headerlen, len = 0, n; FILE *treefile = NULL; - struct got_tree_entries *entries; /* sorted according to Git rules */ + struct got_pathlist_entry *pe; + struct got_tree_entry **sorted_entries; struct got_tree_entry *te; + int i; *id = NULL; SHA1Init(&sha1_ctx); - err = sort_tree_entries_the_way_git_likes_it(&entries, tree_entries); - if (err) - return err; + sorted_entries = calloc(nentries, sizeof(struct got_tree_entry *)); + if (sorted_entries == NULL) + return got_error_from_errno("calloc"); - SIMPLEQ_FOREACH(te, &entries->head, entry) { + i = 0; + TAILQ_FOREACH(pe, paths, entry) + sorted_entries[i++] = pe->data; + mergesort(sorted_entries, nentries, sizeof(struct got_tree_entry *), + sort_tree_entries_the_way_git_likes_it); + + for (i = 0; i < nentries; i++) { + te = sorted_entries[i]; err = mode2str(modebuf, sizeof(modebuf), te->mode); if (err) goto done; @@ -366,7 +291,8 @@ got_object_tree_create(struct got_object_id **id, goto done; } - SIMPLEQ_FOREACH(te, &entries->head, entry) { + for (i = 0; i < nentries; i++) { + te = sorted_entries[i]; err = mode2str(modebuf, sizeof(modebuf), te->mode); if (err) goto done; @@ -387,12 +313,12 @@ got_object_tree_create(struct got_object_id **id, SHA1Update(&sha1_ctx, te->name, len); len = SHA1_DIGEST_LENGTH; - n = fwrite(te->id->sha1, 1, len, treefile); + n = fwrite(te->id.sha1, 1, len, treefile); if (n != len) { err = got_ferror(treefile, GOT_ERR_IO); goto done; } - SHA1Update(&sha1_ctx, te->id->sha1, len); + SHA1Update(&sha1_ctx, te->id.sha1, len); } *id = malloc(sizeof(**id)); @@ -411,8 +337,7 @@ got_object_tree_create(struct got_object_id **id, err = create_object_file(*id, treefile, repo); done: free(header); - got_object_tree_entries_close(entries); - free(entries); + free(sorted_entries); if (treefile && fclose(treefile) != 0 && err == NULL) err = got_error_from_errno("fclose"); if (err) { blob - 912407084a50328b63f743b536ff77698ad6d979 blob + 6cbd86452cc57df644a546d9772e9d89fe4b7976 --- lib/object_parse.c +++ lib/object_parse.c @@ -614,26 +614,6 @@ done: } void -got_object_tree_entry_close(struct got_tree_entry *te) -{ - free(te->id); - free(te->name); - free(te); -} - -void -got_object_tree_entries_close(struct got_tree_entries *entries) -{ - struct got_tree_entry *te; - - while (!SIMPLEQ_EMPTY(&entries->head)) { - te = SIMPLEQ_FIRST(&entries->head); - SIMPLEQ_REMOVE_HEAD(&entries->head, entry); - got_object_tree_entry_close(te); - } -} - -void got_object_tree_close(struct got_tree_object *tree) { if (tree->refcnt > 0) { @@ -642,25 +622,8 @@ got_object_tree_close(struct got_tree_object *tree) return; } - got_object_tree_entries_close(&tree->entries); + free(tree->entries); free(tree); -} - -struct got_tree_entry * -got_alloc_tree_entry_partial(void) -{ - struct got_tree_entry *te; - - te = malloc(sizeof(*te)); - if (te == NULL) - return NULL; - - te->id = malloc(sizeof(*te->id)); - if (te->id == NULL) { - free(te); - te = NULL; - } - return te; } static const struct got_error * blob - 72b117bda7b580c8148fc198ffdf9d09d95fc927 blob + e6cfe31da698ae3a453b783d83fddd18b3d803e5 --- lib/privsep.c +++ lib/privsep.c @@ -785,7 +785,7 @@ get_more: n = imsg_get(ibuf, &imsg); if (n == 0) { - if (*tree && (*tree)->entries.nentries != nentries) + if (*tree && (*tree)->nentries != nentries) goto get_more; break; } @@ -815,8 +815,13 @@ get_more: err = got_error_from_errno("malloc"); break; } - (*tree)->entries.nentries = itree->nentries; - SIMPLEQ_INIT(&(*tree)->entries.head); + (*tree)->entries = calloc(itree->nentries, + sizeof(struct got_tree_entry)); + if ((*tree)->entries == NULL) { + err = got_error_from_errno("malloc"); + break; + } + (*tree)->nentries = itree->nentries; (*tree)->refcnt = 0; break; case GOT_IMSG_TREE_ENTRY: @@ -838,24 +843,17 @@ get_more: } ite = imsg.data; - te = got_alloc_tree_entry_partial(); - if (te == NULL) { - err = got_error_from_errno( - "got_alloc_tree_entry_partial"); + if (datalen + 1 > sizeof(te->name)) { + err = got_error(GOT_ERR_NO_SPACE); break; } - te->name = malloc(datalen + 1); - if (te->name == NULL) { - free(te); - err = got_error_from_errno("malloc"); - break; - } + te = &(*tree)->entries[nentries]; memcpy(te->name, imsg.data + sizeof(*ite), datalen); te->name[datalen] = '\0'; - memcpy(te->id->sha1, ite->id, SHA1_DIGEST_LENGTH); + memcpy(te->id.sha1, ite->id, SHA1_DIGEST_LENGTH); te->mode = ite->mode; - SIMPLEQ_INSERT_TAIL(&(*tree)->entries.head, te, entry); + te->idx = nentries; nentries++; break; default: @@ -866,7 +864,7 @@ get_more: imsg_free(&imsg); } done: - if (*tree && (*tree)->entries.nentries != nentries) { + if (*tree && (*tree)->nentries != nentries) { if (err == NULL) err = got_error(GOT_ERR_PRIVSEP_LEN); got_object_tree_close(*tree); blob - b7c702a676bb40a91a470d8fb32d5501e32c18cb blob + 439627eae44fd277d180de1edf1539b5e44f6c2c --- lib/reference.c +++ lib/reference.c @@ -21,6 +21,7 @@ #include <errno.h> #include <ctype.h> #include <dirent.h> +#include <limits.h> #include <sha1.h> #include <stdio.h> #include <stdlib.h> blob - 9dffdcd83aa6b08ebbb5d3c8526500f507c72877 blob + a5b0f8fded6c31a6c08dace849ceda974c1ef3c8 --- lib/repository.c +++ lib/repository.c @@ -1349,17 +1349,17 @@ alloc_added_blob_tree_entry(struct got_tree_entry **ne if (*new_te == NULL) return got_error_from_errno("calloc"); - (*new_te)->name = strdup(name); - if ((*new_te)->name == NULL) { - err = got_error_from_errno("strdup"); + if (strlcpy((*new_te)->name, name, sizeof((*new_te)->name)) >= + sizeof((*new_te)->name)) { + err = got_error(GOT_ERR_NO_SPACE); goto done; } (*new_te)->mode = S_IFREG | (mode & ((S_IRWXU | S_IRWXG | S_IRWXO))); - (*new_te)->id = blob_id; + memcpy(&(*new_te)->id, blob_id, sizeof((*new_te)->id)); done: if (err && *new_te) { - got_object_tree_entry_close(*new_te); + free(*new_te); *new_te = NULL; } return err; @@ -1422,6 +1422,7 @@ import_subdir(struct got_tree_entry **new_te, struct d got_repo_import_cb progress_cb, void *progress_arg) { const struct got_error *err; + struct got_object_id *id = NULL; char *subdirpath; if (asprintf(&subdirpath, "%s%s%s", path, @@ -1432,18 +1433,22 @@ import_subdir(struct got_tree_entry **new_te, struct d if (*new_te == NULL) return got_error_from_errno("calloc"); (*new_te)->mode = S_IFDIR; - (*new_te)->name = strdup(de->d_name); - if ((*new_te)->name == NULL) { - err = got_error_from_errno("strdup"); + if (strlcpy((*new_te)->name, de->d_name, sizeof((*new_te)->name)) >= + sizeof((*new_te)->name)) { + err = got_error(GOT_ERR_NO_SPACE); goto done; } - - err = write_tree(&(*new_te)->id, subdirpath, ignores, repo, + err = write_tree(&id, subdirpath, ignores, repo, progress_cb, progress_arg); + if (err) + goto done; + memcpy(&(*new_te)->id, id, sizeof((*new_te)->id)); + done: + free(id); free(subdirpath); if (err) { - got_object_tree_entry_close(*new_te); + free(*new_te); *new_te = NULL; } return err; @@ -1457,7 +1462,7 @@ write_tree(struct got_object_id **new_tree_id, const c const struct got_error *err = NULL; DIR *dir; struct dirent *de; - struct got_tree_entries new_tree_entries; + int nentries; struct got_tree_entry *new_te = NULL; struct got_pathlist_head paths; struct got_pathlist_entry *pe; @@ -1465,8 +1470,6 @@ write_tree(struct got_object_id **new_tree_id, const c *new_tree_id = NULL; TAILQ_INIT(&paths); - new_tree_entries.nentries = 0; - SIMPLEQ_INIT(&new_tree_entries.head); dir = opendir(path_dir); if (dir == NULL) { @@ -1474,6 +1477,7 @@ write_tree(struct got_object_id **new_tree_id, const c goto done; } + nentries = 0; while ((de = readdir(dir)) != NULL) { int ignore = 0; @@ -1508,6 +1512,7 @@ write_tree(struct got_object_id **new_tree_id, const c err = insert_tree_entry(new_te, &paths); if (err) goto done; + nentries++; } if (TAILQ_EMPTY(&paths)) { @@ -1518,8 +1523,6 @@ write_tree(struct got_object_id **new_tree_id, const c TAILQ_FOREACH(pe, &paths, entry) { struct got_tree_entry *te = pe->data; char *path; - new_tree_entries.nentries++; - SIMPLEQ_INSERT_TAIL(&new_tree_entries.head, te, entry); if (!S_ISREG(te->mode)) continue; if (asprintf(&path, "%s/%s", path_dir, pe->path) == -1) { @@ -1532,11 +1535,10 @@ write_tree(struct got_object_id **new_tree_id, const c goto done; } - err = got_object_tree_create(new_tree_id, &new_tree_entries, repo); + err = got_object_tree_create(new_tree_id, &paths, nentries, repo); done: if (dir) closedir(dir); - got_object_tree_entries_close(&new_tree_entries); got_pathlist_free(&paths); return err; } blob - 7f537736429accac7e42d3ec791edb2abbed2205 blob + c56c307e7fad0d579e6eb3fa799150a8b8d31558 --- lib/worktree.c +++ lib/worktree.c @@ -1271,14 +1271,14 @@ update_blob(struct got_worktree *worktree, goto done; } if (got_fileindex_entry_has_blob(ie) && - memcmp(ie->blob_sha1, te->id->sha1, + memcmp(ie->blob_sha1, te->id.sha1, SHA1_DIGEST_LENGTH) == 0) { err = sync_timestamps(ondisk_path, status, ie, &sb); goto done; } } - err = got_object_open_as_blob(&blob, repo, te->id, 8192); + err = got_object_open_as_blob(&blob, repo, &te->id, 8192); if (err) goto done; @@ -3683,7 +3683,7 @@ write_subtree(struct got_object_id **new_subtree_id, got_path_is_root_dir(parent_path) ? "" : "/", te->name) == -1) return got_error_from_errno("asprintf"); - err = got_object_open_as_tree(&subtree, repo, te->id); + err = got_object_open_as_tree(&subtree, repo, &te->id); if (err) return err; @@ -3735,18 +3735,14 @@ alloc_modified_blob_tree_entry(struct got_tree_entry * (*new_te)->mode = get_ct_file_mode(ct); - free((*new_te)->id); if (ct->staged_status == GOT_STATUS_MODIFY) - (*new_te)->id = got_object_id_dup(ct->staged_blob_id); + memcpy(&(*new_te)->id, ct->staged_blob_id, + sizeof((*new_te)->id)); else - (*new_te)->id = got_object_id_dup(ct->blob_id); - if ((*new_te)->id == NULL) { - err = got_error_from_errno("got_object_id_dup"); - goto done; - } + memcpy(&(*new_te)->id, ct->blob_id, sizeof((*new_te)->id)); done: if (err && *new_te) { - got_object_tree_entry_close(*new_te); + free(*new_te); *new_te = NULL; } return err; @@ -3770,25 +3766,22 @@ alloc_added_blob_tree_entry(struct got_tree_entry **ne err = got_error_from_errno2("basename", ct->path); goto done; } - (*new_te)->name = strdup(ct_name); - if ((*new_te)->name == NULL) { - err = got_error_from_errno("strdup"); + if (strlcpy((*new_te)->name, ct_name, sizeof((*new_te)->name)) >= + sizeof((*new_te)->name)) { + err = got_error(GOT_ERR_NO_SPACE); goto done; } (*new_te)->mode = get_ct_file_mode(ct); if (ct->staged_status == GOT_STATUS_ADD) - (*new_te)->id = got_object_id_dup(ct->staged_blob_id); + memcpy(&(*new_te)->id, ct->staged_blob_id, + sizeof((*new_te)->id)); else - (*new_te)->id = got_object_id_dup(ct->blob_id); - if ((*new_te)->id == NULL) { - err = got_error_from_errno("got_object_id_dup"); - goto done; - } + memcpy(&(*new_te)->id, ct->blob_id, sizeof((*new_te)->id)); done: if (err && *new_te) { - got_object_tree_entry_close(*new_te); + free(*new_te); *new_te = NULL; } return err; @@ -3881,7 +3874,7 @@ match_deleted_or_modified_ct(struct got_commitable **c continue; } - if (got_object_id_cmp(ct->base_blob_id, te->id) != 0) + if (got_object_id_cmp(ct->base_blob_id, &te->id) != 0) continue; err = match_ct_parent_path(&path_matches, ct, base_tree_path); @@ -3914,6 +3907,7 @@ make_subtree_for_added_blob(struct got_tree_entry **ne const struct got_error *err = NULL; struct got_tree_entry *new_te; char *subtree_path; + struct got_object_id *id = NULL; *new_tep = NULL; @@ -3926,19 +3920,21 @@ make_subtree_for_added_blob(struct got_tree_entry **ne if (new_te == NULL) return got_error_from_errno("calloc"); new_te->mode = S_IFDIR; - new_te->name = strdup(child_path); - if (new_te->name == NULL) { - err = got_error_from_errno("strdup"); - got_object_tree_entry_close(new_te); + + if (strlcpy(new_te->name, child_path, sizeof(new_te->name)) >= + sizeof(new_te->name)) { + err = got_error(GOT_ERR_NO_SPACE); goto done; } - err = write_tree(&new_te->id, NULL, subtree_path, + err = write_tree(&id, NULL, subtree_path, commitable_paths, status_cb, status_arg, repo); if (err) { - got_object_tree_entry_close(new_te); + free(new_te); goto done; } + memcpy(&new_te->id, id, sizeof(new_te->id)); done: + free(id); free(subtree_path); if (err == NULL) *new_tep = new_te; @@ -3953,15 +3949,12 @@ write_tree(struct got_object_id **new_tree_id, struct got_repository *repo) { const struct got_error *err = NULL; - const struct got_tree_entries *base_entries = NULL; struct got_pathlist_head paths; - struct got_tree_entries new_tree_entries; struct got_tree_entry *te, *new_te = NULL; struct got_pathlist_entry *pe; + int nentries = 0; TAILQ_INIT(&paths); - new_tree_entries.nentries = 0; - SIMPLEQ_INIT(&new_tree_entries.head); /* Insert, and recurse into, newly added entries first. */ TAILQ_FOREACH(pe, commitable_paths, entry) { @@ -3994,6 +3987,7 @@ write_tree(struct got_object_id **new_tree_id, err = insert_tree_entry(new_te, &paths); if (err) goto done; + nentries++; } else { *slash = '\0'; /* trim trailing path components */ if (base_tree == NULL || @@ -4008,16 +4002,19 @@ write_tree(struct got_object_id **new_tree_id, err = insert_tree_entry(new_te, &paths); if (err) goto done; + nentries++; } } } if (base_tree) { + int i, nbase_entries; /* Handle modified and deleted entries. */ - base_entries = got_object_tree_get_entries(base_tree); - SIMPLEQ_FOREACH(te, &base_entries->head, entry) { + nbase_entries = got_object_tree_get_nentries(base_tree); + for (i = 0; i < nbase_entries; i++) { struct got_commitable *ct = NULL; + te = got_object_tree_get_entry(base_tree, i); if (got_object_tree_entry_is_submodule(te)) { /* Entry is a submodule; just copy it. */ err = got_object_tree_entry_dup(&new_te, te); @@ -4026,6 +4023,7 @@ write_tree(struct got_object_id **new_tree_id, err = insert_tree_entry(new_te, &paths); if (err) goto done; + nentries++; continue; } @@ -4040,16 +4038,20 @@ write_tree(struct got_object_id **new_tree_id, goto done; /* Avoid recursion into unmodified subtrees. */ if (modified) { - free(new_te->id); - err = write_subtree(&new_te->id, te, + struct got_object_id *new_id; + err = write_subtree(&new_id, te, path_base_tree, commitable_paths, status_cb, status_arg, repo); if (err) goto done; + memcpy(&new_te->id, new_id, + sizeof(new_te->id)); + free(new_id); } err = insert_tree_entry(new_te, &paths); if (err) goto done; + nentries++; continue; } @@ -4069,6 +4071,7 @@ write_tree(struct got_object_id **new_tree_id, err = insert_tree_entry(new_te, &paths); if (err) goto done; + nentries++; } err = report_ct_status(ct, status_cb, status_arg); @@ -4082,19 +4085,14 @@ write_tree(struct got_object_id **new_tree_id, err = insert_tree_entry(new_te, &paths); if (err) goto done; + nentries++; } } } /* Write new list of entries; deleted entries have been dropped. */ - TAILQ_FOREACH(pe, &paths, entry) { - struct got_tree_entry *te = pe->data; - new_tree_entries.nentries++; - SIMPLEQ_INSERT_TAIL(&new_tree_entries.head, te, entry); - } - err = got_object_tree_create(new_tree_id, &new_tree_entries, repo); + err = got_object_tree_create(new_tree_id, &paths, nentries, repo); done: - got_object_tree_entries_close(&new_tree_entries); got_pathlist_free(&paths); return err; } blob - 9a8671fcef058130186736a3dc39b490362cc7ef blob + ba2b42bdfcb5a8abcf06df94f35d91f85ca419cb --- regress/idset/idset_test.c +++ regress/idset/idset_test.c @@ -16,6 +16,7 @@ #include <sys/queue.h> +#include <limits.h> #include <stdarg.h> #include <stdlib.h> #include <stdio.h> blob - 1586b0cde4e0cf1d65db30b9a5e44ae7a347674a blob + fba0211e89a10dbfe6e65eae4d1a4d72c1359d07 --- tog/tog.c +++ tog/tog.c @@ -366,7 +366,6 @@ struct tog_tree_view_state { char *tree_label; struct got_tree_object *root; struct got_tree_object *tree; - const struct got_tree_entries *entries; struct got_tree_entry *first_displayed_entry; struct got_tree_entry *last_displayed_entry; struct got_tree_entry *selected_entry; @@ -1768,7 +1767,6 @@ tree_view_visit_subtree(struct got_tree_object *subtre parent->selected = s->selected; TAILQ_INSERT_HEAD(&s->parents, parent, entry); s->tree = subtree; - s->entries = got_object_tree_get_entries(s->tree); s->selected = 0; s->first_displayed_entry = NULL; return NULL; @@ -1782,7 +1780,6 @@ browse_commit_tree(struct tog_view **new_view, int beg { const struct got_error *err = NULL; struct got_tree_object *tree; - struct got_tree_entry *te; struct tog_tree_view_state *s; struct tog_view *tree_view; char *slash, *subpath = NULL; @@ -1811,27 +1808,33 @@ browse_commit_tree(struct tog_view **new_view, int beg while (p[0] == '/') p++; while (*p) { + struct got_tree_entry *te; struct got_object_id *tree_id; + char *te_name; /* Ensure the correct subtree entry is selected. */ slash = strchr(p, '/'); if (slash == NULL) slash = strchr(p, '\0'); - SIMPLEQ_FOREACH(te, &s->entries->head, entry) { - if (strncmp(p, te->name, slash - p) == 0) { - s->selected_entry = te; - break; - } - s->selected++; + + te_name = strndup(p, slash -p); + if (te_name == NULL) { + err = got_error_from_errno("strndup"); + break; } - if (s->selected_entry == NULL) { - err = got_error(GOT_ERR_NO_TREE_ENTRY); + te = got_object_tree_find_entry(s->tree, te_name); + if (te == NULL) { + err = got_error_path(te_name, GOT_ERR_NO_TREE_ENTRY); + free(te_name); break; } + free(te_name); + s->selected_entry = te; + s->selected = got_tree_entry_get_index(te); if (s->tree != s->root) s->selected++; /* skip '..' */ - if (!S_ISDIR(s->selected_entry->mode)) { + if (!S_ISDIR(got_tree_entry_get_mode(s->selected_entry))) { /* Jump to this file's entry. */ s->first_displayed_entry = s->selected_entry; s->selected = 0; @@ -4258,14 +4261,14 @@ draw_tree_entries(struct tog_view *view, struct got_tree_entry **last_displayed_entry, struct got_tree_entry **selected_entry, int *ndisplayed, const char *label, int show_ids, const char *parent_path, - const struct got_tree_entries *entries, int selected, int limit, + struct got_tree_object *tree, int selected, int limit, int isroot, struct tog_colors *colors) { const struct got_error *err = NULL; struct got_tree_entry *te; wchar_t *wline; struct tog_color *tc; - int width, n; + int width, n, i, nentries; *ndisplayed = 0; @@ -4309,8 +4312,8 @@ draw_tree_entries(struct tog_view *view, if (--limit <= 0) return NULL; - te = SIMPLEQ_FIRST(&entries->head); if (*first_displayed_entry == NULL) { + te = got_object_tree_get_first_entry(tree); if (selected == 0) { if (view->focussed) wstandout(view->window); @@ -4325,30 +4328,35 @@ draw_tree_entries(struct tog_view *view, n = 1; } else { n = 0; - while (te != *first_displayed_entry) - te = SIMPLEQ_NEXT(te, entry); + te = *first_displayed_entry; } - while (te) { + nentries = got_object_tree_get_nentries(tree); + for (i = got_tree_entry_get_index(te); i < nentries; i++) { char *line = NULL, *id_str = NULL; const char *modestr = ""; + mode_t mode; + te = got_object_tree_get_entry(tree, i); + mode = got_tree_entry_get_mode(te); + if (show_ids) { - err = got_object_id_str(&id_str, te->id); + err = got_object_id_str(&id_str, + got_tree_entry_get_id(te)); if (err) return got_error_from_errno( "got_object_id_str"); } if (got_object_tree_entry_is_submodule(te)) modestr = "$"; - else if (S_ISLNK(te->mode)) + else if (S_ISLNK(mode)) modestr = "@"; - else if (S_ISDIR(te->mode)) + else if (S_ISDIR(mode)) modestr = "/"; - else if (te->mode & S_IXUSR) + else if (mode & S_IXUSR) modestr = "*"; if (asprintf(&line, "%s %s%s", id_str ? id_str : "", - te->name, modestr) == -1) { + got_tree_entry_get_name(te), modestr) == -1) { free(id_str); return got_error_from_errno("asprintf"); } @@ -4383,7 +4391,6 @@ draw_tree_entries(struct tog_view *view, *last_displayed_entry = te; if (--limit <= 0) break; - te = SIMPLEQ_NEXT(te, entry); } return err; @@ -4392,52 +4399,50 @@ draw_tree_entries(struct tog_view *view, static void tree_scroll_up(struct tog_view *view, struct got_tree_entry **first_displayed_entry, int maxscroll, - const struct got_tree_entries *entries, int isroot) + struct got_tree_object *tree, int isroot) { - struct got_tree_entry *te, *prev; + struct got_tree_entry *te; int i; if (*first_displayed_entry == NULL) return; - te = SIMPLEQ_FIRST(&entries->head); + te = got_object_tree_get_entry(tree, 0); if (*first_displayed_entry == te) { if (!isroot) *first_displayed_entry = NULL; return; } - /* XXX this is stupid... switch to TAILQ? */ - for (i = 0; i < maxscroll; i++) { - while (te != *first_displayed_entry) { - prev = te; - te = SIMPLEQ_NEXT(te, entry); - } - *first_displayed_entry = prev; - te = SIMPLEQ_FIRST(&entries->head); + i = 0; + while (*first_displayed_entry && i < maxscroll) { + *first_displayed_entry = got_tree_entry_get_prev(tree, + *first_displayed_entry); + i++; } - if (!isroot && te == SIMPLEQ_FIRST(&entries->head) && i < maxscroll) + if (!isroot && te == got_object_tree_get_first_entry(tree) && i < maxscroll) *first_displayed_entry = NULL; } static int tree_scroll_down(struct got_tree_entry **first_displayed_entry, int maxscroll, struct got_tree_entry *last_displayed_entry, - const struct got_tree_entries *entries) + struct got_tree_object *tree) { struct got_tree_entry *next, *last; int n = 0; if (*first_displayed_entry) - next = SIMPLEQ_NEXT(*first_displayed_entry, entry); + next = got_tree_entry_get_next(tree, *first_displayed_entry); else - next = SIMPLEQ_FIRST(&entries->head); + next = got_object_tree_get_first_entry(tree); + last = last_displayed_entry; while (next && last && n++ < maxscroll) { - last = SIMPLEQ_NEXT(last, entry); + last = got_tree_entry_get_next(tree, last); if (last) { *first_displayed_entry = next; - next = SIMPLEQ_NEXT(next, entry); + next = got_tree_entry_get_next(tree, next); } } return n; @@ -4452,9 +4457,10 @@ tree_entry_path(char **path, struct tog_parent_trees * size_t len = 2; /* for leading slash and NUL */ TAILQ_FOREACH(pt, parents, entry) - len += strlen(pt->selected_entry->name) + 1 /* slash */; + len += strlen(got_tree_entry_get_name(pt->selected_entry)) + + 1 /* slash */; if (te) - len += strlen(te->name); + len += strlen(got_tree_entry_get_name(te)); *path = calloc(1, len); if (path == NULL) @@ -4463,7 +4469,8 @@ tree_entry_path(char **path, struct tog_parent_trees * (*path)[0] = '/'; pt = TAILQ_LAST(parents, tog_parent_trees); while (pt) { - if (strlcat(*path, pt->selected_entry->name, len) >= len) { + const char *name = got_tree_entry_get_name(pt->selected_entry); + if (strlcat(*path, name, len) >= len) { err = got_error(GOT_ERR_NO_SPACE); goto done; } @@ -4474,7 +4481,7 @@ tree_entry_path(char **path, struct tog_parent_trees * pt = TAILQ_PREV(pt, tog_parent_trees, entry); } if (te) { - if (strlcat(*path, te->name, len) >= len) { + if (strlcat(*path, got_tree_entry_get_name(te), len) >= len) { err = got_error(GOT_ERR_NO_SPACE); goto done; } @@ -4571,9 +4578,8 @@ open_tree_view(struct tog_view *view, struct got_tree_ } s->root = s->tree = root; - s->entries = got_object_tree_get_entries(root); - s->first_displayed_entry = SIMPLEQ_FIRST(&s->entries->head); - s->selected_entry = SIMPLEQ_FIRST(&s->entries->head); + s->first_displayed_entry = got_object_tree_get_entry(s->tree, 0); + s->selected_entry = got_object_tree_get_entry(s->tree, 0); s->commit_id = got_object_id_dup(commit_id); if (s->commit_id == NULL) { err = got_error_from_errno("got_object_id_dup"); @@ -4672,14 +4678,15 @@ match_tree_entry(struct got_tree_entry *te, regex_t *r { regmatch_t regmatch; - return regexec(regex, te->name, 1, &regmatch, 0) == 0; + return regexec(regex, got_tree_entry_get_name(te), 1, &regmatch, + 0) == 0; } static const struct got_error * search_next_tree_view(struct tog_view *view) { struct tog_tree_view_state *s = &view->state.tree; - struct got_tree_entry *entry = NULL, *te; + struct got_tree_entry *te = NULL; if (!view->searching) { view->search_next_done = 1; @@ -4689,66 +4696,46 @@ search_next_tree_view(struct tog_view *view) if (s->matched_entry) { if (view->searching == TOG_SEARCH_FORWARD) { if (s->selected_entry) - entry = SIMPLEQ_NEXT(s->selected_entry, entry); + te = got_tree_entry_get_next(s->tree, + s->selected_entry); else - entry = SIMPLEQ_FIRST(&s->entries->head); + te = got_object_tree_get_first_entry(s->tree); + } else { + if (s->selected_entry == NULL) + te = got_object_tree_get_last_entry(s->tree); + else + te = got_tree_entry_get_prev(s->tree, + s->selected_entry); } - else { - if (s->selected_entry == NULL) { - SIMPLEQ_FOREACH(te, &s->entries->head, entry) - entry = te; - } else { - SIMPLEQ_FOREACH(te, &s->entries->head, entry) { - entry = te; - if (SIMPLEQ_NEXT(te, entry) == - s->selected_entry) - break; - } - } - } } else { if (view->searching == TOG_SEARCH_FORWARD) - entry = SIMPLEQ_FIRST(&s->entries->head); - else { - SIMPLEQ_FOREACH(te, &s->entries->head, entry) - entry = te; - } + te = got_object_tree_get_first_entry(s->tree); + else + te = got_object_tree_get_last_entry(s->tree); } while (1) { - if (entry == NULL) { + if (te == NULL) { if (s->matched_entry == NULL) { view->search_next_done = 1; return NULL; } if (view->searching == TOG_SEARCH_FORWARD) - entry = SIMPLEQ_FIRST(&s->entries->head); - else { - SIMPLEQ_FOREACH(te, &s->entries->head, entry) - entry = te; - } + te = got_object_tree_get_first_entry(s->tree); + else + te = got_object_tree_get_last_entry(s->tree); } - if (match_tree_entry(entry, &view->regex)) { + if (match_tree_entry(te, &view->regex)) { view->search_next_done = 1; - s->matched_entry = entry; + s->matched_entry = te; break; } if (view->searching == TOG_SEARCH_FORWARD) - entry = SIMPLEQ_NEXT(entry, entry); - else { - if (SIMPLEQ_FIRST(&s->entries->head) == entry) - entry = NULL; - else { - SIMPLEQ_FOREACH(te, &s->entries->head, entry) { - if (SIMPLEQ_NEXT(te, entry) == entry) { - entry = te; - break; - } - } - } - } + te = got_tree_entry_get_next(s->tree, te); + else + te = got_tree_entry_get_prev(s->tree, te); } if (s->matched_entry) { @@ -4773,7 +4760,7 @@ show_tree_view(struct tog_view *view) err = draw_tree_entries(view, &s->first_displayed_entry, &s->last_displayed_entry, &s->selected_entry, &s->ndisplayed, s->tree_label, s->show_ids, parent_path, - s->entries, s->selected, view->nlines, s->tree == s->root, + s->tree, s->selected, view->nlines, s->tree == s->root, &s->colors); free(parent_path); @@ -4789,6 +4776,7 @@ input_tree_view(struct tog_view **new_view, struct tog struct tog_tree_view_state *s = &view->state.tree; struct tog_view *log_view; int begin_x = 0, nscrolled; + mode_t mode; switch (ch) { case 'i': @@ -4826,14 +4814,14 @@ input_tree_view(struct tog_view **new_view, struct tog if (s->selected > 0) break; tree_scroll_up(view, &s->first_displayed_entry, 1, - s->entries, s->tree == s->root); + s->tree, s->tree == s->root); break; case KEY_PPAGE: tree_scroll_up(view, &s->first_displayed_entry, - MAX(0, view->nlines - 4 - s->selected), s->entries, + MAX(0, view->nlines - 4 - s->selected), s->tree, s->tree == s->root); s->selected = 0; - if (SIMPLEQ_FIRST(&s->entries->head) == + if (got_object_tree_get_first_entry(s->tree) == s->first_displayed_entry && s->tree != s->root) s->first_displayed_entry = NULL; break; @@ -4843,14 +4831,15 @@ input_tree_view(struct tog_view **new_view, struct tog s->selected++; break; } - if (SIMPLEQ_NEXT(s->last_displayed_entry, entry) == NULL) + if (got_tree_entry_get_next(s->tree, s->last_displayed_entry) + == NULL) /* can't scroll any further */ break; tree_scroll_down(&s->first_displayed_entry, 1, - s->last_displayed_entry, s->entries); + s->last_displayed_entry, s->tree); break; case KEY_NPAGE: - if (SIMPLEQ_NEXT(s->last_displayed_entry, entry) + if (got_tree_entry_get_next(s->tree, s->last_displayed_entry) == NULL) { /* can't scroll any further; move cursor down */ if (s->selected < s->ndisplayed - 1) @@ -4858,14 +4847,14 @@ input_tree_view(struct tog_view **new_view, struct tog break; } nscrolled = tree_scroll_down(&s->first_displayed_entry, - view->nlines, s->last_displayed_entry, s->entries); + view->nlines, s->last_displayed_entry, s->tree); if (nscrolled < view->nlines) { int ndisplayed = 0; struct got_tree_entry *te; te = s->first_displayed_entry; do { ndisplayed++; - te = SIMPLEQ_NEXT(te, entry); + te = got_tree_entry_get_next(s->tree, te); } while (te); s->selected = ndisplayed - 1; } @@ -4873,6 +4862,7 @@ input_tree_view(struct tog_view **new_view, struct tog case KEY_ENTER: case '\r': case KEY_BACKSPACE: + mode = got_tree_entry_get_mode(s->selected_entry); if (s->selected_entry == NULL || ch == KEY_BACKSPACE) { struct tog_parent_tree *parent; /* user selected '..' */ @@ -4883,18 +4873,16 @@ input_tree_view(struct tog_view **new_view, struct tog entry); got_object_tree_close(s->tree); s->tree = parent->tree; - s->entries = - got_object_tree_get_entries(s->tree); s->first_displayed_entry = parent->first_displayed_entry; s->selected_entry = parent->selected_entry; s->selected = parent->selected; free(parent); - } else if (S_ISDIR(s->selected_entry->mode)) { + } else if (S_ISDIR(mode)) { struct got_tree_object *subtree; - err = got_object_open_as_tree(&subtree, - s->repo, s->selected_entry->id); + err = got_object_open_as_tree(&subtree, s->repo, + got_tree_entry_get_id(s->selected_entry)); if (err) break; err = tree_view_visit_subtree(subtree, s); @@ -4902,7 +4890,7 @@ input_tree_view(struct tog_view **new_view, struct tog got_object_tree_close(subtree); break; } - } else if (S_ISREG(s->selected_entry->mode)) { + } else if (S_ISREG(mode)) { struct tog_view *blame_view; int begin_x = view_is_parent_view(view) ? view_split_begin_x(view->begin_x) : 0;

2019-11-26 21:49 Stefan Sperling:
convert tree entries to an array
- 2019-11-28 02:34 Stefan Sperling:
  convert tree entries to an array