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