From 9990de5ea16ed1f6c6df647a9dd43f7c4f5f2653 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Fri, 14 Aug 2020 17:44:55 +0200
Subject: Erste Version der DEQUE kann Elemente aufnehemen und wieder
 entfernen.

---
 deque.c | 115 +++++++++++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file 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;
 
@@ -106,10 +110,87 @@ prepend_chunk(struct deque *d)
 	d->first_chunk = prev;
 }
 
+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);
-- 
cgit v1.3