Re: [PATCH 2/4] basic priority queue implementation

[Thiago Farina <tfransosi@gmail.com>]

On Thu, May 19, 2011 at 6:24 PM, Jeff King <peff@peff.net> 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@peff.net>
> ---
>  .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@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>