In C. Fill in the code underneath any comment that reads "// YOUR CODE".

CODE:

#include #include #include

struct Block { int block_size; struct Block *next_block; };

const OVERHEAD_SIZE = __________ // refers to size & pointer of a block const POINTER_SIZE = sizeof(void *); struct Block *free_head;

void my_initialize_heap(int size) { // YOUR CODE }

void *my_alloc(int size) { if (size

size ? }

// Iterators struct Block *curr = free_head; struct Block *prev = 0;

bool found = false; // Iterare through each node, if a node has equal or more space than necessary // to hold size, use that node. while (curr != NULL) { if (________________) { found = true; // Determine if the current block can be split. if (______________________________________) { // Splittable // Create a pointer to the newly split block's position then assign its // structure members. // Your code

// Update Curr's block size as a result of splitting. // Your code

// Adjust the double linked list, depending on whether curr is the head or // not. // Your code

}

else { // Not splittable // If curr is the head, curr's next block is the new head. // Your code } // If curr is not the head, the previous block points to curr's next block. else { // Your code } // Since we found a block, no need to keep searching. break; } // Haven't found an available space yet. else { // Your code } } // Return a pointer to the allocated data, if possible. // Your code }

void my_free(void *data) { struct Block *freed_block = _____________________________; freed_block->next_block = ____________; free_head = ______________________; }

void menuOptionOne() { int *numOne = my_alloc(sizeof(int)); printf("Address of int A: %p ", numOne); my_free(numOne);

int *numTwo = my_alloc(sizeof(int)); printf("Address of int B: %p ", numTwo); };

// Allocate two ints and print their addresses; they should be exactly the size // of your overhead plus the larger of (the size of an integer; the minimum // block size) apart. void menuOptionTwo() { int *numOne = my_alloc(sizeof(int)); printf("Address of int A: %p ", numOne); int *numTwo = my_alloc(sizeof(int)); printf("Address of int B: %p ", numTwo); printf("Verifying Results... "); int overheadPlusLarger = OVERHEAD_SIZE + sizeof(void *); printf("Size of overhead + larger of (the size of an integer; the minimum " "block size): %d bytes ", overheadPlusLarger); printf("Address B - Address A: %d bytes ", (int)numTwo - (int)numOne); };

// Allocate three ints and print their addresses, then free the second of the // three. Allocate an array of 2 double values and print its address (to // allocate an array in C, allocate (2 * sizeof(double)); verify that the // address is correct. Allocate another int and print its address; verify that // the address is the same as the int that you freed. void menuOptionThree() { int *numOne = my_alloc(sizeof(int)); printf("Address of int A: %p ", numOne); int *numTwo = my_alloc(sizeof(int)); printf("Address of int B: %p ", numTwo); int *numThree = my_alloc(sizeof(int)); printf("Address of int C: %p ", numThree); my_free(numTwo);

printf("After freeing int B... "); double *arr = my_alloc(2 * sizeof(double)); printf("Address of array of 2 double values: %p ", arr);

int *numFour = my_alloc(sizeof(int)); printf("Address of int D (should be the int B): %p ", numFour); };

// Allocate one char, then allocate one int, and print their addresses. They // should be exactly the same distance apart as in test #2. void menuOptionFour() { int check = 0;

char *charOne = my_alloc(sizeof(char)); printf("Address of char A: %p ", charOne); int *numTwo = my_alloc(sizeof(int)); printf("Address of int B: %p ", numTwo);

int overheadPlusLarger = OVERHEAD_SIZE + sizeof(void *); printf("Size of overhead + larger of (the size of an integer; the minimum " "block size): %d ", overheadPlusLarger); };

// Allocate space for a 80-element int array, then for one more int value. // Verify that the address of the int value is 80 * sizeof(int) + the size of // your header after the array's address. Free the array. Verify that the int's // address and value has not changed. void menuOptionFive() { int *arr = my_alloc(80 * sizeof(int)); int *numOne = my_alloc(sizeof(int)); printf("Address of array: %p ", arr); printf("Address of int A: %p ", numOne); printf("Address of int value: %p ", arr + 80 + sizeof(int)); printf("Value of int A: %d ", *numOne);

