// C programming

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

/* Compute all minimum positions of a and return a dynamically allocated array containing them. Return the size of the array in *rlen. If the array a is empty, do nothing and return NULL.

As in all these exercises, don't call malloc/free directly, but call my_malloc and my_free, which are used for testing your work. */ int *allminpos(int a[], int len, int *rlen) { - - - } //////////////////////////////////////////////////////////////////////////////////// //Use the following files: //Tester.c #include

#include "myalloc.h"

int *allminpos(int a[], int len, int *rlen);

void print(const char *name, const int a[], int alen) { int i; printf("%s: ", name); for (i = 0; i < alen; i++) printf("%d ", a[i]); printf(" "); } int main() { int a[] = { 1, 4, -1, -1, 9, 9, -1, 14, 10 }; int alen = sizeof(a) / sizeof(a[0]); int rlen = 42; int *result = allminpos(a, alen, &rlen); print("result", result, rlen); printf("Expected: 2 3 6 "); printf("rlen: %d ", rlen); printf("Expected: 3 "); printf("Size: %d ", my_size(result)); printf("Expected: 12 "); my_free(result); printf("Allocated: %u ", my_allocated()); printf("Expected: 0 "); 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