Added print_heap again, refactored realloc

1 files changed, 141 insertions, 46 deletions

diff --git a/mm.c b/mm.c
index 6724692..5ed721d 100644
--- a/mm.c
+++ b/mm.c
@@ -529,6 +529,53 @@ static node_t *sremove(node_t *node, node_t *t) {
   return x;
 }
 
+static void print_heap() {
+#ifdef DEBUG
+  msg("-------=[ HEAP BEGIN ]=--------\n");
+  word_t *crawl = heap_start;
+  int blocks_cnt = 0;
+  int used_cnt = 0;
+  chs = 0;
+  while (crawl < heap_end) {
+    // if (cnt < 5) {
+    msg("%p [%ld] %s, %s\n", crawl, get_size(crawl),
+        (is_free(crawl) ? "FREE" : "USED"), (is_prevfree(crawl) ? "pf" : "-"));
+    // }
+    // else if (cnt == 5) {
+    //   msg(".\n.\n.\n");
+    // }
+    blocks_cnt++;
+    if (is_used(crawl)) {
+      chs += get_size(crawl);
+      used_cnt++;
+    }
+    word_t *next = next_block(crawl);
+    if (next < heap_end) {
+      // assert(prev_block())
+      // assert(is_used(crawl));
+      assert(is_used(crawl) || is_prevfree(next));
+    }
+    if (next == heap_end) {
+      assert(last == crawl);
+    }
+    crawl = next;
+  }
+  if (chs > hwm) {
+    hwm = chs;
+  }
+  msg("-------=[  HEAP END  ]=--------\n\n");
+  msg("-------=[  HEAP STATS BEG ]=--------\n");
+  msg("Blocks cnt: [all] %d, [free] %d, [used] %d\n", blocks_cnt,
+      blocks_cnt - used_cnt, used_cnt);
+  msg("last: %p, sentiel: %p\n", last, sentiel);
+  size_t heap_size = (size_t)((void *)heap_end - (void *)heap_start);
+  msg("heap size: %ldB, %ld words\n", heap_size, heap_size / sizeof(word_t));
+  msg("HWM: %ld, CHS: %ld\n", hwm, chs);
+  msg("Util: %f%%\n", (float)hwm / (float)(heap_size / sizeof(word_t)) * 100.0);
+  msg("-------=[  HEAP STATS END ]=--------\n\n");
+#endif /* DEBUG */
+}
+
 /* --=[ Interface implemenetation ]=---------------------------------------- */
 
 static node_t *root;
@@ -642,11 +689,13 @@ static used_block_t *allocate_block(size_t size) {
   } else {
     block = allocate_existing_block(block, size);
   }