printf("Difference betwween array and int A: %d ", (int)numOne - (int)arr);

my_free(arr);

printf("After freeing array... "); printf("Address of int value: %p ", numOne); printf("Value of int A: %d ", *numOne); }

// Testing case int main() { int menuChoice = 0; int runAgain = 1; while (runAgain == 1) { printf(" 1. Allocate an int 2. Allocate two ints 3. Allocate three " "ints 4. Allocate one char 5. Allocate space for an 80-element " "int array 6. Quit Choose a menu option: "); scanf("%d", &menuChoice); printf(" ---Test Case %d--- ", menuChoice); my_initialize_heap(1000);

if (menuChoice == 1) { menuOptionOne(); }

else if (menuChoice == 2) { menuOptionTwo(); }

else if (menuChoice == 3) { menuOptionThree(); }

else if (menuChoice == 4) { menuOptionFour(); }

else if (menuChoice == 5) { menuOptionFive(); }

else if (menuChoice == 6) { printf("Done!"); runAgain = 0; } } return 0; }

In this lab, you will implement your own dynamic memory allocator (heap manager) in C, using a free with_rst-_t block selection. Implementation You must follow these implementation guidelines: 1. Define a struct to represent an allocation block. struct Block \{ int block_size; // \# of bytes in the data section struct Block *next_block; // in C, you have to use _struct Block_as the type \} 2. Determine the size of a Block value using sizeof(struct Block) and assign it to a global const variable. We'll refer to this value as the overhead size. 3. Determine the size of a void* and save it in another const global. We'll refer to this value as the _pointer size_. 4. Create a global pointer struct Block *free_head, which will always point to the rst free block in the free list. 5. Create a function void my_initialize_heap(int size), which uses malloc to initialize a bu_er of the given size to use in your custom allocator. (This is the only time you can use malloc in the entire program.) Your global free_head should point to this bu_er, and you should initialize the header with appropriate values for block_size and next_block. 6. Create a function void my_alloc(int size), which_Ils an allocation request of size bytes and returns a pointer to the data portion of the block used to satisfy the request. (a) size can be any positive integer value, but any block you use must have a data size that is a multiple of your pointer size. So if a pointer is 4 bytes, and the function is told to allocate a 2 byte block, you would actually_nd a block with 4 bytes of data and use that, with 2 bytes being fragmentation. (b) Walk the free list starting at free_head, looking for a block with a large enough size to t the request. If no blocks can be found, return 0 . (null) Use the_rst_t heuristic. (c) Once you have found a block to t the data size, decide whether you need to split that block. i. A block needs to be split if its data portion is large enough to t the (rounded-up) size being allocated, AND the excess space in the data portion is su_cient to t another block with overhead and a minimum block size of the pointer size. Example: if overhead size is 8 and pointer size is 4 , we should split if the remaining space (after the allocation size is accounted for) is at least 12 bytes. ii. If you cannot split the block, then you need to redirect pointers to the block to point to the block that follows it, as if you are removing a node from a singly linked list. A. WARNING: the logic for removing a node in a linked list is di_erent depending on whether or not the node is the head of the list. Draw it out and convince yourself why you need to account for this. iii. If you can split the block, then_nd the byte location of where the new block will start, based on the location of the block you are splitting and the size of the allocation request. Initialize a new struct Block* pointer to that location and assign its new block_size. The new block's next_block pointer needs to point to the same block as the next_pointer of the block you are splitting. Reduce the size of the original block to match the allocation request. (d) Return a pointer to the data region of the block, which is_overhead size_bytes past the start of the block. Use pointer arithmetic. 7. Create a function void my_free(void *data), which deallocates a value that was allocated on the heap. The pointer will be to the data portion of a block; move backwards in memory to nd the block's overhead information, and then link it into the free list. Test your code thoroughly by allocating values of various types. You should write (and turn in) your own testing main, which at least includes the following tests, each a separate branch of main so that only one runs per execution of the program: 1. Allocate an int; print the address of the returned pointer. Free the int, then allocate another int and print its address. The addresses should be the same. 2. Allocate two ints and print their addresses; they should be exactly the size of your overhead plus the larger of (the size of an integer; the minimum block size) apart. 3. Allocate three ints and print their addresses, then free the second of the three. Allocate an array of 2 double values and print its address (to allocate an array in C, allocate ( 2 * sizeof(double)); verify that the address is correct. Allocate another int and print its address; verify that the address is the same as the int that you freed. 4. Allocate one char, then allocate one int, and print their addresses. They should be exactly the same distance apart as in test \#2. 5. Allocate space for a 80-element int array, then for one more int value. Verify that the address of the int value is 80 sizeof(int) + the size of your header after the array's address. Free the array. Verify that the int's address and value has not changed. In this lab, you will implement your own dynamic memory allocator (heap manager) in C, using a free with_rst-_t block selection. Implementation You must follow these implementation guidelines: 1. Define a struct to represent an allocation block. struct Block \{ int block_size; // \# of bytes in the data section struct Block *next_block; // in C, you have to use _struct Block_as the type \} 2. Determine the size of a Block value using sizeof(struct Block) and assign it to a global const variable. We'll refer to this value as the overhead size. 3. Determine the size of a void* and save it in another const global. We'll refer to this value as the _pointer size_. 4. Create a global pointer struct Block *free_head, which will always point to the rst free block in the free list. 5. Create a function void my_initialize_heap(int size), which uses malloc to initialize a bu_er of the given size to use in your custom allocator. (This is the only time you can use malloc in the entire program.) Your global free_head should point to this bu_er, and you should initialize the header with appropriate values for block_size and next_block. 6. Create a function void my_alloc(int size), which_Ils an allocation request of size bytes and returns a pointer to the data portion of the block used to satisfy the request. (a) size can be any positive integer value, but any block you use must have a data size that is a multiple of your pointer size. So if a pointer is 4 bytes, and the function is told to allocate a 2 byte block, you would actually_nd a block with 4 bytes of data and use that, with 2 bytes being fragmentation. (b) Walk the free list starting at free_head, looking for a block with a large enough size to t the request. If no blocks can be found, return 0 . (null) Use the_rst_t heuristic. (c) Once you have found a block to t the data size, decide whether you need to split that block. i. A block needs to be split if its data portion is large enough to t the (rounded-up) size being allocated, AND the excess space in the data portion is su_cient to t another block with overhead and a minimum block size of the pointer size. Example: if overhead size is 8 and pointer size is 4 , we should split if the remaining space (after the allocation size is accounted for) is at least 12 bytes. ii. If you cannot split the block, then you need to redirect pointers to the block to point to the block that follows it, as if you are removing a node from a singly linked list. A. WARNING: the logic for removing a node in a linked list is di_erent depending on whether or not the node is the head of the list. Draw it out and convince yourself why you need to account for this. iii. If you can split the block, then_nd the byte location of where the new block will start, based on the location of the block you are splitting and the size of the allocation request. Initialize a new struct Block* pointer to that location and assign its new block_size. The new block's next_block pointer needs to point to the same block as the next_pointer of the block you are splitting. Reduce the size of the original block to match the allocation request. (d) Return a pointer to the data region of the block, which is_overhead size_bytes past the start of the block. Use pointer arithmetic. 7. Create a function void my_free(void *data), which deallocates a value that was allocated on the heap. The pointer will be to the data portion of a block; move backwards in memory to nd the block's overhead information, and then link it into the free list. Test your code thoroughly by allocating values of various types. You should write (and turn in) your own testing main, which at least includes the following tests, each a separate branch of main so that only one runs per execution of the program: 1. Allocate an int; print the address of the returned pointer. Free the int, then allocate another int and print its address. The addresses should be the same. 2. Allocate two ints and print their addresses; they should be exactly the size of your overhead plus the larger of (the size of an integer; the minimum block size) apart. 3. Allocate three ints and print their addresses, then free the second of the three. Allocate an array of 2 double values and print its address (to allocate an array in C, allocate ( 2 * sizeof(double)); verify that the address is correct. Allocate another int and print its address; verify that the address is the same as the int that you freed. 4. Allocate one char, then allocate one int, and print their addresses. They should be exactly the same distance apart as in test \#2. 5. Allocate space for a 80-element int array, then for one more int value. Verify that the address of the int value is 80 sizeof(int) + the size of your header after the array's address. Free the array. Verify that the int's address and value has not changed