From dd4bc01c0a8fc871a68a5027ed5ac953fa47fc6e Mon Sep 17 00:00:00 2001 From: Kristofer Karlsson Date: Wed, 27 May 2026 15:50:02 +0000 Subject: revision: use priority queue for non-limited streaming walks The streaming (non-limited) walk in get_revision_1() inserts newly discovered parent commits into a date-sorted queue via commit_list_insert_by_date(), which scans the linked list to find the insertion point -- O(w) per insert, where w is the width of the active walk frontier. Replace this with an O(log w) priority queue. Add a commit_queue field to rev_info alongside the existing commits linked list. The two representations are mutually exclusive: setup and external callers that need list access use the linked list, then get_revision_1() lazily drains it into the priority queue on first call. Add a REV_WALK_NO_WALK enum value to distinguish the no_walk case (which still uses the commit list) from the streaming case. The conversion function rev_info_commit_list_to_queue() is public so callers that know they will iterate can convert early. Combined with the limit_list() priority queue change already in master, this eliminates all O(w) sorted linked-list insertion from the revision walk machinery. Signed-off-by: Kristofer Karlsson Signed-off-by: Junio C Hamano --- commit.c | 13 ------------- 1 file changed, 13 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index e3e7352e69..5112c7b2af 100644 --- a/commit.c +++ b/commit.c @@ -729,19 +729,6 @@ void commit_list_free(struct commit_list *list) pop_commit(&list); } -struct commit_list * commit_list_insert_by_date(struct commit *item, struct commit_list **list) -{ - struct commit_list **pp = list; - struct commit_list *p; - while ((p = *pp) != NULL) { - if (p->item->date < item->date) { - break; - } - pp = &p->next; - } - return commit_list_insert(item, pp); -} - static int commit_list_compare_by_date(const struct commit_list *a, const struct commit_list *b) { -- cgit