From 69e65c19890a9e6128cf06b5ae9b03c31b18f304 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Thu, 13 Aug 2020 17:11:22 +0200
Subject: Sichere den Zwischenstand: Management der Chunks sollte nun
 funktionieren!

---
 deque.c | 120 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file 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;
-- 
cgit v1.3