From 13fbe29897cd85d95fb40dc221e833a058813b57 Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Thu, 25 Aug 2016 17:46:05 +0200
Subject: [PATCH] add linkedlist variant

---
 .gitignore |   2 ++
 Makefile   |   7 ++--
 README.md  |   6 ++--
 bfll.c     | 100 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 110 insertions(+), 5 deletions(-)
 create mode 100644 bfll.c

diff --git a/.gitignore b/.gitignore
index 292a768..4ad8ecb 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1 +1,3 @@
 bf
+bfll
+*.bf
diff --git a/Makefile b/Makefile
index 15107c0..05499c6 100644
--- a/Makefile
+++ b/Makefile
@@ -1,6 +1,7 @@
-PROGRAM:=bf
+CFLAGS:=-g
+PROGRAMS:=bf bfll
 
-all: $(PROGRAM)
+all: $(PROGRAMS)
 
 clean:
-	$(RM) -v $(PROGRAM)
+	$(RM) -v $(PROGRAMS)
diff --git a/README.md b/README.md
index bf6671f..31f4728 100644
--- a/README.md
+++ b/README.md
@@ -1,7 +1,9 @@
 # bf, a brainfuck interpreter
 ### Description
 This is my implementation of a [brainfuck][bf] interpreter. It uses a
-potentially infinite stack by reallocating more when necessary.
+potentially infinite stack by reallocating more when necessary. `bf` is an
+implementation with arrays, `bfll` is an implementation where the tape is a
+doubly linked list.
 
 ### Installation
 Compiling is as easy as running `make`
@@ -10,7 +12,7 @@ Cleaning up the mess can be done by running `make clean`
 
 ### Usage
 Say you have a file containing a program on disk called `hello.bf`. Then you
-can run the file by running `./bf hello.bf`.
+can run the file by running `./bf hello.bf` or `./bfll hello.bf`.
 
 ### License
 Do what ever you want with this code.
diff --git a/bfll.c b/bfll.c
new file mode 100644
index 0000000..dfbc456
--- /dev/null
+++ b/bfll.c
@@ -0,0 +1,100 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <errno.h>
+
+#define die(s, as...) {fprintf(stderr, s, ## as); return EXIT_FAILURE;}
+#define check_fail(v, s, f) if((v) == f) die("%s(): %s\n", s, strerror(errno))
+#define check_null(v, s) check_fail(v, s, NULL)
+
+#define INITIALBUFSIZE 2
+
+struct buf {
+	char v;
+	struct buf *n, *p;
+};
+
+struct cs {
+	long pl;
+	struct cs *next;
+};
+
+int main(int argc, char *argv[])
+{
+	size_t depth;
+	struct buf *p;
+	struct cs *temp, *cs;
+	FILE *in;
+
+	if(argc != 2)
+		die("Usage: %s PROGRAM\n", argv[0]);
+   
+	check_null(in = fopen(argv[1], "r"), "fopen");
+	check_null(p = calloc(sizeof (struct buf), 1), "calloc");
+
+	while (1){
+		switch (fgetc(in)){
+		case EOF:
+			check_fail(fclose(in), "fclose", -1);
+			while(p->p != NULL)
+				p = p->p;
+			while(p->n != NULL)
+				free((p = p->n)->p);
+			free(p);
+			return EXIT_SUCCESS;
+		case '>':
+			if(p->n == NULL){
+				check_null(p->n = calloc(
+					sizeof (struct buf), 1), "calloc");
+				p->n->p = p;
+			}
+			p = p->n;
+			break;
+		case '<':
+			if(p->p == NULL){
+				check_null(p->p = calloc(
+					sizeof (struct buf), 1), "calloc");
+				p->p->n = p;
+			}
+			p = p->p;
+			break;
+		case '+':
+			++(p->v);
+			break;
+		case '-':
+			--(p->v);
+			break;
+		case '.':
+			putchar(p->v);
+			break;
+		case ',':
+			p->v = getchar();
+			break;
+		case '[':
+			if (p->v){
+				temp = cs;
+				check_null(cs = malloc(
+					sizeof(struct cs)), "malloc");
+				cs->next = temp;
+				check_fail(cs->pl = ftell(in), "ftell", -1);
+			} else {
+				depth = 1;
+				while (depth > 0){
+					switch (fgetc(in)){
+					case ']':
+						depth--;
+						break;
+					case '[':
+						depth++;
+					}
+				}
+			}
+			break;
+		case ']':
+			check_fail(fseek(in, cs->pl-1, SEEK_SET), "fseek", -1);
+			temp = cs;
+			cs = cs->next;
+			free(temp);
+		}
+	}
+}
-- 
2.20.1