malloc_sim.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Parameters
const int MAXE = 10;
const int MAXR = 9;
const int HEAPSZ = 50;
const double PROBF = 0.3;
int srandSwitch = 1; // A switch for srand, 1 is on, 0 is off

// Linked list to implement free lists and allocation list
typedef struct node{
	int index;
	int size;
	struct node* next;
} Node;

Node* freelistHead = NULL;
Node* alloclistHead = NULL;
int numAlloc = 0;

void insertAtStart(Node** head, int index, int size) {
	Node* new = malloc(sizeof(Node));
	new->index = index;
	new->size = size;
	new->next = *head;
	*head = new;
}

void insertAtEnd(Node** head, int index, int size) {
	Node* new = malloc(sizeof(Node));
	new->index = index;
	new->size = size;
	new->next = NULL;

	Node* current = *head;
	if (current == NULL) {
		*head = new;
		return;
	}

	while (current->next != NULL) {
		current = current->next;
	}
	current->next = new;
}

// When allocate, update free at and sz, append to free list
void allocateMem(int heap[], int maxsize, int data) {
	// Random memory block size between 1 and maxsize
	int size = ((double)rand()/RAND_MAX) * (maxsize-1) + 1;

	// Iterate free list
	Node* current = freelistHead;
	Node* prev = current;

	// Find a free block with sufficient size
	while (current != NULL && current->size < size) {
		prev = current;
		current = current->next;
	}
	if (current == NULL) {
		printf("Unable to find block of memory with sufficient size.\n");
		return;
	}

	// Fill data
	int start = current->index;
	int i = start;
	for (; i < current->index + size; i++) {
		heap[i] = data;
	}

	// Add remaining free memory of block to free list if exists
	if (current->size > size) {
		insertAtEnd(&freelistHead, i, current->size - size);
	}

	// Delete allocated block off of free list
	if (current == freelistHead) {
		Node* second = freelistHead->next;
		free(freelistHead);
		freelistHead = second;
	}
	else {
		Node* next = current->next;
		free(current);
		prev->next = next;
	}

	// Store the allocation
	insertAtEnd(&alloclistHead, start, size);
	numAlloc++;
	
}

void freeMem(int heap[]) {
	// Pick a number between 0 and numAlloc
	int toFree = ((double)rand()/RAND_MAX) * numAlloc;
	
	// Iterate allocation list til the picked allocation
	Node *cur = alloclistHead;
	Node *prev = cur;
	int i=0;
	while (i < toFree) {
		prev = cur;
		cur = cur->next;
		i++;
	}
	if (cur == NULL) {
		return;
	}
	int freeat = cur->index;
	int freesz = cur->size;

	// Free memory
	for (int j=freeat; j < freeat + freesz; j++) {
		heap[j] = -1;
	}

	// Remove from allocation list
	if (cur == alloclistHead) {
		Node *second = cur->next;
		free(cur);
		alloclistHead = second;
	}
	else {
		prev->next = cur->next;
		free(cur);
	}
	numAlloc--;

	// Prepend to free list
	insertAtStart(&freelistHead, freeat, freesz);
}

void printFreelist() {
	printf("freeatlist=");
	Node* cur = freelistHead;
	if (cur == NULL) {
		printf("Empty list");
	} else {
		while (cur != NULL) {
			printf("%d", cur->index + 1);
			if (cur->next != NULL)  printf(";");
			cur = cur->next;
		}
	}
	printf("\nfreeszlist=");
	cur = freelistHead;
	if (cur == NULL) {
		printf("Empty list");
	} else {
		while (cur != NULL) {
			printf("%d", cur->size);
			if (cur->next != NULL)  printf(";");
			cur = cur->next;
		}
	}
	printf("\n");
}

int main() {
	// Initialize heap
	int heap[HEAPSZ];
	for (int i=0; i<HEAPSZ; i++) {
		heap[i] = -1;
	}

	// At start, all memory is free
	insertAtStart(&freelistHead, 0, HEAPSZ);

	if (srandSwitch) srand(time(NULL)); // TOASK: run this once for whole program or once per rand() call

	// Simulator
	for (int t=1; t <= MAXE; t++) {

		// Allocate
		if(((double) rand()/RAND_MAX) > PROBF) {
			allocateMem(&heap[0], MAXR, t%10);
			printf("t=%d\n*", t);
		}
		// Free 
		else {
			freeMem(&heap[0]);
			printf("Ft=%d\n*", t);
		}

		// Print heap and free lists
		for (int i=0; i<HEAPSZ; i++) {
			if (heap[i] == -1) printf("_");
			else printf("%d", heap[i]);
		}
		printf("\n");
		printFreelist();
		printf("\n\n");
	}

	return 0;
}