first-commit
Merge branch 'master' of https://github.com/SRP2504/malloc_lab

/*
* Simple, 32-bit and 64-bit clean allocator based on an implicit free list,
* first fit placement, and boundary tag coalescing, as described in the
* CS:APP2e text.  Blocks are aligned to double-word boundaries.  This
* yields 8-byte aligned blocks on a 32-bit processor, and 16-byte aligned
* blocks on a 64-bit processor.  However, 16-byte alignment is stricter
* than necessary; the assignment only requires 8-byte alignment.  The
* minimum block size is four words.
*
* This allocator uses the size of a pointer, e.g., sizeof(void *), to
* define the size of a word.  This allocator also uses the standard
* type uintptr_t to define unsigned integers that are the same size
* as a pointer, i.e., sizeof(uintptr_t) == sizeof(void *).
*/

/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team = {
    /* Team name */
    "abcd",
    /* First member's full name */
    "Saurabh Patel",
    /* First member's email address */
    "201201051@daiict.ac.in",
    /* Second member's full name (leave blank if none) */
    "Malveeka Bhandari",
    /* Second member's email address (leave blank if none) */
    "201201008@daiict.ac.in"
};

//* Basic constants and macros: */

/*Max value of 2 values*/

/* Pack a size and allocated bit into a word */

/* Read and write a word at address p. */

/* Read the size and allocated fields from address p */

/* Given block ptr bp, compute address of its header and footer */

/* Given block ptr bp, compute address of next and previous blocks */

/* Given ptr in free list, get next and previous ptr in the list */

/* Puts pointers in the next and previous elements of free list */

/* Global declarations */
static char *heap_listp ;
static char *free_head ;// Pointer to beginning of the free list

/* Function prototypes for internal helper routines */
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);

/* Function prototypes for maintaining free list(add will attach free blocks at the root of free list)*/
static void addFreeBlock(void *bp);
static void delFreeBlock(void *bp);

/* Function prototypes for heap consistency checker routines: */
static void checkblock(void *bp);
static void checkheap(bool verbose);
static void printblock(void *bp);

/**
* Initialize the memory manager.
* @param - void no parameter passed in
* @return - int 0 for success or -1 for failure
*/
int mm_init(void) {

 /* Create the initial empty heap. */
 if ((heap_listp = mem_sbrk(8*WSIZE)) == NULL)
   return -1;

 PUT(heap_listp, 0);                            /* Alignment padding */
 PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* Prologue header */
 PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
 PUT(heap_listp + (3 * WSIZE), PACK(0, 1));     /* Epilogue header */
 heap_listp = heap_listp + 2*WSIZE;
 free_head = heap_listp;

 /* Extend the empty heap with a free block of minimum possible block size */
 if (extend_heap(CHUNKSIZE/WSIZE) == NULL){
   return -1;
 }
 return 0;
}

/*
* Requires:
*   None.
*
* Effects:
*   Allocate a block with at least "size" bytes of payload, unless "size" is
*   zero.  Returns the address of this block if the allocation was successful
*   and NULL otherwise.
*/
void *mm_malloc(size_t size)
{
 size_t asize;      /* Adjusted block size */
 size_t extendsize; /* Amount to extend heap if no fit */
 void *bp;

 /* Ignore spurious requests. */
 if (size == 0)
   return (NULL);

 /* Adjust block size to include overhead and alignment reqs. */
 if (size <= DSIZE)
   asize = 2 * DSIZE;
 else
   asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);

 /* Search the free list for a fit. */
 if ((bp = find_fit(asize)) != NULL) {
   place(bp, asize);
   return (bp);
 }

 /* No fit found.  Get more memory and place the block. */
 extendsize = MAX(asize, CHUNKSIZE);
 if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
   return (NULL);

 place(bp, asize);
 return (bp);
}

