// COMP1521 19t2 ... Assignment 2: heap management system

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "myHeap.h"

/** minimum total space for heap */
#define MIN_HEAP 4096
/** minimum amount of space for a free Chunk (includes Header) */
#define MIN_CHUNK 32


#define ALLOC 0x55555555
#define FREE  0xAAAAAAAA

/// Types:

typedef unsigned int  uint;
typedef unsigned char byte;

typedef uintptr_t     addr; // an address as a numeric type

/** The header for a chunk. */
typedef struct header {
	uint status;    /**< the chunk's status -- ALLOC or FREE */
	uint size;      /**< number of bytes, including header */
	byte data[];    /**< the chunk's data -- not interesting to us */
} header;

/** The heap's state */
struct heap {
	void  *heapMem;     /**< space allocated for Heap */
	uint   heapSize;    /**< number of bytes in heapMem */
	void **freeList;    /**< array of pointers to free chunks */
	uint   freeElems;   /**< number of elements in freeList[] */
	uint   nFree;       /**< number of free chunks */
};


/// Variables:

/** The heap proper. */
static struct heap Heap;


/// Functions:

static addr heapMaxAddr (void);

// function to round up to next multiple if necessary
static int roundup(int numToRoundUp, int multiple);

// function returns index of supplied chunk
static int indexOfFreeChunk(header *chunk);

// function readjusts pointers after removal from freeList
static void readjustPointers(int indexChunk);

/** Initialise the Heap. */
int initHeap (int size)
{
    
	
	/// TODO ///
    if (size < MIN_HEAP) {
        size = MIN_HEAP;
    }
    
    size = roundup(size, 4);
    // heapMem is pointing to a chunk
    Heap.heapMem = malloc(size);
    if (Heap.heapMem == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(-1);
    }
    // set heapMem to be all zeroes, memset returns pointer to chunk
    
    Heap.heapMem = memset(Heap.heapMem, 0, size);
    
    Heap.heapSize = size;
    // pointer to chunkHeader
    header *chunkHeader = (header *)(Heap.heapMem);
    
    // setting heapMem to be a single free chunk of size;
    
    chunkHeader->size = size;
    chunkHeader->status = FREE;
    
    Heap.freeElems = 1;
    Heap.freeList = malloc(Heap.freeElems * sizeof(void *));
    if (Heap.freeList == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(-1);
    }
    Heap.freeList[0] = chunkHeader; // check???
    Heap.nFree = 1;
    
    
	
	
    
    
	return 0; // this just keeps the compiler quiet
}

/** Release resources associated with the heap. */
void freeHeap (void)
{
	free (Heap.heapMem);
	free (Heap.freeList);
}

/** Allocate a chunk of memory large enough to store `size' bytes. */
void *myMalloc (int size)
{
	/// TODO ///
	if (size < 1) {
	    return NULL;
    }
    size = roundup(size, 4);
    // round up size to nearest multiple of 4 if necessary
	
    // find the first chunk that fits
    // check if I have found minimum if not return null
    // start up another loop to update minimum chunk
    
    header *minChunk;
    /* for (int i = 0; i < Heap.freeElems; i++) {
        header *currentChunk = (header *) Heap.freeList[i];
        
        
        if (currentChunk->size >= size + sizeof(header)) {
            minChunk = currentChunk;
            break;
        }
    } */
    
    int i = 0;
    int j;
    
   
    while (i < Heap.freeElems) {
        header *currentChunk = (header *) Heap.freeList[i];
        
        if (currentChunk->size >= size + sizeof(header)) {
            minChunk = currentChunk;
            j = i + 1;
            break;
        }
        i++;
    }
       
        
    // didn't find any chunk that fits
    
    if (minChunk == NULL) {
        return NULL;
    }
    
    // finding min available chunk
    
    
    while (j < Heap.freeElems) {
        header *currentChunk = (header *) Heap.freeList[j];
        if ( (currentChunk->size >= size + sizeof(header)) 
        && (currentChunk->size < minChunk->size) ) {
            minChunk = currentChunk;
        }
        j++;
    }
        
    
    if (minChunk->size >= size + sizeof(header) + MIN_CHUNK) {
        
        // split and make excess a new small free chunk
        // allocating space for "size"
        header *allocatedChunk = minChunk;
        allocatedChunk->status = ALLOC; 
        
        

        // calculating excessSize
        header * newChunkHeader = (header *) 
                            ((addr) allocatedChunk + size + sizeof(header));
        
        uint excessSize = minChunk->size - (size + sizeof(header));
        printf("excessSize = %d\n", excessSize);
        allocatedChunk->size = size + sizeof(header);
        newChunkHeader->size = excessSize;
        newChunkHeader->status = FREE;
        
        // readjusting pointer
        
        Heap.freeList[ indexOfFreeChunk(allocatedChunk) ] = newChunkHeader;
        return ( (void *) ( (addr) allocatedChunk + sizeof(header)) ); 
        
    } else {
        
        // allocate whole chunk
        minChunk->status = ALLOC;
        // readjust pointers from minChunk onwards
        readjustPointers( indexOfFreeChunk(minChunk) );
        Heap.nFree--;
        
        return ( (void *) ( (addr) minChunk + sizeof(header)) ); 
    }
	    
    return 0; // this just keeps the compiler quiet
}
    
	
	
	    
	    
    
            
            
            
            
            
            
            
                
            
            
            
            
             
            
            
        
            
        
	    
	    
	    
	    
	    

