Merge branch 'deque'

1 files changed, 337 insertions, 67 deletions

diff --git a/deque.c b/deque.c
index 7125764..168669e 100644
--- a/deque.c
+++ b/deque.c
@@ -1,125 +1,395 @@
+#include <assert.h>
+#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];
+#define START_MAP_CAPACITY 4
+#define CHUNK_CAPACITY 17
+
+struct deque {
+        T **map;
+
+        size_t map_begin;
+        size_t map_end;
+        size_t map_capacity;
+
+        size_t offset;
+        size_t size;
 };
 
+void
+deque_init(struct deque *d)
+{
+        d->map_begin = 0;
+        d->map_end   = 0;
+        d->offset    = 0;
+        d->size      = 0;
+
+        // TODO: Error handling
+        d->map = calloc(START_MAP_CAPACITY, sizeof *d->map);
+        if ( d->map != NULL ) {
+                d->map_capacity = START_MAP_CAPACITY;
+
+                for ( size_t i = 0; i != d->map_capacity; ++i ) {
+                        d->map[i] = NULL;
+                }
+        }
+}
+
+void
+deque_free(struct deque *d)
+{
+        // free all chunks
+        for ( size_t i = 0; i != d->map_capacity; ++i ) {
+                free(d->map[i]);
+        }
+
+        // free the map itself
+        free(d->map);
+        d->map = NULL;
+}
+
+size_t
+deque_size(struct deque *d)
+{
+        return d->size;
+}
+
+bool
+deque_is_empty(struct deque *d)
+{
+        return d->map_begin == d->map_end;
+}
+
+static void
+grow_map(struct deque *d)
+{
+        const size_t capacity = d->map_capacity + d->map_capacity / 2;
+        T **         map      = calloc(capacity, sizeof *map);
+
+        // copy elements
+        size_t i, j;
+        for ( i = 0, j = d->map_begin; i != d->map_capacity; ++i, ++j ) {
+                if ( j == d->map_capacity ) {
+                        j = 0;
+                }
+                map[i] = d->map[j];
+        }
+
+        // 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->map_begin = 0;
+        d->map_end   = d->map_capacity - 1;
+
+        // set new map_capacity
+        d->map_capacity = capacity;
+}
+
 static void
-chunk_init(struct chunk *c)
+map_append_chunk(struct deque *d)
 {
-        c->head = 0;
-        c->tail = 0;
+        size_t next = (d->map_end + 1) % d->map_capacity;
+
+        if ( next == d->map_begin ) { // Resize the map
+                grow_map(d);
+
+                next = d->map_end + 1;
+        }
+
+        d->map[d->map_end] = calloc(CHUNK_CAPACITY, sizeof **d->map);
+        d->map_end         = next;
 }
 
-static bool
-chunk_put(struct chunk *c, T data)
+static void
+map_prepend_chunk(struct deque *d)
 {
-        const int next = (c->head + 1) % NELEM(c->array);
+        size_t prev = (d->map_begin + d->map_capacity - 1) % d->map_capacity;
 
-        if ( next == c->tail )  /* full? */
+        if ( prev == d->map_end ) {
+                grow_map(d);
+
+                prev = d->map_capacity - 1;
+        }
+
+        d->map[prev] = calloc(CHUNK_CAPACITY, sizeof **d->map);
+        d->map_begin = prev;
+}
+
+static void
+map_remove_front_chunk(struct deque *d)
+{
+        if ( d->map_begin == d->map_end ) {
+                return;
+        }
+
+        const size_t next = (d->map_begin + 1) % d->map_capacity;
+
+        free(d->map[d->map_begin]);
+        d->map[d->map_begin] = NULL;
+
+        d->map_begin = next;
+}
+
+static void
+map_remove_tail_chunk(struct deque *d)
+{
+        if ( d->map_begin == d->map_end ) {
+                return;
+        }
+
+        const size_t prev = (d->map_end + d->map_capacity - 1) % d->map_capacity;
+
+        free(d->map[prev]);
+        d->map[prev] = NULL;
+
+        d->map_end = prev;
+}
+
+bool
+deque_get_at(struct deque *d, size_t idx, T *data)
+{
+        if ( idx >= d->size ) {
                 return false;
+        }
+
+        const size_t pos       = d->offset + idx;
+        const size_t chunk_off = pos % CHUNK_CAPACITY;
+        const size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;
 
-        c->array[c->head] = data;
-        c->head = next;
+        *data = d->map[chunk_num][chunk_off];
 
         return true;
 }
 
-static bool
-chunk_get(struct chunk *c, T *data)
+bool
+deque_set_at(struct deque *d, size_t idx, T data)
 {
-        if ( c->head == c->tail )       /* empty? */
+        if ( idx >= d->size ) {
                 return false;
+        }
 
-        const int next = (c->tail + 1) % NELEM(c->array);
+        const size_t pos       = d->offset + idx;
+        const size_t chunk_off = pos % CHUNK_CAPACITY;
+        const size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;
 
-        *data = c->array[c->tail];
-        c->tail = next;
+        d->map[chunk_num][chunk_off] = data;
 
         return true;
 }
 
-static int
-chunk_size(struct chunk *c)
+void
+deque_push_back(struct deque *d, T data)
 {
-        return (c->head + NELEM(c->array) - c->tail) % NELEM(c->array);
+        const size_t pos       = d->offset + d->size;
+        const size_t chunk_off = pos % CHUNK_CAPACITY;
+        size_t       chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;
+
+        if ( chunk_num == d->map_end ) {
+                map_append_chunk(d);
+                chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;
+        }
+
+        d->map[chunk_num][chunk_off] = data;
+        ++d->size;
 }
 
