bounded deque

deque.c

#include <stdlib.h>
#include <assert.h>

typedef struct deque
{
    int left, right;
    int size;
    void **data;
} deque;

void initdeque(deque *d, int size)
{
    d->left = d->right = 0;
    d->size = size;
    d->data = malloc(size * sizeof(void *));
}

#define WRAP(i, n) (i < n ? i : i - n)

void pushleft(deque *d, void *x)
{
    assert(d->right - d->left != d->size);

    d->left--;
    if (d->left < 0) {
        d->left += d->size;
        d->right += d->size;
    }

    d->data[WRAP(d->left, d->size)] = x;
}

void pushright(deque *d, void *x)
{
    assert(d->right - d->left != d->size);

    int i = d->right++;
    if (d->right >= 2 * d->size) {
        d->left -= d->size;
        d->right -= d->size;
    }

    d->data[WRAP(i, d->size)] = x;
}

void *popleft(deque *d, void *x)
{
    assert(d->left != d->right);

    int i = d->left++;
    return d->data[WRAP(i, d->size)];
}

void *popright(deque *d, void *x)
{
    assert(d->left != d->right);

    d->right--;
    return d->data[WRAP(d->right, d->size)];
}

#undef WRAP