Erste Version der DEQUE kann Elemente aufnehemen und wieder entfernen.

1 files changed, 96 insertions, 19 deletions

diff --git a/deque.c b/deque.c
index 6cf114d..070040b 100644
--- a/deque.c
+++ b/deque.c
@@ -7,7 +7,7 @@
 typedef int T;
 
 #define START_MAP_CAPACITY 4
-#define CHUNK_CAPACITY 10
+#define CHUNK_CAPACITY 17
 
 struct deque {
         T **map;
@@ -15,6 +15,8 @@ struct deque {
         size_t first_chunk;
         size_t last_chunk;
 
+        size_t start;
+        size_t size;
         size_t capacity;
 };
 
@@ -23,6 +25,8 @@ deque_init(struct deque *d)
 {
         d->first_chunk = 0;
         d->last_chunk  = 0;
+        d->start       = 0;
+        d->size        = 0;
 
         // TODO: Error handling
         d->map = calloc(START_MAP_CAPACITY, sizeof *d->map);
@@ -50,7 +54,7 @@ deque_free(struct deque *d)
 static void
 grow_map(struct deque *d)
 {
-        const size_t capacity = d->capacity + (d->capacity / 2);
+        const size_t capacity = d->capacity + d->capacity / 2;
         T **         map      = calloc(capacity, sizeof *map);
 
         // copy elements
@@ -77,7 +81,7 @@ grow_map(struct deque *d)
 }
 
 static void
-append_chunk(struct deque *d)
+map_append_chunk(struct deque *d)
 {
         size_t next = (d->last_chunk + 1) % d->capacity;
 
@@ -92,7 +96,7 @@ append_chunk(struct deque *d)
 }
 
 static void
-prepend_chunk(struct deque *d)
+map_prepend_chunk(struct deque *d)
 {
         size_t prev = (d->first_chunk + d->capacity - 1) % d->capacity;
 
@@ -107,9 +111,86 @@ prepend_chunk(struct deque *d)
 }
 
 static void
+map_remove_front_chunk(struct deque *d)
+{
+        if ( d->first_chunk == d->last_chunk )
+                return;
+
+        const size_t next = (d->first_chunk + 1) % d->capacity;
+
+        free(d->map[d->first_chunk]);
+        d->map[d->first_chunk] = NULL;
+
+        d->first_chunk = next;
+}
+
+static void
+map_remove_tail_chunk(struct deque *d)
+{
+        if ( d->first_chunk == d->last_chunk )
+                return;
+
+        const size_t prev = (d->last_chunk + d->capacity - 1) % d->capacity;
+
+        free(d->map[prev]);
+        d->map[prev] = NULL;
+
+        d->last_chunk = prev;
+}
+
+void
+deque_get_at(struct deque *d, size_t idx, T *data)
+{
+        const size_t offset    = d->start + idx;
+        const size_t chunk_off = offset % CHUNK_CAPACITY;
+        const size_t chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity;
+
+        *data = d->map[chunk_num][chunk_off];
+}
+
+void
+deque_push_back(struct deque *d, T data)
+{
+        const size_t offset    = d->start + d->size;
+        const size_t chunk_off = offset % CHUNK_CAPACITY;
+        size_t       chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity;
+
+        if ( chunk_num == d->last_chunk ) {
+                map_append_chunk(d);
+                chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity;
+        }
+
+        d->map[chunk_num][chunk_off] = data;
+        ++d->size;
+}
+
+bool
+deque_pop_front(struct deque *d, T *data)
+{
+        if ( d->size == 0 )
+                return false;
+
+        const size_t chunk_off = d->start % CHUNK_CAPACITY;
+        const size_t chunk_num = ((d->start / CHUNK_CAPACITY) + d->first_chunk) % d->capacity;
+
+        *data = d->map[chunk_num][chunk_off];
+
+        --d->size;
+        ++d->start;
+
+        if ( d->size == 0 || d->start == CHUNK_CAPACITY ) {
+                map_remove_front_chunk(d);
+                d->start = 0;
+        }
+
+        return true;
+}
+
+static void
 deque_show(struct deque *d)
 {
-        printf("first: %zu -- last: %zu -- capacity: %zu\n", d->first_chunk, d->last_chunk, d->capacity);
+        printf("first: %zu -- last: %zu -- size: %zu -- capacity: %zu -- start: %zu\n",
+               d->first_chunk, d->last_chunk, d->size, d->capacity, d->start);
         for ( size_t i = 0; i != d->capacity; ++i ) {
                 printf("%zu(%p) ", i, (void *) d->map[i]);
         }
@@ -123,20 +204,16 @@ main(void)
 
         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);
+        for ( int i = 0; i != 100; ++i ) {
+                deque_push_back(&c, i);
+                //deque_show(&c);
+        }
+
+        T data;
+        while ( deque_pop_front(&c, &data) ) {
+                printf("%u, ", data);
+        }
+        putchar('\n');
         deque_show(&c);
 
         deque_free(&c);