#include <stdio.h> // Any other headers we need here
#include <malloc.h> // We bring in the old malloc function
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <pthread.h>
#include<string.h>


// The Node in the linked list
    struct block
    {
        size_t size;
        int is_free;
        struct block *next;
    };
struct block *head, *tail;

struct block* getFreeBlock(size_t size);

void* mymalloc(size_t size)
{
    size_t total_size; //total_size = size + header_size
    void* block;
    struct block *header;
    if(!size)
        return NULL;
    header = getFreeBlock(size);
    if(header)
    {
        header->is_free = 0;
        printf("Allocated %zu bytesn",header->size);
        return (void*)(header+1); //This is the first byte of the actual memory block.
    }
    total_size = sizeof(struct block) + size;
    block = sbrk(total_size);
    if(block == (void*)-1)
    {
        printf("Malloc Failed!n");
        return NULL;
    }
    header = block;
    header->size = size;
    header->is_free = 0;
    header->next = NULL;
    if(!head)
        head = header; // the first block is a list of free + allocated blocks
    if(tail)
        tail->next = header; // if tail is initialized then
    tail = header; //if tail is not initialized, this this block must be the first and the last block
    printf("Allocated %zu bytesn",header->size);

    return (void*)(header+1); //header+1 = memory block
}

struct block* getFreeBlock(size_t size)
{
    struct block *current = head;
    while(current)
    {
        if(current->is_free)
        {
            if(current->size >= size)
                return current;
        }
        current = current->next;
    }
    return NULL;
}

void myfree(void *block){
    struct block *header, *temp;
    void *brk;
    if(!block)
        return;
    header = (struct block*)block - 1; // moving to the block that is just behind the block we want to free.
    brk = sbrk(0);
    // WE check if the block t be freed is at the end of the heap can compare it to the current program break.
    if((char*)block + header->size == brk)
    {
        // If we only have one block, and that block is freed
        if(head == tail)
            head = tail = NULL;
        // Traversing to the end of the linked list.
        else
        {
            temp = head;
            while(temp)
            {
                if(temp->next == tail)
                {
                    temp->next = NULL;
                    tail = temp;
                }
                temp = temp->next;
            }
        }
        // Releasing the memory
        // total_size = size_of_block + header_size
        sbrk(- (sizeof(struct block) + header->size));
        printf("Freed some memoryn");
        return;
    }
    // If the block is not the last block, then we simply set the block as free.
    // The getFreeBlock function first checks for free blocks, before calling sbrk().
    header->is_free = 1;
    printf("Freed some memoryn");
}