erster Commit

1 files changed, 125 insertions, 0 deletions

diff --git a/deque.c b/deque.c
new file mode 100644
index 0000000..7125764
--- /dev/null
+++ b/deque.c
@@ -0,0 +1,125 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+#define NELEM(x)        (sizeof(x) / sizeof(x[0]))
+
+typedef int T;
+
+struct chunk {
+        int head, tail;
+        T array[8];
+};
+
+static void
+chunk_init(struct chunk *c)
+{
+        c->head = 0;
+        c->tail = 0;
+}
+
+static bool
+chunk_put(struct chunk *c, T data)
+{
+        const int next = (c->head + 1) % NELEM(c->array);
+
+        if ( next == c->tail )  /* full? */
+                return false;
+
+        c->array[c->head] = data;
+        c->head = next;
+
+        return true;
+}
+
+static bool
+chunk_get(struct chunk *c, T *data)
+{
+        if ( c->head == c->tail )       /* empty? */
+                return false;
+
+        const int next = (c->tail + 1) % NELEM(c->array);
+
+        *data = c->array[c->tail];
+        c->tail = next;
+
+        return true;
+}
+
+static int
+chunk_size(struct chunk *c)
+{
+        return (c->head + NELEM(c->array) - c->tail) % NELEM(c->array);
+}
+
+static bool
+chunk_full(struct chunk *c)
+{
+        return ((c->head + 1) % NELEM(c->array)) == c->tail;
+}
+
+static bool
+chunk_empty(struct chunk *c)
+{
+        return c->head == c->tail;
+}
+
+static T*
+chunk_at(struct chunk *c, int idx)
+{
+        if ( idx < 0 || idx >= chunk_size(c) )  /* invalid index? */
+                return NULL;
+
+        return &c->array[(c->head + idx) % NELEM(c->array)];
+}
+
+/* ================= */
+
+struct deque {
+        int head, tail, capacity;
+
+        struct chunk **chunks;
+};
+
+void
+deque_init(struct deque *d)
+{
+        int i;
+
+        d->head = 0;
+        d->tail = 0;
+        d->capacity = 1;
+
+        d->chunks = calloc(d->capacity, sizeof(struct chunk *));
+
+        for ( i = 0; i != d->capacity; ++i ) {
+                d->chunks[i] = malloc(sizeof(struct chunk));
+                chunk_init(d->chunks[i]);
+        }
+}
+
+
+int main(void)
+{
+        struct chunk c;
+        int data;
+
+        chunk_init(&c);
+
+        chunk_put(&c, '0');
+        chunk_put(&c, '0');
+        chunk_get(&c, &data);
+        chunk_get(&c, &data);
+
+        chunk_put(&c, 'A');
+        chunk_put(&c, 'B');
+        chunk_put(&c, 'C');
+        chunk_put(&c, 'D');
+        chunk_put(&c, 'E');
+        chunk_put(&c, 'F');
+        chunk_put(&c, 'G');
+
+        printf("head: %d -- tail: %d -- size: %d\n", c.head, c.tail, chunk_size(&c));
+        return 0;
+}
+