From ac55496d881e0a17b3eff85f1faae5aafbc53b50 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Wed, 22 Jul 2020 17:30:45 +0200
Subject: erster Commit

---
 deque.c | 125 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 125 insertions(+)
 create mode 100644 deque.c

(limited to 'deque.c')

diff --git a/deque.c b/deque.c
new file mode 100644
index 0000000..7125764
--- /dev/null
+++ b/deque.c
@@ -0,0 +1,125 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+#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)];
+}
+
+/* ================= */
+
+struct deque {
+	int head, tail, capacity;
+
+	struct chunk **chunks;
+};
+
+void
+deque_init(struct deque *d)
+{
+	int i;
+
+	d->head = 0;
+	d->tail = 0;
+	d->capacity = 1;
+
+	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]);
+	}
+}
+
+
+int main(void)
+{
+	struct chunk c;
+	int data;
+
+	chunk_init(&c);
+
+	chunk_put(&c, '0');
+	chunk_put(&c, '0');
+	chunk_get(&c, &data);
+	chunk_get(&c, &data);
+
+	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');
+
+	printf("head: %d -- tail: %d -- size: %d\n", c.head, c.tail, chunk_size(&c));
+	return 0;
+}
+
-- 
cgit v1.3