aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore1
-rw-r--r--Makefile3
-rw-r--r--prio-queue.c71
-rw-r--r--prio-queue.h45
-rwxr-xr-xt/t0009-prio-queue.sh50
-rw-r--r--test-prio-queue.c39
6 files changed, 209 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
index 6669bf0c6..b753817ad 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 598d6313d..0246194ab 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 000000000..f2a4973a0
--- /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 000000000..c766abec3
--- /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 000000000..94045c3fa
--- /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 000000000..7be72f008
--- /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;
+}