[PATCH v2 2/2] revision.c: reduce memory usage on reverse before

[Mirko Faina <mroik@delayed.space>]

Due to the nature of --reverse=before we have to walk all of the history
and store each non-filtered processed commit, this can be expensive on
memory for projects with a long history. When --max-count is being used
we don't really have to keep every processed commit, we can discard
older commits (as in have been processed before than the ones we're now
considering, from a chronological commit order they are the newer
commits) as we surpass the --max-count limit.

Teach get_revision() to keep only the newer commits as we walk a
revision with --reverse=before and --max-count=<k>. We do this through a
simple queue. With N nodes and K as the --max-count argument, assuming K
< N, we go from a space complexity of O(N) to O(K). When it comes down
to time complexity, the queue has an ammortized time of O(1) for pops,
so the complexity remains O(N).

Signed-off-by: Mirko Faina <mroik@delayed.space>
---
 revision.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 52 insertions(+), 2 deletions(-)

diff --git a/revision.c b/revision.c
index d581f5e38e..4730f21ea6 100644
--- a/revision.c
+++ b/revision.c
@@ -4530,6 +4530,52 @@ static struct commit *get_revision_internal(struct rev_info *revs)
 	return c;
 }
 
+static void retrieve_with_window(struct rev_info *revs, int max_count,
+			  struct commit_list **reversed)
+{
+	struct commit *c;
+	struct commit_list *into_queue = NULL;
+	struct commit_list *outo_queue = NULL;
+	int into_count = 0;
+	int outo_count = 0;
+
+	while ((c = get_revision_internal(revs))) {
+		commit_list_insert(c, &into_queue);
+		into_count++;
+		if (into_count + outo_count > max_count) {
+			if (!outo_count) {
+				while (into_count) {
+					c = pop_commit(&into_queue);
+					into_count--;
+					commit_list_insert(c, &outo_queue);
+					outo_count++;
+				}
+			}
+			pop_commit(&outo_queue);
+			outo_count--;
+		}
+	}
+
+	while (outo_count) {
+		c = pop_commit(&outo_queue);
+		outo_count--;
+		commit_list_insert(c, reversed);
+	}
+
+	while (into_count) {
+		c = pop_commit(&into_queue);
+		into_count--;
+		commit_list_insert(c, &outo_queue);
+		outo_count++;
+	}
+
+	while (outo_count) {
+		c = pop_commit(&outo_queue);
+		outo_count--;
+		commit_list_insert(c, reversed);
+	}
+}
+
 struct commit *get_revision(struct rev_info *revs)
 {
 	struct commit *c;
@@ -4546,8 +4592,12 @@ struct commit *get_revision(struct rev_info *revs)
 			revs->max_count = -1;
 
 		reversed = NULL;
-		while ((c = get_revision_internal(revs)))
-			commit_list_insert(c, &reversed);
+		if (revs->reverse == REVERSE_BEFORE && max_count != -1) {
+			retrieve_with_window(revs, max_count, &reversed);
+		} else {
+			while ((c = get_revision_internal(revs)))
+				commit_list_insert(c, &reversed);
+		}
 		commit_list_free(revs->commits);
 		revs->commits = reversed;
 		revs->reverse_output_stage = 1;
-- 
2.54.0