git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v3 2/4] prio-queue: priority queue of pointers to structs

From
Junio C Hamano <gitster@pobox.com>
Date
Jun 11, 2013, 22:19 UTC
Message-ID
<1370989149-28538-3-git-send-email-gitster@pobox.com>
In-Reply-To
<1370989149-28538-1-git-send-email-gitster@pobox.com>

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>
---
 .gitignore            |  1 +
 Makefile              |  3 +++
 prio-queue.c          | 71 +++++++++++++++++++++++++++++++++++++++++++++++++++
 prio-queue.h          | 45 ++++++++++++++++++++++++++++++++
 t/t0009-prio-queue.sh | 50 ++++++++++++++++++++++++++++++++++++
 test-prio-queue.c     | 39 ++++++++++++++++++++++++++++
 6 files changed, 209 insertions(+)
 create mode 100644 prio-queue.c
 create mode 100644 prio-queue.h
 create mode 100755 t/t0009-prio-queue.sh
 create mode 100644 test-prio-queue.c
diff --git a/.gitignore b/.gitignore
index 6669bf0..b753817 100644
--- a/.gitignore
+++ b/.gitignore
@@ -190,6 +190,7 @@
 /test-mktemp
 /test-parse-options
 /test-path-utils
+/test-prio-queue
 /test-regex
 /test-revision-walking
 /test-run-command
diff --git a/Makefile b/Makefile
index 598d631..0246194 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
diff --git a/prio-queue.c b/prio-queue.c
new file mode 100644
index 0000000..f2a4973
--- /dev/null
+++ b/prio-queue.c
@@ -0,0 +1,71 @@
+#include "cache.h"
+#include "commit.h"
+#include "prio-queue.h"
+
+void clear_prio_queue(struct prio_queue *queue)
+{
+	free(queue->array);
+	queue->nr = 0;
+	queue->alloc = 0;
+	queue->array = NULL;
+}
+
+void prio_queue_put(struct prio_queue *queue, void *thing)
+{
+	prio_queue_compare_fn compare = queue->compare;
+	int ix, parent;
+
+	/* Append at the end */
+	ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
+	queue->array[queue->nr++] = thing;
+	if (!compare)
+		return; /* LIFO */
+
+	/* Bubble up the new one */
+	for (ix = queue->nr - 1; ix; ix = parent) {
+		parent = (ix - 1) / 2;
+		if (compare(queue->array[parent], queue->array[ix],
+			    queue->cb_data) <= 0)
+			break;
+
+		thing = queue->array[parent];
+		queue->array[parent] = queue->array[ix];
+		queue->array[ix] = thing;
+	}
+}
+
+void *prio_queue_get(struct prio_queue *queue)
+{
+	void *result, *swap;
+	int ix, child;
+	prio_queue_compare_fn compare = queue->compare;
+
+	if (!queue->nr)
+		return NULL;
+	if (!compare)
+		return queue->array[--queue->nr]; /* LIFO */
+
+	result = queue->array[0];
+	if (!--queue->nr)
+		return result;
+
+	queue->array[0] = queue->array[queue->nr];
+
+	/* Push down the one at the root */
+	for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
+		child = ix * 2 + 1; /* left */
+		if ((child + 1 < queue->nr) &&
+		    (compare(queue->array[child], queue->array[child + 1],
+			     queue->cb_data) >= 0))
+			child++; /* use right child */
+
+		if (compare(queue->array[ix], queue->array[child],
+			    queue->cb_data) <= 0)
+			break;
+
+		swap = queue->array[child];
+		queue->array[child] = queue->array[ix];
+		queue->array[ix] = swap;
+	}
+	return result;
+}
diff --git a/prio-queue.h b/prio-queue.h
new file mode 100644
index 0000000..ed354a5
--- /dev/null
+++ b/prio-queue.h
@@ -0,0 +1,45 @@
+#ifndef PRIO_QUEUE_H
+#define PRIO_QUEUE_H
+
+/*
+ * A priority queue implementation, primarily for keeping track of
+ * commits in the 'date-order' so that we process them from new to old
+ * as they are discovered, but can be used to hold any pointer to
+ * struct.  The caller is responsible for supplying a function to
+ * compare two "things".
+ *
+ * Alternatively, this data structure can also be used as a LIFO stack
+ * by specifying NULL as the comparison function.
+ */
+
+/*
+ * Compare two "things", one and two; the third parameter is cb_data
+ * in the prio_queue structure.  The result is returned as a sign of
+ * the return value, being the same as the sign of the result of
+ * subtracting "two" from "one" (i.e. negative if "one" sorts earlier
+ * than "two").
+ */
+typedef int (*prio_queue_compare_fn)(const void *one, const void *two, void *cb_data);
+
+struct prio_queue {
+	prio_queue_compare_fn compare;
+	void *cb_data;
+	int alloc, nr;
+	void **array;
+};
+
+/*
+ * Add the "thing" to the queue.
+ */
+extern void prio_queue_put(struct prio_queue *, void *thing);
+
+/*
+ * Extract the "thing" that compares the smallest out of the queue,
+ * or NULL.  If compare function is NULL, the queue acts as a LIFO
+ * stack.
+ */
+extern void *prio_queue_get(struct prio_queue *);
+
+extern void clear_prio_queue(struct prio_queue *);
+
+#endif /* PRIO_QUEUE_H */
diff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh
new file mode 100755
index 0000000..94045c3
--- /dev/null
+++ b/t/t0009-prio-queue.sh
@@ -0,0 +1,50 @@
+#!/bin/sh
+
+test_description='basic tests for priority queue implementation'
+. ./test-lib.sh
+
+cat >expect <<'EOF'
+1
+2
+3
+4
+5
+5
+6
+7
+8
+9
+10
+EOF
+test_expect_success 'basic ordering' '
+	test-prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
+	test_cmp expect actual
+'
+
+cat >expect <<'EOF'
+2
+3
+4
+1
+5
+6
+EOF
+test_expect_success 'mixed put and get' '
+	test-prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
+	test_cmp expect actual
+'
+
+cat >expect <<'EOF'
+1
+2
+NULL
+1
+2
+NULL
+EOF
+test_expect_success 'notice empty queue' '
+	test-prio-queue 1 2 get get get 1 2 get get get >actual &&
+	test_cmp expect actual
+'
+
+test_done
diff --git a/test-prio-queue.c b/test-prio-queue.c
new file mode 100644
index 0000000..7be72f0
--- /dev/null
+++ b/test-prio-queue.c
@@ -0,0 +1,39 @@
+#include "cache.h"
+#include "prio-queue.h"
+
+static int intcmp(const void *va, const void *vb, void *data)
+{
+	const int *a = va, *b = vb;
+	return *a - *b;
+}
+
+static void show(int *v)
+{
+	if (!v)
+		printf("NULL\n");
+	else
+		printf("%d\n", *v);
+	free(v);
+}
+
+int main(int argc, char **argv)
+{
+	struct prio_queue pq = { intcmp };
+
+	while (*++argv) {
+		if (!strcmp(*argv, "get"))
+			show(prio_queue_get(&pq));
+		else if (!strcmp(*argv, "dump")) {
+			int *v;
+			while ((v = prio_queue_get(&pq)))
+			       show(v);
+		}
+		else {
+			int *v = malloc(sizeof(*v));
+			*v = atoi(*argv);
+			prio_queue_put(&pq, v);
+		}
+	}
+
+	return 0;
+}

