/*
* mm-naive.c - The fastest, least memory-efficient malloc package.
*
* In this naive approach, a block is allocated by simply incrementing
* the brk pointer.  A block is pure payload. There are no headers or
* footers.  Blocks are never coalesced or reused. Realloc is
* implemented directly using mm_malloc and mm_free.
*
* NOTE TO STUDENTS: Replace this header comment with your own header
* comment that gives a high level description of your solution.
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

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

/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team = {
  /* Team name */
  "Foo and the Bars",
  /* First member's full name */
  "Winston Xu",
  /* First member's email address */
  "winston.xu@coloradocollege.edu",
  /* Second member's full name (leave blank if none) */
  "David Bai",
  /* Second member's email address (leave blank if none) */
  "david.bai@coloradocollege.edu"
};

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)


#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
//everything below, up to realloc, is pretty much straight from the book (~pg 855, section 9.9.12)
//I understand the concepts/psuedocode, but haven't examined the actual details
//super carefully yet - still, I feel pretty good about what is below. Though maybe I shouldn't...
#define WSIZE 4 //word size may be different, thus d size as well
#define DSIZE 8
#define CHUNKSIZE (1<<12)

#define MAX(x,y) ( (x) > (y) ? (x) : (y) )

#define PACK(size, alloc) ((size) | (alloc))

#define GET(p) (*(unsigned int *)(p))         //gives bits at pointer p interpreted as an unsigned int
#define PUT(p, val) (*(unsigned int *)(p) = (val))

#define GET_SIZE(p) (GET(p) & ~0x7) //functionally ignore last 3 bits (assign them all 0)
#define GET_ALLOC(p) (GET(p) & 0x1) //only look at last bit (0 or 1 depending on allocation bit)

#define HDRP(bp) ((char *)(bp) - WSIZE)  //just 1 byte so math doesn't need to divide/multiply
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

#define NEXT_BLKP(bp) ( (char *)(bp) + GET_SIZE( ((char *)(bp) - WSIZE) ) )
#define PREV_BLKP(bp) ( (char *)(bp) - GET_SIZE( ((char *)(bp) - DSIZE) ) )

/*
*Tries to free up space by combining adjacent free blocks
*/
static void *coalesce(void *bp)
{
  size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
  size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
  size_t size = GET_SIZE(HDRP(bp));
  //printf("Entered coalesce\n");
  //printf("Previous block size %d\n", GET_SIZE(PREV_BLKP(bp)));
  //printf("Next Block size %d\n", GET_SIZE(NEXT_BLKP(bp)));
  // fflush(stdout);
  if (prev_alloc && next_alloc) {
    // printf("No change\n");
    // fflush(stdout);
    return bp;
  }
  else if( prev_alloc && !next_alloc){
    // printf("Next is free\n");
    // fflush(stdout);
    size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
  }
  else if( !prev_alloc && next_alloc){
    // printf("Prev is free\n");
    // fflush(stdout);
    size += GET_SIZE(HDRP(PREV_BLKP(bp)));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
    bp = PREV_BLKP(bp);
  }
  else{
    // printf("Both prev and next are free\n");
    // fflush(stdout);
    size += GET_SIZE(HDRP(PREV_BLKP(bp)))+GET_SIZE(FTRP(NEXT_BLKP(bp)));
    PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
    PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
    bp = PREV_BLKP(bp);
  }
  return bp;
}

//helper function which puts the right header and footer values in the new allocated block
static void place(char *blockpointer, size_t size)
{
  int remaining_space = GET_SIZE(HDRP(blockpointer)) - size;
  PUT( HDRP(blockpointer), PACK(size, 1) );
  PUT( FTRP(blockpointer), PACK(size, 1) );
  PUT( HDRP(NEXT_BLKP(blockpointer)), PACK(remaining_space, 0));
  PUT( FTRP(NEXT_BLKP(blockpointer)), PACK(remaining_space, 0));
}

/*
*How malloc finds the next free block
*Uses next fit for now, starts at beginning of list and iterates through
*/
/*static*/ char *find_fit(size_t size)
{
  //starting at first free block, which can be a global var
  //last free block's 'next' pointer should point to null
  // printf("Enter find_fit\n");
  // fflush(stdout);
  char *freeBlockP = (char *)(mem_heap_lo() + 4*WSIZE);
  printf("Looking for free block. Free? %s Size %d\n",
   GET_ALLOC(HDRP(freeBlockP)) ? "No" : "Yes", GET_SIZE(HDRP(freeBlockP)));
  fflush(stdout);
  while(GET_ALLOC(HDRP(freeBlockP)) == 1 || GET_SIZE(HDRP(freeBlockP)) < size)
  {
    printf("Looking for free block in loop. Free? %s Size %d\n",
     GET_ALLOC(HDRP(freeBlockP)) ? "No" : "Yes", GET_SIZE(HDRP(freeBlockP)));
    fflush(stdout);
    sleep(1);
    //go through free block
    //update freeblockP
    freeBlockP = NEXT_BLKP(freeBlockP);
  }
  if(GET_SIZE(HDRP(freeBlockP)) < size)
  {
    return NULL;
  }
  return freeBlockP;
}

