summaryrefslogtreecommitdiff
path: root/Makefile
diff options
context:
space:
mode:
authorJunio C Hamano <gitster@pobox.com>2013-06-06 19:13:50 -0700
committerJunio C Hamano <gitster@pobox.com>2013-06-11 15:15:21 -0700
commitb4b594a3154078430b04fad4f6ffbed9c7274be5 (patch)
tree71bb8164f9e98ca159fbb952b6a289fd899337ad /Makefile
parent08f704f294e4a3525b405c2cb1f4ee85e73fd92c (diff)
downloadgit-b4b594a3154078430b04fad4f6ffbed9c7274be5.tar.gz
prio-queue: priority queue of pointers to structs
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: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'Makefile')
-rw-r--r--Makefile3
1 files changed, 3 insertions, 0 deletions
diff --git a/Makefile b/Makefile
index 598d6313da..0246194abe 100644
--- a/Makefile
+++ b/Makefile
@@ -552,6 +552,7 @@ TEST_PROGRAMS_NEED_X += test-mergesort
TEST_PROGRAMS_NEED_X += test-mktemp
TEST_PROGRAMS_NEED_X += test-parse-options
TEST_PROGRAMS_NEED_X += test-path-utils
+TEST_PROGRAMS_NEED_X += test-prio-queue
TEST_PROGRAMS_NEED_X += test-regex
TEST_PROGRAMS_NEED_X += test-revision-walking
TEST_PROGRAMS_NEED_X += test-run-command
@@ -685,6 +686,7 @@ LIB_H += parse-options.h
LIB_H += patch-ids.h
LIB_H += pathspec.h
LIB_H += pkt-line.h
+LIB_H += prio-queue.h
LIB_H += progress.h
LIB_H += prompt.h
LIB_H += quote.h
@@ -824,6 +826,7 @@ LIB_OBJS += pathspec.o
LIB_OBJS += pkt-line.o
LIB_OBJS += preload-index.o
LIB_OBJS += pretty.o
+LIB_OBJS += prio-queue.o
LIB_OBJS += progress.o
LIB_OBJS += prompt.o
LIB_OBJS += quote.o