/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <unistd.h>
#include <limits.h>

#include "mm.h"
#include "memlib.h"

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
//#define DEBUG_MALLOC
//#define DEBUG_REALLOC
//#define DEBUG_INIT
//#define DEBUG_COUNT
//#define DEBUG_FREE_COUNT
//#define DEBUG_MALLOC_COUNT
//#define DEBUG_REALLOC_COUNT

//#define DEBUG_FREE
//#define DEBUG_CHECKLISTS
//#define DEBUG_CHECKUTIL

#ifdef DEBUG_COUNT
int op_count;
#endif


/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define BHEADER_SIZE ALIGN(sizeof(bHeader))
#define STRIPPED_HEADER ALIGN(sizeof(size_t))
#define BFOOTER_SIZE ALIGN(sizeof(bFooter))
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

typedef struct header bHeader;
typedef struct footer bFooter;
bHeader * find_fit(size_t size);

struct header{
   size_t size;
   bHeader * next;
   bHeader * prev;
};
struct footer{
   bHeader * head;
};

#define NUM_BINS 10
struct header heads[NUM_BINS];
//int cutoff[NUM_BINS]={16,64,112,128,160,1620,4072,4095,8190,INT_MAX};
int cutoff[NUM_BINS]={17,65,113,129,449,1621,4073,4096,8191,INT_MAX};

int getIndex(size_t size){
   int index;
   for(index = 0; index<NUM_BINS; ++index){
      if(size< cutoff[index])
         break;
   }
   return index;
}
//#define BLOCK_CACHING
#ifdef BLOCK_CACHING
#define NUM_BLOCK_CACHE 10
#define BLOCK_TRIGGER 10
typedef struct block_cache bcache;
struct block_cache{
   size_t size;
   size_t count;
};
struct block_cache blocks[NUM_BLOCK_CACHE];
void poke_block(size_t size){
   int i;
   int lowest=INT_MAX;
   int low_index = 0;
   for(i=0;i<NUM_BLOCK_CACHE;++i){
      if(blocks[i].count<lowest){
         lowest=blocks[i].count;
         low_index=i;
      }
      if(blocks[i].size==size){
         if(blocks[i].count++>BLOCK_TRIGGER){
            size_t size = ALIGN((blocks[i].size+STRIPPED_HEADER+BFOOTER_SIZE)*blocks[i].count);
            bHeader * p = mem_sbrk(size);
            p->size=size;
            ((bFooter *)((char *)p+((p->size)&~1)-BFOOTER_SIZE))->head = p;
            bHeader * front = &heads[getIndex(size)];
            front->next->prev = p;
            p->next=front->next;
            p->prev=front;
            front->next=p;
            blocks[i].count=0;
         }
         return;
      }
   }
   blocks[low_index].size=size;
   blocks[low_index].count=1;
}
#endif
int freecount;


void printHeap(){
   printf("++++++BEGIN HEAP+++++\n");
   bHeader * p = mem_heap_lo();
   while(p<(bHeader *)mem_heap_hi()){
      printf("%s block at %p, size %d, footer %s\n",
            (p->size&1)?"allocated":"free",
            p,
            (int)(p->size & ~1),
            (p==((bFooter *)((char *)p +((p->size)&~1)-BFOOTER_SIZE))->head)?"valid":"invalid");
      p = (bHeader *)((char *)p+(p->size & ~1));
   }
   printf("++++++END HEAP+++++\n");
}
void printList(){
   printf("-----BEGIN LIST-----\n");
   int index;
   for(index = 0; index<NUM_BINS; ++index){
      printf("BIN %d\n",index);
      bHeader * p = heads[index].next;
      while(p!=&heads[index]){
         printf("%s block at %p, size %d, footer %s\n",
               (p->size&1)?"allocated":"free",
               p,
               (int)(p->size & ~1),
               (p==((bFooter *)((char *)p +((p->size)&~1)-BFOOTER_SIZE))->head)?"valid":"invalid");
         p = p->next;
      }
      printf("-----END LIST-----\n");
   }
}
void checkLists(){
   int index;
   for(index = 0; index<NUM_BINS; ++index){
      bHeader * p = heads[index].next;
      while(p!=&heads[index]){
         if(p->size&1){
            printf("broken lists\n");
            exit(10);
         }
         p=p->next;
      }
   }
}
void checkFree(){
   int checkfree = 0;
   bHeader * p = mem_heap_lo();
   while(p<(bHeader *)mem_heap_hi()){
      checkfree+=!(p->size&1);
      p = (bHeader *)((char *)p+(p->size & ~1));
   }
   printf("actual: %d, recorded %d\n",checkfree,freecount);
   if (checkfree!=freecount){
      printf("broken freecount\n");
      exit(11);
   }
}
void checkHeap(){
   bHeader * p = mem_heap_lo();
   while(p<(bHeader *)mem_heap_hi()){
      if(!(p==((bFooter *)((char *)p +((p->size)&~1)-BFOOTER_SIZE))->head)){
         printf("broken heap\n");
         exit(12);
      }
      p = (bHeader *)((char *)p+(p->size & ~1));
   }
}