/*
* Requires:
*   "bp" is either the address of an allocated block or NULL.
*
* Effects:
*   Free a block.
*/
void mm_free(void *bp){
 size_t size;
 /* Ignore spurious requests. */
 if (bp == NULL)
   return;
 /* Free and coalesce the block. */
 size = GET_SIZE(HDRP(bp));
 PUT(HDRP(bp), PACK(size, 0));
 PUT(FTRP(bp), PACK(size, 0));
 coalesce(bp);
}

/*
* Requires:
*   "ptr" is either the address of an allocated block or NULL.
*
* Effects:
*   Reallocates the block "ptr" to a block with at least "size" bytes of
*   payload, unless "size" is zero.  If "size" is zero, frees the block
*   "ptr" and returns NULL.  If the block "ptr" is already a block with at
*   least "size" bytes of payload, then "ptr" may optionally be returned.
*   Otherwise, a new block is allocated and the contents of the old block
*   "ptr" are copied to that new block.  Returns the address of this new
*   block if the allocation was successful and NULL otherwise.
*/
void *mm_realloc(void *ptr, size_t size){

    size_t oldsize;
    void *newptr;

    /* If size == 0 then this is just free, and we return NULL. */
    if (size == 0) {
        mm_free(ptr);
        return (NULL);
    }

    /* If oldptr is NULL, then this is just malloc. */
    if (ptr == NULL)
        return (mm_malloc(size));

    oldsize = GET_SIZE(HDRP(ptr));

    size_t newsize;

    if (size <= DSIZE)
      newsize = 2 * DSIZE;
    else
      newsize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);
/*To avoid unneccessary calls to malloc, we use the following code*/
    if(newsize <= oldsize){ //if the requested size is less, we can send the same pointer back
      return ptr;
    }
    else {
      size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
      size_t tsize;
      if (!next_alloc) {// If the next block is free, we can check if we can return the same pointer, provided there's enough space
          tsize = oldsize + GET_SIZE(HDRP(NEXT_BLKP(ptr)));
          if(tsize >= newsize){// If the spce is enough, we pack the header with the changed size and return the same pointer
            delFreeBlock(NEXT_BLKP(ptr));
            PUT(HDRP(ptr), PACK(tsize, 1));
            PUT(FTRP(ptr), PACK(tsize, 1));
            return ptr;
          }
		  /*In case the next block of next blolck is epilogue,we extend heap and return the same pointer*/
          else if( (GET_SIZE(HDRP(NEXT_BLKP(NEXT_BLKP(ptr)))) == 0)){
            tsize = newsize - oldsize - GET_SIZE(HDRP(NEXT_BLKP(ptr)));
            extend_heap(tsize/WSIZE);
            PUT(HDRP(ptr), PACK(newsize, 1));
            PUT(FTRP(ptr), PACK(newsize, 1));
            return ptr;
          }
      }
		/*In case the next block is the epilogue, we again extend thee heap*/
      else if(GET_SIZE(HDRP(NEXT_BLKP(ptr))) == 0){
        tsize = newsize - oldsize;
        extend_heap(tsize/WSIZE);\
        PUT(HDRP(ptr), PACK(newsize, 1));
        PUT(FTRP(ptr), PACK(newsize, 1));
        return ptr;
      }
	/*If the next block is neither free nor the epilogue, we call malloc and copy the contents and then free the given block*/
        newptr = mm_malloc(size);

          /* If realloc() fails the original block is left untouched  */
          if (newptr == NULL)
              return (NULL);

          place (newptr, newsize);

          memcpy(newptr, ptr, oldsize);

          /* Free the old block. */
          mm_free(ptr);

          return (newptr);
    }
}

/*
* The following routines are internal helper routines.
*/

/*
* Requires:
*   "bp" is the address of a newly freed block.
*
* Effects:
*   Perform boundary tag coalescing.  Returns the address of the coalesced
*   block.
*/
static void *coalesce(void *bp){

 //If previous block is allocated or its size is zero then PREV_ALLOC will be set.
 size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
 size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))) || (!GET_SIZE((void *)(bp) - DSIZE));
 size_t size = GET_SIZE(HDRP(bp));
