// C programming

//Complete the missing source code - - - #include #include #include "myalloc.h"

/* Given a string, return an array of the head strings. For example, if str is "Hello", you return an array of five strings "H", "He", "Hel", "Hell", "Hello". You will need to dynamically allocate the array and the strings. Use my_malloc. */ char **heads(const char str[]) { int n = strlen(str); char **result = (char **) my_malloc(n * sizeof(char *)); - - - return result; } /////////////////////////////////////////////////////////////////////////////// //Use the following files: //Tester.c #include #include

#include "myalloc.h"

char **heads(const char str[]);

int main() { char** result = heads("Hello"); printf("%s %s %s %s %s ", result[0], result[1], result[2], result[3], result[4]); printf("Expected: H He Hel Hell Hello "); char** result2 = heads("Bonjour "); printf("%s %s %s %s %s %s %s ", result2[0], result2[1], result2[2], result2[3], result2[4], result2[5], result2[6]); printf("Expected: B Bo Bon Bonj Bonjo Bonjou Bonjour "); printf("Size: %d ", my_size(result)); printf("Expected: %ld ", 5 * sizeof(char*)); printf("Size: %d ", my_size(result[0])); printf("Expected: 2 "); printf("Size: %d ", my_size(result[4])); printf("Expected: 6 "); printf("Allocated: %d ", my_allocated()); printf("Expected: 15 "); return 0; }

myalloc.c #include #include #include

#define POOL_SIZE 100000 #define HEADER_SIZE (2 * sizeof(int))

static unsigned char pool[POOL_SIZE]; static unsigned char *pool_end = pool; static int allocated = 0;

void* my_malloc(int size) { if (pool == pool_end) { // first time for (int i = 0; i < POOL_SIZE; i++) pool[i] = 0xDB; } unsigned char *result = NULL; if (pool_end + HEADER_SIZE + size <= pool + POOL_SIZE) { int* header = (int*) pool_end; if (header[0] == 0xDBDBDBDB) { // else corrupted unsigned char *contents = pool_end + HEADER_SIZE; result = contents; pool_end = pool_end + HEADER_SIZE + size; header[0] = 0xBEEFBEEF; header[1] = size; while (size-- > 0) *contents++ = 0xBB; allocated++; } else fprintf(stderr, "Pool corrupted "); } return result; }

void my_free(void *p) { unsigned char *contents = (unsigned char *) p; if (pool <= contents - HEADER_SIZE && contents < pool_end) { int* header = (int *)(contents - HEADER_SIZE); if (header[0] == 0xBEEFBEEF) { int size = header[1]; if (0 <= size && size <= pool_end - contents) { header[0] = 0xDEADBEEF; while (size-- > 0) *contents++ = 0xDB; allocated--; } } } else fprintf(stderr, "Bad free "); }

int my_size(void *p) { unsigned char *contents = (unsigned char *) p; if (pool <= contents - HEADER_SIZE && contents < pool_end) { int* header = (int *)(contents - HEADER_SIZE); if (header[0] == 0xBEEFBEEF) { int size = header[1]; if (0 <= size && size <= pool_end - contents) return size; } } return -1; }

static bool pool_corrupted() { unsigned char *p = pool; while (p < pool_end) { int *header = (int *) p; unsigned char *contents = p + HEADER_SIZE; int size = header[1]; if (header[0] != 0xBEEFBEEF && header[0] != 0xDEADBEEF) return true; if (size < 0 || size > pool_end - contents) return true; p = contents + size; if (header[0] == 0xDEADBEEF) { while (size-- > 0) { if (*contents++ != 0xDB) return false; } } } while (p < pool + POOL_SIZE) if (*p++ != 0xDB) return false; return false; }

int my_allocated() { if (pool_corrupted()) return -1; else return allocated; }

myalloc.h #include

void* my_malloc(int size); void my_free(void *p); int my_allocated(); // number of allocated blocks or -1 if pool corrupted int my_size(void *p); // size of p or -1 if not if allocated // by this allocator or if corrupted