/* heaptest.c -- heap exercise program for MP5*/
/* written by Douglas W. Jones
 *   -- as distributed, uses malloc instead of a self-written heap manager
 */

/* this program tests a heap implementation, included in this file,
 * by randomly allocating and deallocating memory blocks of random
 * size.  (Actually, pseudorandom)
 */

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

/******************* 
 * heap parameters * 
 *******************/

#define HEAPSIZE 10000
/* notice that HEAPSIZE is not a power of 2 and will be
 * very unlikely to be aligned on a page boundry */

#define VOIDCOUNT (HEAPSIZE / sizeof( void * ))

/*****************************
 * synthetic load parameters * 
 *****************************/

#define TRIALS 10000
#define MAXBLOCKS (HEAPSIZE/100)

/***********************
 * memory for the heap * 
 ***********************/

void * voidheap[ VOIDCOUNT ];
/* the above code guarantees that if the hardware has alignment
 * constraints, the heap will be aligned appropriately */

/***********************
 * heap implementation * 
 ***********************/

/* small static data structures needed for heap management
 * should be declared here */

void * heap; /* the pointer to the entire heap, if needed */

void heapinit() {
	/* this is just an example */
	heap = & (voidheap[0]);

	/* in what follows, this heap is never used */
}

void * mymalloc( size_t size ) {
	/* temporary implementation used to test the exerciser */
	/* this temporary implementation must be replaced */

	/* the final version must use the block of memory pointed to by
	   heap, plus any other data structures required */
	return( malloc( size ));
}

void myfree( void * ptr ) {
	/* temporary implementation used to test the exerciser */
	/* this temporary implementation must be replaced */
	free( ptr );
}

/******************** 
 * the test program * 
 ********************/

/* statistics gathering */
int totalalloc = 0;   /* total blocks allocated */
int totaldealloc = 0; /* total blocks deallocated */
int blocksalloc = 0;  /* count of blocks allocated */
int curdemand = 0;    /* current memory demand */
int maxdemand = 0;    /* maximum memory demand */
int failures = 0;     /* number of failed allocates */

int main(){
        int i; /* for loop index */
	void * demand[MAXBLOCKS];
        void * root = NULL; /* structure */

	/* initialize the heap being tested */
	heapinit();

	for (i = 0; i < MAXBLOCKS; i++ ) {
		demand[i] = NULL;
	}

	/* test the heap */
	for (i = 0; i < TRIALS; i++ ) { /* pick a random pointer */
		int j = random() % (MAXBLOCKS);
		if (demand[j] == NULL) { /* if null, malloc */

			int s = random() % (HEAPSIZE / 2);
			s = random() % (s+1); /* bias s toward small sizes */
			s = random() % (s+1); /* but s may get quite large */
			s = random() % (s+1);
			s = random() % (s+1);
			s = s + sizeof( void * ); /* set minimum size */

			demand[j] = mymalloc(s);

			if (demand[j] != NULL) { /* initialize the block */
				int k;
				char * p = demand[j];
				*((intptr_t *)p) = s;
				p = (char *)(((intptr_t *)p) + 1);
				for (k = sizeof(intptr_t); k < s; k++) {
					*p = (k & 0x7F);
					p++;
				}
				totalalloc += s;
				curdemand += s;
				if (curdemand > maxdemand) {
					maxdemand = curdemand;
				}
				blocksalloc++;
			} else { /* malloc returned null */
				failures++;
			}
			
		} else { /* if not null, free */
			int k;
			char * p = demand[j];
			int s = *((intptr_t *)p);
			p = (char *)(((intptr_t *)p) + 1);
			totaldealloc ++;
			for (k = sizeof(intptr_t); k < s; k++) {
				if (*p != (k & 0x7F)) {
					printf( "corrupted heap"
						"at trial %d\n", i );
					printf( "after %d deallocations\n",
						totaldealloc );
					exit( EXIT_FAILURE );
				}
				p++;
			}
			myfree( demand[j] );
			demand[j] = NULL;
			curdemand -= s;
		}
	}
	/* report statistics */
	printf( "After %d allocations", blocksalloc);
	printf( " from a heap of size %d\n", HEAPSIZE);
	printf( " Average block size: %d\n", totalalloc/blocksalloc );
	printf( " Maxim aggregate demand: %d\n", maxdemand );
	printf( " Failed allocations: %d\n", failures);
}