{"thread":{"id":"46679","subject":"[PATCH 0/3] merge-recursive: replace string_list with hashmap","startedAt":"2017-08-28T20:29:44Z","lastAt":"2017-09-06T03:35:31Z","messageCount":15,"participants":["Kevin Willford","Ben Peart","Jeff King","Stefan Beller","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"327289","messageId":"20170828202829.3056-1-kewillf@microsoft.com","threadId":"46679","inReplyTo":null,"subject":"[PATCH 0/3] merge-recursive: replace string_list with hashmap","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-08-28T20:28:26Z","receivedAt":"2017-08-28T20:29:44Z","isPatch":true,"sender":{"key":"kewillf@microsoft.com","avatar":null},"body":"Code was using two string_lists, one for the directories and\none for the files.  The code never checks the lists independently\nso we should be able to only use one list.  The string_list also\nis a O(log n) for lookup and insertion.  Switching this to use a\nhashmap will give O(1) which will save some time when there are\nmillions of paths that will be checked.\n\nAlso cleaned up a memory leak and method where the return was not\nbeing used.\n\nKevin Willford (3):\n  merge-recursive: fix memory leak\n  merge-recursive: remove return value from get_files_dirs\n  merge-recursive: change current file dir string_lists to hashmap\n\n merge-recursive.c | 68 +++++++++++++++++++++++++++++++++++++++----------------\n merge-recursive.h |  3 +--\n 2 files changed, 49 insertions(+), 22 deletions(-)\n\n-- \n2.14.1.329.g6edf0add19\n\n"},{"id":"327290","messageId":"20170828202829.3056-2-kewillf@microsoft.com","threadId":"46679","inReplyTo":"20170828202829.3056-1-kewillf@microsoft.com","subject":"[PATCH 1/3] merge-recursive: fix memory leak","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-08-28T20:28:27Z","receivedAt":"2017-08-28T20:29:47Z","isPatch":true,"sender":{"key":"kewillf@microsoft.com","avatar":null},"body":"In merge_trees if process_renames or process_entry returns less\nthan zero, the method will just return and not free re_merge,\nre_head, or entries.\n\nThis change cleans up the allocated variables before returning\nto the caller.\n\nSigned-off-by: Kevin Willford <kewillf@microsoft.com>\n---\n merge-recursive.c | 12 +++++++++---\n 1 file changed, 9 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 1494ffdb82..033d7cd406 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -1956,7 +1956,7 @@ int merge_trees(struct merge_options *o,\n \t\tre_merge = get_renames(o, merge, common, head, merge, entries);\n \t\tclean = process_renames(o, re_head, re_merge);\n \t\tif (clean < 0)\n-\t\t\treturn clean;\n+\t\t\tgoto cleanup;\n \t\tfor (i = entries->nr-1; 0 <= i; i--) {\n \t\t\tconst char *path = entries->items[i].string;\n \t\t\tstruct stage_data *e = entries->items[i].util;\n@@ -1964,8 +1964,10 @@ int merge_trees(struct merge_options *o,\n \t\t\t\tint ret = process_entry(o, path, e);\n \t\t\t\tif (!ret)\n \t\t\t\t\tclean = 0;\n-\t\t\t\telse if (ret < 0)\n-\t\t\t\t\treturn ret;\n+\t\t\t\telse if (ret < 0) {\n+\t\t\t\t\tclean = ret;\n+\t\t\t\t\tgoto cleanup;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t\tfor (i = 0; i < entries->nr; i++) {\n@@ -1975,6 +1977,7 @@ int merge_trees(struct merge_options *o,\n \t\t\t\t    entries->items[i].string);\n \t\t}\n \n+cleanup:\n \t\tstring_list_clear(re_merge, 0);\n \t\tstring_list_clear(re_head, 0);\n \t\tstring_list_clear(entries, 1);\n@@ -1982,6 +1985,9 @@ int merge_trees(struct merge_options *o,\n \t\tfree(re_merge);\n \t\tfree(re_head);\n \t\tfree(entries);\n+\n+\t\tif (clean < 0)\n+\t\t\treturn clean;\n \t}\n \telse\n \t\tclean = 1;\n-- \n2.14.1.329.g6edf0add19\n\n"},{"id":"327291","messageId":"20170828202829.3056-3-kewillf@microsoft.com","threadId":"46679","inReplyTo":"20170828202829.3056-1-kewillf@microsoft.com","subject":"[PATCH 2/3] merge-recursive: remove return value from get_files_dirs","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-08-28T20:28:28Z","receivedAt":"2017-08-28T20:29:51Z","isPatch":true,"sender":{"key":"kewillf@microsoft.com","avatar":null},"body":"The return value of the get_files_dirs call is never being used.\nLooking at the history of the file and it was originally only\nbeing used for debug output statements.  Also when\nread_tree_recursive return value is non zero it is changed to\nzero.  This leads me to believe that it doesn't matter if\nread_tree_recursive gets an error.\n\nSince the debug output has been removed and the caller isn't\nchecking the return value there is no reason to keep calulating\nand returning a value.\n\nSigned-off-by: Kevin Willford <kewillf@microsoft.com>\n---\n merge-recursive.c | 8 ++------\n 1 file changed, 2 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 033d7cd406..d47f40ea81 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -328,15 +328,11 @@ static int save_files_dirs(const unsigned char *sha1,\n \treturn (S_ISDIR(mode) ? READ_TREE_RECURSIVE : 0);\n }\n \n-static int get_files_dirs(struct merge_options *o, struct tree *tree)\n+static void get_files_dirs(struct merge_options *o, struct tree *tree)\n {\n-\tint n;\n \tstruct pathspec match_all;\n \tmemset(&match_all, 0, sizeof(match_all));\n-\tif (read_tree_recursive(tree, \"\", 0, 0, &match_all, save_files_dirs, o))\n-\t\treturn 0;\n-\tn = o->current_file_set.nr + o->current_directory_set.nr;\n-\treturn n;\n+\tread_tree_recursive(tree, \"\", 0, 0, &match_all, save_files_dirs, o);\n }\n \n /*\n-- \n2.14.1.329.g6edf0add19\n\n"},{"id":"327292","messageId":"20170828202829.3056-4-kewillf@microsoft.com","threadId":"46679","inReplyTo":"20170828202829.3056-1-kewillf@microsoft.com","subject":"[PATCH 3/3] merge-recursive: change current file dir string_lists to hashmap","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-08-28T20:28:29Z","receivedAt":"2017-08-28T20:29:57Z","isPatch":true,"sender":{"key":"kewillf@microsoft.com","avatar":null},"body":"The code was using two string_lists, one for the directories and\none for the files.  The code never checks the lists independently\nso we should be able to only use one list.  The string_list also\nis a O(log n) for lookup and insertion.  Switching this to use a\nhashmap will give O(1) which will save some time when there are\nmillions of paths that will be checked.\n\nSigned-off-by: Kevin Willford <kewillf@microsoft.com>\n---\n merge-recursive.c | 48 +++++++++++++++++++++++++++++++++++++-----------\n merge-recursive.h |  3 +--\n 2 files changed, 38 insertions(+), 13 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex d47f40ea81..ef4fe5f09f 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -24,6 +24,26 @@\n #include \"dir.h\"\n #include \"submodule.h\"\n \n+struct path_hashmap_entry {\n+\tstruct hashmap_entry;\n+\tchar path[FLEX_ARRAY];\n+};\n+\n+static unsigned int (*pathhash)(const char *path);\n+static int (*pathcmp)(const char *a, const char *b);\n+\n+static int path_hashmap_cmp(const void *cmp_data,\n+\t\t\t    const void *entry,\n+\t\t\t    const void *entry_or_key,\n+\t\t\t    const void *keydata)\n+{\n+\tconst struct path_hashmap_entry *a = entry;\n+\tconst struct path_hashmap_entry *b = entry_or_key;\n+\tconst char *key = keydata;\n+\n+\treturn pathcmp(a->path, key ? key : b->path);\n+}\n+\n static void flush_output(struct merge_options *o)\n {\n \tif (o->buffer_output < 2 && o->obuf.len) {\n@@ -314,15 +334,15 @@ static int save_files_dirs(const unsigned char *sha1,\n \t\tstruct strbuf *base, const char *path,\n \t\tunsigned int mode, int stage, void *context)\n {\n+\tstruct path_hashmap_entry *entry;\n \tint baselen = base->len;\n \tstruct merge_options *o = context;\n \n \tstrbuf_addstr(base, path);\n \n-\tif (S_ISDIR(mode))\n-\t\tstring_list_insert(&o->current_directory_set, base->buf);\n-\telse\n-\t\tstring_list_insert(&o->current_file_set, base->buf);\n+\tFLEX_ALLOC_MEM(entry, path, base->buf, base->len);\n+\thashmap_entry_init(entry, pathhash(entry->path));\n+\thashmap_add(&o->current_file_dir_set, entry);\n \n \tstrbuf_setlen(base, baselen);\n \treturn (S_ISDIR(mode) ? READ_TREE_RECURSIVE : 0);\n@@ -642,6 +662,8 @@ static void add_flattened_path(struct strbuf *out, const char *s)\n \n static char *unique_path(struct merge_options *o, const char *path, const char *branch)\n {\n+\tstruct path_hashmap_entry dummy;\n+\tstruct path_hashmap_entry *entry;\n \tstruct strbuf newpath = STRBUF_INIT;\n \tint suffix = 0;\n \tsize_t base_len;\n@@ -650,14 +672,17 @@ static char *unique_path(struct merge_options *o, const char *path, const char *\n \tadd_flattened_path(&newpath, branch);\n \n \tbase_len = newpath.len;\n-\twhile (string_list_has_string(&o->current_file_set, newpath.buf) ||\n-\t       string_list_has_string(&o->current_directory_set, newpath.buf) ||\n+\thashmap_entry_init(&dummy, pathhash(newpath.buf));\n+\twhile (hashmap_get(&o->current_file_dir_set, &dummy, newpath.buf) ||\n \t       (!o->call_depth && file_exists(newpath.buf))) {\n \t\tstrbuf_setlen(&newpath, base_len);\n \t\tstrbuf_addf(&newpath, \"_%d\", suffix++);\n+\t\thashmap_entry_init(&dummy, pathhash(newpath.buf));\n \t}\n \n-\tstring_list_insert(&o->current_file_set, newpath.buf);\n+\tFLEX_ALLOC_MEM(entry, path, newpath.buf, newpath.len);\n+\thashmap_entry_init(entry, pathhash(entry->path));\n+\thashmap_add(&o->current_file_dir_set, entry);\n \treturn strbuf_detach(&newpath, NULL);\n }\n \n@@ -1941,8 +1966,7 @@ int merge_trees(struct merge_options *o,\n \tif (unmerged_cache()) {\n \t\tstruct string_list *entries, *re_head, *re_merge;\n \t\tint i;\n-\t\tstring_list_clear(&o->current_file_set, 1);\n-\t\tstring_list_clear(&o->current_directory_set, 1);\n+\t\thashmap_init(&o->current_file_dir_set, path_hashmap_cmp, NULL, 512);\n \t\tget_files_dirs(o, head);\n \t\tget_files_dirs(o, merge);\n \n@@ -1978,6 +2002,8 @@ int merge_trees(struct merge_options *o,\n \t\tstring_list_clear(re_head, 0);\n \t\tstring_list_clear(entries, 1);\n \n+\t\thashmap_free(&o->current_file_dir_set, 1);\n+\n \t\tfree(re_merge);\n \t\tfree(re_head);\n \t\tfree(entries);\n@@ -2179,8 +2205,8 @@ void init_merge_options(struct merge_options *o)\n \tif (o->verbosity >= 5)\n \t\to->buffer_output = 0;\n \tstrbuf_init(&o->obuf, 0);\n-\tstring_list_init(&o->current_file_set, 1);\n-\tstring_list_init(&o->current_directory_set, 1);\n+\tpathhash = ignore_case ? strihash : strhash;\n+\tpathcmp = ignore_case ? strcasecmp : strcmp;\n \tstring_list_init(&o->df_conflict_file_set, 1);\n }\n \ndiff --git a/merge-recursive.h b/merge-recursive.h\nindex 735343b413..80d69d1401 100644\n--- a/merge-recursive.h\n+++ b/merge-recursive.h\n@@ -25,8 +25,7 @@ struct merge_options {\n \tint show_rename_progress;\n \tint call_depth;\n \tstruct strbuf obuf;\n-\tstruct string_list current_file_set;\n-\tstruct string_list current_directory_set;\n+\tstruct hashmap current_file_dir_set;\n \tstruct string_list df_conflict_file_set;\n };\n \n-- \n2.14.1.329.g6edf0add19\n\n"},{"id":"327297","messageId":"770a93c1-9115-3104-ebae-3cdc69d658de@gmail.com","threadId":"46679","inReplyTo":"20170828202829.3056-2-kewillf@microsoft.com","subject":"Re: [PATCH 1/3] merge-recursive: fix memory leak","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-08-28T22:42:58Z","receivedAt":"2017-08-28T22:43:06Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 8/28/2017 4:28 PM, Kevin Willford wrote:\n> In merge_trees if process_renames or process_entry returns less\n> than zero, the method will just return and not free re_merge,\n> re_head, or entries.\n> \n> This change cleans up the allocated variables before returning\n> to the caller.\n> \n> Signed-off-by: Kevin Willford <kewillf@microsoft.com>\n\nNice catch on the leaks.  Looks good to me.\n\n> ---\n>   merge-recursive.c | 12 +++++++++---\n>   1 file changed, 9 insertions(+), 3 deletions(-)\n> \n> diff --git a/merge-recursive.c b/merge-recursive.c\n> index 1494ffdb82..033d7cd406 100644\n> --- a/merge-recursive.c\n> +++ b/merge-recursive.c\n> @@ -1956,7 +1956,7 @@ int merge_trees(struct merge_options *o,\n>   \t\tre_merge = get_renames(o, merge, common, head, merge, entries);\n>   \t\tclean = process_renames(o, re_head, re_merge);\n>   \t\tif (clean < 0)\n> -\t\t\treturn clean;\n> +\t\t\tgoto cleanup;\n>   \t\tfor (i = entries->nr-1; 0 <= i; i--) {\n>   \t\t\tconst char *path = entries->items[i].string;\n>   \t\t\tstruct stage_data *e = entries->items[i].util;\n> @@ -1964,8 +1964,10 @@ int merge_trees(struct merge_options *o,\n>   \t\t\t\tint ret = process_entry(o, path, e);\n>   \t\t\t\tif (!ret)\n>   \t\t\t\t\tclean = 0;\n> -\t\t\t\telse if (ret < 0)\n> -\t\t\t\t\treturn ret;\n> +\t\t\t\telse if (ret < 0) {\n> +\t\t\t\t\tclean = ret;\n> +\t\t\t\t\tgoto cleanup;\n> +\t\t\t\t}\n>   \t\t\t}\n>   \t\t}\n>   \t\tfor (i = 0; i < entries->nr; i++) {\n> @@ -1975,6 +1977,7 @@ int merge_trees(struct merge_options *o,\n>   \t\t\t\t    entries->items[i].string);\n>   \t\t}\n>   \n> +cleanup:\n>   \t\tstring_list_clear(re_merge, 0);\n>   \t\tstring_list_clear(re_head, 0);\n>   \t\tstring_list_clear(entries, 1);\n> @@ -1982,6 +1985,9 @@ int merge_trees(struct merge_options *o,\n>   \t\tfree(re_merge);\n>   \t\tfree(re_head);\n>   \t\tfree(entries);\n> +\n> +\t\tif (clean < 0)\n> +\t\t\treturn clean;\n>   \t}\n>   \telse\n>   \t\tclean = 1;\n> \n"},{"id":"327298","messageId":"8f1a7139-6f5b-eb47-ecb6-ded1d550b06a@gmail.com","threadId":"46679","inReplyTo":"20170828202829.3056-3-kewillf@microsoft.com","subject":"Re: [PATCH 2/3] merge-recursive: remove return value from get_files_dirs","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-08-28T22:45:29Z","receivedAt":"2017-08-28T22:45:34Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 8/28/2017 4:28 PM, Kevin Willford wrote:\n> The return value of the get_files_dirs call is never being used.\n> Looking at the history of the file and it was originally only\n> being used for debug output statements.  Also when\n> read_tree_recursive return value is non zero it is changed to\n> zero.  This leads me to believe that it doesn't matter if\n> read_tree_recursive gets an error.\n> \n> Since the debug output has been removed and the caller isn't\n> checking the return value there is no reason to keep calulating\n> and returning a value.\n> \n\nDid a quick search and you're right, nothing is using the return value. \nNo reason to spend time calculating it.  Looks good.\n\n> Signed-off-by: Kevin Willford <kewillf@microsoft.com>\n> ---\n>   merge-recursive.c | 8 ++------\n>   1 file changed, 2 insertions(+), 6 deletions(-)\n> \n> diff --git a/merge-recursive.c b/merge-recursive.c\n> index 033d7cd406..d47f40ea81 100644\n> --- a/merge-recursive.c\n> +++ b/merge-recursive.c\n> @@ -328,15 +328,11 @@ static int save_files_dirs(const unsigned char *sha1,\n>   \treturn (S_ISDIR(mode) ? READ_TREE_RECURSIVE : 0);\n>   }\n>   \n> -static int get_files_dirs(struct merge_options *o, struct tree *tree)\n> +static void get_files_dirs(struct merge_options *o, struct tree *tree)\n>   {\n> -\tint n;\n>   \tstruct pathspec match_all;\n>   \tmemset(&match_all, 0, sizeof(match_all));\n> -\tif (read_tree_recursive(tree, \"\", 0, 0, &match_all, save_files_dirs, o))\n> -\t\treturn 0;\n> -\tn = o->current_file_set.nr + o->current_directory_set.nr;\n> -\treturn n;\n> +\tread_tree_recursive(tree, \"\", 0, 0, &match_all, save_files_dirs, o);\n>   }\n>   \n>   /*\n> \n"},{"id":"327299","messageId":"a9140320-05df-d45b-19bc-e67a7a5b6eb9@gmail.com","threadId":"46679","inReplyTo":"20170828202829.3056-4-kewillf@microsoft.com","subject":"Re: [PATCH 3/3] merge-recursive: change current file dir string_lists to hashmap","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-08-28T23:06:08Z","receivedAt":"2017-08-28T23:06:14Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 8/28/2017 4:28 PM, Kevin Willford wrote:\n> The code was using two string_lists, one for the directories and\n> one for the files.  The code never checks the lists independently\n> so we should be able to only use one list.  The string_list also\n> is a O(log n) for lookup and insertion.  Switching this to use a\n> hashmap will give O(1) which will save some time when there are\n> millions of paths that will be checked.\n> \n\nGood observation that the two string lists were never used \nindependently.  Perhaps the intent was to help the O(log n) issue by \nsplitting them up?  A single hashmap is much faster.  Looks good.\n\n\n> Signed-off-by: Kevin Willford <kewillf@microsoft.com>\n> ---\n>   merge-recursive.c | 48 +++++++++++++++++++++++++++++++++++++-----------\n>   merge-recursive.h |  3 +--\n>   2 files changed, 38 insertions(+), 13 deletions(-)\n> \n> diff --git a/merge-recursive.c b/merge-recursive.c\n> index d47f40ea81..ef4fe5f09f 100644\n> --- a/merge-recursive.c\n> +++ b/merge-recursive.c\n> @@ -24,6 +24,26 @@\n>   #include \"dir.h\"\n>   #include \"submodule.h\"\n>   \n> +struct path_hashmap_entry {\n> +\tstruct hashmap_entry;\n> +\tchar path[FLEX_ARRAY];\n> +};\n> +\n> +static unsigned int (*pathhash)(const char *path);\n> +static int (*pathcmp)(const char *a, const char *b);\n> +\n> +static int path_hashmap_cmp(const void *cmp_data,\n> +\t\t\t    const void *entry,\n> +\t\t\t    const void *entry_or_key,\n> +\t\t\t    const void *keydata)\n> +{\n> +\tconst struct path_hashmap_entry *a = entry;\n> +\tconst struct path_hashmap_entry *b = entry_or_key;\n> +\tconst char *key = keydata;\n> +\n> +\treturn pathcmp(a->path, key ? key : b->path);\n> +}\n> +\n>   static void flush_output(struct merge_options *o)\n>   {\n>   \tif (o->buffer_output < 2 && o->obuf.len) {\n> @@ -314,15 +334,15 @@ static int save_files_dirs(const unsigned char *sha1,\n>   \t\tstruct strbuf *base, const char *path,\n>   \t\tunsigned int mode, int stage, void *context)\n>   {\n> +\tstruct path_hashmap_entry *entry;\n>   \tint baselen = base->len;\n>   \tstruct merge_options *o = context;\n>   \n>   \tstrbuf_addstr(base, path);\n>   \n> -\tif (S_ISDIR(mode))\n> -\t\tstring_list_insert(&o->current_directory_set, base->buf);\n> -\telse\n> -\t\tstring_list_insert(&o->current_file_set, base->buf);\n> +\tFLEX_ALLOC_MEM(entry, path, base->buf, base->len);\n> +\thashmap_entry_init(entry, pathhash(entry->path));\n> +\thashmap_add(&o->current_file_dir_set, entry);\n>   \n>   \tstrbuf_setlen(base, baselen);\n>   \treturn (S_ISDIR(mode) ? READ_TREE_RECURSIVE : 0);\n> @@ -642,6 +662,8 @@ static void add_flattened_path(struct strbuf *out, const char *s)\n>   \n>   static char *unique_path(struct merge_options *o, const char *path, const char *branch)\n>   {\n> +\tstruct path_hashmap_entry dummy;\n> +\tstruct path_hashmap_entry *entry;\n>   \tstruct strbuf newpath = STRBUF_INIT;\n>   \tint suffix = 0;\n>   \tsize_t base_len;\n> @@ -650,14 +672,17 @@ static char *unique_path(struct merge_options *o, const char *path, const char *\n>   \tadd_flattened_path(&newpath, branch);\n>   \n>   \tbase_len = newpath.len;\n> -\twhile (string_list_has_string(&o->current_file_set, newpath.buf) ||\n> -\t       string_list_has_string(&o->current_directory_set, newpath.buf) ||\n> +\thashmap_entry_init(&dummy, pathhash(newpath.buf));\n> +\twhile (hashmap_get(&o->current_file_dir_set, &dummy, newpath.buf) ||\n>   \t       (!o->call_depth && file_exists(newpath.buf))) {\n>   \t\tstrbuf_setlen(&newpath, base_len);\n>   \t\tstrbuf_addf(&newpath, \"_%d\", suffix++);\n> +\t\thashmap_entry_init(&dummy, pathhash(newpath.buf));\n>   \t}\n>   \n> -\tstring_list_insert(&o->current_file_set, newpath.buf);\n> +\tFLEX_ALLOC_MEM(entry, path, newpath.buf, newpath.len);\n> +\thashmap_entry_init(entry, pathhash(entry->path));\n> +\thashmap_add(&o->current_file_dir_set, entry);\n>   \treturn strbuf_detach(&newpath, NULL);\n>   }\n>   \n> @@ -1941,8 +1966,7 @@ int merge_trees(struct merge_options *o,\n>   \tif (unmerged_cache()) {\n>   \t\tstruct string_list *entries, *re_head, *re_merge;\n>   \t\tint i;\n> -\t\tstring_list_clear(&o->current_file_set, 1);\n> -\t\tstring_list_clear(&o->current_directory_set, 1);\n> +\t\thashmap_init(&o->current_file_dir_set, path_hashmap_cmp, NULL, 512);\n>   \t\tget_files_dirs(o, head);\n>   \t\tget_files_dirs(o, merge);\n>   \n> @@ -1978,6 +2002,8 @@ int merge_trees(struct merge_options *o,\n>   \t\tstring_list_clear(re_head, 0);\n>   \t\tstring_list_clear(entries, 1);\n>   \n> +\t\thashmap_free(&o->current_file_dir_set, 1);\n> +\n>   \t\tfree(re_merge);\n>   \t\tfree(re_head);\n>   \t\tfree(entries);\n> @@ -2179,8 +2205,8 @@ void init_merge_options(struct merge_options *o)\n>   \tif (o->verbosity >= 5)\n>   \t\to->buffer_output = 0;\n>   \tstrbuf_init(&o->obuf, 0);\n> -\tstring_list_init(&o->current_file_set, 1);\n> -\tstring_list_init(&o->current_directory_set, 1);\n> +\tpathhash = ignore_case ? strihash : strhash;\n> +\tpathcmp = ignore_case ? strcasecmp : strcmp;\n>   \tstring_list_init(&o->df_conflict_file_set, 1);\n>   }\n>   \n> diff --git a/merge-recursive.h b/merge-recursive.h\n> index 735343b413..80d69d1401 100644\n> --- a/merge-recursive.h\n> +++ b/merge-recursive.h\n> @@ -25,8 +25,7 @@ struct merge_options {\n>   \tint show_rename_progress;\n>   \tint call_depth;\n>   \tstruct strbuf obuf;\n> -\tstruct string_list current_file_set;\n> -\tstruct string_list current_directory_set;\n> +\tstruct hashmap current_file_dir_set;\n>   \tstruct string_list df_conflict_file_set;\n>   };\n>   \n> \n"},{"id":"327301","messageId":"20170829081203.uwt6yfve5uatbhch@sigill.intra.peff.net","threadId":"46679","inReplyTo":"20170828202829.3056-2-kewillf@microsoft.com","subject":"Re: [PATCH 1/3] merge-recursive: fix memory leak","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-29T08:12:03Z","receivedAt":"2017-08-29T08:12:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 28, 2017 at 02:28:27PM -0600, Kevin Willford wrote:\n\n> In merge_trees if process_renames or process_entry returns less\n> than zero, the method will just return and not free re_merge,\n> re_head, or entries.\n> \n> This change cleans up the allocated variables before returning\n> to the caller.\n\nGood catch. I suspect this function could stand to be refactored a bit.\nFor instance, pulling those inner bits of the conditional into a helper\nwould let us do:\n\n  re_merge = get_renames(...);\n  ... other setup ...\n\n  clean = our_new_helper(re_merge, ...);\n\n  string_clear(re_merge);\n  ... other cleanup ...\n\n  if (clean < 0)\n\treturn clean;\n\nwithout having to resort to a goto. But certainly I don't mind this much\nmore minimal change, which fixes the actual functionality problem.\n\n-Peff\n"},{"id":"327302","messageId":"20170829081752.nq5r776rjyf2amzh@sigill.intra.peff.net","threadId":"46679","inReplyTo":"20170828202829.3056-3-kewillf@microsoft.com","subject":"Re: [PATCH 2/3] merge-recursive: remove return value from get_files_dirs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-29T08:17:52Z","receivedAt":"2017-08-29T08:18:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 28, 2017 at 02:28:28PM -0600, Kevin Willford wrote:\n\n> The return value of the get_files_dirs call is never being used.\n> Looking at the history of the file and it was originally only\n> being used for debug output statements.  Also when\n> read_tree_recursive return value is non zero it is changed to\n> zero.  This leads me to believe that it doesn't matter if\n> read_tree_recursive gets an error.\n\nOr that the function is buggy. :)\n\nI'm tempted to say that we should probably die() when\nread_tree_recursive fails. This should only happen if we fail to parse\nthe tree, or if our callback (save_files_dirs here) returns failure, and\nthe latter looks like it never happens.\n\n> Since the debug output has been removed and the caller isn't\n> checking the return value there is no reason to keep calulating\n> and returning a value.\n\nAgreed, and I'm happy to see dead code go.\n\nMinor nit: s/calulating/calculating/ in your commit message.\n\n-Peff\n"},{"id":"327303","messageId":"20170829081919.gvwdid6fcn7avbih@sigill.intra.peff.net","threadId":"46679","inReplyTo":"8f1a7139-6f5b-eb47-ecb6-ded1d550b06a@gmail.com","subject":"Re: [PATCH 2/3] merge-recursive: remove return value from get_files_dirs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-29T08:19:19Z","receivedAt":"2017-08-29T08:19:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 28, 2017 at 06:45:29PM -0400, Ben Peart wrote:\n\n> > Since the debug output has been removed and the caller isn't\n> > checking the return value there is no reason to keep calulating\n> > and returning a value.\n> > \n> \n> Did a quick search and you're right, nothing is using the return value. No\n> reason to spend time calculating it.  Looks good.\n\nThis is actually one we can reasonably trust the compiler to check for\nus. Though of course it doesn't hurt to look at the callers and make\nsure that it's sane that they do not care about this return value (I\ndon't know merge-recursive.c very well, but the current return value\ndoes seem kind of useless).\n\n-Peff\n"},{"id":"327317","messageId":"20170829084155.irpfdixu4kcygzrv@sigill.intra.peff.net","threadId":"46679","inReplyTo":"20170828202829.3056-4-kewillf@microsoft.com","subject":"Re: [PATCH 3/3] merge-recursive: change current file dir string_lists to hashmap","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-29T08:41:55Z","receivedAt":"2017-08-29T08:42:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 28, 2017 at 02:28:29PM -0600, Kevin Willford wrote:\n\n> The code was using two string_lists, one for the directories and\n> one for the files.  The code never checks the lists independently\n> so we should be able to only use one list.  The string_list also\n> is a O(log n) for lookup and insertion.  Switching this to use a\n> hashmap will give O(1) which will save some time when there are\n> millions of paths that will be checked.\n\nMakes sense. I think when this code was written we didn't have the\ngeneralized hashmap.c, which is why it relies on string lists.\n\n> diff --git a/merge-recursive.c b/merge-recursive.c\n> index d47f40ea81..ef4fe5f09f 100644\n> --- a/merge-recursive.c\n> +++ b/merge-recursive.c\n> @@ -24,6 +24,26 @@\n>  #include \"dir.h\"\n>  #include \"submodule.h\"\n>  \n> +struct path_hashmap_entry {\n> +\tstruct hashmap_entry;\n> +\tchar path[FLEX_ARRAY];\n> +};\n\nThis seems like a good use of FLEX_ARRAY.\n\n> +static unsigned int (*pathhash)(const char *path);\n> +static int (*pathcmp)(const char *a, const char *b);\n\nThese global function pointers are sufficiently out of the ordinary that\nit might be worth adding a comment about how they're intended to be\nset and used.\n\nI also suspect they could be stuffed into the merge_options struct along\nwith the hashmap itself, and then passed via the cmp_data pointer (which\nis relatively new-ish; I won't be surprised if you wrote this patch\nbefore that existed and forward-ported it).\n\n> +static int path_hashmap_cmp(const void *cmp_data,\n> +\t\t\t    const void *entry,\n> +\t\t\t    const void *entry_or_key,\n> +\t\t\t    const void *keydata)\n> +{\n> +\tconst struct path_hashmap_entry *a = entry;\n> +\tconst struct path_hashmap_entry *b = entry_or_key;\n> +\tconst char *key = keydata;\n> +\n> +\treturn pathcmp(a->path, key ? key : b->path);\n> +}\n\nThe hashmap interface makes its cmp functions a bit tricky to write, but\nthis all looks correct to me.\n\n> @@ -642,6 +662,8 @@ static void add_flattened_path(struct strbuf *out, const char *s)\n>  \n>  static char *unique_path(struct merge_options *o, const char *path, const char *branch)\n>  {\n> +\tstruct path_hashmap_entry dummy;\n> +\tstruct path_hashmap_entry *entry;\n>  \tstruct strbuf newpath = STRBUF_INIT;\n>  \tint suffix = 0;\n>  \tsize_t base_len;\n> @@ -650,14 +672,17 @@ static char *unique_path(struct merge_options *o, const char *path, const char *\n>  \tadd_flattened_path(&newpath, branch);\n>  \n>  \tbase_len = newpath.len;\n> -\twhile (string_list_has_string(&o->current_file_set, newpath.buf) ||\n> -\t       string_list_has_string(&o->current_directory_set, newpath.buf) ||\n> +\thashmap_entry_init(&dummy, pathhash(newpath.buf));\n> +\twhile (hashmap_get(&o->current_file_dir_set, &dummy, newpath.buf) ||\n>  \t       (!o->call_depth && file_exists(newpath.buf))) {\n>  \t\tstrbuf_setlen(&newpath, base_len);\n>  \t\tstrbuf_addf(&newpath, \"_%d\", suffix++);\n> +\t\thashmap_entry_init(&dummy, pathhash(newpath.buf));\n>  \t}\n\nI think you can use hashmap_get_from_hash() here to avoid dealing with\n\"dummy\" yourself.\n\n> @@ -1941,8 +1966,7 @@ int merge_trees(struct merge_options *o,\n>  \tif (unmerged_cache()) {\n>  \t\tstruct string_list *entries, *re_head, *re_merge;\n>  \t\tint i;\n> -\t\tstring_list_clear(&o->current_file_set, 1);\n> -\t\tstring_list_clear(&o->current_directory_set, 1);\n> +\t\thashmap_init(&o->current_file_dir_set, path_hashmap_cmp, NULL, 512);\n\nThis hunk seems funny. string_list_clear() assumes the input is an\nalready-initialized string list, and we drop all of its entries. But\nhashmap_init assumes we have an _uninitialized_ chunk of memory, and\nthrows away whatever was there.\n\nDo we ever hit this code path when there's actually something in the\nhashmap?\n\nI'd think we would want to hashmap_init() at the same place we used to\nstring_list_init(). I.e., in init_merge_options.\n\n> @@ -1978,6 +2002,8 @@ int merge_trees(struct merge_options *o,\n>  \t\tstring_list_clear(re_head, 0);\n>  \t\tstring_list_clear(entries, 1);\n>  \n> +\t\thashmap_free(&o->current_file_dir_set, 1);\n\nAh, I think this answers my question above. We only care about the\ncontents during this one bit of code, so we do an init/free pair. And\nsince there's no \"clear\" function for a hashmap that drops the entries\nwithout resetting things like the comparison function, we _have_ to\ncall hashmap_init in the earlier hunk.\n\nThat does make me wonder if it would be sane to just declare the hashmap\nlocal to this block, which would make its lifetime much more clear. I\nguess having it in merge_options is convenient for passing it around,\nthough.\n\n> @@ -2179,8 +2205,8 @@ void init_merge_options(struct merge_options *o)\n> [...]\n\nThe rest of the patch looks like a straight-forward conversion. With the\nunderstanding I have above, I think everything here is correct, but\nthere are a few minor bits it might be worth addressing to make the code\nmore clear.\n\n-Peff\n"},{"id":"327323","messageId":"DM2PR21MB0041575B6D9EE53A07C7D3EDB79F0@DM2PR21MB0041.namprd21.prod.outlook.com","threadId":"46679","inReplyTo":"20170829081752.nq5r776rjyf2amzh@sigill.intra.peff.net","subject":"RE: [PATCH 2/3] merge-recursive: remove return value from get_files_dirs","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-08-29T15:58:00Z","receivedAt":"2017-08-29T15:58:07Z","isPatch":true,"sender":{"key":"kewillf@microsoft.com","avatar":null},"body":"> \n> On Mon, Aug 28, 2017 at 02:28:28PM -0600, Kevin Willford wrote:\n> \n> > The return value of the get_files_dirs call is never being used.\n> > Looking at the history of the file and it was originally only\n> > being used for debug output statements.  Also when\n> > read_tree_recursive return value is non zero it is changed to\n> > zero.  This leads me to believe that it doesn't matter if\n> > read_tree_recursive gets an error.\n> \n> Or that the function is buggy. :)\n\nThat was one of my questions as well.  Should read_tree_recursive\nbe propagating a -1 and merge_trees be checking for that and bail\nwhen the call to get_files_dirs return is < 0?  I made a commit with\nthis change and ran the tests and they all still passed so either this\nreturn really doesn't matter or there are not sufficient tests covering\nit.\n\nI went with this change because it was not changing any of the\ncurrent functionality and if we find a case where it matters that\nread_tree_recursive fails due to bad tree or something else we\ncan address it then.\n\n> \n> I'm tempted to say that we should probably die() when\n> read_tree_recursive fails. This should only happen if we fail to parse\n> the tree, or if our callback (save_files_dirs here) returns failure, and\n> the latter looks like it never happens.\n> \n> > Since the debug output has been removed and the caller isn't\n> > checking the return value there is no reason to keep calulating\n> > and returning a value.\n> \n> Agreed, and I'm happy to see dead code go.\n> \n> Minor nit: s/calulating/calculating/ in your commit message.\n\nWhen will that spell checker for git messages be ready? ;)\n\n> \n> -Peff\n"},{"id":"327324","messageId":"20170829165038.xk6yluuqnzbujodq@sigill.intra.peff.net","threadId":"46679","inReplyTo":"DM2PR21MB0041575B6D9EE53A07C7D3EDB79F0@DM2PR21MB0041.namprd21.prod.outlook.com","subject":"Re: [PATCH 2/3] merge-recursive: remove return value from get_files_dirs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-29T16:50:38Z","receivedAt":"2017-08-29T16:50:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 29, 2017 at 03:58:00PM +0000, Kevin Willford wrote:\n\n> > > The return value of the get_files_dirs call is never being used.\n> > > Looking at the history of the file and it was originally only\n> > > being used for debug output statements.  Also when\n> > > read_tree_recursive return value is non zero it is changed to\n> > > zero.  This leads me to believe that it doesn't matter if\n> > > read_tree_recursive gets an error.\n> > \n> > Or that the function is buggy. :)\n> \n> That was one of my questions as well.  Should read_tree_recursive\n> be propagating a -1 and merge_trees be checking for that and bail\n> when the call to get_files_dirs return is < 0?  I made a commit with\n> this change and ran the tests and they all still passed so either this\n> return really doesn't matter or there are not sufficient tests covering\n> it.\n\nRight, in a normal flow I'd say that it should propagate the -1, etc.\nBut since the only possible error is parse_tree() failing, which happens\nin a corrupt repository, I think it would be OK to just die(). That\nsaves having to deal with error propagation. It's not very graceful,\nperhaps, but the important thing is that we don't quietly ignore the\nerror.\n\n> I went with this change because it was not changing any of the\n> current functionality and if we find a case where it matters that\n> read_tree_recursive fails due to bad tree or something else we\n> can address it then.\n\nI think it's worth doing while we're thinking about it now, but it\ncertainly can be a separate patch.\n\n-Peff\n"},{"id":"327493","messageId":"CAGZ79kacO12xkjt3nBEyyY9VBkdDu+uJ2AnzzEkMnovcO5bigw@mail.gmail.com","threadId":"46679","inReplyTo":"DM2PR21MB0041575B6D9EE53A07C7D3EDB79F0@DM2PR21MB0041.namprd21.prod.outlook.com","subject":"Re: [PATCH 2/3] merge-recursive: remove return value from get_files_dirs","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-08-31T18:12:01Z","receivedAt":"2017-08-31T18:12:07Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Aug 29, 2017 at 8:58 AM, Kevin Willford <kewillf@microsoft.com> wrote:\n>>\n>> On Mon, Aug 28, 2017 at 02:28:28PM -0600, Kevin Willford wrote:\n>>\n>> > The return value of the get_files_dirs call is never being used.\n>> > Looking at the history of the file and it was originally only\n>> > being used for debug output statements.  Also when\n>> > read_tree_recursive return value is non zero it is changed to\n>> > zero.  This leads me to believe that it doesn't matter if\n>> > read_tree_recursive gets an error.\n>>\n>> Or that the function is buggy. :)\n>\n> That was one of my questions as well.  Should read_tree_recursive\n> be propagating a -1 and merge_trees be checking for that and bail\n> when the call to get_files_dirs return is < 0?  I made a commit with\n> this change and ran the tests and they all still passed so either this\n> return really doesn't matter or there are not sufficient tests covering\n> it.\n>\n> I went with this change because it was not changing any of the\n> current functionality and if we find a case where it matters that\n> read_tree_recursive fails due to bad tree or something else we\n> can address it then.\n>\n>>\n>> I'm tempted to say that we should probably die() when\n>> read_tree_recursive fails. This should only happen if we fail to parse\n>> the tree, or if our callback (save_files_dirs here) returns failure, and\n>> the latter looks like it never happens.\n>>\n>> > Since the debug output has been removed and the caller isn't\n>> > checking the return value there is no reason to keep calulating\n>> > and returning a value.\n>>\n>> Agreed, and I'm happy to see dead code go.\n>>\n>> Minor nit: s/calulating/calculating/ in your commit message.\n>\n> When will that spell checker for git messages be ready? ;)\n\nDifferent workflows need different setups apparently.\n(me, as a heavy user of git-gui, likes the builtin spell checker,\nthough I need to find a way to train it to accept git lingo, such\nas \"submodule\", or \"gitlink\")\n\nMaybe:\nhttps://tarasalenin.wordpress.com/2010/09/11/configure-git-gui-spell-checker-on-windows/\n\nIf you do not use git-gui... you are at the merci of your $EDITOR\n($GIT_EDITOR, or core.editor) to have spell checking.\n"},{"id":"327630","messageId":"xmqq4lsg8poj.fsf@gitster.mtv.corp.google.com","threadId":"46679","inReplyTo":"20170828202829.3056-4-kewillf@microsoft.com","subject":"Re: [PATCH 3/3] merge-recursive: change current file dir string_lists to hashmap","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-09-06T03:35:24Z","receivedAt":"2017-09-06T03:35:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I needed this squashed into before I could even compile the\nresulting code.  Perhaps my compiler is stale?\n\n\n\nmerge-recursive.c:28:22: error: declaration does not declare anything [-Werror]\n  struct hashmap_entry;\n                      ^\nmerge-recursive.c:29:7: error: flexible array member in otherwise empty struct\n  char path[FLEX_ARRAY];\n       ^\n---\n merge-recursive.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex ef4fe5f09f..1cd35db3f0 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -25,7 +25,7 @@\n #include \"submodule.h\"\n \n struct path_hashmap_entry {\n-\tstruct hashmap_entry;\n+\tstruct hashmap_entry e;\n \tchar path[FLEX_ARRAY];\n };\n \n-- \n2.14.1-546-g97ae4c876d\n\n"}]}