/*If the next and prev blocks are both allocated, no coalescing is possible and we simply add a free block to the free list*/
 if (prev_alloc && next_alloc) {
    addFreeBlock(bp);
 }
/*If the next block is free and the previous is not, we delete the next block from the free list, extend the size of the given block and add it to fre list*/
 else if (prev_alloc && !next_alloc) {
   size += GET_SIZE( HDRP(NEXT_BLKP(bp))  );
   delFreeBlock(NEXT_BLKP(bp));
   PUT(HDRP(bp), PACK(size, 0));
   PUT(FTRP(bp), PACK(size, 0));
   addFreeBlock(bp);
 }
/*If the previous block is free and the next is not, we delete previous from free list, extend its size and add it again to free list */
 else if (!prev_alloc && next_alloc) {
   size += GET_SIZE( HDRP(PREV_BLKP(bp))  );
   bp = PREV_BLKP(bp);
   delFreeBlock(bp);
   PUT(HDRP(bp), PACK(size, 0));
   PUT(FTRP(bp), PACK(size, 0));
   addFreeBlock(bp);
 }
 else {
/*If both next and previous are free, we delete next from free list and extend size of previous to include both current and next*/
   size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
   delFreeBlock(NEXT_BLKP(bp));
   bp = PREV_BLKP(bp);
   PUT(HDRP(bp), PACK(size, 0));
   PUT(FTRP(bp), PACK(size, 0));
 }
 return bp;
}

/*
* Requires:
*   None.
*
* Effects:
*   Extend the heap with a free block and return that block's address.
*/

static void *extend_heap(size_t words) {
 char *bp;
 size_t size;

 /* Allocate an even number of words to maintain alignment */
 size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;

 /* call for more memory space */
    if ((bp = mem_sbrk(size)) == (void *)-1)
         return (NULL);

 /* Initialize free block header/footer and the epilogue header */
 PUT(HDRP(bp), PACK(size, 0));         /* free block header */
 PUT(FTRP(bp), PACK(size, 0));         /* free block footer */
 PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* new epilogue header */
 /* coalesce bp with next and previous blocks */
 return coalesce(bp);
}

/*
* Requires:
*   None.
*
* Effects:
*   Find a fit for a block with "asize" bytes.  Returns that block's address
*   or NULL if no suitable block was found.
*/

static void *find_fit(size_t asize){
 void *bp;
/*we use the first fit policy, starting the search from free_head till we get to prologue*/
 for (bp = free_head; GET_ALLOC(HDRP(bp)) == 0; bp = NEXT_FREE_BLKP(bp) ){
   if (GET_SIZE(HDRP(bp)) >= asize) {
      return bp;
   }
 }
 return NULL;

}

/*
* Requires:
*   "bp" is the address of a free block that is at least "asize" bytes.
*
* Effects:
*   Place a block of "asize" bytes at the start of the free block "bp" and
*   split that block if the remainder would be at least the minimum block
*   size.
*/
static void place(void *bp, size_t asize){
 size_t csize = GET_SIZE(HDRP(bp));
/*If the size of request is sufficiently smaller than the size of the block to create a new block*/
 if ((csize - asize) >= 2 * DSIZE) {
	 /*In this case, we delete the given block pointer from free list, make a new block for remaining size , and add its pointer to free list */
   PUT(HDRP(bp), PACK(asize, 1));
   PUT(FTRP(bp), PACK(asize, 1));
   delFreeBlock(bp);
   bp = NEXT_BLKP(bp);
   PUT(HDRP(bp), PACK(csize-asize, 0));
   PUT(FTRP(bp), PACK(csize-asize, 0));
   addFreeBlock(bp);
 }
 else {
	 /*In case the requested size leaves no scope for a new free block to be created, we set the given block as allocated and delete it from free list*/
   PUT(HDRP(bp), PACK(csize, 1));
   PUT(FTRP(bp), PACK(csize, 1));
   delFreeBlock(bp);
 }
}

