Created
November 5, 2015 08:29
-
-
Save rehrumesh/5fa2bf97e508888f0401 to your computer and use it in GitHub Desktop.
Simple malloc implementation using nodes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
/** | |
* stucture to hold the details about the spaces | |
*/ | |
typedef struct node{ | |
int size; // Original requested size | |
char isFree; // 1 if free or 0 if in use | |
struct node *next; // pointer to to next memory chunk | |
} node; | |
char memory[50000]; // Memory, used to supply memory chunks | |
int initialized = 0; // a tag to mark the 1st use of myMalloc | |
node *head=(node*)&memory[0]; // Header node to hold the starting point | |
/** | |
* initialize the header on the 1st call | |
*/ | |
void initialize(int size) { | |
// checks for the 1st run | |
if(!initialized) { | |
head->size = 50000 - sizeof(node); // Total Available Space | |
head->isFree =1 ; | |
head->next = NULL; | |
initialized = 1; // set the value to 1, so this code won't run again | |
} | |
} | |
/** | |
* myMalloc, which we can used instead of inbuilt "malloc" | |
*/ | |
char* myMalloc(int size) { | |
initialize(size); // If the first run of malloc | |
int isFit=0; // represents the found chunk is fitting or not. | |
int isFound=0; // represents if found a eligible chunk | |
node *temp = head; // temp to slide throgh the list | |
if(size <= 0) return NULL; // returns null if requested size is negative or zero | |
while(temp->next != NULL){ | |
temp = temp->next; | |
/* | |
* if the current chunk is free && its size is bigger than requested. | |
* so the remaining chunk after allocation should atleast fit the node size. | |
* so checking for "sizeof(node)" additional space. | |
*/ | |
if(temp->isFree){ | |
if(temp->size > size + 2*sizeof(node)){ | |
break; | |
isFound=1; | |
} | |
if(temp->size >= size + sizeof(node)){ | |
isFit=1; | |
isFound=1; | |
break; | |
} | |
} | |
} | |
if(isFound || temp==head){ | |
// is there is a nearly fitting chunk, just allocate it. | |
if(isFit){ | |
temp->size=size; | |
temp->isFree=0; | |
}else{ | |
// new node to hold the remaining chunk | |
node *new=(node*) ((char*) temp + size + sizeof(node)); | |
int prevSize=temp->size; | |
temp->next = new; | |
temp->isFree = 0; | |
temp->size = size; | |
new->isFree = 1; | |
new->size = prevSize - sizeof(node)-size; // set the size of remaining chunk | |
// return the pointer points to allocated space | |
} | |
return (char*)temp + sizeof(node); | |
}else{ | |
return NULL; | |
} | |
} | |
/** | |
* myFree, which we can used instead of inbuilt "free" | |
*/ | |
void myFree(int* target){ | |
// get the pointer to set free | |
node* temp=(node*) ((char*)target-sizeof(node)); | |
if(temp!=NULL){ | |
temp->isFree=1; // set free | |
// if the next chunk is also free, combine it with the current chunk. | |
if(temp->next!=NULL && temp->next->isFree==1){ | |
temp->size+=sizeof(node)+temp->next->size; // combined size | |
temp->next = temp->next->next; // join | |
} | |
} | |
} | |
int main(){ | |
char* x=myMalloc(-100); | |
printf("%d\n",x); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment