diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Makefile | 3 | ||||
| -rw-r--r-- | prio-queue.c | 71 | ||||
| -rw-r--r-- | prio-queue.h | 45 | ||||
| -rwxr-xr-x | t/t0009-prio-queue.sh | 50 | ||||
| -rw-r--r-- | test-prio-queue.c | 39 |
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 @@ -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; +} |