[PATCH 13/16] mktree: add directory-file conflict hashmap

From: Victoria Dye via GitGitGadget <gitgitgadget@gmail.com>
Date: Jun 11, 2024, 18:24 UTC
Message-ID: <68acdd3c5ee266fd0c1d3ae45f69af4ef9012e07.1718130288.git.gitgitgadget@gmail.com>
In-Reply-To: <pull.1746.git.1718130288.gitgitgadget@gmail.com>

From: Victoria Dye <vdye@github.com>

Create a hashmap member of a 'struct tree_entry_array' that contains all of the (de-duplicated) provided tree entries, indexed by the hash of their path with *no* trailing slash. This hashmap will be used in a later commit to avoid adding a file to an existing tree that has the same path as a directory, or vice versa.

Signed-off-by: Victoria Dye <vdye@github.com>
---
 builtin/mktree.c | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/builtin/mktree.c b/builtin/mktree.c
index bee359e9978..09b3c5c6244 100644
--- a/builtin/mktree.c
+++ b/builtin/mktree.c
@@ -16,6 +16,8 @@
 #include "object-store-ll.h"
 
 struct tree_entry {
+	struct hashmap_entry ent;
+
 	/* Internal */
 	size_t order;
 
@@ -33,8 +35,33 @@ static inline size_t df_path_len(size_t pathlen, unsigned int mode)
 struct tree_entry_array {
 	size_t nr, alloc;
 	struct tree_entry **entries;
+
+	struct hashmap df_name_hash;
 };
 
+static int df_name_hash_cmp(const void *cmp_data UNUSED,
+			    const struct hashmap_entry *eptr,
+			    const struct hashmap_entry *entry_or_key,
+			    const void *keydata UNUSED)
+{
+	const struct tree_entry *e1, *e2;
+	size_t e1_len, e2_len;
+
+	e1 = container_of(eptr, const struct tree_entry, ent);
+	e2 = container_of(entry_or_key, const struct tree_entry, ent);
+
+	e1_len = df_path_len(e1->len, e1->mode);
+	e2_len = df_path_len(e2->len, e2->mode);
+
+	return e1_len != e2_len ||
+	       name_compare(e1->name, e1_len, e2->name, e2_len);
+}
+
+static void init_tree_entry_array(struct tree_entry_array *arr)
+{
+	hashmap_init(&arr->df_name_hash, df_name_hash_cmp, NULL, 0);
+}
+
 static void tree_entry_array_push(struct tree_entry_array *arr, struct tree_entry *ent)
 {
 	ALLOC_GROW(arr->entries, arr->nr + 1, arr->alloc);
@@ -43,6 +70,7 @@ static void tree_entry_array_push(struct tree_entry_array *arr, struct tree_entr
 
 static void clear_tree_entry_array(struct tree_entry_array *arr)
 {
+	hashmap_clear(&arr->df_name_hash);
 	for (size_t i = 0; i < arr->nr; i++)
 		FREE_AND_NULL(arr->entries[i]);
 	arr->nr = 0;
@@ -50,6 +78,7 @@ static void clear_tree_entry_array(struct tree_entry_array *arr)
 
 static void release_tree_entry_array(struct tree_entry_array *arr)
 {
+	hashmap_clear(&arr->df_name_hash);
 	FREE_AND_NULL(arr->entries);
 	arr->nr = arr->alloc = 0;
 }
@@ -135,6 +164,14 @@ static void sort_and_dedup_tree_entry_array(struct tree_entry_array *arr)
 	/* Sort again to order the entries for tree insertion */
 	ignore_mode = 0;
 	QSORT_S(arr->entries, arr->nr, ent_compare, &ignore_mode);
+
+	/* Finally, initialize the directory-file conflict hash map */
+	for (size_t i = 0; i < count; i++) {
+		struct tree_entry *curr = arr->entries[i];
+		hashmap_entry_init(&curr->ent,
+				   memhash(curr->name, df_path_len(curr->len, curr->mode)));
+		hashmap_put(&arr->df_name_hash, &curr->ent);
+	}
 }
 
 struct tree_entry_iterator {
@@ -302,6 +339,8 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 
 	ac = parse_options(ac, av, prefix, option, mktree_usage, 0);
 
+	init_tree_entry_array(&arr);
+
 	do {
 		ret = read_index_info(nul_term_line, mktree_line, &mktree_line_data);
 		if (ret < 0)

-- 
gitgitgadget