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.h | 2 -- 1 file changed, 2 deletions(-) (limited to 'commit.h') diff --git a/commit.h b/commit.h index 58150045af..385492fbb1 100644 --- a/commit.h +++ b/commit.h @@ -191,8 +191,6 @@ int commit_list_contains(struct commit *item, struct commit_list **commit_list_append(struct commit *commit, struct commit_list **next); unsigned commit_list_count(const struct commit_list *l); -struct commit_list *commit_list_insert_by_date(struct commit *item, - struct commit_list **list); void commit_list_sort_by_date(struct commit_list **list); /* Shallow copy of the input list */ -- cgit