Re: [PATCH 3/3] refs: use strings directly in find_containing_dir()
- From
Junio C Hamano <gitster@pobox.com>
- Date
- May 22, 2012, 21:27 UTC
- Message-ID
- <7vlikj3nzc.fsf@alter.siamese.dyndns.org>
- In-Reply-To
- <4FBBE012.6090702@lsrfire.ath.cx>
René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:
> Why allocate a NUL-terminated copy at all when we can teach the code to > stop after a given number of characters just as easily? Alas, this > will still trigger an allocation in search_ref_dir() (see first patch).
Yeah, but it is only because search_ref_dir() tries to use ref_entry_cmp(), whose signature is geared more towards being used as a qsort(3) callback, as the comparison function for bsearch(3).
A bsearch() callback takes two pointers, one is for the key and the other for an array element, and there is no reason to require the two types be the same.
In other words, something like this patch and we won't need an allocation of the ref_entry that did not have to be a full ref_entry in the first place (it only had to be something that supplies the "key" into a sorted array).
refs.c | 32 +++++++++++++++++++++++--------- 1 file changed, 23 insertions(+), 9 deletions(-)
diff --git a/refs.c b/refs.c index 96e943c..52709ab 100644 --- a/refs.c +++ b/refs.c @@ -315,6 +315,23 @@ static int ref_entry_cmp(const void *a, const void *b) static void sort_ref_dir(struct ref_dir *dir); +struct string_slice { + size_t len; + const char *str; +}; + +static int ref_entry_cmp_sslice(const void *key_, const void *ent_) +{ + struct string_slice *key = (struct string_slice *)key_; + struct ref_entry *ent = *(struct ref_entry **)ent_; + int entlen = strlen(ent->name); + int cmplen = key->len < entlen ? key->len : entlen; + int cmp = memcmp(key->str, ent->name, cmplen); + if (cmp) + return cmp; + return key->len - entlen; +} + /* * Return the entry with the given refname from the ref_dir * (non-recursively), sorting dir if necessary. Return NULL if no @@ -323,20 +340,17 @@ static void sort_ref_dir(struct ref_dir *dir); static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname, size_t len) { - struct ref_entry *e, **r; + struct ref_entry **r; + struct string_slice key; if (refname == NULL || !dir->nr) return NULL; sort_ref_dir(dir); - - e = xmalloc(sizeof(struct ref_entry) + len + 1); - memcpy(e->name, refname, len); - e->name[len] = '\0'; - - r = bsearch(&e, dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp); - - free(e); + key.len = len; + key.str = refname; + r = bsearch(&key, dir->entries, dir->nr, sizeof(*dir->entries), + ref_entry_cmp_sslice); if (r == NULL) return NULL;