[PATCH] use commit_stack instead of prio_queue in LIFO mode

[PATCH] use commit_stack instead of prio_queue in LIFO mode

[René Scharfe]

A prio_queue with a NULL compare function acts as a stack -- the last
element in is the first one out (LIFO).  Use an actual commit_stack
instead where possible, as it documents the behavior better, provides
type safety and saves some memory because prio_queue stores an
additional tie-breaking counter per element.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/name-rev.c    | 16 +++++++---------
 negotiator/default.c  | 10 +++++-----
 negotiator/skipping.c | 10 +++++-----
 3 files changed, 17 insertions(+), 19 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 6188cf98ce..d6594ada53 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -12,7 +12,6 @@
 #include "object-name.h"
 #include "pager.h"
 #include "parse-options.h"
-#include "prio-queue.h"
 #include "hash-lookup.h"
 #include "commit-slab.h"
 #include "commit-graph.h"
@@ -178,7 +177,7 @@ static void name_rev(struct commit *start_commit,
 		const char *tip_name, timestamp_t taggerdate,
 		int from_tag, int deref, struct mem_pool *string_pool)
 {
-	struct prio_queue queue;
+	struct commit_stack stack = COMMIT_STACK_INIT;
 	struct commit *commit;
 	struct commit_stack parents_to_queue = COMMIT_STACK_INIT;
 	struct rev_name *start_name;
@@ -197,10 +196,9 @@ static void name_rev(struct commit *start_commit,
 	else
 		start_name->tip_name = mem_pool_strdup(string_pool, tip_name);
 
-	memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
-	prio_queue_put(&queue, start_commit);
+	commit_stack_push(&stack, start_commit);
 
-	while ((commit = prio_queue_get(&queue))) {
+	while ((commit = commit_stack_pop(&stack))) {
 		struct rev_name *name = get_commit_rev_name(commit);
 		struct commit_list *parents;
 		int parent_number = 1;
@@ -241,13 +239,13 @@ static void name_rev(struct commit *start_commit,
 			}
 		}
 
-		/* The first parent must come out first from the prio_queue */
+		/* The first parent must come out first from the stack */
 		while (parents_to_queue.nr)
-			prio_queue_put(&queue,
-				       commit_stack_pop(&parents_to_queue));
+			commit_stack_push(&stack,
+					  commit_stack_pop(&parents_to_queue));
 	}
 
-	clear_prio_queue(&queue);
+	commit_stack_clear(&stack);
 	commit_stack_clear(&parents_to_queue);
 }
 
diff --git a/negotiator/default.c b/negotiator/default.c
index 116dedcf83..3cac0476a7 100644
--- a/negotiator/default.c
+++ b/negotiator/default.c
@@ -57,19 +57,19 @@ static int clear_marks(const struct reference *ref, void *cb_data UNUSED)
 static void mark_common(struct negotiation_state *ns, struct commit *commit,
 		int ancestors_only, int dont_parse)
 {
-	struct prio_queue queue = { NULL };
+	struct commit_stack stack = COMMIT_STACK_INIT;
 
 	if (!commit || (commit->object.flags & COMMON))
 		return;
 
-	prio_queue_put(&queue, commit);
+	commit_stack_push(&stack, commit);
 	if (!ancestors_only) {
 		commit->object.flags |= COMMON;
 
 		if ((commit->object.flags & SEEN) && !(commit->object.flags & POPPED))
 			ns->non_common_revs--;
 	}
-	while ((commit = prio_queue_get(&queue))) {
+	while ((commit = commit_stack_pop(&stack))) {
 		struct object *o = (struct object *)commit;
 
 		if (!(o->flags & SEEN))
@@ -94,12 +94,12 @@ static void mark_common(struct negotiation_state *ns, struct commit *commit,
 				if ((p->object.flags & SEEN) && !(p->object.flags & POPPED))
 					ns->non_common_revs--;
 
-				prio_queue_put(&queue, parents->item);
+				commit_stack_push(&stack, parents->item);
 			}
 		}
 	}
 
-	clear_prio_queue(&queue);
+	commit_stack_clear(&stack);
 }
 
 /*
diff --git a/negotiator/skipping.c b/negotiator/skipping.c
index 0a272130fb..fe4126ca4d 100644
--- a/negotiator/skipping.c
+++ b/negotiator/skipping.c
@@ -91,15 +91,15 @@ static int clear_marks(const struct reference *ref, void *cb_data UNUSED)
  */
 static void mark_common(struct data *data, struct commit *seen_commit)
 {
-	struct prio_queue queue = { NULL };
+	struct commit_stack stack = COMMIT_STACK_INIT;
 	struct commit *c;
 
 	if (seen_commit->object.flags & COMMON)
 		return;
 
-	prio_queue_put(&queue, seen_commit);
+	commit_stack_push(&stack, seen_commit);
 	seen_commit->object.flags |= COMMON;
-	while ((c = prio_queue_get(&queue))) {
+	while ((c = commit_stack_pop(&stack))) {
 		struct commit_list *p;
 
 		if (!(c->object.flags & POPPED))
@@ -113,11 +113,11 @@ static void mark_common(struct data *data, struct commit *seen_commit)
 				continue;
 
 			p->item->object.flags |= COMMON;
-			prio_queue_put(&queue, p->item);
+			commit_stack_push(&stack, p->item);
 		}
 	}
 
-	clear_prio_queue(&queue);
+	commit_stack_clear(&stack);
 }
 
 /*
-- 
2.53.0

Re: [PATCH] use commit_stack instead of prio_queue in LIFO mode

[Patrick Steinhardt]

On Tue, Mar 17, 2026 at 10:40:07PM +0100, René Scharfe wrote:
> A prio_queue with a NULL compare function acts as a stack -- the last
> element in is the first one out (LIFO).  Use an actual commit_stack
> instead where possible, as it documents the behavior better, provides
> type safety and saves some memory because prio_queue stores an
> additional tie-breaking counter per element.

Right. I doubt that the memory improvement will really make much of a
difference, but I agree that using a commit stack makes the intent
clearer.

The changes all look as expected to me. Thanks!

Patrick