-static bool
-chunk_full(struct chunk *c)
+void
+deque_push_front(struct deque *d, T data)
 {
-        return ((c->head + 1) % NELEM(c->array)) == c->tail;
+        if ( d->offset == 0 ) { // Im ersten Element ist kein Platz mehr frei!
+                map_prepend_chunk(d);
+                d->offset = CHUNK_CAPACITY;
+        }
+
+        --d->offset;
+
+        const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;
+
+        d->map[chunk_num][d->offset] = data;
+        ++d->size;
 }
 
-static bool
-chunk_empty(struct chunk *c)
+bool
+deque_pop_back(struct deque *d, T *data)
 {
-        return c->head == c->tail;
+        if ( d->size == 0 ) {
+                return false;
+        }
+
+        --d->size;
+
+        const size_t pos       = d->offset + d->size;
+        const size_t chunk_off = pos % CHUNK_CAPACITY;
+        const size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;
+
+        *data = d->map[chunk_num][chunk_off];
+
+        if ( d->size == 0 || chunk_off == 0 ) {
+                map_remove_tail_chunk(d);
+        }
+
+        return true;
 }
 
-static T*
-chunk_at(struct chunk *c, int idx)
+bool
+deque_pop_front(struct deque *d, T *data)
 {
-        if ( idx < 0 || idx >= chunk_size(c) )  /* invalid index? */
-                return NULL;
+        if ( d->size == 0 ) {
+                return false;
+        }
 
-        return &c->array[(c->head + idx) % NELEM(c->array)];
-}
+        --d->size;
 
-/* ================= */
+        const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;
 
-struct deque {
-        int head, tail, capacity;
+        *data = d->map[chunk_num][d->offset];
 
-        struct chunk **chunks;
-};
+        ++d->offset;
+
+        if ( d->size == 0 || d->offset == CHUNK_CAPACITY ) {
+                map_remove_front_chunk(d);
+                d->offset = 0;
+        }
+
+        return true;
+}
+
+static void
+deque_show(struct deque *d)
+{
+        printf("first: %zu -- last: %zu -- size: %zu -- map_capacity: %zu -- offset: %zu\n",
+               d->map_begin, d->map_end, d->size, d->map_capacity, d->offset);
+        for ( size_t i = 0; i != d->map_capacity; ++i ) {
+                printf("%zu(%p) ", i, (void *) d->map[i]);
+        }
+        putchar('\n');
+}
 
 void
-deque_init(struct deque *d)
+test_deque(void)
 {
-        int i;
+        struct deque d[1];
 
-        d->head = 0;
-        d->tail = 0;
-        d->capacity = 1;
+        deque_init(d);
 
-        d->chunks = calloc(d->capacity, sizeof(struct chunk *));
+        const int N = 10000000;
 
-        for ( i = 0; i != d->capacity; ++i ) {
-                d->chunks[i] = malloc(sizeof(struct chunk));
-                chunk_init(d->chunks[i]);
+        for ( int i = 0; i != N; ++i ) {
+                deque_push_front(d, i);
         }
-}
 
+        for ( int i = 0; i != N; ++i ) {
+                int data;
+                assert(deque_pop_back(d, &data) == true);
+                assert(data == i);
+        }
+        assert(deque_is_empty(d) == true);
+
+        deque_free(d);
+
+        deque_init(d);
+
+        for ( int i = 0; i != N; ++i ) {
+                deque_push_back(d, i);
+        }
+
+        for ( int i = 0; i != N; ++i ) {
+                int data;
+                assert(deque_pop_front(d, &data) == true);
+                assert(data == i);
+        }
+        assert(deque_is_empty(d) == true);
+
+        deque_free(d);
+
+        deque_init(d);
+
+        for ( int i = 0; i != N; ++i ) {
+                deque_push_back(d, i);
+        }
+
+        for ( int i = N - 1; i >= 0; --i ) {
+                int data;
+                assert(deque_pop_back(d, &data) == true);
+                assert(data == i);
+        }
+        assert(deque_is_empty(d) == true);
+
+        deque_free(d);
 
-int main(void)
+        deque_init(d);
+
+        for ( int i = 0; i != N; ++i ) {
+                if ( i & 1 ) {
+                        deque_push_front(d, i);
+                }
+                else {
+                        deque_push_back(d, i);
+                }
+        }
+
+        for ( int i = N - 1; i >= 0; --i ) {
+                int data;
+                if ( i & 1 ) {
+                        assert(deque_pop_front(d, &data) == true);
+                }
+                else {
+                        assert(deque_pop_back(d, &data) == true);
+                }
+                if ( data != i ) {
+                        printf("i: %d - data: %d\n", i, data);
+                }
+                assert(data == i);
+        }
+        assert(deque_is_empty(d) == true);
+
+        deque_free(d);
+
+        deque_init(d);
+
+        for ( int i = 0; i != N; ++i ) {
+                deque_push_front(d, i);
+        }
+
+        for ( int i = N - 1; i >= 0; --i ) {
+                int data;
+                assert(deque_pop_front(d, &data) == true);
+                assert(data == i);
+        }
+        assert(deque_is_empty(d) == true);
+
+        deque_free(d);
+}
+
+int
+main(void)
 {
-        struct chunk c;
-        int data;
+        test_deque();
+
+        struct deque c;
 
-        chunk_init(&c);
+        deque_init(&c);
 
-        chunk_put(&c, '0');
-        chunk_put(&c, '0');
-        chunk_get(&c, &data);
-        chunk_get(&c, &data);
+        T data;
+        while ( deque_pop_front(&c, &data) ) {
+                printf("%u, ", data);
+        }
+        putchar('\n');
+        deque_show(&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_free(&c);
 
-        printf("head: %d -- tail: %d -- size: %d\n", c.head, c.tail, chunk_size(&c));
         return 0;
 }
-