void checkUtil(){
   int free = 0;
   bHeader * p = mem_heap_lo();
   while(p<(bHeader *)mem_heap_hi()){
      free+=(p->size)*!(p->size&1);
      p = (bHeader *)((char *)p+(p->size & ~1));
   }
   printf("util %f\n",1-free/(float)(mem_heap_hi()-mem_heap_lo()));
}



/* 
 * mm_init - initialize the malloc package.
 */
#ifdef DEBUG_INIT
int init_calltimes= 0;
#endif
int mm_init(void)
{
#ifdef DEBUG_COUNT
   op_count= 0;
#endif
#ifdef SBRK_COUNT
   sbrk_count = 0;
#endif
   freecount = 0;
   bHeader *p = mem_sbrk(BHEADER_SIZE+BFOOTER_SIZE);
   p->next=p;
   p->prev=p;
   p->size=BHEADER_SIZE+BFOOTER_SIZE+1;
   bFooter *q=(bFooter *)((char *)p+BHEADER_SIZE);
   q->head=p;
   int i;
   for(i = 0; i<NUM_BINS;++i){
      heads[i].next=&heads[i];
      heads[i].prev=&heads[i];
      heads[i].size=BHEADER_SIZE+BFOOTER_SIZE+1;
   }

#ifdef DEBUG_INIT
   printf("#############INIT CALLED %d TIME(S)#################\n",++init_calltimes);
#endif
   return 0;
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size)
{
#ifdef DEBUG_MALLOC_COUNT
   static int malloc_count;
   printf("malloc : %d\n",++malloc_count);
#endif
   size_t newsize = ALIGN(size + STRIPPED_HEADER+ BFOOTER_SIZE);
   bHeader *p;
   if(freecount > 0 && (p=find_fit(newsize))!=NULL){
      if(((p->size)&~1)-newsize>=7+BHEADER_SIZE+BFOOTER_SIZE){
         //split off extra, put it on end
         size_t oldsize = p->size;
         p->size = newsize;
         ((bFooter *)((char *)p+((p->size)&~1)-BFOOTER_SIZE))->head = p;
         bHeader *split=(bHeader *)((char *)p + (p->size & ~1));
         split->size=oldsize-p->size; 
         ((bFooter *)((char *)split+((split->size)&~1)-BFOOTER_SIZE))->head = split;
         int index = getIndex(split->size-STRIPPED_HEADER-BFOOTER_SIZE);
         split->next = heads[index].next;
         heads[index].next=split;
         split->next->prev=split;
         split->prev=&heads[index];
         ++freecount;
      }
      if(freecount>0){
         --freecount;
      }
      p->prev->next=p->next;
      p->next->prev=p->prev;
      p->size|= 1;
   }else{
      bHeader * last=(((bFooter *)((char *)mem_heap_hi()+1-BFOOTER_SIZE))->head);
      if((freecount>0)&&(!(last->size &1))){
         --freecount;
         mem_sbrk(newsize-last->size);
         last->size = newsize | 1;
         ((bFooter *)((char *)last+((last->size)&~1)-BFOOTER_SIZE))->head = last;
         last->prev->next=last->next;
         last->next->prev=last->prev;
         p = last;
      } else {
#ifdef BLOCK_CACHING
         poke_block(size);
#endif
         p = mem_sbrk(newsize);
         if ((long)p == -1){
#ifdef DEBUG_CHECKLISTS
            checkLists();
            checkFree();
            checkHeap();
#endif
            return NULL;
         }
         else {
            p->size=newsize | 1;
            bFooter *q=(bFooter *)((char *)p+((p->size)&~1)-BFOOTER_SIZE);
            q->head=p;
         }
      }
   }
#ifdef DEBUG_MALLOC
   printHeap();
   printList();
#endif
#ifdef DEBUG_CHECKLISTS
   checkLists();
   checkFree();
   checkHeap();
#endif
#ifdef DEBUG_CHECKUTIL
   checkUtil();
#endif

   return (void *)((char *)p+sizeof(size_t));
}


