[PATCH 1/5] refs: store submodule ref stores in a hashmap

[Michael Haggerty <mhagger@alum.mit.edu>]

Aside from scaling better, this means that the submodule name needn't be
stored in the ref_store instance anymore (which will be changed in a
moment). This, in turn, will help loosen the strict 1:1 relationship
between ref_stores and submodules.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c               | 61 ++++++++++++++++++++++++++++++++++++++++------------
 refs/refs-internal.h |  6 ------
 2 files changed, 47 insertions(+), 20 deletions(-)

diff --git a/refs.c b/refs.c
index cd36b64..50d192c 100644
--- a/refs.c
+++ b/refs.c
@@ -3,6 +3,7 @@
  */
 
 #include "cache.h"
+#include "hashmap.h"
 #include "lockfile.h"
 #include "refs.h"
 #include "refs/refs-internal.h"
@@ -1357,11 +1358,42 @@ int resolve_gitlink_ref(const char *submodule, const char *refname,
 	return 0;
 }
 
+struct submodule_hash_entry
+{
+	struct hashmap_entry ent; /* must be the first member! */
+
+	struct ref_store *refs;
+
+	/* NUL-terminated name of submodule: */
+	char submodule[FLEX_ARRAY];
+};
+
+static int submodule_hash_cmp(const void *entry, const void *entry_or_key,
+			      const void *keydata)
+{
+	const struct submodule_hash_entry *e1 = entry, *e2 = entry_or_key;
+	const char *submodule = keydata;
+
+	return strcmp(e1->submodule, submodule ? submodule : e2->submodule);
+}
+
+static struct submodule_hash_entry *alloc_submodule_hash_entry(
+		const char *submodule, struct ref_store *refs)
+{
+	size_t len = strlen(submodule);
+	struct submodule_hash_entry *entry = malloc(sizeof(*entry) + len + 1);
+
+	hashmap_entry_init(entry, strhash(submodule));
+	entry->refs = refs;
+	memcpy(entry->submodule, submodule, len + 1);
+	return entry;
+}
+
 /* A pointer to the ref_store for the main repository: */
 static struct ref_store *main_ref_store;
 
-/* A linked list of ref_stores for submodules: */
-static struct ref_store *submodule_ref_stores;
+/* A hashmap of ref_stores, stored by submodule name: */
+static struct hashmap submodule_ref_stores;
 
 void base_ref_store_init(struct ref_store *refs,
 			 const struct ref_storage_be *be,
@@ -1373,16 +1405,17 @@ void base_ref_store_init(struct ref_store *refs,
 			die("BUG: main_ref_store initialized twice");
 
 		refs->submodule = "";
-		refs->next = NULL;
 		main_ref_store = refs;
 	} else {
-		if (lookup_ref_store(submodule))
+		refs->submodule = xstrdup(submodule);
+
+		if (!submodule_ref_stores.tablesize)
+			hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
+
+		if (hashmap_put(&submodule_ref_stores,
+				alloc_submodule_hash_entry(submodule, refs)))
 			die("BUG: ref_store for submodule '%s' initialized twice",
 			    submodule);
-
-		refs->submodule = xstrdup(submodule);
-		refs->next = submodule_ref_stores;
-		submodule_ref_stores = refs;
 	}
 }
 
@@ -1402,17 +1435,17 @@ struct ref_store *ref_store_init(const char *submodule)
 
 struct ref_store *lookup_ref_store(const char *submodule)
 {
-	struct ref_store *refs;
+	struct submodule_hash_entry *entry;
 
 	if (!submodule || !*submodule)
 		return main_ref_store;
 
-	for (refs = submodule_ref_stores; refs; refs = refs->next) {
-		if (!strcmp(submodule, refs->submodule))
-			return refs;
-	}
+	if (!submodule_ref_stores.tablesize)
+		hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
 
-	return NULL;
+	entry = hashmap_get_from_hash(&submodule_ref_stores,
+				      strhash(submodule), submodule);
+	return entry ? entry->refs : NULL;
 }
 
 struct ref_store *get_ref_store(const char *submodule)
diff --git a/refs/refs-internal.h b/refs/refs-internal.h
index 25444cf..4ed5f89 100644
--- a/refs/refs-internal.h
+++ b/refs/refs-internal.h
@@ -634,12 +634,6 @@ struct ref_store {
 	 * reference store:
 	 */
 	const char *submodule;
-
-	/*
-	 * Submodule reference store instances are stored in a linked
-	 * list using this pointer.
-	 */
-	struct ref_store *next;
 };
 
 /*
-- 
2.9.3