Commit d307a0134b97475abb03d0365458c318ba817f95
2015-10-27T22:17:32
reuc: Be smarter when inserting new REUC entries Inserting new REUC entries can quickly become pathological given that each insert unsorts the REUC vector, and both subsequent lookups *and* insertions will require sorting it again before being successful. To avoid this, we're switching to `git_vector_insert_sorted`: this keeps the REUC vector constantly sorted and lets us use the `on_dup` callback to skip an extra binary search on each insertion.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
diff --git a/src/index.c b/src/index.c
index 334a131..d9e7138 100644
--- a/src/index.c
+++ b/src/index.c
@@ -2000,27 +2000,24 @@ size_t git_index_reuc_entrycount(git_index *index)
return index->reuc.length;
}
+static int index_reuc_on_dup(void **old, void *new)
+{
+ index_entry_reuc_free(*old);
+ *old = new;
+ return GIT_EEXISTS;
+}
+
static int index_reuc_insert(
git_index *index,
- git_index_reuc_entry *reuc,
- int replace)
+ git_index_reuc_entry *reuc)
{
- git_index_reuc_entry **existing = NULL;
- size_t position;
+ int res;
assert(index && reuc && reuc->path != NULL);
+ assert(git_vector_is_sorted(&index->reuc));
- if (!git_index_reuc_find(&position, index, reuc->path))
- existing = (git_index_reuc_entry **)&index->reuc.contents[position];
-
- if (!replace || !existing)
- return git_vector_insert(&index->reuc, reuc);
-
- /* exists, replace it */
- git__free(*existing);
- *existing = reuc;
-
- return 0;
+ res = git_vector_insert_sorted(&index->reuc, reuc, &index_reuc_on_dup);
+ return res == GIT_EEXISTS ? 0 : res;
}
int git_index_reuc_add(git_index *index, const char *path,
@@ -2035,7 +2032,7 @@ int git_index_reuc_add(git_index *index, const char *path,
if ((error = index_entry_reuc_init(&reuc, path, ancestor_mode,
ancestor_oid, our_mode, our_oid, their_mode, their_oid)) < 0 ||
- (error = index_reuc_insert(index, reuc, 1)) < 0)
+ (error = index_reuc_insert(index, reuc)) < 0)
index_entry_reuc_free(reuc);
return error;
@@ -2055,7 +2052,7 @@ const git_index_reuc_entry *git_index_reuc_get_bypath(
if (!index->reuc.length)
return NULL;
- git_vector_sort(&index->reuc);
+ assert(git_vector_is_sorted(&index->reuc));
if (git_index_reuc_find(&pos, index, path) < 0)
return NULL;
@@ -2067,8 +2064,8 @@ const git_index_reuc_entry *git_index_reuc_get_byindex(
git_index *index, size_t n)
{
assert(index);
+ assert(git_vector_is_sorted(&index->reuc));
- git_vector_sort(&index->reuc);
return git_vector_get(&index->reuc, n);
}
@@ -2077,7 +2074,7 @@ int git_index_reuc_remove(git_index *index, size_t position)
int error;
git_index_reuc_entry *reuc;
- git_vector_sort(&index->reuc);
+ assert(git_vector_is_sorted(&index->reuc));
reuc = git_vector_get(&index->reuc, position);
error = git_vector_remove(&index->reuc, position);