8.8: initial commit

4 files changed, 192 insertions, 0 deletions

diff --git a/8.8/Makefile b/8.8/Makefile
new file mode 100644
index 0000000..eaa18c7
--- /dev/null
+++ b/8.8/Makefile
@@ -0,0 +1,12 @@
+OBJECTS = main.o malloc.o
+CC = gcc
+CFLAGS = -g -Wvla -Wall -Wextra -Wstrict-prototypes -Wmissing-prototypes -fsanitize=address
+
+main: $(OBJECTS)
+	$(CC) $(CFLAGS) -o main $(OBJECTS)
+
+main.o: malloc.h
+
+.PHONY: clean
+clean:
+	rm -f main $(OBJECTS)
diff --git a/8.8/main.c b/8.8/main.c
new file mode 100644
index 0000000..f4ef71e
--- /dev/null
+++ b/8.8/main.c
@@ -0,0 +1,24 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include "malloc.h"
+
+int main(void)
+{
+	char *s;
+
+	/* size of header is 16 bytes so the mem space should
+	 * be atleast 16 * 2 = 32 bytes to call bfree */
+	s = malloc(32);
+	bfree(s, 32);
+	s = my_malloc(11);
+
+	strcpy(s, "just werks");
+	printf("%s\n", s);
+
+	/* ||-16:HEADER-||||-16:FREE-|| */
+	my_free(s);
+	free(s - 16);
+
+	return 0;
+}
diff --git a/8.8/malloc.c b/8.8/malloc.c
new file mode 100644
index 0000000..df91a2d
--- /dev/null
+++ b/8.8/malloc.c
@@ -0,0 +1,150 @@
+#include <unistd.h>
+#include <stdio.h>
+#include "malloc.h"
+
+#define NALLOC		128
+#define MAX_BYTES	(size_t) 8192
+
+typedef long long Align;
+
+typedef union header {
+	struct {
+		union header *ptr;
+		size_t size;
+	} s;
+
+	Align x;
+} Header;
+
+/* see my_free
+ * static size_t maxalloc; */
+static Header base;
+static Header *freep = NULL;
+
+/* static Header *my_morecore(size_t nunits); */
+
+void *my_calloc(size_t n ,size_t size)
+{
+	char *p, *temp;
+	size_t nb;
+
+	nb = n * size;
+	if ((p = temp = my_malloc(nb)) == NULL)
+		while (nb-- > 0)
+			*temp++ = '\0';
+
+	return p;
+}
+
+void *my_malloc(size_t nbytes)
+{
+	Header *prevp, *p;
+	size_t nunits;
+
+	if (nbytes > MAX_BYTES) {
+		fprintf(stderr, "alloc:can't allocate more than %lu bytes\n",
+		      MAX_BYTES);
+		return NULL;
+	}
+
+	if ((prevp = freep) == NULL) {
+		base.s.ptr = prevp = freep = &base;
+		base.s.size = 0;
+	}
+
+	nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
+	for (p = freep->s.ptr; ; prevp = p, p = p->s.ptr) {
+		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 = my_morecore(nunits)) == NULL) \
+			* we fully rely on mem from stdlib malloc */
+			return NULL;
+	}
+
+	return NULL;
+}
+
+/* see my_free
+ * static Header *my_morecore(size_t nunits)
+ *{
+ *	Header *p;
+ *
+ *	if (nunits < NALLOC)
+ *		nunits = NALLOC;
+ *
+ *	if ((p = sbrk(nunits * sizeof(Header))) == (Header *) -1)
+ *		return NULL;
+ *
+ *	p->s.size = nunits;
+ *	if ((p->s.size = nunits) > maxalloc)
+ *	 	maxalloc = nunits;
+ *
+ *	my_free (p + 1);
+ *	return freep;
+ * } */
+
+void my_free(void *ap)
+{
+	Header *bp, *p;
+
+	bp = (Header *)ap - 1;
+
+	if (freep == NULL) {
+		base.s.ptr = freep = &base;
+		base.s.size = 0;
+	}
+
+	/* we accept random values from bfree 
+	 * if (bp->s.size == 0 || bp->s.size > maxalloc) {
+	 *	fprintf(stderr, "alloc: can't free %lu units\n", bp->s.size);
+	 *	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 += 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 += bp->s.size;
+		p->s.ptr = bp->s.ptr;
+	} else {
+		p->s.ptr = bp;
+	}
+
+	freep = p;
+}
+
+size_t bfree(void *ap, size_t n)
+{
+	Header *p;
+
+	if (n < sizeof(Header) * 2) {
+		fprintf(stderr, "bfree: can't free %lu bytes\n", n);
+		return 0;
+	}
+
+	p = (Header *) ap;
+	p->s.size = (n / sizeof(Header));
+	my_free(p + 1);
+
+	return p->s.size;
+}
diff --git a/8.8/malloc.h b/8.8/malloc.h
new file mode 100644
index 0000000..3287a56
--- /dev/null
+++ b/8.8/malloc.h
@@ -0,0 +1,6 @@
+#include <stddef.h>
+
+void *my_malloc(size_t nbytes);
+void *my_calloc(size_t n ,size_t size);
+void my_free(void *ap);
+size_t bfree(void *ap, size_t n);