From: Eric Sunshine Date: Fri, 07 Jun 2013 05:29:34 GMT Subject: Re: [PATCH 2/3] commit-queue: LIFO or priority queue of commits Message-ID: In-Reply-To: <1370581872-31580-3-git-send-email-gitster@pobox.com> On Fri, Jun 7, 2013 at 1:11 AM, Junio C Hamano wrote: > Traditionally we used a singly linked list of commits to hold a set > of in-flight commits while traversing history. The most typical use > of the list is to insert commit that is newly discovered in it, keep s/commit/a commit/ Also, "in it" is perhaps implied by "insert", so s/in it// may be appropriate. > it sorted by commit timestamp, pick up the newest one from the list, > and keep digging. The cost of keeping the singly linked list sorted > is nontrivial, and this typical use pattern better matches a priority > queue. > > Introduce a commit-queue structure, that can be used either as a > LIFO stack, or a priority queue. This will be used in the next > patch to hold in-flight commits during sort-in-topological-order. > > Signed-off-by: Junio C Hamano