]> git.ipfire.org Git - thirdparty/git.git/commit
commit-reach: deduplicate queue entries in paint_down_to_common
authorKristofer Karlsson <krka@spotify.com>
Mon, 25 May 2026 14:28:04 +0000 (14:28 +0000)
committerJunio C Hamano <gitster@pobox.com>
Mon, 25 May 2026 22:17:26 +0000 (07:17 +0900)
commitf767dae3e6c8359128d0ec83acd009751e92e419
tree7f6b2172a2b24facb80cb851675c6b8db075abaa
parent85a30b5b26c2953aa836c554af5fc58eed707e4a
commit-reach: deduplicate queue entries in paint_down_to_common

paint_down_to_common() can enqueue the same commit multiple times
when it is reached through different parents with different flag
combinations. Add an ENQUEUED flag to track whether a commit is
currently in the priority queue, and skip it if already present.

Introduce prio_queue_put_dedup() and prio_queue_get_dedup()
wrappers that manage the ENQUEUED flag on enqueue and dequeue.

This change is performance-neutral on its own: the O(n)
queue_has_nonstale() scan still dominates the per-iteration cost.
However, the deduplication guarantee (each commit appears in the
queue at most once) is a prerequisite for the next commit, which
replaces that scan with O(1) tracking.

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit-reach.c
object.h