// C programming

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

struct node { int data; struct node *next; };

/* Given an integer n, return a pointer to a linked list containing the digits of n in each node. Allocate the linked list dynamically with my_malloc. For example, if n is 1792, you return a list 1 -> 7 -> 9 -> 2. */ struct node *digits(int n) { struct node *result = NULL; while (n > 0) { int digit = n % 10; n /= 10; - - - } return result; } //////////////////////////////////////////////////////////////////////////////// //Use the following files: //Tester.c #include #include #include

#include "myalloc.h"

struct node { int data; struct node *next; };

struct node *digits(int n);

void print(struct node *lst) { while (lst != NULL) { printf("%d ", lst->data); lst = lst->next; } printf(" "); } int main() { struct node *result = digits(1729); print(result); printf("Expected: 1 7 2 9 "); printf("Size: %d ", my_size(result)); printf("Expected: %ld ", sizeof(struct node)); char* result2 = digits(1123581318); print(result2); printf("Expected: 1 1 2 3 5 8 1 3 1 8 "); printf("Allocated: %d ", my_allocated()); printf("Expected: 14 "); 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