Heap Management !!!!
-
Hi ! I'm writing a heap mangement functions namely Alloc and Free. An array of 4096 character is simulated as the heap. The main progam which has been written call Alloc 60% of the time and Free 40% of the time. The heap management is implemented by the linked-list. The algorithm to choose the page is first fit. The Alloc is passed in the number of bytes to be allocated. The Free function takes in the pointer at the begining of the chunk to be allocated. Here is what i've attempt at it. I define a linked-list structure with *next is the pointer to the next node, size is the size in byte of how big the chunk is.
#include #include "ssHeap.h" typedef struct _HEAP_STRUCT { DWORD size; struct _HEAP_STRUCT *next; }HEAP_STRUCT; HEAP_STRUCT *front; HEAP_STRUCT *temp, *prevNode; HEAP_STRUCT *node; char HeapSpace[4096]; LPVOID beginOfTheHeap; void ssInit(void) { front = new HEAP_STRUCT; beginOfTheHeap = malloc(sizeof(HeapSpace)); front = (HEAP_STRUCT*)beginOfTheHeap; front->next = NULL; front->size = 0; node = new HEAP_STRUCT; node->next = NULL; node->size = 0; }; LPVOID ssAlloc(LONG nBytes) { HEAP_STRUCT *alloc = new HEAP_STRUCT; int allocated = false; while(nBytes % 8 != 0) //make this multiple of 8. nBytes++; //if this is not multiple of 8, increase it //for example if 31%8 =7, then it will allocate 32bytes. if(front->next == NULL) // this only happen if ssAlloc is called the first time { node = new HEAP_STRUCT; //create a new node node->next = NULL; //new node ->next points to NULL node = front + nBytes; //this node address is nBytes away from the front front->size = nBytes; //this new node's size is what is left off front->next = node; return node; } while(front->next != NULL) { long freeSpace = ((int)front->next - (int)(front + front->size))/sizeof(char); //the free space between block if( freeSpace> nBytes) //if the size is greater than nBytes { while(freeSpace != nBytes) //the size must be multiple of 8 { freeSpace = freeSpace / 2; //divide the free space to two } node = new HEAP_STRUCT; //create a new node node = front + front->size; //the mem location of the new node; node->size = nBytes; node->next = front->next ; //point to the next free space that temp point to front->next = node; //now this one is point to the node that is new allocated alloc = node; //for returning purpose. -
Hi ! I'm writing a heap mangement functions namely Alloc and Free. An array of 4096 character is simulated as the heap. The main progam which has been written call Alloc 60% of the time and Free 40% of the time. The heap management is implemented by the linked-list. The algorithm to choose the page is first fit. The Alloc is passed in the number of bytes to be allocated. The Free function takes in the pointer at the begining of the chunk to be allocated. Here is what i've attempt at it. I define a linked-list structure with *next is the pointer to the next node, size is the size in byte of how big the chunk is.
#include #include "ssHeap.h" typedef struct _HEAP_STRUCT { DWORD size; struct _HEAP_STRUCT *next; }HEAP_STRUCT; HEAP_STRUCT *front; HEAP_STRUCT *temp, *prevNode; HEAP_STRUCT *node; char HeapSpace[4096]; LPVOID beginOfTheHeap; void ssInit(void) { front = new HEAP_STRUCT; beginOfTheHeap = malloc(sizeof(HeapSpace)); front = (HEAP_STRUCT*)beginOfTheHeap; front->next = NULL; front->size = 0; node = new HEAP_STRUCT; node->next = NULL; node->size = 0; }; LPVOID ssAlloc(LONG nBytes) { HEAP_STRUCT *alloc = new HEAP_STRUCT; int allocated = false; while(nBytes % 8 != 0) //make this multiple of 8. nBytes++; //if this is not multiple of 8, increase it //for example if 31%8 =7, then it will allocate 32bytes. if(front->next == NULL) // this only happen if ssAlloc is called the first time { node = new HEAP_STRUCT; //create a new node node->next = NULL; //new node ->next points to NULL node = front + nBytes; //this node address is nBytes away from the front front->size = nBytes; //this new node's size is what is left off front->next = node; return node; } while(front->next != NULL) { long freeSpace = ((int)front->next - (int)(front + front->size))/sizeof(char); //the free space between block if( freeSpace> nBytes) //if the size is greater than nBytes { while(freeSpace != nBytes) //the size must be multiple of 8 { freeSpace = freeSpace / 2; //divide the free space to two } node = new HEAP_STRUCT; //create a new node node = front + front->size; //the mem location of the new node; node->size = nBytes; node->next = front->next ; //point to the next free space that temp point to front->next = node; //now this one is point to the node that is new allocated alloc = node; //for returning purpose.Probably lots of time is lost in finding a chunk of the wanted size. This used to be a known problem in C run time libraries, that's why many people wrote their own memory management module. A good idea is to prepare 'pools' of predefined sizes (e.g. multiples of 8) and manage lists of vectors in each of the pools. If your application then requests e.g. 15 bytes, you round it up to the next multiple of 8 (16 in this case) and then go to the pool of 16 bytes. If it's empty, you allocate space for e.g. 10 chunks of 16 bytes. The next time you need 16 bytes (>9, <=16), it will be much faster. Of course you need to foresee additional list-pointers in your vector of 10 chunks of 16 bytes to store information about which chunk is already handed out to the application, which one is free, what the size is, ... Enjoy life, this is not a rehearsal !!!