/**********************************************
 * storage allocation test program for MP 6   *
 * calls heap-init, myalloc and myfree        *
 * by: Douglas Jones, 4/29/2003               *
 *                                            *
 * the output of this program is just a list  *
 * of high-water marks in allocation.  Block  *
 * sizes range from 1 to 1000 bytes, randomly *
 **********************************************/

#include <stdlib.h>

#define INTENSITY 250

long int totalalloc = 0;   /* total of all successful allocation requests */
long int totaldealloc = 0; /* total of all deallocation requests */

void * makeitem()
/* allocate and initialize an item, return a pointer to it.
   the item size is randomly from 1 to INTENSITY, and items
   are initialized to record their size and hold size-1 pointers */
{
	int s = (random() % INTENSITY) + 1;
	int i; /* loop counter */

	/* now allocate an item that can hold s pointers */
	void * p = myalloc( s * sizeof(void *) );
	long int * pi = (long int *) p;

	if (p != NULL) {
		/* track allocations */
		totalalloc = totalalloc + (s * sizeof(void *));

		/* initialize pi[0] through pi[s-1] */
		pi[0] = s;
		/* now loop to initialize pointers in pi[1] to pi[s-1] */
		for (i = 1; i < s; i++) {
			pi[i] = (long int) NULL;
		}
	}
	return p;
}

void deleteitem( void * p )
/* given an item allocated by makeitem, deallocate it */
{
	long int * pi = (long int *) p;
	int s = pi[0];
	int i; /* loop counter */

	/* first deal with any non-nil pointers */
	for (i = 1; i < s; i++) {
		if ((void *)pi[i] != NULL) deleteitem( (void *) pi[i] );
	}

	/* second, deallocate item */
	myfree( (void *) p, s * sizeof(void *) );

	/* and track deallocation */
	totaldealloc = totaldealloc + (s * sizeof(void *));
}

void changeitem( void * p, int depth )
/* given an item allocated by makeitem, change it randomly */
{
	long int * pi = (long int *) p;
	int s = pi[0];

	/* pointers in pi[1] to pi[s-1] may be of interest */
	if (s > 1) {
		int i = (random() % (s - 1)) + 1; /* index into item */
		if ((void *)pi[i] == NULL) {
			pi[i] = (long int)makeitem();
		} else if (depth <= 0) {
			deleteitem( (void *)pi[i] );	
			pi[i] = (long int)NULL;
		} else {
			changeitem( (void *)pi[i], depth - 1 );
		}
	}
}

main ()
{
	void * p; /* pointer to an item in the heap */
	long int i; /* for loop index */
	long int record; /* record allocation so far */

	heap_init();

	p = makeitem();

	record = totalalloc - totaldealloc;
	for (i = 1; i < 100000; i++) {
		int j = random() % 4;
		changeitem( p, j );
		if ((totalalloc - totaldealloc) > record) {
			record = totalalloc - totaldealloc;
			printf( "record allocation = %ld\n", record );
		}
	}
}