diff options
-rw-r--r-- | include/git2/index.h | 10 | ||||
-rw-r--r-- | src/attr.c | 15 | ||||
-rw-r--r-- | src/attr_file.c | 11 | ||||
-rw-r--r-- | src/commit.c | 3 | ||||
-rw-r--r-- | src/diff_tform.c | 25 | ||||
-rw-r--r-- | src/index.c | 69 | ||||
-rw-r--r-- | src/iterator.c | 2 | ||||
-rw-r--r-- | src/pack.c | 5 | ||||
-rw-r--r-- | src/remote.c | 3 | ||||
-rw-r--r-- | src/stash.c | 2 | ||||
-rw-r--r-- | src/submodule.c | 8 | ||||
-rw-r--r-- | src/tree.c | 70 | ||||
-rw-r--r-- | src/util.c | 12 | ||||
-rw-r--r-- | src/util.h | 5 | ||||
-rw-r--r-- | src/vector.c | 132 | ||||
-rw-r--r-- | src/vector.h | 17 | ||||
-rw-r--r-- | tests-clar/attr/repo.c | 5 | ||||
-rw-r--r-- | tests-clar/index/filemodes.c | 5 | ||||
-rw-r--r-- | tests-clar/index/rename.c | 6 | ||||
-rw-r--r-- | tests-clar/index/stage.c | 14 | ||||
-rw-r--r-- | tests-clar/index/tests.c | 11 | ||||
-rw-r--r-- | tests-clar/submodule/status.c | 5 |
22 files changed, 235 insertions, 200 deletions
diff --git a/include/git2/index.h b/include/git2/index.h index ad6d19733..9f9d144cf 100644 --- a/include/git2/index.h +++ b/include/git2/index.h @@ -403,11 +403,12 @@ GIT_EXTERN(int) git_index_remove_bypath(git_index *index, const char *path); * Find the first index of any entries which point to given * path in the Git index. * + * @param at_pos the address to which the position of the index entry is written (optional) * @param index an existing index object * @param path path to search - * @return an index >= 0 if found, -1 otherwise + * @return 0 if found, < 0 otherwise (GIT_ENOTFOUND) */ -GIT_EXTERN(int) git_index_find(git_index *index, const char *path); +GIT_EXTERN(int) git_index_find(size_t *at_pos, git_index *index, const char *path); /**@}*/ @@ -495,11 +496,12 @@ GIT_EXTERN(unsigned int) git_index_reuc_entrycount(git_index *index); * Finds the resolve undo entry that points to the given path in the Git * index. * + * @param at_pos the address to which the position of the reuc entry is written (optional) * @param index an existing index object * @param path path to search - * @return an index >= 0 if found, -1 otherwise + * @return 0 if found, < 0 otherwise (GIT_ENOTFOUND) */ -GIT_EXTERN(int) git_index_reuc_find(git_index *index, const char *path); +GIT_EXTERN(int) git_index_reuc_find(size_t *at_pos, git_index *index, const char *path); /** * Get a resolve undo entry from the index. diff --git a/src/attr.c b/src/attr.c index 1b414417e..a1d9932e9 100644 --- a/src/attr.c +++ b/src/attr.c @@ -61,8 +61,9 @@ int git_attr_get( git_vector_foreach(&files, i, file) { git_attr_file__foreach_matching_rule(file, &path, j, rule) { - int pos = git_vector_bsearch(&rule->assigns, &attr); - if (pos >= 0) { + size_t pos; + + if (!git_vector_bsearch(&pos, &rule->assigns, &attr)) { *value = ((git_attr_assignment *)git_vector_get( &rule->assigns, pos))->value; goto cleanup; @@ -116,7 +117,7 @@ int git_attr_get_many( git_attr_file__foreach_matching_rule(file, &path, j, rule) { for (k = 0; k < num_attr; k++) { - int pos; + size_t pos; if (info[k].found != NULL) /* already found assignment */ continue; @@ -126,8 +127,7 @@ int git_attr_get_many( info[k].name.name_hash = git_attr_file__name_hash(names[k]); } - pos = git_vector_bsearch(&rule->assigns, &info[k].name); - if (pos >= 0) { + if (!git_vector_bsearch(&pos, &rule->assigns, &info[k].name)) { info[k].found = (git_attr_assignment *) git_vector_get(&rule->assigns, pos); values[k] = info[k].found->value; @@ -294,14 +294,15 @@ static int load_attr_blob_from_index( const char *relfile) { int error; + size_t pos; git_index *index; const git_index_entry *entry; if ((error = git_repository_index__weakptr(&index, repo)) < 0 || - (error = git_index_find(index, relfile)) < 0) + (error = git_index_find(&pos, index, relfile)) < 0) return error; - entry = git_index_get_byindex(index, error); + entry = git_index_get_byindex(index, pos); if (old_oid && git_oid_cmp(old_oid, &entry->oid) == 0) return GIT_ENOTFOUND; diff --git a/src/attr_file.c b/src/attr_file.c index 485bcb434..628cb1544 100644 --- a/src/attr_file.c +++ b/src/attr_file.c @@ -191,9 +191,9 @@ int git_attr_file__lookup_one( name.name_hash = git_attr_file__name_hash(attr); git_attr_file__foreach_matching_rule(file, path, i, rule) { - int pos = git_vector_bsearch(&rule->assigns, &name); + size_t pos; - if (pos >= 0) { + if (!git_vector_bsearch(&pos, &rule->assigns, &name)) { *value = ((git_attr_assignment *) git_vector_get(&rule->assigns, pos))->value; break; @@ -240,14 +240,15 @@ bool git_attr_rule__match( git_attr_assignment *git_attr_rule__lookup_assignment( git_attr_rule *rule, const char *name) { - int pos; + size_t pos; git_attr_name key; key.name = name; key.name_hash = git_attr_file__name_hash(name); - pos = git_vector_bsearch(&rule->assigns, &key); + if (git_vector_bsearch(&pos, &rule->assigns, &key)) + return NULL; - return (pos >= 0) ? git_vector_get(&rule->assigns, pos) : NULL; + return git_vector_get(&rule->assigns, pos); } int git_attr_path__init( diff --git a/src/commit.c b/src/commit.c index 2714f1acc..29ce39107 100644 --- a/src/commit.c +++ b/src/commit.c @@ -137,7 +137,8 @@ int git_commit__parse_buffer(git_commit *commit, const void *data, size_t len) const char *buffer_end = (const char *)data + len; git_oid parent_id; - git_vector_init(&commit->parent_ids, 4, NULL); + if (git_vector_init(&commit->parent_ids, 4, NULL) < 0) + return -1; if (git_oid__parse(&commit->tree_id, &buffer, buffer_end, "tree ") < 0) goto bad_buffer; diff --git a/src/diff_tform.c b/src/diff_tform.c index 873ec3a7e..2c2e1fb19 100644 --- a/src/diff_tform.c +++ b/src/diff_tform.c @@ -250,22 +250,21 @@ static int apply_splits_and_deletes(git_diff_list *diff, size_t expected_size) /* build new delta list without TO_DELETE and splitting TO_SPLIT */ git_vector_foreach(&diff->deltas, i, delta) { - if (delta->status == GIT_DELTA__TO_DELETE) { - git__free(delta); + if (delta->status == GIT_DELTA__TO_DELETE) continue; - } if (delta->status == GIT_DELTA__TO_SPLIT) { git_diff_delta *deleted = diff_delta__dup(delta, &diff->pool); if (!deleted) - return -1; + goto on_error; deleted->status = GIT_DELTA_DELETED; memset(&deleted->new_file, 0, sizeof(deleted->new_file)); deleted->new_file.path = deleted->old_file.path; deleted->new_file.flags |= GIT_DIFF_FILE_VALID_OID; - git_vector_insert(&onto, deleted); + if (git_vector_insert(&onto, deleted) < 0) + goto on_error; delta->status = GIT_DELTA_ADDED; memset(&delta->old_file, 0, sizeof(delta->old_file)); @@ -273,15 +272,29 @@ static int apply_splits_and_deletes(git_diff_list *diff, size_t expected_size) delta->old_file.flags |= GIT_DIFF_FILE_VALID_OID; } - git_vector_insert(&onto, delta); + if (git_vector_insert(&onto, delta) < 0) + goto on_error; } + /* cannot return an error past this point */ + git_vector_foreach(&diff->deltas, i, delta) + if (delta->status == GIT_DELTA__TO_DELETE) + git__free(delta); + /* swap new delta list into place */ git_vector_sort(&onto); git_vector_swap(&diff->deltas, &onto); git_vector_free(&onto); return 0; + +on_error: + git_vector_foreach(&onto, i, delta) + git__free(delta); + + git_vector_free(&onto); + + return -1; } static unsigned int calc_similarity( diff --git a/src/index.c b/src/index.c index e9dffab8d..1e00dd3fa 100644 --- a/src/index.c +++ b/src/index.c @@ -97,7 +97,7 @@ static int parse_index(git_index *index, const char *buffer, size_t buffer_size) static bool is_index_extended(git_index *index); static int write_index(git_index *index, git_filebuf *file); -static int index_find(git_index *index, const char *path, int stage); +static int index_find(size_t *at_pos, git_index *index, const char *path, int stage); static void index_entry_free(git_index_entry *entry); static void index_entry_reuc_free(git_index_reuc_entry *reuc); @@ -504,13 +504,13 @@ const git_index_entry *git_index_get_byindex( const git_index_entry *git_index_get_bypath( git_index *index, const char *path, int stage) { - int pos; + size_t pos; assert(index); git_vector_sort(&index->entries); - if((pos = index_find(index, path, stage)) < 0) + if (index_find(&pos, index, path, stage) < 0) return NULL; return git_index_get_byindex(index, pos); @@ -665,8 +665,7 @@ static void index_entry_free(git_index_entry *entry) static int index_insert(git_index *index, git_index_entry *entry, int replace) { - size_t path_length; - int position; + size_t path_length, position; git_index_entry **existing = NULL; assert(index && entry && entry->path != NULL); @@ -682,7 +681,7 @@ static int index_insert(git_index *index, git_index_entry *entry, int replace) entry->flags |= GIT_IDXENTRY_NAMEMASK; /* look if an entry with this path already exists */ - if ((position = index_find(index, entry->path, index_entry_stage(entry))) >= 0) { + if (!index_find(&position, index, entry->path, index_entry_stage(entry))) { existing = (git_index_entry **)&index->entries.contents[position]; /* update filemode to existing values if stat is not trusted */ @@ -787,14 +786,14 @@ int git_index_add(git_index *index, const git_index_entry *source_entry) int git_index_remove(git_index *index, const char *path, int stage) { - int position; + size_t position; int error; git_index_entry *entry; git_vector_sort(&index->entries); - if ((position = index_find(index, path, stage)) < 0) - return position; + if (index_find(&position, index, path, stage) < 0) + return GIT_ENOTFOUND; entry = git_vector_get(&index->entries, position); if (entry != NULL) @@ -846,7 +845,7 @@ int git_index_remove_directory(git_index *index, const char *dir, int stage) return error; } -static int index_find(git_index *index, const char *path, int stage) +static int index_find(size_t *at_pos, git_index *index, const char *path, int stage) { struct entry_srch_key srch_key; @@ -855,20 +854,18 @@ static int index_find(git_index *index, const char *path, int stage) srch_key.path = path; srch_key.stage = stage; - return git_vector_bsearch2(&index->entries, index->entries_search, &srch_key); + return git_vector_bsearch2(at_pos, &index->entries, index->entries_search, &srch_key); } -int git_index_find(git_index *index, const char *path) +int git_index_find(size_t *at_pos, git_index *index, const char *path) { - int pos; + size_t pos; assert(index && path); - if ((pos = git_vector_bsearch2( - &index->entries, index->entries_search_path, path)) < 0) - { + if (git_vector_bsearch2(&pos, &index->entries, index->entries_search_path, path) < 0) { giterr_set(GITERR_INDEX, "Index does not contain %s", path); - return pos; + return GIT_ENOTFOUND; } /* Since our binary search only looked at path, we may be in the @@ -883,7 +880,10 @@ int git_index_find(git_index *index, const char *path) --pos; } - return pos; + if (at_pos) + *at_pos = pos; + + return 0; } size_t git_index__prefix_position(git_index *index, const char *path) @@ -895,7 +895,7 @@ size_t git_index__prefix_position(git_index *index, const char *path) srch_key.stage = 0; git_vector_sort(&index->entries); - git_vector_bsearch3( + git_vector_bsearch2( &pos, &index->entries, index->entries_search, &srch_key); return pos; @@ -945,7 +945,8 @@ int git_index_conflict_get(git_index_entry **ancestor_out, git_index_entry **their_out, git_index *index, const char *path) { - int pos, posmax, stage; + size_t pos, posmax; + int stage; git_index_entry *conflict_entry; int error = GIT_ENOTFOUND; @@ -955,10 +956,10 @@ int git_index_conflict_get(git_index_entry **ancestor_out, *our_out = NULL; *their_out = NULL; - if ((pos = git_index_find(index, path)) < 0) - return pos; + if (git_index_find(&pos, index, path) < 0) + return GIT_ENOTFOUND; - for (posmax = (int)git_index_entrycount(index); pos < posmax; ++pos) { + for (posmax = git_index_entrycount(index); pos < posmax; ++pos) { conflict_entry = git_vector_get(&index->entries, pos); @@ -990,16 +991,16 @@ int git_index_conflict_get(git_index_entry **ancestor_out, int git_index_conflict_remove(git_index *index, const char *path) { - int pos, posmax; + size_t pos, posmax; git_index_entry *conflict_entry; int error = 0; assert(index && path); - if ((pos = git_index_find(index, path)) < 0) - return pos; + if (git_index_find(&pos, index, path) < 0) + return GIT_ENOTFOUND; - posmax = (int)git_index_entrycount(index); + posmax = git_index_entrycount(index); while (pos < posmax) { conflict_entry = git_vector_get(&index->entries, pos); @@ -1012,7 +1013,7 @@ int git_index_conflict_remove(git_index *index, const char *path) continue; } - if ((error = git_vector_remove(&index->entries, (unsigned int)pos)) < 0) + if ((error = git_vector_remove(&index->entries, pos)) < 0) return error; index_entry_free(conflict_entry); @@ -1064,11 +1065,11 @@ unsigned int git_index_reuc_entrycount(git_index *index) static int index_reuc_insert(git_index *index, git_index_reuc_entry *reuc, int replace) { git_index_reuc_entry **existing = NULL; - int position; + size_t position; assert(index && reuc && reuc->path != NULL); - if ((position = git_index_reuc_find(index, reuc->path)) >= 0) + if (!git_index_reuc_find(&position, index, reuc->path)) existing = (git_index_reuc_entry **)&index->reuc.contents[position]; if (!replace || !existing) @@ -1102,15 +1103,15 @@ int git_index_reuc_add(git_index *index, const char *path, return error; } -int git_index_reuc_find(git_index *index, const char *path) +int git_index_reuc_find(size_t *at_pos, git_index *index, const char *path) { - return git_vector_bsearch2(&index->reuc, index->reuc_search, path); + return git_vector_bsearch2(at_pos, &index->reuc, index->reuc_search, path); } const git_index_reuc_entry *git_index_reuc_get_bypath( git_index *index, const char *path) { - int pos; + size_t pos; assert(index && path); if (!index->reuc.length) @@ -1118,7 +1119,7 @@ const git_index_reuc_entry *git_index_reuc_get_bypath( git_vector_sort(&index->reuc); - if ((pos = git_index_reuc_find(index, path)) < 0) + if (git_index_reuc_find(&pos, index, path) < 0) return NULL; return git_vector_get(&index->reuc, pos); diff --git a/src/iterator.c b/src/iterator.c index 1c36cac78..8ad639d6b 100644 --- a/src/iterator.c +++ b/src/iterator.c @@ -689,7 +689,7 @@ static void workdir_iterator__seek_frame_start( return; if (wi->base.start) - git_vector_bsearch3( + git_vector_bsearch2( &wf->index, &wf->entries, wi->entrycmp, wi->base.start); else wf->index = 0; diff --git a/src/pack.c b/src/pack.c index e19fc4bf3..f36f3cf6b 100644 --- a/src/pack.c +++ b/src/pack.c @@ -760,12 +760,11 @@ git_off_t get_delta_base( } else if (type == GIT_OBJ_REF_DELTA) { /* If we have the cooperative cache, search in it first */ if (p->has_cache) { - int pos; + size_t pos; struct git_pack_entry key; git_oid_fromraw(&key.sha1, base_info); - pos = git_vector_bsearch(&p->cache, &key); - if (pos >= 0) { + if (!git_vector_bsearch(&pos, &p->cache, &key)) { *curpos += 20; return ((struct git_pack_entry *)git_vector_get(&p->cache, pos))->offset; } diff --git a/src/remote.c b/src/remote.c index 7dcba6d6b..920ca7a18 100644 --- a/src/remote.c +++ b/src/remote.c @@ -681,9 +681,8 @@ int git_remote_download( static int update_tips_callback(git_remote_head *head, void *payload) { git_vector *refs = (git_vector *)payload; - git_vector_insert(refs, head); - return 0; + return git_vector_insert(refs, head); } static int remote_head_for_fetchspec_src(git_remote_head **out, git_vector *update_heads, const char *fetchspec_src) diff --git a/src/stash.c b/src/stash.c index d4f81aefe..877af3312 100644 --- a/src/stash.c +++ b/src/stash.c @@ -192,7 +192,7 @@ static int update_index_cb( case GIT_DELTA_DELETED: if (!data->include_changed) break; - if (git_index_find(data->index, delta->old_file.path) == 0) + if (git_index_find(NULL, data->index, delta->old_file.path) == 0) data->error = git_index_remove( data->index, delta->old_file.path, 0); break; diff --git a/src/submodule.c b/src/submodule.c index 2be179303..359306498 100644 --- a/src/submodule.c +++ b/src/submodule.c @@ -157,7 +157,7 @@ int git_submodule_foreach( * and path are not the same. */ if (sm->refcount > 1) { - if (git_vector_bsearch(&seen, sm) != GIT_ENOTFOUND) + if (git_vector_bsearch(NULL, &seen, sm) != GIT_ENOTFOUND) continue; if ((error = git_vector_insert(&seen, sm)) < 0) break; @@ -716,7 +716,8 @@ int git_submodule_reload(git_submodule *submodule) { git_repository *repo; git_index *index; - int pos, error; + int error; + size_t pos; git_tree *head; git_config_backend *mods; @@ -732,8 +733,7 @@ int git_submodule_reload(git_submodule *submodule) ~(GIT_SUBMODULE_STATUS_IN_INDEX | GIT_SUBMODULE_STATUS__INDEX_OID_VALID); - pos = git_index_find(index, submodule->path); - if (pos >= 0) { + if (!git_index_find(&pos, index, submodule->path)) { const git_index_entry *entry = git_index_get_byindex(index, pos); if (S_ISGITLINK(entry->mode)) { diff --git a/src/tree.c b/src/tree.c index c34e9b940..7fd096020 100644 --- a/src/tree.c +++ b/src/tree.c @@ -132,45 +132,56 @@ static int homing_search_cmp(const void *key, const void *array_member) * around the area for our target file. */ static int tree_key_search( - git_vector *entries, const char *filename, size_t filename_len) + size_t *at_pos, git_vector *entries, const char *filename, size_t filename_len) { struct tree_key_search ksearch; const git_tree_entry *entry; - int homing, i; + size_t homing, i; ksearch.filename = filename; ksearch.filename_len = filename_len; /* Initial homing search; find an entry on the tree with * the same prefix as the filename we're looking for */ - homing = git_vector_bsearch2(entries, &homing_search_cmp, &ksearch); - if (homing < 0) - return homing; + if (git_vector_bsearch2(&homing, entries, &homing_search_cmp, &ksearch) < 0) + return GIT_ENOTFOUND; /* We found a common prefix. Look forward as long as * there are entries that share the common prefix */ - for (i = homing; i < (int)entries->length; ++i) { + for (i = homing; i < entries->length; ++i) { entry = entries->contents[i]; if (homing_search_cmp(&ksearch, entry) < 0) break; if (entry->filename_len == filename_len && - memcmp(filename, entry->filename, filename_len) == 0) - return i; + memcmp(filename, entry->filename, filename_len) == 0) { + if (at_pos) + *at_pos = i; + + return 0; + } } /* If we haven't found our filename yet, look backwards * too as long as we have entries with the same prefix */ - for (i = homing - 1; i >= 0; --i) { - entry = entries->contents[i]; + if (homing > 0) { + i = homing - 1; - if (homing_search_cmp(&ksearch, entry) > 0) - break; + do { + entry = entries->contents[i]; - if (entry->filename_len == filename_len && - memcmp(filename, entry->filename, filename_len) == 0) - return i; + if (homing_search_cmp(&ksearch, entry) > 0) + break; + + if (entry->filename_len == filename_len && + memcmp(filename, entry->filename, filename_len) == 0) { + if (at_pos) + *at_pos = i; + + return 0; + } + } while (i-- > 0); } /* The filename doesn't exist at all */ @@ -267,8 +278,9 @@ int git_tree_entry_to_object( static const git_tree_entry *entry_fromname( git_tree *tree, const char *name, size_t name_len) { - int idx = tree_key_search(&tree->entries, name, name_len); - if (idx < 0) + size_t idx; + + if (tree_key_search(&idx, &tree->entries, name, name_len) < 0) return NULL; return git_vector_get(&tree->entries, idx); @@ -317,7 +329,7 @@ int git_tree__prefix_position(git_tree *tree, const char *path) ksearch.filename_len = strlen(path); /* Find tree entry with appropriate prefix */ - git_vector_bsearch3(&at_pos, entries, &homing_search_cmp, &ksearch); + git_vector_bsearch2(&at_pos, entries, &homing_search_cmp, &ksearch); for (; at_pos < entries->length; ++at_pos) { const git_tree_entry *entry = entries->contents[at_pos]; @@ -612,7 +624,7 @@ int git_treebuilder_insert( git_filemode_t filemode) { git_tree_entry *entry; - int pos; + size_t pos; assert(bld && id && filename); @@ -622,41 +634,35 @@ int git_treebuilder_insert( if (!valid_entry_name(filename)) return tree_error("Failed to insert entry. Invalid name for a tree entry", filename); - pos = tree_key_search(&bld->entries, filename, strlen(filename)); - - if (pos >= 0) { + if (!tree_key_search(&pos, &bld->entries, filename, strlen(filename))) { entry = git_vector_get(&bld->entries, pos); if (entry->removed) entry->removed = 0; } else { entry = alloc_entry(filename); GITERR_CHECK_ALLOC(entry); - } - - git_oid_cpy(&entry->oid, id); - entry->attr = filemode; - if (pos < 0) { if (git_vector_insert(&bld->entries, entry) < 0) return -1; } - if (entry_out != NULL) { + git_oid_cpy(&entry->oid, id); + entry->attr = filemode; + + if (entry_out) *entry_out = entry; - } return 0; } static git_tree_entry *treebuilder_get(git_treebuilder *bld, const char *filename) { - int idx; + size_t idx; git_tree_entry *entry; assert(bld && filename); - idx = tree_key_search(&bld->entries, filename, strlen(filename)); - if (idx < 0) + if (tree_key_search(&idx, &bld->entries, filename, strlen(filename)) < 0) return NULL; entry = git_vector_get(&bld->entries, idx); diff --git a/src/util.c b/src/util.c index 085b627ce..059108ece 100644 --- a/src/util.c +++ b/src/util.c @@ -501,11 +501,11 @@ int git__bsearch( int (*compare)(const void *, const void *), size_t *position) { - unsigned int lim; + size_t lim; int cmp = -1; void **part, **base = array; - for (lim = (unsigned int)array_len; lim != 0; lim >>= 1) { + for (lim = array_len; lim != 0; lim >>= 1) { part = base + (lim >> 1); cmp = (*compare)(key, *part); if (cmp == 0) { @@ -521,7 +521,7 @@ int git__bsearch( if (position) *position = (base - array); - return (cmp == 0) ? 0 : -1; + return (cmp == 0) ? 0 : GIT_ENOTFOUND; } int git__bsearch_r( @@ -532,11 +532,11 @@ int git__bsearch_r( void *payload, size_t *position) { - unsigned int lim; + size_t lim; int cmp = -1; void **part, **base = array; - for (lim = (unsigned int)array_len; lim != 0; lim >>= 1) { + for (lim = array_len; lim != 0; lim >>= 1) { part = base + (lim >> 1); cmp = (*compare_r)(key, *part, payload); if (cmp == 0) { @@ -552,7 +552,7 @@ int git__bsearch_r( if (position) *position = (base - array); - return (cmp == 0) ? 0 : -1; + return (cmp == 0) ? 0 : GIT_ENOTFOUND; } /** diff --git a/src/util.h b/src/util.h index 9bcd3203e..e75d777a8 100644 --- a/src/util.h +++ b/src/util.h @@ -13,6 +13,9 @@ #ifndef min # define min(a,b) ((a) < (b) ? (a) : (b)) #endif +#ifndef max +# define max(a,b) ((a) > (b) ? (a) : (b)) +#endif /* * Custom memory allocation wrappers @@ -132,7 +135,7 @@ extern void git__tsort_r( /** * @param position If non-NULL, this will be set to the position where the * element is or would be inserted if not found. - * @return pos (>=0) if found or -1 if not found + * @return 0 if found; GIT_ENOTFOUND if not found */ extern int git__bsearch( void **array, diff --git a/src/vector.c b/src/vector.c index 7fa30970c..66842d4f1 100644 --- a/src/vector.c +++ b/src/vector.c @@ -9,33 +9,59 @@ #include "repository.h" #include "vector.h" -static const double git_vector_resize_factor = 1.75; -static const size_t git_vector_minimum_size = 8; +/* In elements, not bytes */ +#define MIN_ALLOCSIZE 8 -static int resize_vector(git_vector *v) +GIT_INLINE(size_t) compute_new_size(git_vector *v) { - v->_alloc_size = (size_t)(v->_alloc_size * git_vector_resize_factor) + 1; - if (v->_alloc_size < git_vector_minimum_size) - v->_alloc_size = git_vector_minimum_size; + size_t new_size = v->_alloc_size; + + /* Use a resize factor of 1.5, which is quick to compute using integer + * instructions and less than the golden ratio (1.618...) */ + if (new_size < MIN_ALLOCSIZE) + new_size = MIN_ALLOCSIZE; + else if (new_size <= SIZE_MAX / 3) + new_size = new_size * 3 / 2 + 1; + else + new_size = SIZE_MAX; + + return new_size; +} - v->contents = git__realloc(v->contents, v->_alloc_size * sizeof(void *)); - GITERR_CHECK_ALLOC(v->contents); +GIT_INLINE(int) resize_vector(git_vector *v, size_t new_size) +{ + size_t new_bytes = new_size * sizeof(void *); + void *new_contents; + + /* Check for overflow */ + if (new_bytes / sizeof(void *) != new_size) + GITERR_CHECK_ALLOC(NULL); + + new_contents = git__realloc(v->contents, new_bytes); + GITERR_CHECK_ALLOC(new_contents); + + v->_alloc_size = new_size; + v->contents = new_contents; return 0; } int git_vector_dup(git_vector *v, const git_vector *src, git_vector_cmp cmp) { + size_t bytes; + assert(v && src); + bytes = src->length * sizeof(void *); + v->_alloc_size = src->length; v->_cmp = cmp; v->length = src->length; v->sorted = src->sorted && cmp == src->_cmp; - v->contents = git__malloc(src->length * sizeof(void *)); + v->contents = git__malloc(bytes); GITERR_CHECK_ALLOC(v->contents); - memcpy(v->contents, src->contents, src->length * sizeof(void *)); + memcpy(v->contents, src->contents, bytes); return 0; } @@ -55,21 +81,13 @@ int git_vector_init(git_vector *v, size_t initial_size, git_vector_cmp cmp) { assert(v); - memset(v, 0x0, sizeof(git_vector)); - - if (initial_size == 0) - initial_size = git_vector_minimum_size; - - v->_alloc_size = initial_size; + v->_alloc_size = 0; v->_cmp = cmp; - v->length = 0; v->sorted = 1; + v->contents = NULL; - v->contents = git__malloc(v->_alloc_size * sizeof(void *)); - GITERR_CHECK_ALLOC(v->contents); - - return 0; + return resize_vector(v, max(initial_size, MIN_ALLOCSIZE)); } int git_vector_insert(git_vector *v, void *element) @@ -77,7 +95,7 @@ int git_vector_insert(git_vector *v, void *element) assert(v); if (v->length >= v->_alloc_size && - resize_vector(v) < 0) + resize_vector(v, compute_new_size(v)) < 0) return -1; v->contents[v->length++] = element; @@ -98,26 +116,25 @@ int git_vector_insert_sorted( git_vector_sort(v); if (v->length >= v->_alloc_size && - resize_vector(v) < 0) + resize_vector(v, compute_new_size(v)) < 0) return -1; /* If we find the element and have a duplicate handler callback, * invoke it. If it returns non-zero, then cancel insert, otherwise * proceed with normal insert. */ - if (git__bsearch(v->contents, v->length, element, v->_cmp, &pos) >= 0 && - on_dup != NULL && - (result = on_dup(&v->contents[pos], element)) < 0) + if (!git__bsearch(v->contents, v->length, element, v->_cmp, &pos) && + on_dup && (result = on_dup(&v->contents[pos], element)) < 0) return result; /* shift elements to the right */ - if (pos < v->length) { + if (pos < v->length) memmove(v->contents + pos + 1, v->contents + pos, (v->length - pos) * sizeof(void *)); - } v->contents[pos] = element; v->length++; + return 0; } @@ -125,47 +142,44 @@ void git_vector_sort(git_vector *v) { assert(v); - if (v->sorted || v->_cmp == NULL) + if (v->sorted || !v->_cmp) return; git__tsort(v->contents, v->length, v->_cmp); v->sorted = 1; } -int git_vector_bsearch3( +int git_vector_bsearch2( size_t *at_pos, git_vector *v, git_vector_cmp key_lookup, const void *key) { - int rval; - size_t pos; - assert(v && key && key_lookup); /* need comparison function to sort the vector */ - assert(v->_cmp != NULL); + if (!v->_cmp) + return -1; git_vector_sort(v); - rval = git__bsearch(v->contents, v->length, key, key_lookup, &pos); - - if (at_pos != NULL) - *at_pos = pos; - - return (rval >= 0) ? (int)pos : GIT_ENOTFOUND; + return git__bsearch(v->contents, v->length, key, key_lookup, at_pos); } int git_vector_search2( - const git_vector *v, git_vector_cmp key_lookup, const void *key) + size_t *at_pos, const git_vector *v, git_vector_cmp key_lookup, const void *key) { size_t i; assert(v && key && key_lookup); for (i = 0; i < v->length; ++i) { - if (key_lookup(key, v->contents[i]) == 0) - return (int)i; + if (key_lookup(key, v->contents[i]) == 0) { + if (at_pos) + *at_pos = i; + + return 0; + } } return GIT_ENOTFOUND; @@ -176,22 +190,25 @@ static int strict_comparison(const void *a, const void *b) return (a == b) ? 0 : -1; } -int git_vector_search(const git_vector *v, const void *entry) +int git_vector_search(size_t *at_pos, const git_vector *v, const void *entry) { - return git_vector_search2(v, v->_cmp ? v->_cmp : strict_comparison, entry); + return git_vector_search2(at_pos, v, v->_cmp ? v->_cmp : strict_comparison, entry); } int git_vector_remove(git_vector *v, size_t idx) { - size_t i; + size_t shift_count; assert(v); - if (idx >= v->length || v->length == 0) + if (idx >= v->length) return GIT_ENOTFOUND; - for (i = idx; i < v->length - 1; ++i) - v->contents[i] = v->contents[i + 1]; + shift_count = v->length - idx - 1; + + if (shift_count) + memmove(&v->contents[idx], &v->contents[idx + 1], + shift_count * sizeof(void *)); v->length--; return 0; @@ -249,12 +266,13 @@ void git_vector_swap(git_vector *a, git_vector *b) { git_vector t; - if (!a || !b || a == b) - return; + assert(a && b); - memcpy(&t, a, sizeof(t)); - memcpy(a, b, sizeof(t)); - memcpy(b, &t, sizeof(t)); + if (a != b) { + memcpy(&t, a, sizeof(t)); + memcpy(a, b, sizeof(t)); + memcpy(b, &t, sizeof(t)); + } } int git_vector_resize_to(git_vector *v, size_t new_length) @@ -262,9 +280,9 @@ int git_vector_resize_to(git_vector *v, size_t new_length) if (new_length <= v->length) return 0; - while (new_length >= v->_alloc_size) - if (resize_vector(v) < 0) - return -1; + if (new_length > v->_alloc_size && + resize_vector(v, new_length) < 0) + return -1; memset(&v->contents[v->length], 0, sizeof(void *) * (new_length - v->length)); diff --git a/src/vector.h b/src/vector.h index 023f4b663..690e4af9c 100644 --- a/src/vector.h +++ b/src/vector.h @@ -30,29 +30,22 @@ void git_vector_swap(git_vector *a, git_vector *b); void git_vector_sort(git_vector *v); /** Linear search for matching entry using internal comparison function */ -int git_vector_search(const git_vector *v, const void *entry); +int git_vector_search(size_t *at_pos, const git_vector *v, const void *entry); /** Linear search for matching entry using explicit comparison function */ -int git_vector_search2(const git_vector *v, git_vector_cmp cmp, const void *key); +int git_vector_search2(size_t *at_pos, const git_vector *v, git_vector_cmp cmp, const void *key); /** * Binary search for matching entry using explicit comparison function that * returns position where item would go if not found. */ -int git_vector_bsearch3( +int git_vector_bsearch2( size_t *at_pos, git_vector *v, git_vector_cmp cmp, const void *key); /** Binary search for matching entry using internal comparison function */ -GIT_INLINE(int) git_vector_bsearch(git_vector *v, const void *key) +GIT_INLINE(int) git_vector_bsearch(size_t *at_pos, git_vector *v, const void *key) { - return git_vector_bsearch3(NULL, v, v->_cmp, key); -} - -/** Binary search for matching entry using explicit comparison function */ -GIT_INLINE(int) git_vector_bsearch2( - git_vector *v, git_vector_cmp cmp, const void *key) -{ - return git_vector_bsearch3(NULL, v, cmp, key); + return git_vector_bsearch2(at_pos, v, v->_cmp, key); } GIT_INLINE(void *) git_vector_get(const git_vector *v, size_t position) diff --git a/tests-clar/attr/repo.c b/tests-clar/attr/repo.c index 926a0d8a2..ca3e71e7f 100644 --- a/tests-clar/attr/repo.c +++ b/tests-clar/attr/repo.c @@ -266,14 +266,13 @@ static void add_to_workdir(const char *filename, const char *content) static void assert_proper_normalization(git_index *index, const char *filename, const char *expected_sha) { - int index_pos; + size_t index_pos; const git_index_entry *entry; add_to_workdir(filename, CONTENT); cl_git_pass(git_index_add_bypath(index, filename)); - index_pos = git_index_find(index, filename); - cl_assert(index_pos >= 0); + cl_assert(!git_index_find(&index_pos, index, filename)); entry = git_index_get_byindex(index, index_pos); cl_assert_equal_i(0, git_oid_streq(&entry->oid, expected_sha)); diff --git a/tests-clar/index/filemodes.c b/tests-clar/index/filemodes.c index 1acd2e341..1bb44173c 100644 --- a/tests-clar/index/filemodes.c +++ b/tests-clar/index/filemodes.c @@ -53,13 +53,12 @@ static void replace_file_with_mode( static void add_and_check_mode( git_index *index, const char *filename, unsigned int expect_mode) { - int pos; + size_t pos; const git_index_entry *entry; cl_git_pass(git_index_add_bypath(index, filename)); - pos = git_index_find(index, filename); - cl_assert(pos >= 0); + cl_assert(!git_index_find(&pos, index, filename)); entry = git_index_get_byindex(index, pos); cl_assert(entry->mode == expect_mode); diff --git a/tests-clar/index/rename.c b/tests-clar/index/rename.c index 400bbdf15..4deef1332 100644 --- a/tests-clar/index/rename.c +++ b/tests-clar/index/rename.c @@ -5,7 +5,7 @@ void test_index_rename__single_file(void) { git_repository *repo; git_index *index; - int position; + size_t position; git_oid expected; const git_index_entry *entry; @@ -24,7 +24,7 @@ void test_index_rename__single_file(void) cl_git_pass(git_oid_fromstr(&expected, "d4fa8600b4f37d7516bef4816ae2c64dbf029e3a")); - position = git_index_find(index, "lame.name.txt"); + cl_assert(!git_index_find(&position, index, "lame.name.txt")); entry = git_index_get_byindex(index, position); cl_assert(git_oid_cmp(&expected, &entry->oid) == 0); @@ -38,7 +38,7 @@ void test_index_rename__single_file(void) cl_git_pass(git_index_add_bypath(index, "fancy.name.txt")); cl_assert(git_index_entrycount(index) == 1); - position = git_index_find(index, "fancy.name.txt"); + cl_assert(!git_index_find(&position, index, "fancy.name.txt")); entry = git_index_get_byindex(index, position); cl_assert(git_oid_cmp(&expected, &entry->oid) == 0); diff --git a/tests-clar/index/stage.c b/tests-clar/index/stage.c index 477456846..58dc1fb5e 100644 --- a/tests-clar/index/stage.c +++ b/tests-clar/index/stage.c @@ -26,36 +26,36 @@ void test_index_stage__cleanup(void) void test_index_stage__add_always_adds_stage_0(void) { - int entry_idx; + size_t entry_idx; const git_index_entry *entry; cl_git_mkfile("./mergedrepo/new-file.txt", "new-file\n"); cl_git_pass(git_index_add_bypath(repo_index, "new-file.txt")); - cl_assert((entry_idx = git_index_find(repo_index, "new-file.txt")) >= 0); + cl_assert(!git_index_find(&entry_idx, repo_index, "new-file.txt")); cl_assert((entry = git_index_get_byindex(repo_index, entry_idx)) != NULL); cl_assert(git_index_entry_stage(entry) == 0); } void test_index_stage__find_gets_first_stage(void) { - int entry_idx; + size_t entry_idx; const git_index_entry *entry; - cl_assert((entry_idx = git_index_find(repo_index, "one.txt")) >= 0); + cl_assert(!git_index_find(&entry_idx, repo_index, "one.txt")); cl_assert((entry = git_index_get_byindex(repo_index, entry_idx)) != NULL); cl_assert(git_index_entry_stage(entry) == 0); - cl_assert((entry_idx = git_index_find(repo_index, "two.txt")) >= 0); + cl_assert(!git_index_find(&entry_idx, repo_index, "two.txt")); cl_assert((entry = git_index_get_byindex(repo_index, entry_idx)) != NULL); cl_assert(git_index_entry_stage(entry) == 0); - cl_assert((entry_idx = git_index_find(repo_index, "conflicts-one.txt")) >= 0); + cl_assert(!git_index_find(&entry_idx, repo_index, "conflicts-one.txt")); cl_assert((entry = git_index_get_byindex(repo_index, entry_idx)) != NULL); cl_assert(git_index_entry_stage(entry) == 1); - cl_assert((entry_idx = git_index_find(repo_index, "conflicts-two.txt")) >= 0); + cl_assert(!git_index_find(&entry_idx, repo_index, "conflicts-two.txt")); cl_assert((entry = git_index_get_byindex(repo_index, entry_idx)) != NULL); cl_assert(git_index_entry_stage(entry) == 1); } diff --git a/tests-clar/index/tests.c b/tests-clar/index/tests.c index 3c2a6899c..64f547ead 100644 --- a/tests-clar/index/tests.c +++ b/tests-clar/index/tests.c @@ -10,7 +10,7 @@ static const size_t index_entry_count_2 = 1437; // Suite data struct test_entry { - int index; + size_t index; char path[128]; git_off_t file_size; git_time_t mtime; @@ -131,8 +131,10 @@ void test_index_tests__find_in_existing(void) cl_git_pass(git_index_open(&index, TEST_INDEX_PATH)); for (i = 0; i < ARRAY_SIZE(test_entries); ++i) { - int idx = git_index_find(index, test_entries[i].path); - cl_assert(idx == test_entries[i].index); + size_t idx; + + cl_assert(!git_index_find(&idx, index, test_entries[i].path)); + cl_assert(idx == test_entries[i].index); } git_index_free(index); @@ -146,8 +148,7 @@ void test_index_tests__find_in_empty(void) cl_git_pass(git_index_open(&index, "fake-index")); for (i = 0; i < ARRAY_SIZE(test_entries); ++i) { - int idx = git_index_find(index, test_entries[i].path); - cl_assert(idx == GIT_ENOTFOUND); + cl_assert(GIT_ENOTFOUND == git_index_find(NULL, index, test_entries[i].path)); } git_index_free(index); diff --git a/tests-clar/submodule/status.c b/tests-clar/submodule/status.c index 325013466..3fd6960c9 100644 --- a/tests-clar/submodule/status.c +++ b/tests-clar/submodule/status.c @@ -100,11 +100,10 @@ void test_submodule_status__ignore_none(void) /* remove sm_changed_head from index */ { git_index *index; - int pos; + size_t pos; cl_git_pass(git_repository_index(&index, g_repo)); - pos = git_index_find(index, "sm_changed_head"); - cl_assert(pos >= 0); + cl_assert(!git_index_find(&pos, index, "sm_changed_head")); cl_git_pass(git_index_remove(index, "sm_changed_head", 0)); cl_git_pass(git_index_write(index)); |