bHeader * find_fit(size_t size){
   int index = getIndex(size);
   bHeader * p ;
   for(; index<NUM_BINS; ++index){
      for(p = heads[index].next; (p != &heads[index])&&(p->size<size+STRIPPED_HEADER+BFOOTER_SIZE);p=p->next);
      if(p != &heads[index])
         return p;
   }
   return NULL;
}




/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr){
   ++freecount;
#ifdef DEBUG_FREE_COUNT
   static int free_count;
   printf("free: %d\n",free_count++);
#endif
   //Get the header of the current block
   bHeader *p = (bHeader *)((char *)ptr - STRIPPED_HEADER);
   //back up and get the previous block's header
   bHeader *prev = ((bFooter *)((char *)p - BFOOTER_SIZE))->head;
   //set the current block to free
   p->size &= ~1;
   //if the previous block is also free
   if(!((prev->size)&1)){
	   //link the list around the current block
      prev->prev->next=prev->next;
      prev->next->prev=prev->prev;
      prev->size+=p->size;
      ((bFooter *)((char *)p+((p->size)&~1)-BFOOTER_SIZE))->head = prev;
      p = prev;
      --freecount;
   }
   bHeader *next=(bHeader *)((char *)p + (p->size &= ~1));
   if(((void *)((char *)p+p->size) <= mem_heap_hi()) && !((next->size)&1)){
      p->size+=next->size;
      ((bFooter *)((char *)p+((p->size)&~1)-BFOOTER_SIZE))->head = p;
      next->prev->next=next->next;
      next->next->prev=next->prev;
      --freecount;
   }
   bHeader * front = &heads[getIndex(p->size-STRIPPED_HEADER-BFOOTER_SIZE)];
   p->prev=front;
   p->next=front->next;
   front->next->prev = p;
   front->next=p;
#ifdef DEBUG_FREE
   printHeap();
   printList();
#endif
#ifdef DEBUG_CHECKLISTS
   checkLists();
   checkFree();
   checkHeap();
#endif
#ifdef DEBUG_CHECKUTIL
   checkUtil();
#endif
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
#ifdef DEBUG_REALLOC_COUNT
   static int realloc_count;
   printf("realloc: %d\n",++realloc_count);
#endif
#ifdef DEBUG_REALLOC
   printHeap();
   printList();
#endif
   size_t newsize = ALIGN(size + STRIPPED_HEADER+ BFOOTER_SIZE);
   bHeader *p = (bHeader *)((char *)ptr - sizeof(size_t));
   bHeader *next=(bHeader *)((char *)p + (p->size &= ~1));
   if((p->size&~1)>newsize){
#ifdef DEBUG_CHECKLISTS
      checkLists();
      checkFree();
      checkHeap();
#endif
      return ptr;
   }
   if(((void *)((char *)p+p->size) <= mem_heap_hi()) && !((next->size)&1) && (next->size + (p->size&~1) > newsize)){
      p->size=(p->size+next->size)|1;
      ((bFooter *)((char *)p+((p->size)&~1)-BFOOTER_SIZE))->head = p;
      next->prev->next=next->next;
      next->next->prev=next->prev;
#ifdef DEBUG_CHECKLISTS
      checkLists();
      checkFree();
      checkHeap();
#endif
      return ptr;
   }
   if(((void *)((char *)p+p->size) >= mem_heap_hi())){
      mem_sbrk(newsize-p->size);
      p->size=newsize;
      ((bFooter *)((char *)p+((p->size)&~1)-BFOOTER_SIZE))->head = p;
#ifdef DEBUG_CHECKLISTS
      checkLists();
      checkFree();
      checkHeap();
#endif
      return ptr;
   }
   void * new = mm_malloc(size);
   memcpy(new,ptr,p->size-STRIPPED_HEADER-BFOOTER_SIZE);
   mm_free(ptr);
   return new;
#ifdef DEBUG_CHECKLISTS
   checkLists();
   checkFree();
   checkHeap();
#endif
}