{"thread":{"id":"45107","subject":"[PATCH 1/2] ls-files: pass prefix length explicitly to prune_cache()","startedAt":"2017-02-10T19:49:17Z","lastAt":"2017-02-10T22:52:06Z","messageCount":3,"participants":["René Scharfe","Brandon Williams"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"311299","messageId":"f480bd26-f74e-9088-844d-26cde0843baa@web.de","threadId":"45107","inReplyTo":null,"subject":"[PATCH 1/2] ls-files: pass prefix length explicitly to prune_cache()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-02-10T19:42:28Z","receivedAt":"2017-02-10T19:49:17Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"The function prune_cache() relies on the fact that it is only called on\nmax_prefix and sneakily uses the matching global variable max_prefix_len\ndirectly.  Tighten its interface by passing both the string and its\nlength as parameters.  While at it move the NULL check into the function\nto collect all cache-pruning related logic in one place.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\nNot urgent, of course.\n\n builtin/ls-files.c | 12 +++++++-----\n 1 file changed, 7 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/ls-files.c b/builtin/ls-files.c\nindex 1592290815..18105ec7ea 100644\n--- a/builtin/ls-files.c\n+++ b/builtin/ls-files.c\n@@ -369,11 +369,14 @@ static void show_files(struct dir_struct *dir)\n /*\n  * Prune the index to only contain stuff starting with \"prefix\"\n  */\n-static void prune_cache(const char *prefix)\n+static void prune_cache(const char *prefix, size_t prefixlen)\n {\n-\tint pos = cache_name_pos(prefix, max_prefix_len);\n+\tint pos;\n \tunsigned int first, last;\n \n+\tif (!prefix)\n+\t\treturn;\n+\tpos = cache_name_pos(prefix, prefixlen);\n \tif (pos < 0)\n \t\tpos = -pos-1;\n \tmemmove(active_cache, active_cache + pos,\n@@ -384,7 +387,7 @@ static void prune_cache(const char *prefix)\n \twhile (last > first) {\n \t\tint next = (last + first) >> 1;\n \t\tconst struct cache_entry *ce = active_cache[next];\n-\t\tif (!strncmp(ce->name, prefix, max_prefix_len)) {\n+\t\tif (!strncmp(ce->name, prefix, prefixlen)) {\n \t\t\tfirst = next+1;\n \t\t\tcontinue;\n \t\t}\n@@ -641,8 +644,7 @@ int cmd_ls_files(int argc, const char **argv, const char *cmd_prefix)\n \t      show_killed || show_modified || show_resolve_undo))\n \t\tshow_cached = 1;\n \n-\tif (max_prefix)\n-\t\tprune_cache(max_prefix);\n+\tprune_cache(max_prefix, max_prefix_len);\n \tif (with_tree) {\n \t\t/*\n \t\t * Basic sanity check; show-stages and show-unmerged\n-- \n2.11.1\n\n"},{"id":"311302","messageId":"de84d0f4-cfce-1e73-6d5d-ad18df507d32@web.de","threadId":"45107","inReplyTo":"f480bd26-f74e-9088-844d-26cde0843baa@web.de","subject":"[PATCH 2/2] ls-files: move only kept cache entries in prune_cache()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-02-10T20:03:30Z","receivedAt":"2017-02-10T20:04:44Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"prune_cache() first identifies those entries at the start of the sorted\narray that can be discarded.  Then it moves the rest of the entries up.\nLast it identifies the unwanted trailing entries among the moved ones\nand cuts them off.\n\nChange the order: Identify both start *and* end of the range to keep\nfirst and then move only those entries to the top.  The resulting code\nis slightly shorter and a bit more efficient.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\nThe performance impact is probably only measurable with a *really* big\nindex.\n\n builtin/ls-files.c | 9 ++++-----\n 1 file changed, 4 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/ls-files.c b/builtin/ls-files.c\nindex 18105ec7ea..1c0f057d02 100644\n--- a/builtin/ls-files.c\n+++ b/builtin/ls-files.c\n@@ -379,10 +379,7 @@ static void prune_cache(const char *prefix, size_t prefixlen)\n \tpos = cache_name_pos(prefix, prefixlen);\n \tif (pos < 0)\n \t\tpos = -pos-1;\n-\tmemmove(active_cache, active_cache + pos,\n-\t\t(active_nr - pos) * sizeof(struct cache_entry *));\n-\tactive_nr -= pos;\n-\tfirst = 0;\n+\tfirst = pos;\n \tlast = active_nr;\n \twhile (last > first) {\n \t\tint next = (last + first) >> 1;\n@@ -393,7 +390,9 @@ static void prune_cache(const char *prefix, size_t prefixlen)\n \t\t}\n \t\tlast = next;\n \t}\n-\tactive_nr = last;\n+\tmemmove(active_cache, active_cache + pos,\n+\t\t(last - pos) * sizeof(struct cache_entry *));\n+\tactive_nr = last - pos;\n }\n \n /*\n-- \n2.11.1\n\n"},{"id":"311325","messageId":"20170210225156.GA128190@google.com","threadId":"45107","inReplyTo":"de84d0f4-cfce-1e73-6d5d-ad18df507d32@web.de","subject":"Re: [PATCH 2/2] ls-files: move only kept cache entries in prune_cache()","fromName":"Brandon Williams","fromEmail":"bmwill@google.com","sentAt":"2017-02-10T22:51:56Z","receivedAt":"2017-02-10T22:52:06Z","isPatch":true,"sender":{"key":"bwilliams.eng@gmail.com","avatar":null},"body":"On 02/10, René Scharfe wrote:\n> prune_cache() first identifies those entries at the start of the sorted\n> array that can be discarded.  Then it moves the rest of the entries up.\n> Last it identifies the unwanted trailing entries among the moved ones\n> and cuts them off.\n> \n> Change the order: Identify both start *and* end of the range to keep\n> first and then move only those entries to the top.  The resulting code\n> is slightly shorter and a bit more efficient.\n> \n> Signed-off-by: Rene Scharfe <l.s.r@web.de>\n> ---\n> The performance impact is probably only measurable with a *really* big\n> index.\n\nWell there's been a lot of talk recently about *really* big indexes, so\nI'm sure someone out there will be happy :)\n\n> \n>  builtin/ls-files.c | 9 ++++-----\n>  1 file changed, 4 insertions(+), 5 deletions(-)\n> \n> diff --git a/builtin/ls-files.c b/builtin/ls-files.c\n> index 18105ec7ea..1c0f057d02 100644\n> --- a/builtin/ls-files.c\n> +++ b/builtin/ls-files.c\n> @@ -379,10 +379,7 @@ static void prune_cache(const char *prefix, size_t prefixlen)\n>  \tpos = cache_name_pos(prefix, prefixlen);\n>  \tif (pos < 0)\n>  \t\tpos = -pos-1;\n> -\tmemmove(active_cache, active_cache + pos,\n> -\t\t(active_nr - pos) * sizeof(struct cache_entry *));\n> -\tactive_nr -= pos;\n> -\tfirst = 0;\n> +\tfirst = pos;\n>  \tlast = active_nr;\n>  \twhile (last > first) {\n>  \t\tint next = (last + first) >> 1;\n> @@ -393,7 +390,9 @@ static void prune_cache(const char *prefix, size_t prefixlen)\n>  \t\t}\n>  \t\tlast = next;\n>  \t}\n> -\tactive_nr = last;\n> +\tmemmove(active_cache, active_cache + pos,\n> +\t\t(last - pos) * sizeof(struct cache_entry *));\n> +\tactive_nr = last - pos;\n>  }\n>  \n>  /*\n> -- \n> 2.11.1\n> \n\nBoth these patches look good to me.\n\n-- \nBrandon Williams\n"}]}