From: "René Scharfe" <l.s.r@web•de>
To: Git List <git@vger•kernel.org>
Subject: [PATCH] use commit_stack instead of prio_queue in LIFO mode
Date: Tue, 17 Mar 2026 22:40:07 +0100 [thread overview]
Message-ID: <05fc946f-6670-46e9-a058-231ee464029d@web.de> (raw)
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
next reply other threads:[~2026-03-17 21:40 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-03-17 21:40 René Scharfe [this message]
2026-03-19 7:19 ` [PATCH] use commit_stack instead of prio_queue in LIFO mode Patrick Steinhardt
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=05fc946f-6670-46e9-a058-231ee464029d@web.de \
--to=l.s.r@web$(echo .)de \
--cc=git@vger$(echo .)kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox