neue Verzeichnisstruktur

1 files changed, 485 insertions, 0 deletions

diff --git a/src/deque.c b/src/deque.c
new file mode 100644
index 0000000..881d1d3
--- /dev/null
+++ b/src/deque.c
@@ -0,0 +1,485 @@
+#include <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "util.h"
+
+#define START_MAP_CAPACITY 4
+#define CHUNK_CAPACITY 17
+
+/* --8<-- deque_type */
+typedef int T;
+
+struct deque {
+        T **map;
+
+        size_t map_begin;
+        size_t map_end;
+        size_t map_capacity;
+
+        size_t offset;
+        size_t size;
+};
+/* -->8-- */
+
+/* --8<-- deque_allocate */
+static void *
+allocate(size_t n, size_t sz)
+{
+        void *ptr = calloc(n, sz);
+        if ( ptr == NULL ) {
+                ERROR("out of memory!");
+        }
+        return ptr;
+}
+/* -->8-- */
+
+/* --8<-- deque_init */
+void
+deque_init(struct deque *d)
+{
+        assert(d);
+
+        d->map_begin = 0;
+        d->map_end   = 0;
+        d->offset    = 0;
+        d->size      = 0;
+
+        // TODO: Error handling
+        d->map = allocate(START_MAP_CAPACITY, sizeof *d->map);
+        if ( d->map ) {
+                d->map_capacity = START_MAP_CAPACITY;
+
+                for ( size_t i = 0; i != d->map_capacity; ++i ) {
+                        d->map[i] = NULL;
+                }
+        }
+}
+/* -->8-- */
+
+/* --8<-- deque_free */
+void
+deque_free(struct deque *d)
+{
+        assert(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;
+}
+/* -->8-- */
+
+/* --8<-- deque_size */
+size_t
+deque_size(struct deque *d)
+{
+        assert(d);
+
+        return d->size;
+}
+/* -->8-- */
+
+/* --8<-- deque_is_empty */
+bool
+deque_is_empty(struct deque *d)
+{
+        assert(d);
+
+        return d->map_begin == d->map_end;
+}
+/* -->8-- */
+
+/* --8<-- deque_grow_map */
+static void
+grow_map(struct deque *d)
+{
+        assert(d);
+
+        const size_t capacity = d->map_capacity + d->map_capacity / 2;
+        T **         map      = allocate(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;
+}
+/* -->8-- */
+
+/* --8<-- deque_map_append_chunk */
+static void
+map_append_chunk(struct deque *d)
+{
+        assert(d);
+
+        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] = allocate(CHUNK_CAPACITY, sizeof **d->map);
+        d->map_end         = next;
+}
+/* -->8-- */
+
+/* --8<-- deque_map_prepend_chunk */
+static void
+map_prepend_chunk(struct deque *d)
+{
+        assert(d);
+
+        size_t prev = (d->map_begin + d->map_capacity - 1) % d->map_capacity;
+
+        if ( prev == d->map_end ) {
+                grow_map(d);
+
+                prev = d->map_capacity - 1;
+        }
+
+        d->map[prev] = allocate(CHUNK_CAPACITY, sizeof **d->map);
+        d->map_begin = prev;
+}
+/* -->8-- */
+
+/* --8<-- deque_map_remove_front_chunk */
+static void
+map_remove_front_chunk(struct deque *d)
+{
+        assert(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;
+}
+/* -->8-- */
+
+/* --8<-- deque_remove_tail_chunk */
+static void
+map_remove_tail_chunk(struct deque *d)
+{
+        assert(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;
+}
+/* -->8-- */
+
+/* --8<-- deque_get_at */
+bool
+deque_get_at(struct deque *d, size_t idx, T *data)
+{
+        assert(d);
+        assert(idx < d->size);
+        assert(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;
+
+        *data = d->map[chunk_num][chunk_off];
+
+        return true;
+}
+/* -->8-- */
+
+/* --8<-- deque_set_at */
+bool
+deque_set_at(struct deque *d, size_t idx, T data)
+{
+        assert(d);
+        assert(idx < d->size);
+
+        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;
+
+        d->map[chunk_num][chunk_off] = data;
+
+        return true;
+}
+/* -->8-- */
+
+/* --8<-- deque_push_back */
+void
+deque_push_back(struct deque *d, T data)
+{
+        assert(d);
+
+        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;
+}
+/* -->8-- */
+
+/* --8<-- deque_push_front */
+void
+deque_push_front(struct deque *d, T data)
+{
+        assert(d);
+
+        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;
+}
+/* -->8-- */
+
+/* --8<-- deque_pop_back */
+bool
+deque_pop_back(struct deque *d, T *data)
+{
+        assert(d);
+        assert(data);
+
+        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;
+}
+/* -->8-- */
+
+/* --8<-- deque_pop_front */
+bool
+deque_pop_front(struct deque *d, T *data)
+{
+        assert(d);
+        assert(data);
+
+        if ( d->size == 0 ) {
+                return false;
+        }
+
+        --d->size;
+
+        const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;
+
+        *data = d->map[chunk_num][d->offset];
+
+        ++d->offset;
+
+        if ( d->size == 0 || d->offset == CHUNK_CAPACITY ) {
+                map_remove_front_chunk(d);
+                d->offset = 0;
+        }
+
+        return true;
+}
+/* -->8-- */
+
+static void
+deque_show(struct deque *d)
+{
+        assert(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
+test_deque(void)
+{
+#ifndef NDEBUG
+        struct deque d[1];
+
+        deque_init(d);
+
+        const int N = 100000;
+
+        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);
+        assert(deque_size(d) == 0);
+
+        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);
+        assert(deque_size(d) == 0);
+
+        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);
+        assert(deque_size(d) == 0);
+
+        deque_free(d);
+
+        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);
+        assert(deque_size(d) == 0);
+
+        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);
+        assert(deque_size(d) == 0);
+
+        deque_free(d);
+
+        puts("all tests passed.");
+#endif
+}
+
+int
+main(void)
+{
+        test_deque();
+
+        struct deque c;
+
+        deque_init(&c);
+
+        T data;
+        while ( deque_pop_front(&c, &data) ) {
+                printf("%u, ", data);
+        }
+        putchar('\n');
+        deque_show(&c);
+
+        deque_free(&c);
+
+        return 0;
+}