summaryrefslogtreecommitdiff
path: root/object.c
diff options
context:
space:
mode:
authorMichael Haggerty <mhagger@alum.mit.edu>2013-05-25 11:08:10 +0200
committerJunio C Hamano <gitster@pobox.com>2013-05-28 09:25:01 -0700
commit1506510c170d23b8f769757dc81904f334c40281 (patch)
treec5f89d862073b5aca88dd082a08591d097cbb8bb /object.c
parentbe6754c67f5aff02e9528116d06890391524f48e (diff)
downloadgit-1506510c170d23b8f769757dc81904f334c40281.tar.gz
object_array_remove_duplicates(): rewrite to reduce copying
The old version copied one entry to its destination position, then deleted any matching entries from the tail of the array. This required the tail of the array to be copied multiple times. It didn't affect the complexity of the algorithm because the whole tail has to be searched through anyway. But all the copying was unnecessary. Instead, check for the existence of an entry with the same name in the *head* of the list before copying an entry to its final position. This way each entry has to be copied at most one time. Extract a helper function contains_name() to do a bit of the work. Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'object.c')
-rw-r--r--object.c32
1 files changed, 21 insertions, 11 deletions
diff --git a/object.c b/object.c
index fcd4a82c13..10b5349461 100644
--- a/object.c
+++ b/object.c
@@ -294,22 +294,32 @@ void object_array_filter(struct object_array *array,
array->nr = dst;
}
+/*
+ * Return true iff array already contains an entry with name.
+ */
+static int contains_name(struct object_array *array, const char *name)
+{
+ unsigned nr = array->nr, i;
+ struct object_array_entry *object = array->objects;
+
+ for (i = 0; i < nr; i++, object++)
+ if (!strcmp(object->name, name))
+ return 1;
+ return 0;
+}
+
void object_array_remove_duplicates(struct object_array *array)
{
- unsigned int ref, src, dst;
+ unsigned nr = array->nr, src;
struct object_array_entry *objects = array->objects;
- for (ref = 0; ref + 1 < array->nr; ref++) {
- for (src = ref + 1, dst = src;
- src < array->nr;
- src++) {
- if (!strcmp(objects[ref].name, objects[src].name))
- continue;
- if (src != dst)
- objects[dst] = objects[src];
- dst++;
+ array->nr = 0;
+ for (src = 0; src < nr; src++) {
+ if (!contains_name(array, objects[src].name)) {
+ if (src != array->nr)
+ objects[array->nr] = objects[src];
+ array->nr++;
}
- array->nr = dst;
}
}