USA: +1 (725) 712-1730 
Sign in
Can Someone Please read the question in detail and respond them as its instructions says in pure coding. I do not want any abstracts answers. I already Posted
this question 3 times all I’m getting is a different answers or different code or abstracts answers. I want the exact coding for this!!!!!!!!!!!!!!!!!!!!!!!!
Programming Assignment 7
Simulated Heap Using Linked Lists
DUE: See Canvas Programming Assignment 7 link.
Create a file called mallok.h The contents of that file should be
void create_pool(int size);
void *my_malloc(int size);
void my_free(void *block);
void free_pool();
You may not modify these prototypes. The work you submit will be tested using a secret grader program written to compile with this header. If you modify these prototypes at all (including the parameter descriptions or the capitalization or spelling of the function names) the grader’s program may not compile and your work will be penalized.
Your implementation will be an “abstract object”, not an ADT as discussed in Chapter 19. In other words, you will be programming a single global heap, not a heap class. You may use a small number of global variables to implement your heap, but these should be marked “static” to limit access to them. The argument for create_pool indicates how many bytes should be included in the heap. Your implementation of create_pool must use malloc to acquire a single block of exactly this size. This single block is your “private heap”. All calls to my_alloc must be satisfied by returning a piece of this private heap if possible. my_alloc should not simply use malloc to allocate the block the caller has asked for. Likewise, my _free should return a block to the private heap, not to the built-in heap by calling free. my_malloc and my_free have the same parameters as malloc and free (although the types have been simplified just a little).
Initially the private heap contains a single free block that has the same size as the call to create_pool. In responding to my_alloc and my_free calls, this initial block will sometimes be split into smaller pieces and these pieces must later be recombined (coalesce) whenever possible. At any given time, some of the blocks will be in use because my_alloc has given them to a caller, or they will be free, meaning they are (back) in the private heap. You must build a single linked list to keep track of all the blocks, whether they are free or not. The linked list will be similar to the list you built in HW6, but each node will keep track of a storageblock taken from the private heap. For each block, be sure to remember – where it starts (a memory address) – how big it is (a number of bytes) – whether it is free or not. Your linked list of blocks must be kept in order by the starting address of the block. This means that blocks that are next to each other in memory will also be next to each other in your linked list of blocks, i.e. you need the capability of inserted nodes “anywhere” within your list. To build your linked list of blocks, you will need to create list nodes. You ARE allowed to use malloc in the usual way to create a linked list node. (But as stated above, you are NOT allowed to use malloc to create the blocks themselves.) my_malloc must search the block list for the FIRST free block that is big enough to satisfy the requested size. If the first free block is more than big enough, then my_malloc should use the first part of the block to satisfy the request and keep the latter part in the private heap. (For example, if my_malloc is looking for a block of 200 bytes and the chosen free block has 1000 bytes starting at address 6000, then the allocated block returned to the caller must be 200 bytes starting at address 6000. A second block of 800 bytes starting at address 6200 is kept in the private heap for possible later use.)
my_free should return a block to the private heap, making that storage once again available. In the process you must recombine the block with any neighboring blocks that are also free.
free_pool() completely frees the private heap. Be sure all allocated memory is freed when this function is called by the client. This is important for multiple tests run while grading. Many students make errors where subsequent tests are rendered useless. Adding the free_pool function to your private heap package affords the ability to start over whenever an error arises during testing. The tests used will call this function whenever an error occurs followed by a call to create_pool to start over with a clean heap for continued testing.
Calls to my_malloc that cannot be satisfied should return NULL. Calls to my_free that provide an invalid pointer should do nothing. Put your implementation in a file called mallok.c
In a file called mallok_test.c, write code that will test your implementation. Your testing must include at least the following scenarios (call free_pool after each of these preliminary simple tests):
-create a pool of 1000 bytes. Count how times you can successfully request a block of size 10.
-create a pool of 1000 bytes. Make 5 requests for blocks of 200 bytes. Free all 5 blocks. Repeat this request/free pattern several times to make sure you can reuse blocks after they are returned.
-create a pool of 1000 bytes. Make 5 requests for blocks of 200 bytes. Free the middle block. Request a block of 210 bytes (it should fail) Request a block of 150 bytes (it should succeed) Request a block of 60 bytes (it should fail) Request a block of 50 bytes (it should succeed) etc.
-create a pool of 1000 bytes. Request 5 blocks of 200 bytes. Fill the first block with the letter ‘A’, the second block with ‘B’, etc. Verify that the values stored in each block are still there. (Is the first block full of A’s, second block full of B’s, etc.)
-create a pool of 1000 bytes. Request and return a block of 1000 bytes Request and return four blocks of 250 bytes Request and return ten blocks of 100 bytes
The above tests are only a starting point. The grading tests will make many calls to create_pool, free_pool, my_malloc and my_free with much segmentation and small non-contiguous free blocks generated. For this reason, you should design many more tests than listed above.
Your test code will make many calls to my_malloc, often saving the returned pointers and then using those pointers to call my_free. Your test code should print out messages indicating if the different tests are working as expected.
Here is a diagram showing aspects of the implementation. The private heap is shown at the top. Although dotted lines are shown, it is actually one large piece of memory that was obtained from a single call to malloc during execution of create_pool. The nodes of the linked list have additional fields that are not shown.
There are many factors to consider:
•create_pool should do nothing if the private heap is still active.
•my_malloc should do nothing if the private heap is not active (doesn’t exist) or if the requested bytes are not available.
•my_free should do nothing if the received pointer (block) does not exist.
•free_pool should place the private heap in the same state as when the program first began execution, i.e.
“ALL” blocks are freed, “ALL” pointers are freed which includes the entire list AND the private heap itself. Any time this function is called, no heap operations can be performed until a new heap is requested through a call to create_pool
•Be ABSOLUTELY sure to ALWAYS set any pointers to NULL following a system call to free(p), i.e. you will be using malloc for various reasons and free to free up space on the actual heap. Not doing so will cause many of the grading tests to fail and will result in high loss of grade points.This warning suggest that your various functions should ALWAYS be checking for the validity of a pointer before proceeding with any operations. For example, what would happen if the client calls my_malloc BEFORE ever calling create_pool, wants to start over by calling free_pool followed by create_pool, calls free_pool and immediately calls my_malloc, etc.
As with HW6, your program should compile at the command prompt and your code files (mallok.h, mallok.c, and mallok_test.c and a make file for compiling and linking – 4 files in all) should be zipped into a single zipped folder using the Windows zip utility (select files, right click one of the selected group, point to Send to… and click Compressed (zipped) Folder. Upload this zipped folder to the link for Home work 7. Also, follow proper documentation rules. Be sure to name all files and functions EXACTLY as named here.
Expert Answer
#include <stdio.h>
#include “mallok.h”
// pool of 1000 bytes
// count how many times block size of 10 is requested
void test1()
{
printf(“######## Start Test 1 ########n”);
create_pool(1000);
int counter = 0;
printf(“Creating 100, 10-byte blocks.n”);
printf(“Counter: %dn”, counter);
while (my_malloc(10) != NULL)
{
counter++;
}
printf(“Counter: %dn”, counter);
printAll();
free_pool();
printf(“######## End Test 1 ########nn”);
}
// pool of 1000 bytes, make 5 requests for 5 blocks of 200 bytes
// free all 5 blocks
// request/free several times to make sure reusable
void test2()
{
printf(“######## Start Test 2 ########n”);
create_pool(1000);
void *foo1 = my_malloc(200);
void *foo2 = my_malloc(200);
void *foo3 = my_malloc(200);
void *foo4 = my_malloc(200);
void *foo5 = my_malloc(200);
printAll();
printf(“Creating 5 blocks of 200 bytes:n”);
printf(“First block: %pn”, foo1);
printf(“Second block: %pn”, foo2);
printf(“Third block: %pn”, foo3);
printf(“Fourth block: %pn”, foo4);
printf(“Fifth block: %pn”, foo5);
my_free(foo1);
my_free(foo2);
my_free(foo3);
my_free(foo4);
my_free(foo5);
//printAll();
printf(“Freeing 5 blocks of 200 bytes:n”);
printf(“First block: %pn”, foo1);
printf(“Second block: %pn”, foo2);
printf(“Third block: %pn”, foo3);
printf(“Fourth block: %pn”, foo4);
printf(“Fifth block: %pn”, foo5);
printf(“nCreating 2 blocks of 200 bytes:n”);
foo1 = my_malloc(200);
foo2 = my_malloc(200);
printf(“First block: %pn”, foo1);
printf(“Second block: %pn”, foo2);
printAll();
printf(“nFreeing 2 blocks of 200 bytes:n”);
my_free(foo1);
my_free(foo2);
printf(“First block: %pn”, foo1);
printf(“Second block: %pn”, foo2);
printAll();
free_pool();
printf(“######## End Test 2 ########nn”);
}
// create pool of 1000 bytes
// make 5 requests for blocks of 200 bytes
// free middle block
// request 210 bytes (fail)
// request 150 bytes (success)
// request 60 bytes (fail)
// request 50 bytes (success)
void test3()
{
printf(“######## Start Test 3 ########n”);
create_pool(1000);
void *foo1 = my_malloc(200);
void *foo2 = my_malloc(200);
void *foo3 = my_malloc(200);
void *foo4 = my_malloc(200);
void *foo5 = my_malloc(200);
printAll();
my_free(foo3); // free middle node
printAll();
void *foo6 = my_malloc(210); // fail
if (foo6 == NULL)
printf(“Request for 210 bytes: FAILEDn”);
else
printf(“Request for 210 bytes: PASSEDn”);
foo3 = my_malloc(150); // success
if (foo3 == NULL)
printf(“Request for 150 bytes: FAILEDn”);
else
printf(“Request for 150 bytes: PASSEDn”);
//printAll();
foo6 = my_malloc(60); // fail
if (foo6 == NULL)
printf(“Request for 60 bytes: FAILEDn”);
else
printf(“Request for 60 bytes: PASSEDn”);
foo6 = my_malloc(50); // success
if (foo6 == NULL)
printf(“Request for 50 bytes: FAILEDn”);
else
printf(“Request for 50 bytes: PASSEDn”);
printAll();
free_pool();
printf(“######## End Test 3 ########nn”);
}
// create pool of 1000 bytes
// request 5 blocks of 200 bytes
// fill first block with ‘A’, second with ‘B’, etc.
// verify values stored in each block still there
void test4()
{
int i;
printf(“######## Start Test 4 ########n”);
create_pool(1000);
char *foo1 = (char *) my_malloc(200);
char *foo2 = (char *) my_malloc(200);
char *foo3 = (char *) my_malloc(200);
char *foo4 = (char *) my_malloc(200);
char *foo5 = (char *) my_malloc(200);
printAll();
for (i = 0; i < 200; i++)
{
foo1[i] = ‘A’;
foo2[i] = ‘B’;
foo3[i] = ‘C’;
foo4[i] = ‘D’;
foo5[i] = ‘E’;
}
//int i = 0;
while (i < 200)
{
if (foo1[i] != ‘A’)
{
printf(“FAILED CHARACTER TEST ON ‘A’!n”);
break;
}
if (foo2[i] != ‘B’)
{
printf(“FAILED CHARACTER TEST ON ‘B’!n”);
break;
}
if (foo3[i] != ‘C’)
{
printf(“FAILED CHARACTER TEST ON ‘C’!n”);
break;
}
if (foo4[i] != ‘D’)
{
printf(“FAILED CHARACTER TEST ON ‘D’!n”);
break;
}
if (foo5[i] != ‘E’)
{
printf(“FAILED CHARACTER TEST ON ‘E’!n”);
break;
}
i++;
}
printf(“Successful if no characters printed out.n”);
//free_pool();
printf(“######## End Test 4 ########nn”);
}
// create pool of 1000 bytes
// request and return 1000 bytes
// request and return 4 blocks of 250 bytes
// request and return 10 blocks of 100
void test5()
{
printf(“######## Start Test 5 ########n”);
create_pool(1000);
void *foo1, *foo2, *foo3, *foo4, *foo5,
*foo6, *foo7, *foo8, *foo9, *foo10;
printf(“Requesting 1000 bytesn”);
foo1 = my_malloc(1000);
//printAll();
printf(“Returning the 1000 bytesn”);
my_free(foo1);
//printAll();
printf(“Requesting four blocks of 250 bytesn”);
//printAll();
foo1 = my_malloc(250);
foo2 = my_malloc(250);
foo3 = my_malloc(250);
foo4 = my_malloc(250);
printAll();
printf(“Returning the blocks of 250 bytesn”);
my_free(foo1);
my_free(foo2);
my_free(foo3);
my_free(foo4);
printAll();
printf(“Requesting ten blocks of 100 bytesn”);
foo1 = my_malloc(100);
foo2 = my_malloc(100);
foo3 = my_malloc(100);
foo4 = my_malloc(100);
foo5 = my_malloc(100);
foo6 = my_malloc(100);
foo7 = my_malloc(100);
foo8 = my_malloc(100);
foo9 = my_malloc(100);
foo10 = my_malloc(100);
//printAll();
printf(“Returning the blocks of 100 bytesn”);
my_free(foo1);
my_free(foo2);
my_free(foo3);
my_free(foo4);
my_free(foo5);
my_free(foo6);
my_free(foo7);
my_free(foo8);
my_free(foo9);
my_free(foo10);
//printAll();
free_pool();
printf(“######## End Test 5 ########nn”);
}
int main(void)
{
test1();
test2();
test3();
test4();
test5();
return 0;
}
mallok.c
#include <stdio.h> // temporarily
#include <stdlib.h>
#include “mallok.h”
struct node
{
void *startAddr; // [0-pool]
int blockSize; // size of block
int isFree; // Bool: 0 = false, 1 = true
struct node *next;
};
typedef struct node Node;
typedef enum {false, true} Bool;
//void printNode(Node *);
// static global vars
static Node *head = NULL;
static void *heapSpace;
// allocates initial pool of memory (in bytes)
void create_pool(int size)
{
// track internal state
heapSpace = malloc(size);
// create first node of free space
head = (Node *) malloc(sizeof(Node));
head->startAddr = heapSpace;
head->blockSize = size;
head->isFree = true;
head->next = NULL;
}
// allocates specified chunk from my heap
void *my_malloc(int size)
{
Node *curr = head;
void *heapAddr = NULL;
// traverse list
while (curr != NULL)
{
if (curr->isFree && curr->blockSize == size)
{
curr->isFree = false;
heapAddr = curr->startAddr;
break;
}
else if (curr->isFree && curr->blockSize > size)
{
// create new node, copy curr node data to new
Node *newNode = (Node *) malloc(sizeof(Node));
newNode->startAddr = curr->startAddr + size;
newNode->blockSize = curr->blockSize – size;
newNode->isFree = curr->isFree;
newNode->next = curr->next;
// update curr node
curr->blockSize = size;
curr->isFree = false;
curr->next = newNode;
heapAddr = curr->startAddr;
break;
}
curr = curr->next;
}
return heapAddr;
}
// returns memory back to my heap
void my_free(void *block)
{
if (block != NULL)
{
Node *curr = head;
Node *prev = NULL;
// find node to be freed
while (curr != NULL && curr->startAddr != block)
{
prev = curr;
curr = curr->next;
}
if (prev == NULL) // removing head node
{
if (curr->next != NULL && curr->next->isFree) // mergeable
{
Node *temp = curr->next;
curr->blockSize += curr->next->blockSize;
curr->next = curr->next->next;
free(temp);
}
curr->isFree = true;
}
else // somewhere else in list
{
// check if we can merge previous node
if (prev->isFree)
{
// is this not needed?
if (prev->startAddr < head->startAddr)
{
head = prev;
}
prev->blockSize += curr->blockSize;
prev->next = curr->next;
free(curr);
curr = prev;
}
// check if we can merge next node
if (curr->next != NULL && curr->next->isFree)
{
// update current
curr->blockSize += curr->next->blockSize;
curr->next = curr->next->next;
free(curr->next);
}
else // can’t merge: make this node free space
{
curr->isFree = true;
}
}
}
}
// print entire list of nodes
void printAll()
{
printf(“~~~~~ list start ~~~~~n”);
printf(” head node at addr: %pn”, head);
Node *curr = head;
int count = 1;
while (curr != NULL)
{
printf(“node #%d at addr: %pn”, count, curr);
printf(” startAddr: %pn”, curr->startAddr);
printf(” blockSize: %dn”, curr->blockSize);
printf(” isFree: %d (0 false, 1 true)n”, curr->isFree);
printf(” next: %pn”, curr->next);
curr = curr->next;
count++;
}
printf(“~~~~~ list end ~~~~~nn”);
}
// frees all memory
void free_pool()
{
Node *curr = NULL;
while (head != NULL)
{
curr = head;
head = head->next;
free(curr);
}
free(heapSpace);
free(head);
heapSpace = NULL;
head = NULL;
}
mallok.h
void create_pool(int size);
void *my_malloc(int size);
void my_free(void *block);
void printAll();
void free_pool();
