]> git.ipfire.org Git - thirdparty/git.git/commit - object.h
object_array_remove_duplicates(): rewrite to reduce copying
authorMichael Haggerty <mhagger@alum.mit.edu>
Sat, 25 May 2013 09:08:10 +0000 (11:08 +0200)
committerJunio C Hamano <gitster@pobox.com>
Tue, 28 May 2013 16:25:01 +0000 (09:25 -0700)
commit1506510c170d23b8f769757dc81904f334c40281
treec5f89d862073b5aca88dd082a08591d097cbb8bb
parentbe6754c67f5aff02e9528116d06890391524f48e
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>
object.c
object.h