1 files changed, 73 insertions, 0 deletions
diff --git a/free.c b/free.c
new file mode 100644
index 0000000..d0ce540
--- /dev/null
+++ b/free.c
@@ -0,0 +1,73 @@
+#include "malloc.h"
+#include <assert.h>
+
+bucket_t*
+__bucket_from_obj(heap_cache_t *cache, bucket_obj_t *obj)
+{
+    assert(cache != NULL);
+    assert(cache->head != NULL);
+    /* Buckets are always aligned to the nearest page boundary, and that the 
+     * metadata is always below the object. We use this fact to quickly find 
+     * owning buckets.*/
+    uintptr_t objptr = (uintptr_t)obj;
+    uintptr_t bktptr = objptr & ~0xFFF;
+    while(1) {
+        /* If the page boundary is below the head, we are below the heap memory
+         * region and can stop.*/
+        if(bktptr < (uintptr_t)cache->head) return NULL;
+
+        /* At each page boundary below the object, check for the heap checksum.
+         * If it is found, we can assume that we found a bucket.*/
+        bucket_t *bucket = (bucket_t*)bktptr;
+        if(OBJ_VALID(bucket)) {
+            if(bucket->limit > objptr) return NULL;
+            return bucket;
+        }
+
+        bktptr -= BUCKET_ALIGN;
+    }
+}
+
+void
+__free_impl(heap_cache_t *cache, void *ptr)
+{
+    DBGPRINT("free: asking to free ptr %p\n", ptr);
+    assert(cache != NULL);
+    /* free(NULL) does nothing.*/
+    if(ptr == NULL) return;
+
+    /* Make sure the pointer actually comes from the heap.*/
+    assert((uintptr_t)ptr < (uintptr_t)cache->tail);
+    assert((uintptr_t)ptr > (uintptr_t)cache->head);
+    bucket_obj_t *obj = OBJ_FROM_PTR(ptr);
+    assert(OBJ_VALID(obj));
+
+    /* Mask the taken bit in the object to mark it free.*/
+    DBGPRINT("free: masking taken bit in object %p (was %i, now ", 
+            obj, obj->size_taken);
+    obj->size_taken &= ~1;
+    DBGPRINT("%i)\n", obj->size_taken);
+
+    /* If the buckets' lastfree is greater than this new free object, this 
+     * object will be the lastfree.*/
+    bucket_t *bucket = __bucket_from_obj(cache, obj);
+    if(bucket != NULL && bucket->firstfree > obj)
+        bucket->firstfree = obj;
+
+    /* Start trying to merge this free object with the next object.
+     * If the object after is taken, do nothing.*/
+    bucket_obj_t *after = OBJ_AFTER(obj);    
+    if((uintptr_t)after > bucket->limit) return;
+    assert(OBJ_VALID(after));
+    if(OBJ_TAKEN(after)) return;
+    
+    /* Merge with the next object.
+     * from:
+     * [meta| -objw-][meta| -afterw-]
+     * to:
+     * [meta| ---------objw---------]*/
+    DBGPRINT("free: obj %p merging with adjacent free object %p (was %i, now \n", 
+            obj, after, obj->size_taken);
+    obj->size_taken += sizeof(bucket_obj_t) + after->size_taken;
+    DBGPRINT("%i)\n", obj->size_taken);
+}