[PATCH v2] sequencer: simplify allocation of result array in todo_list_rearrange_squash()

[PATCH v2] sequencer: simplify allocation of result array in todo_list_rearrange_squash()

[Oswald Buddenhagen]

The operation doesn't change the number of elements in the array, so we do
not need to allocate the result piecewise.

This moves the re-assignment of todo_list->alloc at the end slighly up,
so it's right after the newly added assert which also refers to `nr`
(and which indeed should come first). Also, the value is more likely to
be still in a register at that point.

Signed-off-by: Oswald Buddenhagen <oswald.buddenhagen@gmx.de>
---
v2:
- removed redundant assignment of `items` in ALLOC_ARRAY() call
- added 2nd paragraph to commit message
- broken out of the bigger series, as the aggregation just unnecessarily
  holds it up

Cc: Phillip Wood <phillip.wood123@gmail.com>
---
 sequencer.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/sequencer.c b/sequencer.c
index cc9821ece2..947cb89e60 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -6233,7 +6233,7 @@ static int skip_fixupish(const char *subject, const char **p) {
 int todo_list_rearrange_squash(struct todo_list *todo_list)
 {
 	struct hashmap subject2item;
-	int rearranged = 0, *next, *tail, i, nr = 0, alloc = 0;
+	int rearranged = 0, *next, *tail, i, nr = 0;
 	char **subjects;
 	struct commit_todo_item commit_todo;
 	struct todo_item *items = NULL;
@@ -6345,6 +6345,8 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)
 	}
 
 	if (rearranged) {
+		ALLOC_ARRAY(items, todo_list->nr);
+
 		for (i = 0; i < todo_list->nr; i++) {
 			enum todo_command command = todo_list->items[i].command;
 			int cur = i;
@@ -6357,16 +6359,15 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)
 				continue;
 
 			while (cur >= 0) {
-				ALLOC_GROW(items, nr + 1, alloc);
 				items[nr++] = todo_list->items[cur];
 				cur = next[cur];
 			}
 		}
 
+		assert(nr == todo_list->nr);
+		todo_list->alloc = nr;
 		FREE_AND_NULL(todo_list->items);
 		todo_list->items = items;
-		todo_list->nr = nr;
-		todo_list->alloc = alloc;
 	}
 
 	free(next);
-- 
2.40.0.152.g15d061e6df

Re: [PATCH v2] sequencer: simplify allocation of result array in todo_list_rearrange_squash()

[Junio C Hamano]

Oswald Buddenhagen <oswald.buddenhagen@gmx.de> writes:

>  	if (rearranged) {
> +		ALLOC_ARRAY(items, todo_list->nr);
> +
>  		for (i = 0; i < todo_list->nr; i++) {
>  			enum todo_command command = todo_list->items[i].command;
>  			int cur = i;
> @@ -6357,16 +6359,15 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)
>  				continue;
>  
>  			while (cur >= 0) {
> -				ALLOC_GROW(items, nr + 1, alloc);
>  				items[nr++] = todo_list->items[cur];
>  				cur = next[cur];
>  			}
>  		}
>  
> +		assert(nr == todo_list->nr);

The assert() made me wonder what kind of bugs we are worried about.

The next[] array elements are initialized to -1 and then gets "i"
that runs (0..todo_list->nr) and get shuffled among the elements of
the same array, so next[cur] reference in the while loop we see
above will always be within (0..todo_list->nr).  It is trivial to
see that the items[] array that is preallocated so that it can hold
up to todo_list->nr items is large enough.

But the condition of the assert() is even stronger.  We want to make
sure we did not drop any original items in the todo_list, as the
objective of this helper function is to shuffle the insns and
selectively turn "pick 01234567 fixup! title of another commit"
into "fixup 01234567 fixup! title of another commit".  There is no
reason we should have fewer elements in the result.

All makes sense.  Nice.

Thanks, will queue.




> +		todo_list->alloc = nr;
>  		FREE_AND_NULL(todo_list->items);
>  		todo_list->items = items;
> -		todo_list->nr = nr;
> -		todo_list->alloc = alloc;
>  	}
>  
>  	free(next);