1 files changed, 111 insertions, 9 deletions

diff --git a/deque.c b/deque.c
index 903f64f..6cf114d 100644
--- a/deque.c
+++ b/deque.c
@@ -6,29 +6,114 @@
 
 typedef int T;
 
-#define START_CAPACITY 8
+#define START_MAP_CAPACITY 4
+#define CHUNK_CAPACITY 10
 
 struct deque {
-        T **   chunks;
-        size_t head;
-        size_t tail;
+        T **map;
+
+        size_t first_chunk;
+        size_t last_chunk;
+
         size_t capacity;
 };
 
 void
 deque_init(struct deque *d)
 {
-        d->head     = 0;
-        d->tail     = 0;
-        d->capacity = START_CAPACITY;
+        d->first_chunk = 0;
+        d->last_chunk  = 0;
 
-        d->chunks = calloc(d->capacity, sizeof *d->chunks);
+        // TODO: Error handling
+        d->map = calloc(START_MAP_CAPACITY, sizeof *d->map);
+        if ( d->map != NULL ) {
+                d->capacity = START_MAP_CAPACITY;
+
+                for ( size_t i = 0; i != d->capacity; ++i ) {
+                        d->map[i] = NULL;
+                }
+        }
 }
 
 void
 deque_free(struct deque *d)
 {
-        free(d->chunks);
+        // free all chunks
+        for ( size_t i = 0; i != d->capacity; ++i ) {
+                free(d->map[i]);
+        }
+
+        // free the map itself
+        free(d->map);
+}
+
+static void
+grow_map(struct deque *d)
+{
+        const size_t capacity = d->capacity + (d->capacity / 2);
+        T **         map      = calloc(capacity, sizeof *map);
+
+        // copy elements
+        size_t i;
+        for ( i = 0; i != d->capacity; ++i ) {
+                map[i] = d->map[(i + d->first_chunk) % d->capacity];
+        }
+
+        // initialize the rest (new) elements with NULL
+        for ( ; i != capacity; ++i ) {
+                map[i] = NULL;
+        }
+
+        // free old & assign new map
+        free(d->map);
+        d->map = map;
+
+        // adjust pointers
+        d->first_chunk = 0;
+        d->last_chunk  = d->capacity - 1;
+
+        // set new capacity
+        d->capacity = capacity;
+}
+
+static void
+append_chunk(struct deque *d)
+{
+        size_t next = (d->last_chunk + 1) % d->capacity;
+
+        if ( next == d->first_chunk ) { // Resize the map
+                grow_map(d);
+
+                next = d->last_chunk + 1;
+        }
+
+        d->map[d->last_chunk] = calloc(CHUNK_CAPACITY, sizeof **d->map);
+        d->last_chunk         = next;
+}
+
+static void
+prepend_chunk(struct deque *d)
+{
+        size_t prev = (d->first_chunk + d->capacity - 1) % d->capacity;
+
+        if ( prev == d->last_chunk ) {
+                grow_map(d);
+
+                prev = d->capacity - 1;
+        }
+
+        d->map[prev]   = calloc(CHUNK_CAPACITY, sizeof **d->map);
+        d->first_chunk = prev;
+}
+
+static void
+deque_show(struct deque *d)
+{
+        printf("first: %zu -- last: %zu -- capacity: %zu\n", d->first_chunk, d->last_chunk, d->capacity);
+        for ( size_t i = 0; i != d->capacity; ++i ) {
+                printf("%zu(%p) ", i, (void *) d->map[i]);
+        }
+        puts("");
 }
 
 int
@@ -37,6 +122,23 @@ main(void)
         struct deque c;
 
         deque_init(&c);
+
+        deque_show(&c);
+        append_chunk(&c);
+        deque_show(&c);
+        append_chunk(&c);
+        deque_show(&c);
+        append_chunk(&c);
+        deque_show(&c);
+        prepend_chunk(&c);
+        deque_show(&c);
+        append_chunk(&c);
+        deque_show(&c);
+        prepend_chunk(&c);
+        deque_show(&c);
+        prepend_chunk(&c);
+        deque_show(&c);
+
         deque_free(&c);
 
         return 0;