Solve Exercise 8-8: bfree()

Well, here it is. The final solution to the final exercise! These last
few exercise solutions are not ideal by any measure of coding
excellence, but they function.

I plan to come back to this some day, with better debugging knowledge.
Then I can correct any issues.

1 files changed, 200 insertions, 0 deletions

diff --git a/ch8/8-08_bfree.c b/ch8/8-08_bfree.c
new file mode 100644
index 0000000..2414d25
--- /dev/null
+++ b/ch8/8-08_bfree.c
@@ -0,0 +1,200 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <string.h>
+#include <limits.h>
+#include <unistd.h>
+
+/* The C Programming Language: 2nd Edition
+ *
+ * Exercise 8-8: Write a routine `bfree(p,n)` that will free an arbitrary block
+ * `p` of `n` characters into the free list maintained by `malloc` and `free`.
+ * By using `bfree`, a user can add a static or external array to the free list
+ * at any time.
+ *
+ * Notes: It's unclear exactly what the goal is with bfree. It seems like it's
+ * a way to add space into the heap for a data structure before copying it to
+ * memory. I've done what I could to indicate things are being added to the
+ * free list, but the real world applications of this are not clear to me.
+ */
+
+typedef long Align;
+
+union header {
+	struct {
+		union header *ptr;
+		unsigned size;
+	} s;
+	/* unused, just for alignment */
+	Align x;
+} hdr;
+
+typedef union header Header;
+
+static Header base;
+static Header *freep = NULL;
+static Header *zmorecore(unsigned);
+void *zmalloc(unsigned);
+void zfree(void *);
+
+void *zmalloc(unsigned nbytes) {
+	if (nbytes == 0 || nbytes > (UINT_MAX - sizeof (Header))) {
+		/* cannot ask for zero memory */
+		errno = EINVAL;
+		return NULL;
+	}
+	if (nbytes < (sizeof (Header) * 2)) {
+		nbytes = sizeof (Header) * 2;
+	}
+	printf("Requesting %d bytes.\n", nbytes);
+	Header *p, *prevp;
+	unsigned nunits;
+	nunits = (nbytes + sizeof (Header) - 1) / sizeof (Header) + 1;
+	printf("%d units need allocated.\n", nunits);
+
+	if ((prevp = freep) == NULL) {
+		base.s.ptr = freep = prevp = &base;
+		base.s.size = 0;
+	}
+	for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
+		/* larger than requested units */
+		if (p->s.size >= nunits) {
+			if (p->s.size == nunits) {
+				prevp->s.ptr = p->s.ptr;
+			} else {
+				p->s.size -= nunits;
+				p += p->s.size;
+				p->s.size = nunits;
+			}
+			freep = prevp;
+			return (void *)(p+1);
+		}
+		if (p == freep) {
+			if ((p = zmorecore(nunits)) == NULL) {
+				errno = ENOMEM;
+				return NULL;
+			}
+		}
+	}
+}
+
+#define NALLOC 1024
+
+static Header *zmorecore(unsigned nu) {
+	char *cp;
+	Header *up;
+	if (nu < NALLOC) {
+		nu = NALLOC;
+	}
+	cp = sbrk(nu * sizeof (Header));
+	if (errno == ENOMEM) {
+		return NULL;
+	}
+	up = (Header *) cp;
+	up->s.size = nu;
+	zfree((void *)(up+1));
+	return freep;
+}
+
+void zfree(void *ap) {
+	if (ap == NULL) {
+		printf("Cannot free null pointer.\n");
+		errno = EINVAL;
+		return;
+	}
+	Header *bp, *p;
+	bp = (Header *)ap - 1;
+	if (bp->s.size == 0) {
+		printf("Cannot free block of size 0.\n");
+		errno = EINVAL;
+		return;
+	}
+	for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) {
+		if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) {
+			break;
+		}
+	}
+	if (bp + bp->s.size == p->s.ptr && bp->s.size < (UINT_MAX - p->s.ptr->s.size)) {
+		bp->s.size += p->s.ptr->s.size;
+		bp->s.ptr = p->s.ptr->s.ptr;
+	} else {
+		bp->s.ptr = p->s.ptr;
+	}
+	if (p + p->s.size == bp && p->s.size < (UINT_MAX - bp->s.size)) {
+		p->s.size += bp->s.size;
+		p->s.ptr = bp->s.ptr;
+	} else {
+		p->s.ptr = bp;
+	}
+	freep = p;
+}
+
+void * zcalloc(int count, unsigned size) {
+	char *p;
+	int i;
+	p = zmalloc(count * size);
+	if (p != NULL) {
+		for (i = 0; i < (count * size); i++) {
+			p[i] = '\0';
+		}
+		return p;
+	} else {
+		return (int *)(-1);
+	}
+}
+
+void bfree(void *p, unsigned n) {
+	if (p == NULL) {
+		errno = EINVAL;
+		return;
+	}
+	if (n > (UINT_MAX - sizeof (Header)) ||
+		n == 0) {
+		errno = EINVAL;
+		return;
+	}
+	if (n < sizeof (Header) * 2) {
+		printf("Buffer not large enough to be worth putting in the heap.\n");
+		return;
+	}
+	if (freep == NULL) {
+		base.s.ptr = freep = &base;
+		base.s.size = 0;
+	}
+	Header *hp = (Header *) p;
+	hp->s.size = (n / sizeof(Header)) - 1;
+	zfree((void *)(hp + 1));
+}
+
+int main(int argc, char *argv[]) {
+	char foo[sizeof (Header) * 3] = "Hello world!";
+	char *bar = zcalloc(40, sizeof (char));
+	strcpy(bar, foo);
+	printf("%s\n", bar);
+	bfree(foo, sizeof (Header) * 3);
+	if (errno == EINVAL) {
+		printf("Bad juju.\n");
+		exit(1);
+	}
+
+	bfree(bar, 40);
+	if (errno == EINVAL) {
+		printf("Bad juju.\n");
+		exit(1);
+	}
+
+	Header *i;
+	int c = 1;
+	for (i = freep; ; i = i->s.ptr, c++) {
+		if (c > 1 && i == &base ||
+			i->s.ptr == i) {
+			break;
+		}
+		printf("Header %d:\n", c);
+		printf("Address: %p\n", i);
+		printf("Size:    %d\n", i->s.size);
+		printf("Next:    %p\n", i->s.ptr);
+		printf("Data:\n%s\n", i+i->s.size+1);
+	}
+	return 0;
+}