Neustart der Implementierung von Deque's

1 files changed, 21 insertions, 103 deletions

diff --git a/deque.c b/deque.c
index 7125764..22e2d82 100644
--- a/deque.c
+++ b/deque.c
@@ -1,125 +1,43 @@
+#include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
-#include <stdbool.h>
 
-#define NELEM(x)        (sizeof(x) / sizeof(x[0]))
+#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)];
-}
-
-/* ================= */
+#define START_CAPACITY 8
 
 struct deque {
-        int head, tail, capacity;
-
-        struct chunk **chunks;
+        T **   chunks;
+        size_t head;
+        size_t tail;
+        size_t capacity;
 };
 
 void
 deque_init(struct deque *d)
 {
-        int i;
-
-        d->head = 0;
-        d->tail = 0;
-        d->capacity = 1;
+        d->head     = 0;
+        d->tail     = 0;
+        d->capacity = START_CAPACITY;
 
-        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]);
-        }
+        d->chunks = calloc(d->capacity, sizeof(*d->chunks));
 }
 
-
-int main(void)
+void
+deque_free(struct deque *d)
 {
-        struct chunk c;
-        int data;
-
-        chunk_init(&c);
+        free(d->chunks);
+}
 
-        chunk_put(&c, '0');
-        chunk_put(&c, '0');
-        chunk_get(&c, &data);
-        chunk_get(&c, &data);
+int
+main(void)
+{
+        struct deque c;
 
-        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');
+        deque_init(&c);
+        deque_free(&c);
 
-        printf("head: %d -- tail: %d -- size: %d\n", c.head, c.tail, chunk_size(&c));
         return 0;
 }
-