Only splay, no debug

1 files changed, 0 insertions, 311 deletions

diff --git a/mm.c b/mm.c
index 161b304..a0b09b8 100644
--- a/mm.c
+++ b/mm.c
@@ -142,23 +142,6 @@
 #include "mm.h"
 #include "memlib.h"
 
-// #define LIST_IMP
-#define SPLAY_IMP
-
-#ifdef LIST_IMP
-
-/* Insertion policy */
-// #define LIFO
-// #define FIFO
-#define SORT /* Keep the list sorted by block size */
-// #define SORT_ADDR       /* Keep the list sorted by block address */
-
-/* Find-fit policy */
-#define FIRSTFIT
-// #define BESTFIT
-
-#endif /* LIST_IMP */
-
 /* If you want debugging output, use the following macro.
  * When you hand in, remove the #define DEBUG line. */
 // #define DEBUG
@@ -191,13 +174,8 @@ typedef enum {
 
 typedef struct {
   word_t header;
-#ifdef LIST_IMP
-  word_t prev_block;
-  word_t next_block;
-#elif defined(SPLAY_IMP)
   word_t left;
   word_t right;
-#endif
   word_t _offset; /* needed so the sizeof(free_block_t) includes the footer */
   word_t payload[];
 } free_block_t;
@@ -284,17 +262,11 @@ static inline word_t *get_header_from_footer(word_t *footer) {
 
 /* Gets payload address from used block. */
 static inline void *get_payload(used_block_t *block) {
-#ifdef DEBUG
-  // assert(is_used((word_t *)block));
-#endif
   return block + 1;
 }
 
 /* Gets payload size from used block. */
 static inline size_t get_payload_size(used_block_t *block) {
-#ifdef DEBUG
-  assert(is_used((word_t *)block));
-#endif
   return (get_size(block) - 1) * sizeof(word_t);
 }
 
@@ -320,9 +292,6 @@ static inline bt_flags is_prevfree(void *bt) {
 
 /* Assumes that is_prevfree(bt) == true */
 static inline void *prev_block(void *bt) {
-#ifdef DEBUG
-  assert(is_prevfree(bt));
-#endif
   return get_header_from_footer((word_t *)bt - 1);
 }
 
@@ -386,8 +355,6 @@ static free_block_t *find_fit(size_t reqsz);
 
 /* --=[ Splay functions ]=-------------------------------------------------- */
 
-#ifdef SPLAY_IMP
-
 typedef free_block_t node_t;
 static node_t *mock; /* One mock block used for upperbound method. */
 
@@ -443,24 +410,6 @@ static inline bool is_lesser(node_t *a, node_t *b) {
   return (as < bs || (as == bs && a < b));
 }
 
-#ifdef DEBUG
-/* Prints the splay tree. */
-static void print_splay(node_t *node, int ind) {
-  if (is_sentiel(node))
-    return;
-  for (int i = 0; i < ind; i++)
-    msg(" ");
-  msg("[%p], size %ld, left %p, right %p\n", node, get_size(node), sleft(node),
-      sright(node));
-  if (!is_left_sentiel(node))
-    assert(is_lesser(sleft(node), node));
-  if (!is_right_sentiel(node))
-    assert(is_greater(sright(node), node));
-  print_splay(sleft(node), ind + 2);
-  print_splay(sright(node), ind + 2);
-}
-#endif /* DEBUG */
-
 /* Get the lowest node greater or equal to the mock node. Store it in ub */
 static node_t *ub;
 static void upperbound(node_t *t) {
@@ -553,11 +502,7 @@ static node_t *sinsert(node_t *node, node_t *t) {
    Base on Daniel's splay. */
 static node_t *sremove(node_t *node, node_t *t) {
   node_t *x;
-  msg("removing %p\n", node);
   t = splay(node, t);
-#ifdef DEBUG
-  assert(node == t);
-#endif
   if (is_left_sentiel(t)) {
     x = sright(t);
   } else {
@@ -610,249 +555,15 @@ static free_block_t *find_fit(size_t reqsz) {
   return root;
 }
 
-#endif /* SPLAY_IMP */
-
-/* --=[ list functions ]=--------------------------------------------------- */
-
-#ifdef LIST_IMP
-static inline word_t lget_offset(free_block_t *from, free_block_t *to) {
-  return (word_t)((void *)to - (void *)from);
-}
-
-static inline void lset_next(free_block_t *block, free_block_t *next) {
-  block->next_block = lget_offset(block, next);
-}
-
-static inline void lset_prev(free_block_t *block, free_block_t *prev) {
-  block->prev_block = lget_offset(block, prev);
-}
-
-static inline free_block_t *lnext(free_block_t *block) {
-  return (void *)block + block->next_block;
-}
-
-static inline free_block_t *lprev(free_block_t *block) {
-  return (void *)block + block->prev_block;
-}
-
-static inline word_t is_sentiel(free_block_t *block) {
-  return block == sentiel;
-}
-
-static void lerase(free_block_t *block) {
-  free_block_t *prev = lprev(block);
-  free_block_t *next = lnext(block);
-  lset_next(prev, next);
-  lset_prev(next, prev);
-}
-
-/* ...-> |prev| -> |block| -> |next| -...
- *  ...- |    | <- |     | <- |    | <-...
- */
-static void ladd_after(free_block_t *block, free_block_t *prev) {
-  free_block_t *next = lnext(prev);
-  lset_prev(next, block);
-  lset_next(prev, block);
-
-  lset_prev(block, prev);
-  lset_next(block, next);
-}
-
-/* --=[ list insertions ]=-------------------------------------------------- */
-
-#ifdef LIFO
-static void linsert(free_block_t *block) {
-  ladd_after(block, sentiel);
-}
-#elif defined(FIFO)
-static void linsert(free_block_t *block) {
-  ladd_after(block, lprev(sentiel));
-}
-#elif defined(SORT)
-static void linsert(free_block_t *block) {
-  free_block_t *crawl = lnext(sentiel);
-  size_t sz = get_size(block);
-  while (crawl != sentiel) {
-    if (get_size(crawl) >= sz) {
-      break;
-    }
-    crawl = lnext(crawl);
-  }
-  ladd_after(block, lprev(crawl));
-}
-#elif defined(SORT_ADDR)
-static void linsert(free_block_t *block) {
-  free_block_t *crawl = lnext(sentiel);
-  while (crawl != sentiel) {
-    if (crawl > block)
-      break;
-    crawl = lnext(crawl);
-  }
-  ladd_after(block, lprev(crawl));
-}
-#else
-#error "No linsert implementation."
-#endif /* Insertion policy */
-
-static void insert_fb(free_block_t *block) {
-  linsert(block);
-}
-
-static void erase_fb(free_block_t *block) {
-  lerase(block);
-}
-
-/* find_fit returns NULL if there's no good free block */
-#ifdef FIRSTFIT
-/* First fit startegy. */
-static free_block_t *find_fit(size_t reqsz) {
-  free_block_t *crawl = lnext(sentiel);
-  while (crawl != sentiel && get_size(crawl) < reqsz) {
-    crawl = lnext(crawl);
-  }
-  if (is_sentiel(crawl))
-    return NULL;
-  return crawl;
-}
-#elif defined(BESTFIT)
-/* Best fit startegy. */
-static free_block_t *find_fit(size_t reqsz) {
-  free_block_t *crawl = lnext(sentiel);
-  free_block_t *best = sentiel;
-  size_t best_size = MAX_HEAP;
-  while (crawl != sentiel) {
-    size_t sz = get_size(crawl);
-    if (sz == reqsz)
-      return crawl;
-    if (sz < best_size && sz >= reqsz) {
-      best_size = sz;
-      best = crawl;
-    }
-    crawl = lnext(crawl);
-  }
-  return best;
-}
-#elif defined(NEXTFIT)
-static free_block_t *find_fit(size_t reqsz) {
-}
-#else
-#error "No find-fit implementation"
-#endif /* Find-fit policy */
-#endif /* LIST_IMP */
-
-/* --=[ list debug ]=-------------------------------------------------------- */
-
-static void print_data_structure() {
-#ifdef DEBUG
-#ifdef LIST_IMP
-  msg("---------=[ FREE LIST BEG ]=---------\n");
-  free_block_t *crawl = lnext(sentiel);
-  int cnt = 0;
-  while (crawl != sentiel) {
-    cnt++;
-    if (cnt < 10) {
-      msg("%p, size: %ld, prev: %p, next: %p\n", crawl, get_size(crawl),
-          lprev(crawl), lnext(crawl));
-    } else if (cnt == 5) {
-      msg(".\n.\n.\n");
-    }
-
-    word_t *next = next_block((word_t *)crawl);
-    assert(is_free((word_t *)crawl));
-    assert(heap_end == next || is_prevfree(next));
-
-    crawl = lnext(crawl);
-  }
-  msg("---------=[ FREE LIST END ]=---------\n\n");
-#elif defined(SPLAY_IMP)
-  msg("------------=[ SPLAY BEG ]=-------------\n");
-  print_splay(root, 0);
-  msg("------------=[ SPLAY END ]=-------------\n\n");
-#endif /* LIST_IMP */
-#endif /* DEBUG */
-}
-
-/* --=[ general debug ]=----------------------------------------------------- */
-
-/* Print the heap and check its integrity. */
-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));
-#ifdef LIST_IMP
-      if (is_free(crawl)) {
-        assert((uint64_t)lnext((free_block_t *)crawl) % 4 == 0);
-        assert((uint64_t)lprev((free_block_t *)crawl) % 4 == 0);
-        assert(!is_free(next));
-      }
-#endif /* LIST_IMP */
-    }
-    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 */
-}
-
 /* --=[ mm_init ]=---------------------------------------------------------- */
 
-#ifdef LIST_IMP
-static void init_data_structure(void *params) {
-  sentiel = params;
-  /* It's quite tricky - sentiel has set the USED flag, so it is not counted
-     as a free block */
-  make_free(sentiel, sizeof(free_block_t), USED);
-  lset_next(sentiel, sentiel);
-  lset_prev(sentiel, sentiel);
-}
-#endif /* LIST_IMP */
-
 int mm_init(void) {
   /* Place for sentiel, offset so that
    * a new block starts just before aligned byte */
   void *ptr = morecore(3 * ALIGNMENT - sizeof(word_t));
   if (!ptr)
     return -1;
-#ifdef LIST_IMP
-  init_data_structure(ptr);
-#elif defined(SPLAY_IMP)
   init_data_structure(ptr);
-#endif
   heap_start = morecore(0);
   heap_end = heap_start;
   chs = 0;
@@ -872,19 +583,13 @@ static void *get_memory_words(size_t sz) {
 
 /* Allocate additional memory on heap and return (phisicaly) last free block.*/
 static used_block_t *allocate_new(size_t sz) {
-  msg("Allocating new.\n");
   int is_last_free = is_free(last) ? PREVFREE : 0;
   size_t alloc_size = sz;
   used_block_t *block;
   if (is_last_free) {
     alloc_size -= get_size(last);
   }
-  msg("alloc size: %ld %ld %ld\n", sz, get_size(last), alloc_size);
-#ifdef DEBUG
-  assert((long)alloc_size > 0);
-#endif
   block = get_memory_words(alloc_size);
-  msg("allocating under %p\n", block);
   if (is_last_free) {
     block = last;
     erase_fb(last);
@@ -896,13 +601,10 @@ static used_block_t *allocate_new(size_t sz) {
 
 /* Block is a free block that has sufficient size to allocate sz words. */
 static used_block_t *allocate_existing_block(used_block_t *block, size_t sz) {
-  // msg("Allocatin exsiting\n");
-  msg("Allocating existing %p.\n", block);
   erase_fb((free_block_t *)block);
   size_t prev_sz = get_size(block);
   make_used(block, sz, 0);
   if (prev_sz > sz) {
-    // msg("Henlo %ld %ld\n", prev_sz, sz);
     free_block_t *next = next_block(block);
     /* Previous block isn't free, otherwise it would be coalessed */
     make_free(next, prev_sz - sz, 0);
@@ -917,16 +619,12 @@ static used_block_t *allocate_existing_block(used_block_t *block, size_t sz) {
 
 /* Allocate a block of sz words size */
 static used_block_t *allocate_block(size_t size) {
-  msg(">>>> Allocating block %ld\n", size);
   used_block_t *block = (used_block_t *)find_fit(size);
-  msg("Block: %p\n", block);
   if (!block) {
     block = allocate_new(size);
   } else {
     block = allocate_existing_block(block, size);
   }
-  print_data_structure();
-  print_heap();
   return block;
 }
 
@@ -987,11 +685,7 @@ void free(void *ptr) {
   if (ptr == NULL)
     return;
   used_block_t *block = block_fromptr(ptr);
-  msg(">>>> Freeing block %p, ptr %p\n", block, ptr);
-  // print_splay(root,0);
   free_block(block);
-  print_data_structure();
-  print_heap();
 }
 
 /* --=[ realloc ]=---------------------------------------------------------- */
@@ -1057,10 +751,7 @@ void *realloc(void *old_ptr, size_t size) {
   }
   size = btw_size(size + sizeof(used_block_t));
   used_block_t *old_block = block_fromptr(old_ptr);
-  msg(">>>> Reallocating %p %ld\n", old_block, size);
   if (maybe_realloc_inplace(old_block, size)) {
-    print_data_structure();
-    print_heap();
     return get_payload(old_block);
   }
   if (old_block == last) {
@@ -1073,8 +764,6 @@ void *realloc(void *old_ptr, size_t size) {
   copy_block_payload(new_block, old_block);
   free_block(old_block);
 
-  print_data_structure();
-  print_heap();
   return get_payload(new_block);
 }