/*
* Requires:
*   "bp" is the address of a free block.
*
* Effects:
*   Places the given block at the beginning of the free list
*/
static void addFreeBlock(void *bp){
    SET_NEXT_FREE_BLKP(bp, free_head);			//setting the next free block pointer of bp to free_head, i.e.the root
    SET_PREV_FREE_BLKP(free_head, bp);			//setting the previous free block pointer of free_head to bp
    SET_PREV_FREE_BLKP(bp, NULL);				//setting the previous free block pointer of bp to NULL
    free_head = bp;											//making bp the new root, or starting pointer of the free list
}

/*
* Requires:
*   "bp" is the address of a block.
*
* Effects:
*   Removes the given block from the free list
*/
static void delFreeBlock(void *bp){
 if (PREV_FREE_BLKP(bp)){
   SET_NEXT_FREE_BLKP(PREV_FREE_BLKP(bp), NEXT_FREE_BLKP(bp));			//setting the next free block pointer of the previous free block pointer to the next free block pointer of bp
   SET_PREV_FREE_BLKP(NEXT_FREE_BLKP(bp), PREV_FREE_BLKP(bp));			//setting the previous free block pointer of the next free block pointer to the previous free block pointer of bp
 }
 else{
   free_head = NEXT_FREE_BLKP(bp);			//If the block to be deleted is free_head itself, then making the next free block of bp as free_head
   SET_PREV_FREE_BLKP(NEXT_FREE_BLKP(bp), NULL); //setting the previous free block pointer of next free block pointer of bp to NULL
 }
}

/*
* The remaining routines are heap consistency checker routines.
*/

/*
* Requires:
*   "bp" is the address of a block.
*
* Effects:
*   Perform a minimal check on the block "bp".
*/
static void
checkblock(void *bp)
{

 if ((uintptr_t)bp % DSIZE)
   printf("Error: %p is not doubleword aligned\n", bp);
 if (GET(HDRP(bp)) != GET(FTRP(bp)))
   printf("Error: header does not match footer\n");
}

/*
* Requires:
*   None.
*
* Effects:
*   Perform a minimal check of the heap for consistency.
*/
void
checkheap(bool verbose)
{
 void *bp;

 if (verbose)
   printf("Heap (%p):\n", heap_listp);

 if (GET_SIZE(HDRP(heap_listp)) != DSIZE ||
     !GET_ALLOC(HDRP(heap_listp)))
   printf("Bad prologue header\n");
 checkblock(heap_listp);

 for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
   if (verbose)
     printblock(bp);
   checkblock(bp);
 }

 if (verbose)
   printblock(bp);
 if (GET_SIZE(HDRP(bp)) != 0 || !GET_ALLOC(HDRP(bp)))
   printf("Bad epilogue header\n");
}

/*
* Requires:
*   "bp" is the address of a block.
*
* Effects:
*   Print the block "bp".
*/
static void
printblock(void *bp)
{
 bool halloc, falloc;
 size_t hsize, fsize;

 checkheap(false);
 hsize = GET_SIZE(HDRP(bp));
 halloc = GET_ALLOC(HDRP(bp));
 fsize = GET_SIZE(FTRP(bp));
 falloc = GET_ALLOC(FTRP(bp));

 if (hsize == 0) {
   printf("%p: end of heap\n", bp);
   return;
 }

 printf("%p: header: [%zu:%c] footer: [%zu:%c]\n", bp,
     hsize, (halloc ? 'a' : 'f'),
     fsize, (falloc ? 'a' : 'f'));
}

/*
* The last lines of this file configures the behavior of the "Tab" key in
* emacs.  Emacs has a rudimentary understanding of C syntax and style.  In
* particular, depressing the "Tab" key once at the start of a new line will
* insert as many tabs and/or spaces as are needed for proper indentation.
*/

/* Local Variables: */
/* mode: c */
/* c-default-style: "bsd" */
/* c-basic-offset: 8 */
/* c-continued-statement-offset: 4 */
/* indent-tabs-mode: t */
/* End: */