diff options
author | Michael Haggerty <mhagger@alum.mit.edu> | 2011-12-12 06:38:37 +0100 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2011-12-12 09:08:55 -0800 |
commit | 061bfe7e64c72dd1a3000695de0ba4998fec17f8 (patch) | |
tree | 10dcf382f467c2f25af351fe3898607d30c3bb02 | |
parent | 47f9443fb01333cc904525227461e3f3200f00e8 (diff) | |
download | git-061bfe7e64c72dd1a3000695de0ba4998fec17f8.tar.gz |
sort_ref_dir(): do not sort if already sorted
Keep track of how many entries in a ref_dir are already sorted. In
sort_ref_dir(), only call qsort() if the dir contains unsorted
entries.
We could store a binary "sorted" value instead of an integer, but
storing the number of sorted entries leaves the way open for a couple
of possible future optimizations:
* In sort_ref_dir(), sort *only* the unsorted entries, then merge them
with the sorted entries. This should be faster if most of the
entries are already sorted.
* Teach search_ref_dir() to do a binary search of any sorted entries,
and if unsuccessful do a linear search of any unsorted entries.
This would avoid the need to sort the list every time that
search_ref_dir() is called, and (given some intelligence about how
often to sort) could significantly improve the speed in certain
hypothetical usage patterns.
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
-rw-r--r-- | refs.c | 29 |
1 files changed, 24 insertions, 5 deletions
@@ -108,6 +108,10 @@ struct ref_value { struct ref_dir { int nr, alloc; + + /* How many of the entries in this directory are sorted? */ + int sorted; + struct ref_entry **entries; }; @@ -210,7 +214,7 @@ static void clear_ref_dir(struct ref_dir *dir) for (i = 0; i < dir->nr; i++) free_ref_entry(dir->entries[i]); free(dir->entries); - dir->nr = dir->alloc = 0; + dir->sorted = dir->nr = dir->alloc = 0; dir->entries = NULL; } @@ -252,8 +256,9 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname /* * We need dir to be sorted so that binary search works. - * FIXME: Sorting the array each time is terribly inefficient, - * and has to be changed. + * Calling sort_ref_dir() here is not quite as terribly + * inefficient as it looks, because directories that are + * already sorted are not re-sorted. */ sort_ref_dir(dir); @@ -358,13 +363,27 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2 return 1; } +/* + * Sort the entries in dir and its subdirectories (if they are not + * already sorted). + */ static void sort_ref_dir(struct ref_dir *dir) { int i, j; struct ref_entry *last = NULL; - if (!dir->nr) + if (dir->sorted == dir->nr) { + /* + * This directory is already sorted and de-duped, but + * we still have to sort subdirectories. + */ + for (i = 0; i < dir->nr; i++) { + struct ref_entry *entry = dir->entries[i]; + if (entry->flag & REF_DIR) + sort_ref_dir(&entry->u.subdir); + } return; + } qsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp); @@ -381,7 +400,7 @@ static void sort_ref_dir(struct ref_dir *dir) last = dir->entries[i++] = entry; } } - dir->nr = i; + dir->sorted = dir->nr = i; } #define DO_FOR_EACH_INCLUDE_BROKEN 01 |