From e45a59955ec78bca12930bcf6aa9642fd94c9e7c Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 17 Jan 2012 06:50:31 +0100 Subject: pack_refs(): remove redundant check handle_one_ref() only adds refs to the cbdata.ref_to_prune list if (cbdata.flags & PACK_REFS_PRUNE) is set. So any references in this list at the end of pack_refs() can be pruned unconditionally. Signed-off-by: Michael Haggerty Signed-off-by: Junio C Hamano --- pack-refs.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/pack-refs.c b/pack-refs.c index 23bbd00e3e..f09a054228 100644 --- a/pack-refs.c +++ b/pack-refs.c @@ -143,7 +143,6 @@ int pack_refs(unsigned int flags) packed.fd = -1; if (commit_lock_file(&packed) < 0) die_errno("unable to overwrite old ref-pack file"); - if (cbdata.flags & PACK_REFS_PRUNE) - prune_refs(cbdata.ref_to_prune); + prune_refs(cbdata.ref_to_prune); return 0; } -- cgit v1.2.3 From e6ed3ca651fac702f9d9a9ef64a14c7efadf7365 Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 17 Jan 2012 06:50:32 +0100 Subject: ref_array: keep track of whether references are sorted Keep track of how many entries at the beginning of a ref_array are already sorted. In sort_ref_array(), return early if the the array is already sorted (i.e., if no new references has been appended to the end of the list since the last call to sort_ref_array()). Sort ref_arrays only when needed, namely in search_ref_array() and in do_for_each_ref(). However, never call sort_ref_array() on the extra_refs, because extra_refs can contain multiple entries with the same name and because sort_ref_array() not only sorts, but de-dups its contents. This change is currently not useful, because entries are not added to ref_arrays after they are created. But in a moment they will be... Implementation note: 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_array(), 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_array() 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_array() 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 Signed-off-by: Junio C Hamano --- refs.c | 33 ++++++++++++++++++++++++++------- 1 file changed, 26 insertions(+), 7 deletions(-) diff --git a/refs.c b/refs.c index 6f436f1cb0..3785cc200c 100644 --- a/refs.c +++ b/refs.c @@ -17,6 +17,15 @@ struct ref_entry { struct ref_array { int nr, alloc; + + /* + * Entries with index 0 <= i < sorted are sorted by name. New + * entries are appended to the list unsorted, and are sorted + * only when required; thus we avoid the need to sort the list + * after the addition of every reference. + */ + int sorted; + struct ref_entry **refs; }; @@ -105,12 +114,18 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2 } } +/* + * Sort the entries in array (if they are not already sorted). + */ static void sort_ref_array(struct ref_array *array) { int i, j; - /* Nothing to sort unless there are at least two entries */ - if (array->nr < 2) + /* + * This check also prevents passing a zero-length array to qsort(), + * which is a problem on some platforms. + */ + if (array->sorted == array->nr) return; qsort(array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp); @@ -124,7 +139,7 @@ static void sort_ref_array(struct ref_array *array) } array->refs[++i] = array->refs[j]; } - array->nr = i + 1; + array->sorted = array->nr = i + 1; } static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname) @@ -137,7 +152,7 @@ static struct ref_entry *search_ref_array(struct ref_array *array, const char *r if (!array->nr) return NULL; - + sort_ref_array(array); len = strlen(refname) + 1; e = xmalloc(sizeof(struct ref_entry) + len); memcpy(e->name, refname, len); @@ -168,6 +183,10 @@ static struct ref_cache { static struct ref_entry *current_ref; +/* + * Never call sort_ref_array() on the extra_refs, because it is + * allowed to contain entries with duplicate names. + */ static struct ref_array extra_refs; static void clear_ref_array(struct ref_array *array) @@ -176,7 +195,7 @@ static void clear_ref_array(struct ref_array *array) for (i = 0; i < array->nr; i++) free(array->refs[i]); free(array->refs); - array->nr = array->alloc = 0; + array->sorted = array->nr = array->alloc = 0; array->refs = NULL; } @@ -268,7 +287,6 @@ static void read_packed_refs(FILE *f, struct ref_array *array) !get_sha1_hex(refline + 1, sha1)) hashcpy(last->peeled, sha1); } - sort_ref_array(array); } void add_extra_ref(const char *refname, const unsigned char *sha1, int flag) @@ -404,7 +422,6 @@ static struct ref_array *get_loose_refs(struct ref_cache *refs) { if (!refs->did_loose) { get_ref_dir(refs, "refs", &refs->loose); - sort_ref_array(&refs->loose); refs->did_loose = 1; } return &refs->loose; @@ -720,6 +737,8 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn for (i = 0; i < extra->nr; i++) retval = do_one_ref(base, fn, trim, flags, cb_data, extra->refs[i]); + sort_ref_array(packed); + sort_ref_array(loose); while (p < packed->nr && l < loose->nr) { struct ref_entry *entry; int cmp = strcmp(packed->refs[p]->name, loose->refs[l]->name); -- cgit v1.2.3 From 30249ee68fa5fa63bfb9bb417987b0547253b8e7 Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 17 Jan 2012 06:50:33 +0100 Subject: add_packed_ref(): new function in the refs API. Add a new function add_packed_ref() that adds a reference directly to the in-memory packed reference cache. This will be useful for creating local references while cloning. Signed-off-by: Michael Haggerty Signed-off-by: Junio C Hamano --- refs.c | 6 ++++++ refs.h | 6 ++++++ 2 files changed, 12 insertions(+) diff --git a/refs.c b/refs.c index 3785cc200c..b8843bb476 100644 --- a/refs.c +++ b/refs.c @@ -319,6 +319,12 @@ static struct ref_array *get_packed_refs(struct ref_cache *refs) return &refs->packed; } +void add_packed_ref(const char *refname, const unsigned char *sha1) +{ + add_ref(get_packed_refs(get_ref_cache(NULL)), + create_ref_entry(refname, sha1, REF_ISPACKED, 1)); +} + static void get_ref_dir(struct ref_cache *refs, const char *base, struct ref_array *array) { diff --git a/refs.h b/refs.h index d4982915c5..00ba1e2813 100644 --- a/refs.h +++ b/refs.h @@ -50,6 +50,12 @@ extern int for_each_rawref(each_ref_fn, void *); extern void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname); +/* + * Add a reference to the in-memory packed reference cache. To actually + * write the reference to the packed-refs file, call pack_refs(). + */ +extern void add_packed_ref(const char *refname, const unsigned char *sha1); + /* * Extra refs will be listed by for_each_ref() before any actual refs * for the duration of this process or until clear_extra_refs() is -- cgit v1.2.3 From 39ef7fae9a398ad4523a211bc87aff599c3d3869 Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 17 Jan 2012 06:50:34 +0100 Subject: write_remote_refs(): create packed (rather than extra) refs write_remote_refs() creates new packed refs from references obtained from the remote repository, which is "out of thin air" as far as the local repository is concerned. Previously it did this by creating "extra" refs, then calling pack_refs() to bake them into the packed-refs file. Instead, create packed refs (in the packed reference cache) directly, then call pack_refs(). Aside from being more logical, this is another step towards removing extra refs entirely. Signed-off-by: Michael Haggerty Signed-off-by: Junio C Hamano --- builtin/clone.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/builtin/clone.c b/builtin/clone.c index 86db954730..9413537a8e 100644 --- a/builtin/clone.c +++ b/builtin/clone.c @@ -441,11 +441,10 @@ static void write_remote_refs(const struct ref *local_refs) for (r = local_refs; r; r = r->next) { if (!r->peer_ref) continue; - add_extra_ref(r->peer_ref->name, r->old_sha1, 0); + add_packed_ref(r->peer_ref->name, r->old_sha1); } pack_refs(PACK_REFS_ALL); - clear_extra_refs(); } static int write_one_config(const char *key, const char *value, void *data) -- cgit v1.2.3