-- 
1.8.3.1-494-g51b8af5
Previous: Junio C HamanoNext: Junio C Hamano
Message 34 of 51 in “add --authorship-order flag to git log / rev-list”
  1. add --authorship-order flag to git log / rev-listelliottcable, Jun 4, 2013
  2. rev-list: add --authorship-order alternative orderingelliottcable, Jun 4, 2013
  3. Junio C HamanoJun 4, 2013
  4. Junio C HamanoJun 4, 2013
  5. Elliott CableJun 6, 2013
  6. Junio C HamanoJun 6, 2013
  7. Elliott CableJun 6, 2013
  8. Junio C HamanoJun 6, 2013
  9. Junio C HamanoJun 6, 2013
  10. toposort: rename "lifo" fieldJunio C Hamano, Jun 6, 2013
  11. Junio C HamanoJun 7, 2013
  12. 0/3 Preparing for --date-order=authorJunio C Hamano, Jun 7, 2013
  13. 1/3 toposort: rename "lifo" fieldJunio C Hamano, Jun 7, 2013
  14. Eric SunshineJun 7, 2013
  15. Junio C HamanoJun 7, 2013
  16. 2/3 commit-queue: LIFO or priority queue of commitsJunio C Hamano, Jun 7, 2013
  17. Eric SunshineJun 7, 2013
  18. 3/3 sort-in-topological-order: use commit-queueJunio C Hamano, Jun 7, 2013
  19. 0/4 log --author-date-orderJunio C Hamano, Jun 9, 2013
  20. 1/4 toposort: rename "lifo" fieldJunio C Hamano, Jun 9, 2013
  21. Eric SunshineJun 10, 2013
  22. Jeff KingJun 10, 2013
  23. 2/4 commit-queue: LIFO or priority queue of commitsJunio C Hamano, Jun 9, 2013
  24. Jeff KingJun 10, 2013
  25. Junio C HamanoJun 10, 2013
  26. Jeff KingJun 10, 2013
  27. Junio C HamanoJun 10, 2013
  28. Jeff KingJun 10, 2013
  29. Junio C HamanoJun 10, 2013
  30. Jeff KingJun 11, 2013
  31. Junio C HamanoJun 11, 2013
  32. 0/4 log --author-date-orderJunio C Hamano, Jun 11, 2013
  33. 1/4 toposort: rename "lifo" fieldJunio C Hamano, Jun 11, 2013
  34. 2/4 prio-queue: priority queue of pointers to structsJunio C Hamano, Jun 11, 2013
  35. 3/4 sort-in-topological-order: use prio-queueJunio C Hamano, Jun 11, 2013
  36. 4/4 log: --author-date-orderJunio C Hamano, Jun 11, 2013
  37. 3/4 sort-in-topological-order: use commit-queueJunio C Hamano, Jun 9, 2013
  38. Junio C HamanoJun 9, 2013
  39. Jeff KingJun 10, 2013
  40. Junio C HamanoJun 10, 2013
  41. Jeff KingJun 10, 2013
  42. 4/4 log: --author-date-orderJunio C Hamano, Jun 9, 2013
  43. Jeff KingJun 10, 2013
  44. Junio C HamanoJun 10, 2013
  45. Jeff KingJun 10, 2013
  46. Junio C HamanoJun 20, 2013
  47. Jeff KingJun 20, 2013
  48. Eric SunshineJun 7, 2013
  49. Jeff KingJun 4, 2013
  50. Junio C HamanoJun 4, 2013
  51. Elliott CableJun 6, 2013

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.