diff options
author | Russell Belfer <arrbee@arrbee.com> | 2012-02-23 03:15:35 +0400 |
---|---|---|
committer | Russell Belfer <arrbee@arrbee.com> | 2012-02-23 03:15:35 +0400 |
commit | 0534641dfec001794ae9a83cfd1cfc7acaef97b7 (patch) | |
tree | d17e72af0ae9a9435aef29cc388d50a67a3cc0b0 /src/iterator.c | |
parent | da337c806468d2d8a27dfa9ee5e75e476f5ad546 (diff) |
Fix iterators based on pull request feedback
This update addresses all of the feedback in pull request #570.
The biggest change was to create actual linked list stacks for
storing the tree and workdir iterator state. This cleaned up
the code a ton. Additionally, all of the static functions had
their 'git_' prefix removed, and a lot of other unnecessary
changes were removed from the original patch.
Diffstat (limited to 'src/iterator.c')
-rw-r--r-- | src/iterator.c | 431 |
1 files changed, 201 insertions, 230 deletions
diff --git a/src/iterator.c b/src/iterator.c index 805ff643e..c2b88ab84 100644 --- a/src/iterator.c +++ b/src/iterator.c @@ -10,36 +10,33 @@ #include "ignore.h" #include "buffer.h" -#define IDX_AS_PTR(I) (void *)((uint64_t)(I)) -#define PTR_AS_IDX(P) (unsigned int)((uint64_t)(P)) +typedef struct tree_iterator_frame tree_iterator_frame; +struct tree_iterator_frame { + tree_iterator_frame *next; + git_tree *tree; + unsigned int index; +}; typedef struct { - git_iterator cb; + git_iterator base; git_repository *repo; - git_vector tree_stack; - git_vector idx_stack; + tree_iterator_frame *stack; git_index_entry entry; git_buf path; -} git_iterator_tree; +} tree_iterator; -static const git_tree_entry *git_iterator__tree_entry(git_iterator_tree *ti) +static const git_tree_entry *tree_iterator__tree_entry(tree_iterator *ti) { - git_tree *tree; - unsigned int tree_idx; - - if ((tree = git_vector_last(&ti->tree_stack)) == NULL) - return NULL; - - tree_idx = PTR_AS_IDX(git_vector_last(&ti->idx_stack)); - return git_tree_entry_byindex(tree, tree_idx); + return (ti->stack == NULL) ? NULL : + git_tree_entry_byindex(ti->stack->tree, ti->stack->index); } -static int git_iterator__tree_current( +static int tree_iterator__current( git_iterator *self, const git_index_entry **entry) { int error; - git_iterator_tree *ti = (git_iterator_tree *)self; - const git_tree_entry *te = git_iterator__tree_entry(ti); + tree_iterator *ti = (tree_iterator *)self; + const git_tree_entry *te = tree_iterator__tree_entry(ti); *entry = NULL; @@ -58,132 +55,111 @@ static int git_iterator__tree_current( return GIT_SUCCESS; } -static int git_iterator__tree_at_end(git_iterator *self) +static int tree_iterator__at_end(git_iterator *self) { - git_iterator_tree *ti = (git_iterator_tree *)self; - git_tree *tree; - return ((tree = git_vector_last(&ti->tree_stack)) == NULL || - git_tree_entry_byindex( - tree, PTR_AS_IDX(git_vector_last(&ti->idx_stack))) == NULL); + return (tree_iterator__tree_entry((tree_iterator *)self) == NULL); } -static int expand_tree_if_needed(git_iterator_tree *ti) +static tree_iterator_frame *tree_iterator__alloc_frame(git_tree *tree) { - int error; - git_tree *tree, *subtree; - unsigned int tree_idx; - const git_tree_entry *te; - - while (1) { - tree = git_vector_last(&ti->tree_stack); - tree_idx = PTR_AS_IDX(git_vector_last(&ti->idx_stack)); - te = git_tree_entry_byindex(tree, tree_idx); + tree_iterator_frame *tf = git__calloc(1, sizeof(tree_iterator_frame)); + tf->tree = tree; + return tf; +} - if (!entry_is_tree(te)) - break; +static int tree_iterator__expand_tree(tree_iterator *ti) +{ + int error; + git_tree *subtree; + const git_tree_entry *te = tree_iterator__tree_entry(ti); + tree_iterator_frame *tf; + while (te != NULL && entry_is_tree(te)) { error = git_tree_lookup(&subtree, ti->repo, &te->oid); if (error != GIT_SUCCESS) return error; - if ((error = git_vector_insert(&ti->tree_stack, subtree)) < GIT_SUCCESS || - (error = git_vector_insert(&ti->idx_stack, IDX_AS_PTR(0))) < GIT_SUCCESS || - (error = git_buf_joinpath(&ti->path, ti->path.ptr, te->filename)) < GIT_SUCCESS) - { - git_tree_free(subtree); + if ((tf = tree_iterator__alloc_frame(subtree)) == NULL) + return GIT_ENOMEM; + + tf->next = ti->stack; + ti->stack = tf; + + error = git_buf_joinpath(&ti->path, ti->path.ptr, te->filename); + if (error < GIT_SUCCESS) return error; - } + + te = tree_iterator__tree_entry(ti); } return GIT_SUCCESS; } -static int git_iterator__tree_advance( +static void tree_iterator__pop_frame(tree_iterator *ti) +{ + tree_iterator_frame *tf = ti->stack; + ti->stack = tf->next; + if (ti->stack != NULL) /* don't free the initial tree */ + git_tree_free(tf->tree); + git__free(tf); +} + +static int tree_iterator__advance( git_iterator *self, const git_index_entry **entry) { int error = GIT_SUCCESS; - git_iterator_tree *ti = (git_iterator_tree *)self; - git_tree *tree = git_vector_last(&ti->tree_stack); - unsigned int tree_idx = PTR_AS_IDX(git_vector_last(&ti->idx_stack)); - const git_tree_entry *te = git_tree_entry_byindex(tree, tree_idx); + tree_iterator *ti = (tree_iterator *)self; + const git_tree_entry *te; if (entry != NULL) *entry = NULL; - if (te == NULL) - return GIT_SUCCESS; - - while (1) { - /* advance this tree */ - tree_idx++; - ti->idx_stack.contents[ti->idx_stack.length - 1] = IDX_AS_PTR(tree_idx); - + while (ti->stack != NULL) { /* remove old entry filename */ git_buf_rtruncate_at_char(&ti->path, '/'); - if ((te = git_tree_entry_byindex(tree, tree_idx)) != NULL) + te = git_tree_entry_byindex(ti->stack->tree, ++ti->stack->index); + if (te != NULL) break; - /* no entry - either we are done or we are done with this subtree */ - if (ti->tree_stack.length == 1) - return GIT_SUCCESS; - - git_tree_free(tree); - git_vector_remove(&ti->tree_stack, ti->tree_stack.length - 1); - git_vector_remove(&ti->idx_stack, ti->idx_stack.length - 1); + tree_iterator__pop_frame(ti); git_buf_rtruncate_at_char(&ti->path, '/'); - - tree = git_vector_last(&ti->tree_stack); - tree_idx = PTR_AS_IDX(git_vector_last(&ti->idx_stack)); } if (te && entry_is_tree(te)) - error = expand_tree_if_needed(ti); + error = tree_iterator__expand_tree(ti); if (error == GIT_SUCCESS && entry != NULL) - error = git_iterator__tree_current(self, entry); + error = tree_iterator__current(self, entry); return error; } -static void git_iterator__tree_free(git_iterator *self) +static void tree_iterator__free(git_iterator *self) { - git_iterator_tree *ti = (git_iterator_tree *)self; - - while (ti->tree_stack.length > 1) { - git_tree *tree = git_vector_last(&ti->tree_stack); - git_tree_free(tree); - git_vector_remove(&ti->tree_stack, ti->tree_stack.length - 1); - } - - git_vector_clear(&ti->tree_stack); - git_vector_clear(&ti->idx_stack); + tree_iterator *ti = (tree_iterator *)self; + while (ti->stack != NULL) + tree_iterator__pop_frame(ti); git_buf_free(&ti->path); } -int git_iterator_for_tree(git_repository *repo, git_tree *tree, git_iterator **iter) +int git_iterator_for_tree( + git_repository *repo, git_tree *tree, git_iterator **iter) { int error; - git_iterator_tree *ti = git__calloc(1, sizeof(git_iterator_tree)); + tree_iterator *ti = git__calloc(1, sizeof(tree_iterator)); if (!ti) return GIT_ENOMEM; - ti->cb.type = GIT_ITERATOR_TREE; - ti->cb.current = git_iterator__tree_current; - ti->cb.at_end = git_iterator__tree_at_end; - ti->cb.advance = git_iterator__tree_advance; - ti->cb.free = git_iterator__tree_free; - ti->repo = repo; - - if (!(error = git_vector_init(&ti->tree_stack, 0, NULL)) && - !(error = git_vector_insert(&ti->tree_stack, tree)) && - !(error = git_vector_init(&ti->idx_stack, 0, NULL))) - error = git_vector_insert(&ti->idx_stack, IDX_AS_PTR(0)); + ti->base.type = GIT_ITERATOR_TREE; + ti->base.current = tree_iterator__current; + ti->base.at_end = tree_iterator__at_end; + ti->base.advance = tree_iterator__advance; + ti->base.free = tree_iterator__free; + ti->repo = repo; + ti->stack = tree_iterator__alloc_frame(tree); - if (error == GIT_SUCCESS) - error = expand_tree_if_needed(ti); - - if (error != GIT_SUCCESS) + if ((error = tree_iterator__expand_tree(ti)) < GIT_SUCCESS) git_iterator_free((git_iterator *)ti); else *iter = (git_iterator *)ti; @@ -193,29 +169,29 @@ int git_iterator_for_tree(git_repository *repo, git_tree *tree, git_iterator **i typedef struct { - git_iterator cb; + git_iterator base; git_index *index; unsigned int current; -} git_iterator_index; +} index_iterator; -static int git_iterator__index_current( +static int index_iterator__current( git_iterator *self, const git_index_entry **entry) { - git_iterator_index *ii = (git_iterator_index *)self; + index_iterator *ii = (index_iterator *)self; *entry = git_index_get(ii->index, ii->current); return GIT_SUCCESS; } -static int git_iterator__index_at_end(git_iterator *self) +static int index_iterator__at_end(git_iterator *self) { - git_iterator_index *ii = (git_iterator_index *)self; + index_iterator *ii = (index_iterator *)self; return (ii->current >= git_index_entrycount(ii->index)); } -static int git_iterator__index_advance( +static int index_iterator__advance( git_iterator *self, const git_index_entry **entry) { - git_iterator_index *ii = (git_iterator_index *)self; + index_iterator *ii = (index_iterator *)self; if (ii->current < git_index_entrycount(ii->index)) ii->current++; if (entry) @@ -223,9 +199,9 @@ static int git_iterator__index_advance( return GIT_SUCCESS; } -static void git_iterator__index_free(git_iterator *self) +static void index_iterator__free(git_iterator *self) { - git_iterator_index *ii = (git_iterator_index *)self; + index_iterator *ii = (index_iterator *)self; git_index_free(ii->index); ii->index = NULL; } @@ -233,16 +209,16 @@ static void git_iterator__index_free(git_iterator *self) int git_iterator_for_index(git_repository *repo, git_iterator **iter) { int error; - git_iterator_index *ii = git__calloc(1, sizeof(git_iterator_index)); + index_iterator *ii = git__calloc(1, sizeof(index_iterator)); if (!ii) return GIT_ENOMEM; - ii->cb.type = GIT_ITERATOR_INDEX; - ii->cb.current = git_iterator__index_current; - ii->cb.at_end = git_iterator__index_at_end; - ii->cb.advance = git_iterator__index_advance; - ii->cb.free = git_iterator__index_free; - ii->current = 0; + ii->base.type = GIT_ITERATOR_INDEX; + ii->base.current = index_iterator__current; + ii->base.at_end = index_iterator__at_end; + ii->base.advance = index_iterator__advance; + ii->base.free = index_iterator__free; + ii->current = 0; if ((error = git_repository_index(&ii->index, repo)) < GIT_SUCCESS) git__free(ii); @@ -252,101 +228,107 @@ int git_iterator_for_index(git_repository *repo, git_iterator **iter) } +typedef struct workdir_iterator_frame workdir_iterator_frame; +struct workdir_iterator_frame { + workdir_iterator_frame *next; + git_vector entries; + unsigned int index; +}; + typedef struct { - git_iterator cb; + git_iterator base; git_repository *repo; size_t root_len; - git_vector dir_stack; /* vector of vectors of paths */ - git_vector idx_stack; + workdir_iterator_frame *stack; git_ignores ignores; git_index_entry entry; git_buf path; int is_ignored; -} git_iterator_workdir; +} workdir_iterator; + +static workdir_iterator_frame *workdir_iterator__alloc_frame(void) +{ + workdir_iterator_frame *wf = git__calloc(1, sizeof(workdir_iterator_frame)); + if (wf == NULL) + return wf; + if (git_vector_init(&wf->entries, 0, git__strcmp_cb) != GIT_SUCCESS) { + git__free(wf); + return NULL; + } + return wf; +} -static void free_directory(git_vector *dir) +static void workdir_iterator__free_frame(workdir_iterator_frame *wf) { unsigned int i; char *path; - git_vector_foreach(dir, i, path) + git_vector_foreach(&wf->entries, i, path) git__free(path); - git_vector_free(dir); - git__free(dir); + git_vector_free(&wf->entries); + git__free(wf); } -static int load_workdir_entry(git_iterator_workdir *wi); +static int workdir_iterator__update_entry(workdir_iterator *wi); -static int push_directory(git_iterator_workdir *wi) +static int workdir_iterator__expand_dir(workdir_iterator *wi) { int error; - git_vector *dir = NULL; - - error = git_vector_alloc(&dir, 0, git__strcmp_cb); - if (error < GIT_SUCCESS) - return error; + workdir_iterator_frame *wf = workdir_iterator__alloc_frame(); + if (wf == NULL) + return GIT_ENOMEM; - /* allocate dir entries with extra byte (the "1" param) so later on we - * can suffix directories with a "/" as needed. + /* allocate dir entries with extra byte (the "1" param) so we + * can suffix directory names with a "/". */ - error = git_path_dirload(wi->path.ptr, wi->root_len, 1, dir); - if (error < GIT_SUCCESS || dir->length == 0) { - free_directory(dir); + error = git_path_dirload(wi->path.ptr, wi->root_len, 1, &wf->entries); + if (error < GIT_SUCCESS || wf->entries.length == 0) { + workdir_iterator__free_frame(wf); return GIT_ENOTFOUND; } - if ((error = git_vector_insert(&wi->dir_stack, dir)) || - (error = git_vector_insert(&wi->idx_stack, IDX_AS_PTR(0)))) - { - free_directory(dir); - return error; - } - - git_vector_sort(dir); + git_vector_sort(&wf->entries); + wf->next = wi->stack; + wi->stack = wf; - if (wi->dir_stack.length > 1) { + /* only push new ignores if this is not top level directory */ + if (wi->stack->next != NULL) { int slash_pos = git_buf_rfind_next(&wi->path, '/'); (void)git_ignore__push_dir(&wi->ignores, &wi->path.ptr[slash_pos + 1]); } - return load_workdir_entry(wi); + return workdir_iterator__update_entry(wi); } -static int git_iterator__workdir_current( +static int workdir_iterator__current( git_iterator *self, const git_index_entry **entry) { - git_iterator_workdir *wi = (git_iterator_workdir *)self; + workdir_iterator *wi = (workdir_iterator *)self; *entry = (wi->entry.path == NULL) ? NULL : &wi->entry; return GIT_SUCCESS; } -static int git_iterator__workdir_at_end(git_iterator *self) +static int workdir_iterator__at_end(git_iterator *self) { - git_iterator_workdir *wi = (git_iterator_workdir *)self; - return (wi->entry.path == NULL); + return (((workdir_iterator *)self)->entry.path == NULL); } -static int git_iterator__workdir_advance( +static int workdir_iterator__advance( git_iterator *self, const git_index_entry **entry) { int error; - git_iterator_workdir *wi = (git_iterator_workdir *)self; - git_vector *dir; - unsigned int pos; + workdir_iterator *wi = (workdir_iterator *)self; + workdir_iterator_frame *wf; const char *next; - if (entry) + if (entry != NULL) *entry = NULL; if (wi->entry.path == NULL) return GIT_SUCCESS; - while (1) { - dir = git_vector_last(&wi->dir_stack); - pos = 1 + PTR_AS_IDX(git_vector_last(&wi->idx_stack)); - wi->idx_stack.contents[wi->idx_stack.length - 1] = IDX_AS_PTR(pos); - - next = git_vector_get(dir, pos); + while ((wf = wi->stack) != NULL) { + next = git_vector_get(&wf->entries, ++wf->index); if (next != NULL) { if (strcmp(next, DOT_GIT) == 0) continue; @@ -354,69 +336,45 @@ static int git_iterator__workdir_advance( break; } - memset(&wi->entry, 0, sizeof(wi->entry)); - if (wi->dir_stack.length == 1) - return GIT_SUCCESS; - - free_directory(dir); - git_vector_remove(&wi->dir_stack, wi->dir_stack.length - 1); - git_vector_remove(&wi->idx_stack, wi->idx_stack.length - 1); + /* pop workdir directory stack */ + wi->stack = wf->next; + workdir_iterator__free_frame(wf); git_ignore__pop_dir(&wi->ignores); + + if (wi->stack == NULL) { + memset(&wi->entry, 0, sizeof(wi->entry)); + return GIT_SUCCESS; + } } - error = load_workdir_entry(wi); + error = workdir_iterator__update_entry(wi); - if (error == GIT_SUCCESS && entry) - return git_iterator__workdir_current(self, entry); + if (error == GIT_SUCCESS && entry != NULL) + error = workdir_iterator__current(self, entry); return error; } -int git_iterator_advance_into_directory( - git_iterator *iter, const git_index_entry **entry) +static void workdir_iterator__free(git_iterator *self) { - git_iterator_workdir *wi = (git_iterator_workdir *)iter; - - if (iter->type != GIT_ITERATOR_WORKDIR) - return git_iterator_current(iter, entry); + workdir_iterator *wi = (workdir_iterator *)self; - /* Loop because the first entry in the ignored directory could itself be - * an ignored directory, but we want to descend to find an actual entry. - */ - if (wi->entry.path && S_ISDIR(wi->entry.mode)) { - if (push_directory(wi) < GIT_SUCCESS) - /* If error loading or if empty, skip the directory. */ - return git_iterator__workdir_advance((git_iterator *)wi, entry); + while (wi->stack != NULL) { + workdir_iterator_frame *wf = wi->stack; + wi->stack = wf->next; + workdir_iterator__free_frame(wf); } - return git_iterator__workdir_current(iter, entry); -} - -static void git_iterator__workdir_free(git_iterator *self) -{ - git_iterator_workdir *wi = (git_iterator_workdir *)self; - - while (wi->dir_stack.length) { - git_vector *dir = git_vector_last(&wi->dir_stack); - free_directory(dir); - git_vector_remove(&wi->dir_stack, wi->dir_stack.length - 1); - } - - git_vector_clear(&wi->dir_stack); - git_vector_clear(&wi->idx_stack); git_ignore__free(&wi->ignores); git_buf_free(&wi->path); } -static int load_workdir_entry(git_iterator_workdir *wi) +static int workdir_iterator__update_entry(workdir_iterator *wi) { int error; - char *relpath; - git_vector *dir = git_vector_last(&wi->dir_stack); - unsigned int pos = PTR_AS_IDX(git_vector_last(&wi->idx_stack)); struct stat st; + char *relpath = git_vector_get(&wi->stack->entries, wi->stack->index); - relpath = git_vector_get(dir, pos); error = git_buf_joinpath( &wi->path, git_repository_workdir(wi->repo), relpath); if (error < GIT_SUCCESS) @@ -425,14 +383,12 @@ static int load_workdir_entry(git_iterator_workdir *wi) memset(&wi->entry, 0, sizeof(wi->entry)); wi->entry.path = relpath; + /* skip over .git directory */ if (strcmp(relpath, DOT_GIT) == 0) - return git_iterator__workdir_advance((git_iterator *)wi, NULL); + return workdir_iterator__advance((git_iterator *)wi, NULL); /* if there is an error processing the entry, treat as ignored */ wi->is_ignored = 1; - error = git_ignore__lookup(&wi->ignores, wi->entry.path, &wi->is_ignored); - if (error != GIT_SUCCESS) - return GIT_SUCCESS; if (p_lstat(wi->path.ptr, &st) < 0) return GIT_SUCCESS; @@ -451,6 +407,11 @@ static int load_workdir_entry(git_iterator_workdir *wi) if (st.st_mode == 0) return GIT_SUCCESS; + /* okay, we are far enough along to look up real ignore rule */ + error = git_ignore__lookup(&wi->ignores, wi->entry.path, &wi->is_ignored); + if (error != GIT_SUCCESS) + return GIT_SUCCESS; + if (S_ISDIR(st.st_mode)) { if (git_path_contains(&wi->path, DOT_GIT) == GIT_SUCCESS) { /* create submodule entry */ @@ -470,30 +431,28 @@ static int load_workdir_entry(git_iterator_workdir *wi) int git_iterator_for_workdir(git_repository *repo, git_iterator **iter) { int error; - git_iterator_workdir *wi = git__calloc(1, sizeof(git_iterator_workdir)); + workdir_iterator *wi = git__calloc(1, sizeof(workdir_iterator)); if (!wi) return GIT_ENOMEM; - wi->cb.type = GIT_ITERATOR_WORKDIR; - wi->cb.current = git_iterator__workdir_current; - wi->cb.at_end = git_iterator__workdir_at_end; - wi->cb.advance = git_iterator__workdir_advance; - wi->cb.free = git_iterator__workdir_free; - wi->repo = repo; - - if ((error = git_buf_sets( - &wi->path, git_repository_workdir(repo))) < GIT_SUCCESS || - (error = git_vector_init(&wi->dir_stack, 0, NULL)) < GIT_SUCCESS || - (error = git_vector_init(&wi->idx_stack, 0, NULL)) < GIT_SUCCESS || - (error = git_ignore__for_path(repo, "", &wi->ignores)) < GIT_SUCCESS) - { + wi->base.type = GIT_ITERATOR_WORKDIR; + wi->base.current = workdir_iterator__current; + wi->base.at_end = workdir_iterator__at_end; + wi->base.advance = workdir_iterator__advance; + wi->base.free = workdir_iterator__free; + wi->repo = repo; + + error = git_buf_sets(&wi->path, git_repository_workdir(repo)); + if (error == GIT_SUCCESS) + error = git_ignore__for_path(repo, "", &wi->ignores); + if (error != GIT_SUCCESS) { git__free(wi); return error; } wi->root_len = wi->path.size; - if ((error = push_directory(wi)) < GIT_SUCCESS) + if ((error = workdir_iterator__expand_dir(wi)) < GIT_SUCCESS) git_iterator_free((git_iterator *)wi); else *iter = (git_iterator *)wi; @@ -501,21 +460,33 @@ int git_iterator_for_workdir(git_repository *repo, git_iterator **iter) return error; } + int git_iterator_current_tree_entry( git_iterator *iter, const git_tree_entry **tree_entry) { - if (iter->type != GIT_ITERATOR_TREE) - *tree_entry = NULL; - else - *tree_entry = git_iterator__tree_entry((git_iterator_tree *)iter); - + *tree_entry = (iter->type != GIT_ITERATOR_TREE) ? NULL : + tree_iterator__tree_entry((tree_iterator *)iter); return GIT_SUCCESS; } int git_iterator_current_is_ignored(git_iterator *iter) { - if (iter->type != GIT_ITERATOR_WORKDIR) - return 0; - else - return ((git_iterator_workdir *)iter)->is_ignored; + return (iter->type != GIT_ITERATOR_WORKDIR) ? 0 : + ((workdir_iterator *)iter)->is_ignored; +} + +int git_iterator_advance_into_directory( + git_iterator *iter, const git_index_entry **entry) +{ + workdir_iterator *wi = (workdir_iterator *)iter; + + if (iter->type == GIT_ITERATOR_WORKDIR && + wi->entry.path && S_ISDIR(wi->entry.mode)) + { + if (workdir_iterator__expand_dir(wi) < GIT_SUCCESS) + /* if error loading or if empty, skip the directory. */ + return workdir_iterator__advance(iter, entry); + } + + return entry ? git_iterator_current(iter, entry) : GIT_SUCCESS; } |