[PATCH] refs.c: get_ref_cache: use a bucket hash

[Andreas Krey <a.krey@gmx.de>]

get_ref_cache used a linear list, which obviously is O(n^2).
Use a fixed bucket hash which just takes a factor of 100000
(~ 317^2) out of the n^2 - which is enough.

Signed-off-by: Andreas Krey <a.krey@gmx.de>
---

This brings 'git clean -ndx' times down from 17 minutes
to 11 seconds on one of our workspaces (which accumulated
a lot of ignored directories). Actuallly using adaptive
hashing or other structures seems overkill.

 refs.c | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

diff --git a/refs.c b/refs.c
index e23542b..8198d9e 100644
--- a/refs.c
+++ b/refs.c
@@ -982,6 +982,8 @@ struct packed_ref_cache {
 	struct stat_validity validity;
 };
 
+#define REF_CACHE_HASH 317
+
 /*
  * Future: need to be in "struct repository"
  * when doing a full libification.
@@ -996,7 +998,7 @@ static struct ref_cache {
 	 * is initialized correctly.
 	 */
 	char name[1];
-} ref_cache, *submodule_ref_caches;
+} ref_cache, *submodule_ref_caches[REF_CACHE_HASH];
 
 /* Lock used for the main packed-refs file: */
 static struct lock_file packlock;
@@ -1065,18 +1067,19 @@ static struct ref_cache *create_ref_cache(const char *submodule)
  */
 static struct ref_cache *get_ref_cache(const char *submodule)
 {
-	struct ref_cache *refs;
+	struct ref_cache *refs, **bucketp;
+	bucketp = submodule_ref_caches + strhash(submodule) % REF_CACHE_HASH;
 
 	if (!submodule || !*submodule)
 		return &ref_cache;
 
-	for (refs = submodule_ref_caches; refs; refs = refs->next)
+	for (refs = *bucketp; refs; refs = refs->next)
 		if (!strcmp(submodule, refs->name))
 			return refs;
 
 	refs = create_ref_cache(submodule);
-	refs->next = submodule_ref_caches;
-	submodule_ref_caches = refs;
+	refs->next = *bucketp;
+	*bucketp = refs;
 	return refs;
 }
 
-- 
2.3.2.223.g7a9409c