• Junio C Hamano's avatar
    prio-queue: priority queue of pointers to structs · b4b594a3
    Junio C Hamano authored
    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 add commits that are newly discovered to it, keep
    the list 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 prio-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.
    Tests and the idea to make it usable for any "void *" pointers to
    "things" are by Jeff King.  Bugs are mine.
    Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
test-prio-queue.c 621 Bytes