On Thu, May 19, 2011 at 6:24 PM, Jeff King <peff@xxxxxxxx> wrote:
> This can provide better algorithmic complexity for some of
> the date-sorted commit list uses, among other things.
>
> The queue is stored as a heap, allowing O(log) insertion and
> top-element removal, and O(1) peeking at the top element.
> Current commit lists are sorted linked lists, giving O(1)
> peeking and top-element removal, but O(n^2) insertion.
>
> Signed-off-by: Jeff King <peff@xxxxxxxx>
> ---
> Â.gitignore    |  Â1 +
> ÂMakefile     |  Â3 ++
> Âqueue.c     Â|  70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
> Âqueue.h     Â|  17 +++++++++++++
> Ât/t0007-queue.sh | Â 50 ++++++++++++++++++++++++++++++++++++++
> Âtest-queue.c   |  39 ++++++++++++++++++++++++++++++
> Â6 files changed, 180 insertions(+), 0 deletions(-)
> Âcreate mode 100644 queue.c
> Âcreate mode 100644 queue.h
> Âcreate mode 100755 t/t0007-queue.sh
> Âcreate mode 100644 test-queue.c
>
> diff --git a/.gitignore b/.gitignore
> index 711fce7..179483a 100644
> --- a/.gitignore
> +++ b/.gitignore
> @@ -174,6 +174,7 @@
> Â/test-obj-pool
> Â/test-parse-options
> Â/test-path-utils
> +/test-queue
> Â/test-run-command
> Â/test-sha1
> Â/test-sigchain
> diff --git a/Makefile b/Makefile
> index d09ee70..737b2d5 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -422,6 +422,7 @@ TEST_PROGRAMS_NEED_X += test-mktemp
> ÂTEST_PROGRAMS_NEED_X += test-obj-pool
> ÂTEST_PROGRAMS_NEED_X += test-parse-options
> ÂTEST_PROGRAMS_NEED_X += test-path-utils
> +TEST_PROGRAMS_NEED_X += test-queue
> ÂTEST_PROGRAMS_NEED_X += test-run-command
> ÂTEST_PROGRAMS_NEED_X += test-sha1
> ÂTEST_PROGRAMS_NEED_X += test-sigchain
> @@ -532,6 +533,7 @@ LIB_H += parse-options.h
> ÂLIB_H += patch-ids.h
> ÂLIB_H += pkt-line.h
> ÂLIB_H += progress.h
> +LIB_H += queue.h
> ÂLIB_H += quote.h
> ÂLIB_H += reflog-walk.h
> ÂLIB_H += refs.h
> @@ -629,6 +631,7 @@ LIB_OBJS += pkt-line.o
> ÂLIB_OBJS += preload-index.o
> ÂLIB_OBJS += pretty.o
> ÂLIB_OBJS += progress.o
> +LIB_OBJS += queue.o
> ÂLIB_OBJS += quote.o
> ÂLIB_OBJS += reachable.o
> ÂLIB_OBJS += read-cache.o
> diff --git a/queue.c b/queue.c
> new file mode 100644
> index 0000000..068b559
> --- /dev/null
> +++ b/queue.c
> @@ -0,0 +1,70 @@
> +#include "queue.h"
> +#include "cache.h"
> +
> +static inline void queue_swap(struct queue *pq, unsigned i, unsigned j)
> +{
> + Â Â Â void *tmp = pq->items[i];
> + Â Â Â pq->items[i] = pq->items[j];
> + Â Â Â pq->items[j] = tmp;
> +}
> +
> +static void queue_heapify_up(struct queue *pq)
> +{
> + Â Â Â unsigned i = pq->nr - 1;
> + Â Â Â while (i > 0) {
> + Â Â Â Â Â Â Â int parent = (i-1)/2;
> +
> + Â Â Â Â Â Â Â if (pq->cmp(pq->items[i], pq->items[parent]) <= 0)
> + Â Â Â Â Â Â Â Â Â Â Â return;
> +
> + Â Â Â Â Â Â Â queue_swap(pq, i, parent);
> + Â Â Â Â Â Â Â i = parent;
> + Â Â Â }
> +}
> +
> +void queue_insert(struct queue *pq, void *item)
> +{
> + Â Â Â ALLOC_GROW(pq->items, pq->nr + 1, pq->alloc);
> + Â Â Â pq->items[pq->nr++] = item;
> + Â Â Â queue_heapify_up(pq);
> +}
> +
> +static void queue_heapify_down(struct queue *pq)
> +{
> + Â Â Â unsigned i = 0;
> + Â Â Â while (1) {
> + Â Â Â Â Â Â Â int largest = i, left = 2*i + 1, right = 2*i + 2;
> +
> + Â Â Â Â Â Â Â if (left < pq->nr &&
> + Â Â Â Â Â Â Â Â Â pq->cmp(pq->items[left], pq->items[largest]) > 0)
> + Â Â Â Â Â Â Â Â Â Â Â largest = left;
> + Â Â Â Â Â Â Â if (right < pq->nr &&
> + Â Â Â Â Â Â Â Â Â pq->cmp(pq->items[right], pq->items[largest]) > 0)
> + Â Â Â Â Â Â Â Â Â Â Â largest = right;
> +
> + Â Â Â Â Â Â Â if (largest == i)
> + Â Â Â Â Â Â Â Â Â Â Â return;
> +
> + Â Â Â Â Â Â Â queue_swap(pq, i, largest);
> + Â Â Â Â Â Â Â i = largest;
> + Â Â Â }
> +}
> +
> +void *queue_peek(struct queue *pq)
> +{
> + Â Â Â return pq->nr ? pq->items[0] : NULL;
> +}
> +
> +void *queue_pop(struct queue *pq)
> +{
> + Â Â Â void *ret;
> +
> + Â Â Â if (!pq->nr)
> + Â Â Â Â Â Â Â return NULL;
> + Â Â Â ret = pq->items[0];
> +
> + Â Â Â pq->items[0] = pq->items[--pq->nr];
> + Â Â Â queue_heapify_down(pq);
> +
> + Â Â Â return ret;
> +}
> diff --git a/queue.h b/queue.h
> new file mode 100644
> index 0000000..fee5a51
> --- /dev/null
> +++ b/queue.h
> @@ -0,0 +1,17 @@
> +#ifndef QUEUE_H
> +#define QUEUE_H
> +
> +typedef int (*queue_comparison_func_t)(const void *, const void *);
> +
> +struct queue {
> + Â Â Â queue_comparison_func_t cmp;
> + Â Â Â void **items;
> + Â Â Â unsigned nr;
> + Â Â Â unsigned alloc;
> +};
> +
> +void queue_insert(struct queue *pq, void *item);
I'd rename this to queue_append as we add |item| to the end of the
array (like you did for sha1_array_append), opposed of inserting it at
some position/index.
> +void *queue_peek(struct queue *pq);
> +void *queue_pop(struct queue *pq);
> +
> +#endif /* QUEUE_H */
> diff --git a/t/t0007-queue.sh b/t/t0007-queue.sh
> new file mode 100755
> index 0000000..ee357bb
> --- /dev/null
> +++ b/t/t0007-queue.sh
> @@ -0,0 +1,50 @@
> +#!/bin/sh
> +
> +test_description='basic tests for priority queue implementation'
> +. ./test-lib.sh
> +
> +cat >expect <<'EOF'
> +10
> +9
> +8
> +7
> +6
> +5
> +5
> +4
> +3
> +2
> +1
> +EOF
> +test_expect_success 'basic ordering' '
> + Â Â Â test-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
> + Â Â Â test_cmp expect actual
> +'
> +
> +cat >expect <<'EOF'
> +3
> +5
> +4
> +6
> +2
> +1
> +EOF
> +test_expect_success 'mixed insert and pop' '
> + Â Â Â test-queue 1 2 3 pop 4 5 pop pop 6 dump >actual &&
> + Â Â Â test_cmp expect actual
> +'
> +
> +cat >expect <<'EOF'
> +2
> +1
> +NULL
> +2
> +1
> +NULL
> +EOF
> +test_expect_success 'notice empty queue' '
> + Â Â Â test-queue 1 2 pop pop pop 1 2 pop pop pop >actual &&
> + Â Â Â test_cmp expect actual
> +'
> +
> +test_done
> diff --git a/test-queue.c b/test-queue.c
> new file mode 100644
> index 0000000..a1e92e2
> --- /dev/null
> +++ b/test-queue.c
> @@ -0,0 +1,39 @@
> +#include "cache.h"
> +#include "queue.h"
> +
> +static int intcmp(const void *va, const void *vb)
> +{
> + Â Â Â 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 queue pq = { intcmp };
> +
> + Â Â Â while (*++argv) {
> + Â Â Â Â Â Â Â if (!strcmp(*argv, "pop"))
> + Â Â Â Â Â Â Â Â Â Â Â show(queue_pop(&pq));
> + Â Â Â Â Â Â Â else if (!strcmp(*argv, "dump")) {
> + Â Â Â Â Â Â Â Â Â Â Â int *v;
> + Â Â Â Â Â Â Â Â Â Â Â while ((v = queue_pop(&pq)))
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Âshow(v);
> + Â Â Â Â Â Â Â }
> + Â Â Â Â Â Â Â else {
> + Â Â Â Â Â Â Â Â Â Â Â int *v = malloc(sizeof(*v));
> + Â Â Â Â Â Â Â Â Â Â Â *v = atoi(*argv);
> + Â Â Â Â Â Â Â Â Â Â Â queue_insert(&pq, v);
> + Â Â Â Â Â Â Â }
> + Â Â Â }
> +
> + Â Â Â return 0;
> +}
> --
> 1.7.5.8.ga95ab
>
> --
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at Âhttp://vger.kernel.org/majordomo-info.html
>
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html