1 files changed, 90 insertions, 0 deletions
diff --git a/umalloc.c b/umalloc.c
new file mode 100644
index 0000000..c0fc4ca
--- /dev/null
+++ b/umalloc.c
@@ -0,0 +1,90 @@
+#include "types.h"
+#include "stat.h"
+#include "user.h"
+#include "param.h"
+
+// Memory allocator by Kernighan and Ritchie, The C programming Language, 
+// 2nd ed.  Section 8.7.
+
+typedef long Align;
+
+union header {
+  struct {
+    union header *ptr;
+    uint size;
+  } s;
+  Align x;
+};
+
+typedef union header Header;
+
+static Header base;
+static Header *freep = 0;
+
+void
+free(void *ap)
+{
+  Header *bp, *p;
+  
+  bp = (Header *) ap - 1;
+  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;
+}
+
+static Header *
+morecore(uint nu)
+{
+  char *cp;
+  Header *up;
+  
+  if (nu < PAGE)
+    nu = PAGE;
+  cp = sbrk(nu * sizeof(Header));
+  if (cp == (char *) -1)
+    return 0;
+  up = (Header *) cp;
+  up->s.size = nu;
+  free((void *)(up + 1));
+  return freep;
+}
+
+void *
+malloc(uint nbytes)
+{
+  Header *p, *prevp;
+  uint nunits;
+
+  nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;
+  if ((prevp = freep) == 0) {
+    base.s.ptr = freep = prevp = &base;
+    base.s.size = 0;
+  }
+  for (p = prevp->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 = morecore(nunits)) == 0)
+	return 0;
+  }
+}