{"thread":{"id":"60095","subject":"[PATCH v2] sequencer: simplify allocation of result array in todo_list_rearrange_squash()","startedAt":"2023-08-09T17:15:52Z","lastAt":"2023-08-09T20:52:05Z","messageCount":2,"participants":["Oswald Buddenhagen","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"480380","messageId":"20230809171532.2564880-1-oswald.buddenhagen@gmx.de","threadId":"60095","inReplyTo":null,"subject":"[PATCH v2] sequencer: simplify allocation of result array in todo_list_rearrange_squash()","fromName":"Oswald Buddenhagen","fromEmail":"oswald.buddenhagen@gmx.de","sentAt":"2023-08-09T17:15:32Z","receivedAt":"2023-08-09T17:15:52Z","isPatch":true,"sender":{"key":"oswald.buddenhagen@gmx.de","avatar":"https://avatars.githubusercontent.com/u/812380?v=4"},"body":"The operation doesn't change the number of elements in the array, so we do\nnot need to allocate the result piecewise.\n\nThis moves the re-assignment of todo_list->alloc at the end slighly up,\nso it's right after the newly added assert which also refers to `nr`\n(and which indeed should come first). Also, the value is more likely to\nbe still in a register at that point.\n\nSigned-off-by: Oswald Buddenhagen <oswald.buddenhagen@gmx.de>\n---\nv2:\n- removed redundant assignment of `items` in ALLOC_ARRAY() call\n- added 2nd paragraph to commit message\n- broken out of the bigger series, as the aggregation just unnecessarily\n  holds it up\n\nCc: Phillip Wood <phillip.wood123@gmail.com>\n---\n sequencer.c | 9 +++++----\n 1 file changed, 5 insertions(+), 4 deletions(-)\n\ndiff --git a/sequencer.c b/sequencer.c\nindex cc9821ece2..947cb89e60 100644\n--- a/sequencer.c\n+++ b/sequencer.c\n@@ -6233,7 +6233,7 @@ static int skip_fixupish(const char *subject, const char **p) {\n int todo_list_rearrange_squash(struct todo_list *todo_list)\n {\n \tstruct hashmap subject2item;\n-\tint rearranged = 0, *next, *tail, i, nr = 0, alloc = 0;\n+\tint rearranged = 0, *next, *tail, i, nr = 0;\n \tchar **subjects;\n \tstruct commit_todo_item commit_todo;\n \tstruct todo_item *items = NULL;\n@@ -6345,6 +6345,8 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)\n \t}\n \n \tif (rearranged) {\n+\t\tALLOC_ARRAY(items, todo_list->nr);\n+\n \t\tfor (i = 0; i < todo_list->nr; i++) {\n \t\t\tenum todo_command command = todo_list->items[i].command;\n \t\t\tint cur = i;\n@@ -6357,16 +6359,15 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)\n \t\t\t\tcontinue;\n \n \t\t\twhile (cur >= 0) {\n-\t\t\t\tALLOC_GROW(items, nr + 1, alloc);\n \t\t\t\titems[nr++] = todo_list->items[cur];\n \t\t\t\tcur = next[cur];\n \t\t\t}\n \t\t}\n \n+\t\tassert(nr == todo_list->nr);\n+\t\ttodo_list->alloc = nr;\n \t\tFREE_AND_NULL(todo_list->items);\n \t\ttodo_list->items = items;\n-\t\ttodo_list->nr = nr;\n-\t\ttodo_list->alloc = alloc;\n \t}\n \n \tfree(next);\n-- \n2.40.0.152.g15d061e6df\n\n"},{"id":"480400","messageId":"xmqqsf8skkgo.fsf@gitster.g","threadId":"60095","inReplyTo":"20230809171532.2564880-1-oswald.buddenhagen@gmx.de","subject":"Re: [PATCH v2] sequencer: simplify allocation of result array in todo_list_rearrange_squash()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-08-09T20:51:51Z","receivedAt":"2023-08-09T20:52:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Oswald Buddenhagen <oswald.buddenhagen@gmx.de> writes:\n\n>  \tif (rearranged) {\n> +\t\tALLOC_ARRAY(items, todo_list->nr);\n> +\n>  \t\tfor (i = 0; i < todo_list->nr; i++) {\n>  \t\t\tenum todo_command command = todo_list->items[i].command;\n>  \t\t\tint cur = i;\n> @@ -6357,16 +6359,15 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)\n>  \t\t\t\tcontinue;\n>  \n>  \t\t\twhile (cur >= 0) {\n> -\t\t\t\tALLOC_GROW(items, nr + 1, alloc);\n>  \t\t\t\titems[nr++] = todo_list->items[cur];\n>  \t\t\t\tcur = next[cur];\n>  \t\t\t}\n>  \t\t}\n>  \n> +\t\tassert(nr == todo_list->nr);\n\nThe assert() made me wonder what kind of bugs we are worried about.\n\nThe next[] array elements are initialized to -1 and then gets \"i\"\nthat runs (0..todo_list->nr) and get shuffled among the elements of\nthe same array, so next[cur] reference in the while loop we see\nabove will always be within (0..todo_list->nr).  It is trivial to\nsee that the items[] array that is preallocated so that it can hold\nup to todo_list->nr items is large enough.\n\nBut the condition of the assert() is even stronger.  We want to make\nsure we did not drop any original items in the todo_list, as the\nobjective of this helper function is to shuffle the insns and\nselectively turn \"pick 01234567 fixup! title of another commit\"\ninto \"fixup 01234567 fixup! title of another commit\".  There is no\nreason we should have fewer elements in the result.\n\nAll makes sense.  Nice.\n\nThanks, will queue.\n\n\n\n\n> +\t\ttodo_list->alloc = nr;\n>  \t\tFREE_AND_NULL(todo_list->items);\n>  \t\ttodo_list->items = items;\n> -\t\ttodo_list->nr = nr;\n> -\t\ttodo_list->alloc = alloc;\n>  \t}\n>  \n>  \tfree(next);\n"}]}