#include<stdio.h>
#include<stdlib.h>

struct memBlock{
    int pid; //ProcessID
    int isFree; //Checks if the node is free
    int size; //size of the node
    struct memBlock *next; //points to the next node
};typedef struct memBlock memBlock;

int free_pid = 00;

//Snapshot of the current memory blocks
void snapshot(struct memBlock* n){
	int pid;
    printf("Process ID\t\tSize\t\tStatus\n");
    printf("------------------------------------------------\n");
    while(n != NULL){ //while the node is not empty
        printf("%d\t\t\t", n->pid); //ProcessID of the node
        printf("%d\t\t", n->size); //Size of the node
        if(n->isFree == 0) //isFree==0 means the node isn't empty
		{
        	if(pid=1)
        	{
        		printf("Operating System\n"); //the node with the ProcessID 1 is allocated for the OS
			}
			else
            {
            	printf("Occupied\n"); //The node is is occupied with a process
			}
        }else{
            printf("Free\n"); //The node is empty/ A free block of memory
        }
        n = n->next;
    }
}

memBlock *newBlock(int new_size){ //Takes in the size of the memory as input
    memBlock *memory = (memBlock*)malloc(sizeof(memBlock *)); //Allocating memory for the MemBlock nodes using malloc()
    memory->isFree = 1; //memory is empty
    memory->pid = free_pid;
    memory->size = new_size; //insert the size of the memory
    memory->next = NULL; //points to NULL to end the list
    return memory;
}

//Adding a new process/node to the list
int addProcess(memBlock* node, int new_size, int new_pid){ //Takes the head node, the size of the new node, and the ProcessID that's to be allocated memory
    while(node != NULL){
        if(node->isFree == 1 && node->size == new_size){
            node->isFree = 0; //the node isn't free anymore
            node->pid = new_pid;
            return 1;
        }

        if(node->isFree == 1 && node->size > new_size){
            memBlock *unused = newBlock(node->size - new_size); //takes some extra space from the unused block of memory
            unused->next = node->next; //points the unused block of memory as the next node
            node->next = unused;
            node->isFree = 0;
            node->size = new_size; //enter the size of the new node
            node->pid = new_pid; //insert the Process ID
            return 1;

        }

        node = node->next; //points to the next node
    }

    printf("No free space!\n");
    return 0;
}


int deleteProcess(memBlock* node, int del_pid){ //Takes in the head node and the ProcessID that needs to be removed.

    //Define the previous node which initially it points to the head.
    //In the initial state, both node and prenode points to the head. Because thats where a linked list starts.
    memBlock* prev_node = node;

    while(node != NULL){  //Traverse through the list untill you meet the node->next = NULL
        //If you find the node that you have to delete, then,
        if(node->pid == del_pid){
            //First make the node a free node. Set is free to true(1)
            node->isFree = 1;
            //Then set the pid of the free node to 0. (I used 0 as the pid to mark all the free blocks)
            node->pid = free_pid;

            //If the node and prenode points to the same block, then return 1 because if node = prenode then the given node is the head
            if(node == prev_node){
                return 1;
            }
            //If the next node to a given node is NULL then the given node is the end of the list. So again we return 1
            if(node->next == NULL){
                return 1;
            }

            if(prev_node->isFree == 1){
                prev_node->size = prev_node->size + node->size;
                prev_node->next = node->next;
                free(node);
                node = prev_node;
            }
            //Right merge
            if(node->next->isFree == 1){
                memBlock* next_node = node->next;
                node->size = next_node->size + node->size;
                node->next = next_node->next;
                node->isFree = 1;
                free(next_node);
            }
            return 1;
        }
        //Increment the loop
        prev_node = node;
        node = node->next;
    }
    printf("No match for Process ID %d\n", del_pid);
    return 0;
}


int main(){
	    int choice;
	    int new_size, new_pid;
	    int del_pid;
	    memBlock* head = newBlock(2560000); //The total size of the memory
	    addProcess(head,400000,1); //Allocating 400k bytes for the Operating system as the 1st Process (pid=1)

    while (1)
    {
    	printf("Memory Management using First-Fit Algorithm\n");
        printf("---------------------------------------------\n");
	    printf("1.Allocate memory for new Process\n");
        printf("2.Deallocate memory from an excisting process\n");
        printf("3.Print current snapshot\n");
        printf("4.Exit\n");
        printf("---------------------------------------------\n");
        printf("Select an option: ");
        scanf("%d", &choice);
        printf("\n\n");

        switch (choice)
        {
            case 1:
            	printf("Enter Process ID\n");
				scanf("%d", &new_pid);
				printf("Enter the size of the memeory block for Process ID %d:\n", new_pid);
				scanf("%d", &new_size);
                addProcess(head,new_size,new_pid);
				printf("Memory allocated for Process %d\n", new_pid);
                break;

            case 2:
            	printf("\nEnter the Process ID you want to terminate:\n");
				scanf("%d", &del_pid);
                deleteProcess(head,del_pid);
                printf("Process %d terminated", del_pid);
                break;

            case 3:
                snapshot(head);
                break;

            case 4:
                printf("Exit\n");
                exit(0);

            default:
                printf("Error!, invalid choice.\n");
                break;
        }

        printf("\n\n");
    }

}