{"thread":{"id":"65285","subject":"[PATCH] use commit_stack instead of prio_queue in LIFO mode","startedAt":"2026-03-17T21:40:15Z","lastAt":"2026-03-19T07:19:48Z","messageCount":2,"participants":["René Scharfe","Patrick Steinhardt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"539260","messageId":"05fc946f-6670-46e9-a058-231ee464029d@web.de","threadId":"65285","inReplyTo":null,"subject":"[PATCH] use commit_stack instead of prio_queue in LIFO mode","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-03-17T21:40:07Z","receivedAt":"2026-03-17T21:40:15Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"A prio_queue with a NULL compare function acts as a stack -- the last\nelement in is the first one out (LIFO).  Use an actual commit_stack\ninstead where possible, as it documents the behavior better, provides\ntype safety and saves some memory because prio_queue stores an\nadditional tie-breaking counter per element.\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n builtin/name-rev.c    | 16 +++++++---------\n negotiator/default.c  | 10 +++++-----\n negotiator/skipping.c | 10 +++++-----\n 3 files changed, 17 insertions(+), 19 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 6188cf98ce..d6594ada53 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -12,7 +12,6 @@\n #include \"object-name.h\"\n #include \"pager.h\"\n #include \"parse-options.h\"\n-#include \"prio-queue.h\"\n #include \"hash-lookup.h\"\n #include \"commit-slab.h\"\n #include \"commit-graph.h\"\n@@ -178,7 +177,7 @@ static void name_rev(struct commit *start_commit,\n \t\tconst char *tip_name, timestamp_t taggerdate,\n \t\tint from_tag, int deref, struct mem_pool *string_pool)\n {\n-\tstruct prio_queue queue;\n+\tstruct commit_stack stack = COMMIT_STACK_INIT;\n \tstruct commit *commit;\n \tstruct commit_stack parents_to_queue = COMMIT_STACK_INIT;\n \tstruct rev_name *start_name;\n@@ -197,10 +196,9 @@ static void name_rev(struct commit *start_commit,\n \telse\n \t\tstart_name->tip_name = mem_pool_strdup(string_pool, tip_name);\n \n-\tmemset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */\n-\tprio_queue_put(&queue, start_commit);\n+\tcommit_stack_push(&stack, start_commit);\n \n-\twhile ((commit = prio_queue_get(&queue))) {\n+\twhile ((commit = commit_stack_pop(&stack))) {\n \t\tstruct rev_name *name = get_commit_rev_name(commit);\n \t\tstruct commit_list *parents;\n \t\tint parent_number = 1;\n@@ -241,13 +239,13 @@ static void name_rev(struct commit *start_commit,\n \t\t\t}\n \t\t}\n \n-\t\t/* The first parent must come out first from the prio_queue */\n+\t\t/* The first parent must come out first from the stack */\n \t\twhile (parents_to_queue.nr)\n-\t\t\tprio_queue_put(&queue,\n-\t\t\t\t       commit_stack_pop(&parents_to_queue));\n+\t\t\tcommit_stack_push(&stack,\n+\t\t\t\t\t  commit_stack_pop(&parents_to_queue));\n \t}\n \n-\tclear_prio_queue(&queue);\n+\tcommit_stack_clear(&stack);\n \tcommit_stack_clear(&parents_to_queue);\n }\n \ndiff --git a/negotiator/default.c b/negotiator/default.c\nindex 116dedcf83..3cac0476a7 100644\n--- a/negotiator/default.c\n+++ b/negotiator/default.c\n@@ -57,19 +57,19 @@ static int clear_marks(const struct reference *ref, void *cb_data UNUSED)\n static void mark_common(struct negotiation_state *ns, struct commit *commit,\n \t\tint ancestors_only, int dont_parse)\n {\n-\tstruct prio_queue queue = { NULL };\n+\tstruct commit_stack stack = COMMIT_STACK_INIT;\n \n \tif (!commit || (commit->object.flags & COMMON))\n \t\treturn;\n \n-\tprio_queue_put(&queue, commit);\n+\tcommit_stack_push(&stack, commit);\n \tif (!ancestors_only) {\n \t\tcommit->object.flags |= COMMON;\n \n \t\tif ((commit->object.flags & SEEN) && !(commit->object.flags & POPPED))\n \t\t\tns->non_common_revs--;\n \t}\n-\twhile ((commit = prio_queue_get(&queue))) {\n+\twhile ((commit = commit_stack_pop(&stack))) {\n \t\tstruct object *o = (struct object *)commit;\n \n \t\tif (!(o->flags & SEEN))\n@@ -94,12 +94,12 @@ static void mark_common(struct negotiation_state *ns, struct commit *commit,\n \t\t\t\tif ((p->object.flags & SEEN) && !(p->object.flags & POPPED))\n \t\t\t\t\tns->non_common_revs--;\n \n-\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\t\t\tcommit_stack_push(&stack, parents->item);\n \t\t\t}\n \t\t}\n \t}\n \n-\tclear_prio_queue(&queue);\n+\tcommit_stack_clear(&stack);\n }\n \n /*\ndiff --git a/negotiator/skipping.c b/negotiator/skipping.c\nindex 0a272130fb..fe4126ca4d 100644\n--- a/negotiator/skipping.c\n+++ b/negotiator/skipping.c\n@@ -91,15 +91,15 @@ static int clear_marks(const struct reference *ref, void *cb_data UNUSED)\n  */\n static void mark_common(struct data *data, struct commit *seen_commit)\n {\n-\tstruct prio_queue queue = { NULL };\n+\tstruct commit_stack stack = COMMIT_STACK_INIT;\n \tstruct commit *c;\n \n \tif (seen_commit->object.flags & COMMON)\n \t\treturn;\n \n-\tprio_queue_put(&queue, seen_commit);\n+\tcommit_stack_push(&stack, seen_commit);\n \tseen_commit->object.flags |= COMMON;\n-\twhile ((c = prio_queue_get(&queue))) {\n+\twhile ((c = commit_stack_pop(&stack))) {\n \t\tstruct commit_list *p;\n \n \t\tif (!(c->object.flags & POPPED))\n@@ -113,11 +113,11 @@ static void mark_common(struct data *data, struct commit *seen_commit)\n \t\t\t\tcontinue;\n \n \t\t\tp->item->object.flags |= COMMON;\n-\t\t\tprio_queue_put(&queue, p->item);\n+\t\t\tcommit_stack_push(&stack, p->item);\n \t\t}\n \t}\n \n-\tclear_prio_queue(&queue);\n+\tcommit_stack_clear(&stack);\n }\n \n /*\n-- \n2.53.0\n"},{"id":"539370","messageId":"abujjg-8hwPPlkMU@pks.im","threadId":"65285","inReplyTo":"05fc946f-6670-46e9-a058-231ee464029d@web.de","subject":"Re: [PATCH] use commit_stack instead of prio_queue in LIFO mode","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-03-19T07:19:42Z","receivedAt":"2026-03-19T07:19:48Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Mar 17, 2026 at 10:40:07PM +0100, René Scharfe wrote:\n> A prio_queue with a NULL compare function acts as a stack -- the last\n> element in is the first one out (LIFO).  Use an actual commit_stack\n> instead where possible, as it documents the behavior better, provides\n> type safety and saves some memory because prio_queue stores an\n> additional tie-breaking counter per element.\n\nRight. I doubt that the memory improvement will really make much of a\ndifference, but I agree that using a commit stack makes the intent\nclearer.\n\nThe changes all look as expected to me. Thanks!\n\nPatrick\n"}]}