/** Deallocate a chunk of memory. */
void myFree (void *obj)
{
	/// TODO ///
	
	// 
    /* int flag = 0;
    addr iterationChunk = (addr) Heap.heapMem;
    while (iterationChunk < heapMaxAddr ()) {
        header *chunk = (header *) iterationChunk;
        if ( chunk->status == ALLOC 
            && (void *) ((addr) chunk + sizeof(header)) == obj) {
            flag = 1;
        }
        iterationChunk += chunk->size;
    }
    
    if (flag == 0) {
        fprintf( stderr, "Attempt to free unallocated chunk\n");
        exit(1);
    }
        
    
    // freeing chunk
    header *freedChunk = (header *) ( (addr) obj - sizeof(header) );
    obj = memset(obj, 0, freedChunk->size - sizeof(header));
    freedChunk->status = FREE;
    
    
    
    // readjust pointers in freeList
    
    // find chunks adjacent to freeChunk and check if they are free
    // if so merge them
    
    
    
    // iterate chunk by chunk
    addr curr = (addr) Heap.heapMem;
	while (curr < heapMaxAddr ()) {
		header *currChunk = (header *) curr;
		
		// behindChunk and aheadChunk are check variables
        header *behindChunk = currChunk;
		header *aheadChunk = currChunk;
		
		// currChunk is behind freedChunk
		if ( (header *) ( (addr) currChunk + currChunk->size) == freedChunk ) {
	        
	        if (currChunk->status == FREE) {
                
                // merging
                
                // adding chunk sizes
                behindChunk->size = behindChunk->size + freedChunk->size;
                // removing header of freedChunk
                freedChunk = memset(freedChunk, 0, sizeof(header));
                // find pointer which points to currChunk in freeList[]
                // readjust it to point at currChunk the trailing chunk
                for (int i = 0; i < Heap.freeElems; i++) {
                    header *chunk = (header *) Heap.freeList[i];
                    if (chunk == currChunk) {
                        Heap.freeList[i] = behindChunk;
                    }
                }
                
	        }
        
        // currChunk is ahead of freedChunk - there is an aheadChunk
        } else if (currChunk == (header *) 
                                ( (addr) freedChunk + freedChunk->size) ) {
            
            
            if (currChunk->status == FREE) {
                
                // case where there was a trailing free chunk already added 
                if (behindChunk != currChunk) {
                    
                    behindChunk->size = behindChunk->size + aheadChunk->size;
                    aheadChunk = memset(aheadChunk, 0, sizeof(header));              
                    // adjust pointers from currChunk onwards
                    readjustPointers( indexOfFreeChunk(currChunk) );
                    
                    
                    
                    
                    
                } else {
                    // adjust current pointer to point at freedChunk
                }
            }
        }
        curr += currChunk->size;
    } */
		  
}

/** Return the first address beyond the range of the heap. */
static addr heapMaxAddr (void)
{
	return (addr) Heap.heapMem + Heap.heapSize;
}

/** Convert a pointer to an offset in the heap. */
int heapOffset (void *obj)
{
	addr objAddr = (addr) obj;
	addr heapMin = (addr) Heap.heapMem;
	addr heapMax =        heapMaxAddr ();
	if (obj == NULL || !(heapMin <= objAddr && objAddr < heapMax))
		return -1;
	else {
		return (int) (objAddr - heapMin);
    }
}
/** Dump the contents of the heap (for testing/debugging). */
void dumpHeap (void)
{
	int onRow = 0;

	// We iterate over the heap, chunk by chunk; we assume that the
	// first chunk is at the first location in the heap, and move along
	// by the size the chunk claims to be.
	addr curr = (addr) Heap.heapMem;
	while (curr < heapMaxAddr ()) {
		header *chunk = (header *) curr;

		char stat;
		switch (chunk->status) {
		case FREE:  stat = 'F'; break;
		case ALLOC: stat = 'A'; break;
		default:
			fprintf (
				stderr,
				"myHeap: corrupted heap: chunk status %08x\n",
				chunk->status
			);
			exit (1);
		}

		printf (
			"+%05d (%c,%5d)%c",
			heapOffset ((void *) curr),
			stat, chunk->size,
			(++onRow % 5 == 0) ? '\n' : ' '
		);

		curr += chunk->size;
	}

	if (onRow % 5 > 0)
		printf ("\n");
}

static int roundup(int numToRoundUp, int multiple) {

    int remainder = numToRoundUp % multiple;
    if (remainder != 0) {
        return numToRoundUp = numToRoundUp + multiple - remainder;
    } else {
        return numToRoundUp;
    }

}

static int indexOfFreeChunk(header *chunk) {
    
    for (int i = 0; i < Heap.freeElems; i++) {
        header *currChunk = (header *) Heap.freeList[i];
        if (currChunk == chunk) {
            return i;
        }
    }
    return -1;
}

static void readjustPointers(int indexChunk) {
    
    while (indexChunk < Heap.freeElems) {
        
        if (indexChunk == Heap.freeElems - 1) {
            Heap.freeList[indexChunk] = NULL;
            break;
        }
        Heap.freeList[indexChunk] = Heap.freeList[indexChunk + 1];   
        indexChunk++;
    }
    
}