priqueue.c

// Implementation of the QuickHeap priority queue
// From http://swp.dcc.uchile.cl/TR/2008/TR_DCC-2008-006.pdf
// tiffany <tiffany@stormbit.net>
// zlib/libpng, I guess

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <assert.h>

typedef struct qstack {
    unsigned *pivots;
    unsigned top, capacity;
} qstack;

typedef struct qheap {
    unsigned *heap;
    unsigned idx, capacity;
    qstack stack;
} qheap;

static qheap qnew(size_t capacity, size_t stack)
{
    qheap q;
    q.heap = calloc(capacity, sizeof(unsigned));
    q.idx = 0;
    q.capacity = capacity;
    q.stack.pivots = calloc(stack, sizeof(unsigned));
    q.stack.pivots[0] = 0;
    q.stack.top = 0;
    q.stack.capacity = stack;
    return q;
}

static qheap *qconv(size_t capacity, const unsigned *arr)
{
    qheap q = qnew(capacity+1, 64);
    memcpy(q.heap, arr, capacity * sizeof(unsigned));
    q.stack.pivots[0] = capacity;
    qheap *m = calloc(1, sizeof(qheap));
    *m = q;
    return m;
}

static unsigned qget(qheap *q, unsigned i)
{
    return q->heap[i % q->capacity];
}

static void qset(qheap *q, unsigned i, unsigned v)
{
    q->heap[i % q->capacity] = v;
}

static void qpush(qstack *stack, unsigned elt)
{
    if (stack->top >= stack->capacity) {
        size_t ns = stack->capacity * 2;
        unsigned *tmp = calloc(ns, sizeof(unsigned));
        memcpy(tmp, stack->pivots, stack->capacity * sizeof(unsigned));
        free(stack->pivots);
        stack->pivots = tmp;
        stack->capacity = ns;
    }
    stack->pivots[++stack->top] = elt;
}

static void qswap(qheap *q, unsigned a, unsigned b)
{
    unsigned tmp = qget(q, b);
    qset(q, b, qget(q, a));
    qset(q, a, tmp);
}

/* https://en.wikipedia.org/wiki/Quicksort
  partition(array, left, right)
     pivotIndex := choose-pivot(array, left, right)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right]
     storeIndex := left
     for i from left to right - 1
         if array[i] ≤ pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right]  // Move pivot to its final place
     return storeIndex
 */
static unsigned qpartition(qheap *q, unsigned left, unsigned right)
{
    if (left == right) {
        return left;
    }
    unsigned pivot = (rand() % (right-left)) + left;
    unsigned pv = qget(q, pivot);
    qswap(q, pivot, right);
    unsigned si = left;
    for (unsigned i = left; i < right; i++) {
        if (qget(q, i) < pv) {
            qswap(q, i, si);
            si++;
        }
    }
    qswap(q, si, right);
    return si;
}

static unsigned qtop(qstack *stack)
{
    return stack->pivots[stack->top];
}

static void qpop(qstack *stack)
{
    assert(stack->top > 0);
    stack->top--;
}

static unsigned qiqs(qheap *q)
{
    if (q->idx == qtop(&q->stack)) {
        return qget(q, q->idx);
    }
    unsigned pidx = qpartition(q, q->idx, qtop(&q->stack) - 1);
    qpush(&q->stack, pidx);
    return qiqs(q);
}

static unsigned qfindmin(qheap *q)
{
    qiqs(q);
    return qget(q, q->idx);
}

static unsigned qextractmin(qheap *q)
{
    qiqs(q);
    qpop(&q->stack);
    return qget(q, q->idx++);
}

static void qinsert(qheap *q, unsigned x)
{
    unsigned pidx = 0;
    unsigned *S = q->stack.pivots;
    while (1) {
        qset(q, S[pidx] + 1, qget(q, S[pidx]));
        S[pidx]++;
        if (q->stack.top == pidx || qget(q, S[pidx+1]) <= x) {
            qset(q, S[pidx] - 1, x);
            return;
        } else {
            qset(q, S[pidx] - 1, qget(q, S[pidx+1]+1));
            pidx++;
            assert(pidx <= q->stack.top);
        }
    }
}

static void func_timersub(struct timeval *a, struct timeval *b, struct timeval *res)
{
    timersub(a,b,res);
}

int main(int argc, char **argv)
{
    if (argc < 2) {
        printf("Usage: priqueue [size]\n");
        return 1;
    }
    unsigned num = atoi(argv[1]);
    struct timeval start, end, diff;
    unsigned *arr = calloc(num, sizeof(unsigned));
    for (unsigned i = 0; i < num; i++) {
        arr[i] = rand() % num;
    }
    if (num <= 100) {
        printf("Data:\n");
        for (unsigned i = 0; i < num; i++) {
            printf("%u, ", arr[i]);
        }
        printf("\n");
    }
    unsigned first;
#define profile(name) for (first = 1, gettimeofday(&start, NULL); first; first = 0, gettimeofday(&end, NULL), func_timersub(&end, &start, &diff), printf(name ": %li.%06lis\n", diff.tv_sec, diff.tv_usec))
    qheap *q;
    /*profile("Initialization") {
        q = qconv(num, arr);
        }*/
    q = calloc(1, sizeof(qheap));
    *q = qnew(num+1, 64);
    profile("Insert All") {
        for (unsigned i = 0; i < num; i++) {
            qinsert(q, arr[i]);
        }
    }
    unsigned *sorted = calloc(num, sizeof(unsigned));
    profile("Extract All") {
        for (unsigned i = 0; i < num; i++) {
            sorted[i] = qextractmin(q);
        }
    }
    if (num <= 100) {
        printf("Sorted data:\n");
        for (unsigned i = 0; i < num; i++) {
            printf("%u, ", sorted[i]);
        }
        printf("\n");
    }
    free(sorted);
    sorted = calloc(num, sizeof(unsigned));
    profile("Alternate (simulates timer queue)") {
        for (unsigned i = 0; i < num / 100; i++) {
            for (unsigned j = 0; j < 100; j++) { // insert a hundred elements, simulating timers
                qinsert(q, arr[i*100 + j]);
            }
            for (unsigned j = 0; j < 50; j++) { // only some are ready
                sorted[i*50+j] = qextractmin(q);
            }
        }
        unsigned i = num / 2; // 100 / 50 = 2
        while (q->stack.pivots[0] != q->idx) { // handle the rest of the timers
            sorted[i] = qextractmin(q);
            i++;
        }
    }
    if (num <= 100) {
        printf("Sorted data:\n");
        for (unsigned i = 0; i < num; i++) {
            printf("%u, ", sorted[i]);
        }
        printf("\n");
    }
    free(sorted);

    return 0;
}