+  print_heap();
   return block;
 }
 
 /* Malloc size bytes */
 void *malloc(size_t size) {
+  msg("Mallocing %ld\n", size);
   if (size == 0)
     return NULL;
   size = btw_size(size + sizeof(used_block_t));
@@ -699,10 +748,12 @@ static void free_block(used_block_t *block) {
 
 /* Free malloced memory under ptr. */
 void free(void *ptr) {
+  msg("Freeing %p", ptr);
   if (ptr == NULL)
     return;
   used_block_t *block = block_fromptr(ptr);
   free_block(block);
+  print_heap();
 }
 
 /* --=[ realloc ]=---------------------------------------------------------- */
@@ -716,47 +767,89 @@ static void copy_block_payload(used_block_t *dest, used_block_t *src) {
   memmove(dest_payload, src_payload, size);
 }
 
+static void reduce_block(used_block_t *block, size_t old_sz, size_t new_sz) {
+  make_used(block, new_sz, is_prevfree(block));
+  free_block_t *next = next_block(block);
+  if (block == last)
+    last = next;
+  make_free(next, old_sz - new_sz, 0);
+  free_block((used_block_t *)next);
+}
+
+static bool maybe_extend_block(used_block_t *block, size_t cur_sz, size_t sz) {
+  free_block_t *next = next_block(block);
+  size_t sz_both = cur_sz + get_size(next);
+  if (sz_both < sz) 
+    return false;
+  erase_fb(next);
+  make_used(block, sz, is_prevfree(block));
+  if (sz_both == sz) {
+    maybe_clr_next_prevfree(block);
+    if (next == last)
+      last = block;
+  }
+  else {
+    free_block_t *new_next = (free_block_t *)next_block(block);
+    make_free(new_next, sz_both - sz, 0);
+    if (last == next)
+      last = new_next;
+    free_block((used_block_t *)new_next);
+  }
+  return true;
+}
+
 /* Try extending the old_block without replacing it. */
-static int maybe_realloc_inplace(used_block_t *old_block, size_t size) {
+static bool maybe_realloc_inplace(used_block_t *block, size_t sz) {
   msg("Maybe maybe?\n");
-  size_t cur_size = get_size(old_block);
-  if (cur_size == size) {
-    return 1;
+  size_t cur_sz = get_size(block);
+  if (cur_sz == sz) {
+    return true;
   }
-  if (cur_size > size) {
-    make_used(old_block, size, is_prevfree(old_block));
-    free_block_t *next = next_block(old_block);
-    make_free(next, cur_size - size, 0);
-    insert_fb(next);
-    maybe_set_next_prevfree(next);
-    if (last == old_block)
-      last = next;
-    return 1;
+  else if (cur_sz > sz) {
+    reduce_block(block, cur_sz, sz);
+    return true;
   }
-  if (is_next_free(old_block)) {
-    free_block_t *next = next_block(old_block);
-    size_t size_together = cur_size + get_size(next);
-    if (size_together >= size) {
-      erase_fb(next);
-      make_used(old_block, size, is_prevfree(old_block));
-      if (size_together == size) {
-        maybe_clr_next_prevfree(old_block);
-        if (next == last)
-          last = old_block;
-      } else {
-        free_block_t *new_next = (free_block_t *)next_block(old_block);
-        make_free(new_next, size_together - size, 0);
-        insert_fb(new_next);
-        if (last == next)
-          last = new_next;
-      }
-      return 1;
-    }
+  else if (is_next_free(block)) {
+    return maybe_extend_block(block, cur_sz, sz);
   }
+  return false;
+}
 
-  return 0;
+static void *realloc_to_heap_end(used_block_t *block, size_t sz) {
+  get_memory_words(sz - get_size(block));
+  make_used(block, sz, is_prevfree(block));
+  return get_payload(block);
 }
 
+static void *realloc_to_new_block(used_block_t *block, size_t sz) {
+  used_block_t *new_block = allocate_block(sz);
+  copy_block_payload(new_block, block);
+  free_block(block);
+  return get_payload(new_block);
+}
+
+// static void *maybe_extend_to_left(used_block_t *block, size_t sz) {
+//   used_block_t *prev = prev_block(block);
+//   size_t both_sz = get_size(prev) + get_size(block);
+//   if (both_sz < sz) return NULL;
+
+//   erase_fb((free_block_t *)prev);
+//   make_used(prev, sz, 0);
+//   copy_block_payload(prev, block);
+//   if (both_sz == sz) {
+//     if (last == block) 
+//       last = prev;
+//   }
+//   else { /* both_sz > sz */
+//     used_block_t *next = next_block(prev);
+//     make_free(next, both_sz - sz, 0);
+//     if (last == block)
+//       last = next;
+//     free_block(next);
+//   }
+//   return get_payload(prev);
+// }
+
 /* Reallocate memory under old_ptr so it has size bytes. */
 void *realloc(void *old_ptr, size_t size) {
   if (old_ptr == NULL) {
@@ -766,22 +859,24 @@ void *realloc(void *old_ptr, size_t size) {
     free(old_ptr);
     return NULL;
   }
+
   size = btw_size(size + sizeof(used_block_t));
-  used_block_t *old_block = block_fromptr(old_ptr);
-  if (maybe_realloc_inplace(old_block, size)) {
-    return get_payload(old_block);
+  used_block_t *block = block_fromptr(old_ptr);
+  msg("Reallocing %p, %ld\n", block, size);
+  if (maybe_realloc_inplace(block, size)) {
+    old_ptr = get_payload(block);
   }
-  if (old_block == last) {
-    get_memory_words(size - get_size(old_block));
-    make_used(old_block, size, is_prevfree(old_block));
-    return get_payload(old_block);
+  // else if (is_prevfree(block) && (old_ptr = maybe_extend_to_left(block, size))) {
+  //   ;    
+  // }
+  else if (block == last) {
+    old_ptr = realloc_to_heap_end(block, size);
   }
-
-  used_block_t *new_block = allocate_block(size);
-  copy_block_payload(new_block, old_block);
-  free_block(old_block);
-
-  return get_payload(new_block);
+  else {
+    old_ptr = realloc_to_new_block(block, size);
+  }
+  print_heap();
+  return old_ptr;
 }
 
 /* --=[ calloc ]=----------------------------------------------------------- */