[[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation

From

KWKevin Willford <kcwillford@gmail.com>

Date

Jul 29, 2016, 16:19 UTC

Message-ID

<20160729161920.3792-2-kcwillford@gmail.com>

In-Reply-To

<20160729161920.3792-1-kcwillford@gmail.com>

From: Kevin Willford <kewillf@microsoft.com>

Signed-off-by: Kevin Willford <kcwillford@gmail.com>
---
 patch-ids.c | 86 +++++++++++++++++++++----------------------------------------
 patch-ids.h |  7 +++--
 2 files changed, 32 insertions(+), 61 deletions(-)

diff --git a/patch-ids.c b/patch-ids.c
index a4d0016..db31fa6 100644
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -16,90 +16,62 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,
 	return diff_flush_patch_id(options, sha1);
 }
 
-static const unsigned char *patch_id_access(size_t index, void *table)
+static int patch_id_cmp(struct patch_id *a,
+			struct patch_id *b,
+			void *keydata)
 {
-	struct patch_id **id_table = table;
-	return id_table[index]->patch_id;
+	return hashcmp(a->patch_id, b->patch_id);
 }
 
-static int patch_pos(struct patch_id **table, int nr, const unsigned char *id)
-{
-	return sha1_pos(id, table, nr, patch_id_access);
-}
-
-#define BUCKET_SIZE 190 /* 190 * 21 = 3990, with slop close enough to 4K */
-struct patch_id_bucket {
-	struct patch_id_bucket *next;
-	int nr;
-	struct patch_id bucket[BUCKET_SIZE];
-};
-
 int init_patch_ids(struct patch_ids *ids)
 {
 	memset(ids, 0, sizeof(*ids));
 	diff_setup(&ids->diffopts);
 	DIFF_OPT_SET(&ids->diffopts, RECURSIVE);
 	diff_setup_done(&ids->diffopts);
+	hashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp, 256);
 	return 0;
 }
 
 int free_patch_ids(struct patch_ids *ids)
 {
-	struct patch_id_bucket *next, *patches;
-
-	free(ids->table);
-	for (patches = ids->patches; patches; patches = next) {
-		next = patches->next;
-		free(patches);
-	}
+	hashmap_free(&ids->patches, 1);
 	return 0;
 }
 
-static struct patch_id *add_commit(struct commit *commit,
-				   struct patch_ids *ids,
-				   int no_add)
+static int init_patch_id_entry(struct patch_id *patch,
+			       struct commit *commit,
+			       struct patch_ids *ids)
 {
-	struct patch_id_bucket *bucket;
-	struct patch_id *ent;
-	unsigned char sha1[20];
-	int pos;
-
-	if (commit_patch_id(commit, &ids->diffopts, sha1))
-		return NULL;
-	pos = patch_pos(ids->table, ids->nr, sha1);
-	if (0 <= pos)
-		return ids->table[pos];
-	if (no_add)
-		return NULL;
-
-	pos = -1 - pos;
+	if (commit_patch_id(commit, &ids->diffopts, patch->patch_id))
+		return -1;
 
-	bucket = ids->patches;
-	if (!bucket || (BUCKET_SIZE <= bucket->nr)) {
-		bucket = xcalloc(1, sizeof(*bucket));
-		bucket->next = ids->patches;
-		ids->patches = bucket;
-	}
-	ent = &bucket->bucket[bucket->nr++];
-	hashcpy(ent->patch_id, sha1);
-
-	ALLOC_GROW(ids->table, ids->nr + 1, ids->alloc);
-	if (pos < ids->nr)
-		memmove(ids->table + pos + 1, ids->table + pos,
-			sizeof(ent) * (ids->nr - pos));
-	ids->nr++;
-	ids->table[pos] = ent;
-	return ids->table[pos];
+	hashmap_entry_init(patch, sha1hash(patch->patch_id));
+	return 0;
 }
 
 struct patch_id *has_commit_patch_id(struct commit *commit,
 				     struct patch_ids *ids)
 {
-	return add_commit(commit, ids, 1);
+	struct patch_id patch;
+
+	memset(&patch, 0, sizeof(patch));
+	if (init_patch_id_entry(&patch, commit, ids))
+		return NULL;
+
+	return hashmap_get(&ids->patches, &patch, NULL);
 }
 
 struct patch_id *add_commit_patch_id(struct commit *commit,
 				     struct patch_ids *ids)
 {
-	return add_commit(commit, ids, 0);
+	struct patch_id *key = xcalloc(1, sizeof(*key));
+
+	if (init_patch_id_entry(key, commit, ids)) {
+		free(key);
+		return NULL;
+	}
+
+	hashmap_add(&ids->patches, key);
+	return key;
 }
diff --git a/patch-ids.h b/patch-ids.h
index eeb56b3..9569ee0 100644
--- a/patch-ids.h
+++ b/patch-ids.h
@@ -2,15 +2,14 @@
 #define PATCH_IDS_H
 
 struct patch_id {
-	unsigned char patch_id[20];
+	struct hashmap_entry ent;
+	unsigned char patch_id[GIT_SHA1_RAWSZ];
 	char seen;
 };
 
 struct patch_ids {
+	struct hashmap patches;
 	struct diff_options diffopts;
-	int nr, alloc;
-	struct patch_id **table;
-	struct patch_id_bucket *patches;
 };
 
 int commit_patch_id(struct commit *commit, struct diff_options *options,

-- 
2.9.2.gvfs.2.42.gb7633a3