From 024cb7031b29c3d6b2f3a42ca18116195d30ea61 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Wed, 12 Aug 2020 17:35:02 +0200
Subject: Neustart der Implementierung von Deque's

---
 deque.c | 124 +++++++++++-----------------------------------------------------
 1 file changed, 21 insertions(+), 103 deletions(-)

(limited to 'deque.c')

diff --git a/deque.c b/deque.c
index 7125764..22e2d82 100644
--- a/deque.c
+++ b/deque.c
@@ -1,125 +1,43 @@
+#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];
-};
-
-static void
-chunk_init(struct chunk *c)
-{
-	c->head = 0;
-	c->tail = 0;
-}
-
-static bool
-chunk_put(struct chunk *c, T data)
-{
-	const int next = (c->head + 1) % NELEM(c->array);
-
-	if ( next == c->tail )	/* full? */
-		return false;
-
-	c->array[c->head] = data;
-	c->head = next;
-
-	return true;
-}
-
-static bool
-chunk_get(struct chunk *c, T *data)
-{
-	if ( c->head == c->tail )	/* empty? */
-		return false;
-
-	const int next = (c->tail + 1) % NELEM(c->array);
-
-	*data = c->array[c->tail];
-	c->tail = next;
-
-	return true;
-}
-
-static int
-chunk_size(struct chunk *c)
-{
-	return (c->head + NELEM(c->array) - c->tail) % NELEM(c->array);
-}
-
-static bool
-chunk_full(struct chunk *c)
-{
-	return ((c->head + 1) % NELEM(c->array)) == c->tail;
-}
-
-static bool
-chunk_empty(struct chunk *c)
-{
-	return c->head == c->tail;
-}
-
-static T*
-chunk_at(struct chunk *c, int idx)
-{
-	if ( idx < 0 || idx >= chunk_size(c) )	/* invalid index? */
-		return NULL;
-
-	return &c->array[(c->head + idx) % NELEM(c->array)];
-}
-
-/* ================= */
+#define START_CAPACITY 8
 
 struct deque {
-	int head, tail, capacity;
-
-	struct chunk **chunks;
+	T **   chunks;
+	size_t head;
+	size_t tail;
+	size_t capacity;
 };
 
 void
 deque_init(struct deque *d)
 {
-	int i;
-
-	d->head = 0;
-	d->tail = 0;
-	d->capacity = 1;
+	d->head     = 0;
+	d->tail     = 0;
+	d->capacity = START_CAPACITY;
 
-	d->chunks = calloc(d->capacity, sizeof(struct chunk *));
-
-	for ( i = 0; i != d->capacity; ++i ) {
-		d->chunks[i] = malloc(sizeof(struct chunk));
-		chunk_init(d->chunks[i]);
-	}
+	d->chunks = calloc(d->capacity, sizeof(*d->chunks));
 }
 
-
-int main(void)
+void
+deque_free(struct deque *d)
 {
-	struct chunk c;
-	int data;
-
-	chunk_init(&c);
+	free(d->chunks);
+}
 
-	chunk_put(&c, '0');
-	chunk_put(&c, '0');
-	chunk_get(&c, &data);
-	chunk_get(&c, &data);
+int
+main(void)
+{
+	struct deque 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_init(&c);
+	deque_free(&c);
 
-	printf("head: %d -- tail: %d -- size: %d\n", c.head, c.tail, chunk_size(&c));
 	return 0;
 }
-
-- 
cgit v1.3