{"thread":{"id":"46723","subject":"[PATCH v3 0/3] merge-recursive: replace string_list with hashmap","startedAt":"2017-09-07T16:26:54Z","lastAt":"2017-09-07T16:27:10Z","messageCount":4,"participants":["Kevin Willford"],"isPatch":true,"patchVersion":3,"patchTotal":3},"messages":[{"id":"327715","messageId":"20170907162556.61384-1-kewillf@microsoft.com","threadId":"46723","inReplyTo":null,"subject":"[PATCH v3 0/3] merge-recursive: replace string_list with hashmap","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-09-07T16:25:53Z","receivedAt":"2017-09-07T16:26:54Z","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\nChanges since last version:\n1. Removed the function pointers and just check the ignore_case in the\ncompare and hash methods.\n2. Added a comment about the hashmap and why it is getting initialized\nand freed but not a local.\n3. Use hashmap_get_from_hash and remove the dummy entry\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 | 76 ++++++++++++++++++++++++++++++++++++++++---------------\n merge-recursive.h |  3 +--\n 2 files changed, 57 insertions(+), 22 deletions(-)\n\n-- \n2.14.1.329.gcdd497e120.dirty\n\n"},{"id":"327716","messageId":"20170907162556.61384-2-kewillf@microsoft.com","threadId":"46723","inReplyTo":"20170907162556.61384-1-kewillf@microsoft.com","subject":"[PATCH v3 1/3] merge-recursive: fix memory leak","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-09-07T16:25:54Z","receivedAt":"2017-09-07T16:26:59Z","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.gcdd497e120.dirty\n\n"},{"id":"327717","messageId":"20170907162556.61384-3-kewillf@microsoft.com","threadId":"46723","inReplyTo":"20170907162556.61384-1-kewillf@microsoft.com","subject":"[PATCH v3 2/3] merge-recursive: remove return value from get_files_dirs","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-09-07T16:25:55Z","receivedAt":"2017-09-07T16:27:04Z","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 calculating\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.gcdd497e120.dirty\n\n"},{"id":"327718","messageId":"20170907162556.61384-4-kewillf@microsoft.com","threadId":"46723","inReplyTo":"20170907162556.61384-1-kewillf@microsoft.com","subject":"[PATCH v3 3/3] merge-recursive: change current file dir string_lists to hashmap","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-09-07T16:25:56Z","receivedAt":"2017-09-07T16:27:10Z","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 | 56 ++++++++++++++++++++++++++++++++++++++++++++-----------\n merge-recursive.h |  3 +--\n 2 files changed, 46 insertions(+), 13 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex d47f40ea81..35af3761ba 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -24,6 +24,31 @@\n #include \"dir.h\"\n #include \"submodule.h\"\n \n+struct path_hashmap_entry {\n+\tstruct hashmap_entry e;\n+\tchar path[FLEX_ARRAY];\n+};\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+\tif (ignore_case)\n+\t\treturn strcasecmp(a->path, key ? key : b->path);\n+\telse\n+\t\treturn strcmp(a->path, key ? key : b->path);\n+}\n+\n+static unsigned int path_hash(const char *path)\n+{\n+\treturn ignore_case ? strihash(path) : strhash(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 +339,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, path_hash(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 +667,7 @@ 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 *entry;\n \tstruct strbuf newpath = STRBUF_INIT;\n \tint suffix = 0;\n \tsize_t base_len;\n@@ -650,14 +676,16 @@ 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+\twhile (hashmap_get_from_hash(&o->current_file_dir_set,\n+\t\t\t\t     path_hash(newpath.buf), 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}\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, path_hash(entry->path));\n+\thashmap_add(&o->current_file_dir_set, entry);\n \treturn strbuf_detach(&newpath, NULL);\n }\n \n@@ -1941,8 +1969,14 @@ 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\t/*\n+\t\t * Only need the hashmap while processing entries, so\n+\t\t * initialize it here and free it when we are done running\n+\t\t * through the entries. Keeping it in the merge_options as\n+\t\t * opposed to decaring a local hashmap is for convenience\n+\t\t * so that we don't have to pass it to around.\n+\t\t */\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 +2012,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 +2215,6 @@ 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 \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.gcdd497e120.dirty\n\n"}]}