// COMP1521 19t2 ... Assignment 2: heap management system
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "myHeap.h"
/** minimum total space for heap */
#define MIN_HEAP 4096
/** minimum amount of space for a free Chunk (includes Header) */
#define MIN_CHUNK 32
#define ALLOC 0x55555555
#define FREE 0xAAAAAAAA
/// Types:
typedef unsigned int uint;
typedef unsigned char byte;
typedef uintptr_t addr; // an address as a numeric type
/** The header for a chunk. */
typedef struct header {
uint status; /**< the chunk's status -- ALLOC or FREE */
uint size; /**< number of bytes, including header */
byte data[]; /**< the chunk's data -- not interesting to us */
} header;
/** The heap's state */
struct heap {
void *heapMem; /**< space allocated for Heap */
uint heapSize; /**< number of bytes in heapMem */
void **freeList; /**< array of pointers to free chunks */
uint freeElems; /**< number of elements in freeList[] */
uint nFree; /**< number of free chunks */
};
/// Variables:
/** The heap proper. */
static struct heap Heap;
/// Functions:
static addr heapMaxAddr (void);
// function to round up to next multiple if necessary
static int roundup(int numToRoundUp, int multiple);
// function returns index of supplied chunk
static int indexOfFreeChunk(header *chunk);
// function readjusts pointers after removal from freeList
static void readjustPointers(int indexChunk);
/** Initialise the Heap. */
int initHeap (int size)
{
/// TODO ///
if (size < MIN_HEAP) {
size = MIN_HEAP;
}
size = roundup(size, 4);
// heapMem is pointing to a chunk
Heap.heapMem = malloc(size);
if (Heap.heapMem == NULL) {
fprintf(stderr, "malloc failed\n");
exit(-1);
}
// set heapMem to be all zeroes, memset returns pointer to chunk
Heap.heapMem = memset(Heap.heapMem, 0, size);
Heap.heapSize = size;
// pointer to chunkHeader
header *chunkHeader = (header *)(Heap.heapMem);
// setting heapMem to be a single free chunk of size;
chunkHeader->size = size;
chunkHeader->status = FREE;
Heap.freeElems = 1;
Heap.freeList = malloc(Heap.freeElems * sizeof(void *));
if (Heap.freeList == NULL) {
fprintf(stderr, "malloc failed\n");
exit(-1);
}
Heap.freeList[0] = chunkHeader; // check???
Heap.nFree = 1;
return 0; // this just keeps the compiler quiet
}
/** Release resources associated with the heap. */
void freeHeap (void)
{
free (Heap.heapMem);
free (Heap.freeList);
}
/** Allocate a chunk of memory large enough to store `size' bytes. */
void *myMalloc (int size)
{
/// TODO ///
if (size < 1) {
return NULL;
}
size = roundup(size, 4);
// round up size to nearest multiple of 4 if necessary
// find the first chunk that fits
// check if I have found minimum if not return null
// start up another loop to update minimum chunk
header *minChunk;
/* for (int i = 0; i < Heap.freeElems; i++) {
header *currentChunk = (header *) Heap.freeList[i];
if (currentChunk->size >= size + sizeof(header)) {
minChunk = currentChunk;
break;
}
} */
int i = 0;
int j;
while (i < Heap.freeElems) {
header *currentChunk = (header *) Heap.freeList[i];
if (currentChunk->size >= size + sizeof(header)) {
minChunk = currentChunk;
j = i + 1;
break;
}
i++;
}
// didn't find any chunk that fits
if (minChunk == NULL) {
return NULL;
}
// finding min available chunk
while (j < Heap.freeElems) {
header *currentChunk = (header *) Heap.freeList[j];
if ( (currentChunk->size >= size + sizeof(header))
&& (currentChunk->size < minChunk->size) ) {
minChunk = currentChunk;
}
j++;
}
if (minChunk->size >= size + sizeof(header) + MIN_CHUNK) {
// split and make excess a new small free chunk
// allocating space for "size"
header *allocatedChunk = minChunk;
allocatedChunk->status = ALLOC;
// calculating excessSize
header * newChunkHeader = (header *)
((addr) allocatedChunk + size + sizeof(header));
uint excessSize = minChunk->size - (size + sizeof(header));
printf("excessSize = %d\n", excessSize);
allocatedChunk->size = size + sizeof(header);
newChunkHeader->size = excessSize;
newChunkHeader->status = FREE;
// readjusting pointer
Heap.freeList[ indexOfFreeChunk(allocatedChunk) ] = newChunkHeader;
return ( (void *) ( (addr) allocatedChunk + sizeof(header)) );
} else {
// allocate whole chunk
minChunk->status = ALLOC;
// readjust pointers from minChunk onwards
readjustPointers( indexOfFreeChunk(minChunk) );
Heap.nFree--;
return ( (void *) ( (addr) minChunk + sizeof(header)) );
}
return 0; // this just keeps the compiler quiet
}
/** Deallocate a chunk of memory. */
void myFree (void *obj)
{
/// TODO ///
//
/* int flag = 0;
addr iterationChunk = (addr) Heap.heapMem;
while (iterationChunk < heapMaxAddr ()) {
header *chunk = (header *) iterationChunk;
if ( chunk->status == ALLOC
&& (void *) ((addr) chunk + sizeof(header)) == obj) {
flag = 1;
}
iterationChunk += chunk->size;
}
if (flag == 0) {
fprintf( stderr, "Attempt to free unallocated chunk\n");
exit(1);
}
// freeing chunk
header *freedChunk = (header *) ( (addr) obj - sizeof(header) );
obj = memset(obj, 0, freedChunk->size - sizeof(header));
freedChunk->status = FREE;
// readjust pointers in freeList
// find chunks adjacent to freeChunk and check if they are free
// if so merge them
// iterate chunk by chunk
addr curr = (addr) Heap.heapMem;
while (curr < heapMaxAddr ()) {
header *currChunk = (header *) curr;
// behindChunk and aheadChunk are check variables
header *behindChunk = currChunk;
header *aheadChunk = currChunk;
// currChunk is behind freedChunk
if ( (header *) ( (addr) currChunk + currChunk->size) == freedChunk ) {
if (currChunk->status == FREE) {
// merging
// adding chunk sizes
behindChunk->size = behindChunk->size + freedChunk->size;
// removing header of freedChunk
freedChunk = memset(freedChunk, 0, sizeof(header));
// find pointer which points to currChunk in freeList[]
// readjust it to point at currChunk the trailing chunk
for (int i = 0; i < Heap.freeElems; i++) {
header *chunk = (header *) Heap.freeList[i];
if (chunk == currChunk) {
Heap.freeList[i] = behindChunk;
}
}
}
// currChunk is ahead of freedChunk - there is an aheadChunk
} else if (currChunk == (header *)
( (addr) freedChunk + freedChunk->size) ) {
if (currChunk->status == FREE) {
// case where there was a trailing free chunk already added
if (behindChunk != currChunk) {
behindChunk->size = behindChunk->size + aheadChunk->size;
aheadChunk = memset(aheadChunk, 0, sizeof(header));
// adjust pointers from currChunk onwards
readjustPointers( indexOfFreeChunk(currChunk) );
} else {
// adjust current pointer to point at freedChunk
}
}
}
curr += currChunk->size;
} */
}
/** Return the first address beyond the range of the heap. */
static addr heapMaxAddr (void)
{
return (addr) Heap.heapMem + Heap.heapSize;
}
/** Convert a pointer to an offset in the heap. */
int heapOffset (void *obj)
{
addr objAddr = (addr) obj;
addr heapMin = (addr) Heap.heapMem;
addr heapMax = heapMaxAddr ();
if (obj == NULL || !(heapMin <= objAddr && objAddr < heapMax))
return -1;
else {
return (int) (objAddr - heapMin);
}
}
/** Dump the contents of the heap (for testing/debugging). */
void dumpHeap (void)
{
int onRow = 0;
// We iterate over the heap, chunk by chunk; we assume that the
// first chunk is at the first location in the heap, and move along
// by the size the chunk claims to be.
addr curr = (addr) Heap.heapMem;
while (curr < heapMaxAddr ()) {
header *chunk = (header *) curr;
char stat;
switch (chunk->status) {
case FREE: stat = 'F'; break;
case ALLOC: stat = 'A'; break;
default:
fprintf (
stderr,
"myHeap: corrupted heap: chunk status %08x\n",
chunk->status
);
exit (1);
}
printf (
"+%05d (%c,%5d)%c",
heapOffset ((void *) curr),
stat, chunk->size,
(++onRow % 5 == 0) ? '\n' : ' '
);
curr += chunk->size;
}
if (onRow % 5 > 0)
printf ("\n");
}
static int roundup(int numToRoundUp, int multiple) {
int remainder = numToRoundUp % multiple;
if (remainder != 0) {
return numToRoundUp = numToRoundUp + multiple - remainder;
} else {
return numToRoundUp;
}
}
static int indexOfFreeChunk(header *chunk) {
for (int i = 0; i < Heap.freeElems; i++) {
header *currChunk = (header *) Heap.freeList[i];
if (currChunk == chunk) {
return i;
}
}
return -1;
}
static void readjustPointers(int indexChunk) {
while (indexChunk < Heap.freeElems) {
if (indexChunk == Heap.freeElems - 1) {
Heap.freeList[indexChunk] = NULL;
break;
}
Heap.freeList[indexChunk] = Heap.freeList[indexChunk + 1];
indexChunk++;
}
}