/*
*Tells heap that more memory is being allocated-if possible
*/
static void *extend_heap(size_t words)
{
  char *bp;
  size_t size;
  //allocate even number of words to maintain alignment
  size = (words % 2) ? (words+1) * WSIZE: words * WSIZE;
  if( (long)(bp = mem_sbrk(size)) == -1) { //couldn't get move brk correctly
    printf("Current heap not big enough\n");
    fflush(stdout);
    return NULL;
  }
  // printf("MM init heap 1 is %d\n", *bp);
  // printf("MM init heap 2 is %d\n", *(bp+WSIZE));
  // printf("MM init heap 3 is %d\n", *(bp+DSIZE));
  // printf("MM init heap 4 is %d\n", *(bp+3*WSIZE));
  //initialize the free block's header and its footer, also the new epilogue header
  PUT( HDRP(bp), PACK(size, 0) );
  // printf("Extend heap header is %d\n", *HDRP(bp));
  // fflush(stdout);
  PUT( FTRP(bp), PACK(size, 0) );
  PUT( HDRP(NEXT_BLKP(bp)), PACK(0, 1) );
  //coalesce if previous block was free
  return coalesce(bp);
}

/*
*Goes through heap to make sure it is as planned
*/
static int mm_check()
{
  int return_value = 0;
  //do checks
  //return value = 1 if any errors
  char *freeBlockP = (char *)(mem_heap_lo() + 4*WSIZE);
  printf("First check: Free? %s Size %d\n",
    GET_ALLOC(HDRP(freeBlockP)) ? "No" : "Yes", GET_SIZE(HDRP(freeBlockP)));
  fflush(stdout);
  while(GET_ALLOC(HDRP(freeBlockP)) == 1)
  {
    // printf("Free? %s Size %d\n",
    //   GET_ALLOC(HDRP(freeBlockP)) ? "No" : "Yes", GET_SIZE(HDRP(freeBlockP)));
    sleep(1);
    //go through free block
    //update freeblockP
    freeBlockP = NEXT_BLKP(freeBlockP);
    printf("Shifted Free? %s Size %d\n",
      GET_ALLOC(HDRP(freeBlockP)) ? "No" : "Yes", GET_SIZE(HDRP(freeBlockP)));
    fflush(stdout);
  }

  return return_value; //if no errors caught by the end, return 0
}
/*********************************************************
* End of Helper Functions
********************************************************/
/*
* mm_init - initialize the malloc package.
*/
int mm_init() //void means no params; just to keep certain versions of c happy
{
  mem_init();
  char *heap_listp;
  if ( (heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1 ){
    return -1;
  }
  PUT(heap_listp, 0);
  PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1));
  PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));
  PUT(heap_listp + (3*WSIZE), PACK(0, 1));
  heap_listp += (2*WSIZE); //probably unnecessary
  //extend the empty heap with a free block of CHUNKSIZE bytes...2^12 (arbitrary?? It's 4kb, aka possible size of page)
  if (extend_heap(CHUNKSIZE/WSIZE) == NULL){ //if couldn't extend heap
    return -1;
  }

  return 0; //if no errors caught by the end, return
}

/*
* 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)
{
  // printf("Before malloc\n");
  // fflush(stdout);
  // mm_check();
  size_t asize;
  size_t extendsize;
  char *bp;
  //printf("--NEW alloc--\n");
  //fflush(stdout);
  if (size == 0){ //strange case to ignore
    // printf("Not allocating anything!");
    // printf("After malloc\n");
    // fflush(stdout);
    // mm_check();
    return NULL;
  }

  //change requested block size to fit header/footer, and align
  if(size <= DSIZE){
    asize = 2*DSIZE; //AKA 2 double words (for alignment, must be some # of double words)
                     //1 double word for headers/footers, at least 1 for data
  }
  else{
    asize = DSIZE * ( ( size + (DSIZE) + (DSIZE-1) ) / DSIZE);
    //
    //take size, add 15 bytes, divide by 8
    // if size % 8 = 0, asize is size + 1 (1 for hdr/ftr)
    // if size % 8 = 1 - 7, asize is size + 2 (1 for some padding, 1 for hdr/ftr)
  }
  printf("Old size %d New Size %d\n", size, asize);
  fflush(stdout);

  //look for fit in the free list
  //Finds first open spot? not enough space for a header
  if( (bp = find_fit(asize)) != NULL){ //
    place(bp, asize);
    // printf("There was still space\n");
    // fflush(stdout);
    // printf("After malloc\n");
    // fflush(stdout);
    // mm_check();
    return bp;
  }
  //reached here if no such fit...get more memory
  extendsize = MAX(asize, CHUNKSIZE);
  if( (bp = extend_heap(extendsize/WSIZE)) == NULL){
    printf("\tOut of memory for heap!\n");
    fflush(stdout);
    // printf("After malloc\n");
    // fflush(stdout);
    // mm_check();
    return NULL;
  }
  printf("\tAdding stuff of size %d\n", asize);
  fflush(stdout);
  place(bp, asize);
  //Reset epilogue
  PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
  // printf("After malloc\n");
  // fflush(stdout);
  // mm_check();
  return bp;
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *ptr)
{
  size_t size = GET_SIZE(HDRP(ptr));
  PUT( HDRP(ptr), PACK(size, 0) );
  PUT( FTRP(ptr), PACK(size, 0) );
  coalesce(ptr);
}

/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
  //check for free blocks to the left, see if it's big enough
  //if big enough, just move footer and adjust values in header/footer of current block and free block
  void *oldptr = ptr;
  void *newptr;
  size_t copySize;

  newptr = mm_malloc(size);
  if (newptr == NULL){
    return NULL;
  }
  copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
  if (size < copySize){
    copySize = size;
  }
  memcpy(newptr, oldptr, copySize);
  mm_free(oldptr);
  return newptr;
}