mymem.c

linked list linked list tree struc

/*
 * Wei Cui
 * wec924
 * 981503
 *
 * Brian Gale
 * bmg002
 * 303473
 */


#include "mymem.h"

TREE *MemUsed, *MemFreeStart, *MemFreeSize;
int numAlloc, numFree, currMemAlloc;
int flag, flag2;



/* init()
 * This function takes no arguments and should not need to be called by the user
 * This function is called automatically by myMalloc().
 * This function is supposed to initialize the variables and create the required
 * trees.
 * I think that this function is O(1).  The TreeAdd() call should be O(1) since
 * the tree is empty, so this function should be the order of malloc() and 
 * TreeCreate().
 */

void meminit() {
	void *init;
	int MEM;
	ITEM *toAdd;
	MEM=MEMORY;
	toAdd=malloc(sizeof(ITEM));
	numAlloc=0;
	numFree=0;
	currMemAlloc=0;
	flag=1;
	init = malloc(sizeof(MEM));
	if (init == 0) {
		printf("tried to allocate too much memory initially.  Quitting.\n");
		exit(-1);
	}
	MemUsed=TreeCreate();
	MemFreeStart=TreeCreate();
	MemFreeSize=TreeCreate();
	toAdd->startAddr=(int) init;
	toAdd->endAddr=toAdd->startAddr+MEM;
	toAdd->size=MEM;
	TreeAdd(MemFreeStart, (TITEM) toAdd,(void *) orderStart);
	TreeAdd(MemFreeSize, (TITEM) toAdd, (void *)orderSize);
}

/* compareSize(ITEM *, ITEM *)
 * This function takes 2 arguments, both of which are ITEMS.
 * It compares the size of both ITEMs and if they are the same, it checks
 * to see if the start addresses of both ITEMs are the same, if so, it returns 0
 * If the sizes are not equal, it returns 1 or -1 depending on if it is to 
 * search left in the tree or right.  If the start addresses are not equal, it 
 * returns 1 or -1 depending on if it is to search left or right in the tree.
 * This function should be O(1).
 */

int compareSize(ITEM *item1, ITEM *item2){
	if (item1->size < item2->size) return 1;
	else if (item1->size == item2->size) {
		if (item1->startAddr < item2->startAddr) return 1;
		else if (item1->startAddr > item2->startAddr) return -1;
		else return 0;
	}
	else return -1;
}

/* compareSize2(ITEM *, ITEM *)
 * This function is supposed to check if the size of the first ITEM is smaller
 * than the size of the second.  If so, it returns 1, otherwise it returns 0.
 * This function should be O(1).
 */

int compareSize2(ITEM *item1, ITEM *item2){
	if (item1->size < item2->size) return 1;
	else return 0;
}

/* compareStart(ITEM *, ITEM *)
 * This function takes 2 arguments, both of which are ITEMS.
 * It compares the start address of the first to the start address of the second
 * If the first is smaller, then it returns 1.
 * If the first is larger, then it returns -1.
 * If they are the same, then it returns 0.
 * This function should be O(1).
 */

int compareStart(ITEM *item1, ITEM *item2){
	if (item1->startAddr < item2->startAddr) return 1;
	else if (item1->startAddr > item2->startAddr) return -1;
	else return 0;
}

/* MyMalloc(size_t)
 * This function takes 1 argument which is a size_t.
 * This function is supposed to let the user know where their memory is 
 * allocated.
 * It calls meminit() if meminit() has not been called before.
 * It adds the memory that the user requested to the required trees.
 * This function should be O(logN).
 */

void *MyMalloc(size_t size){
	ITEM *tostore1, *tostore2, *item;
	item=malloc(sizeof(item));
	if (flag == 0)
	{
		meminit();
	}
	numAlloc+=1;
	if (size == 0) {
		return NULL;
	}
	item->size=size;
	while (flag2==1);
	flag2+=1;
	TreeRoot(MemFreeSize);
	tostore1=TreeKeySearch(MemFreeSize,(void *) compareSize2, (TITEM) item);
	if (tostore1==NULL) {
		printf("Not enough free memory for an allocation of %d\n", size);
		flag2=0;
		return NULL;
	}
	item->startAddr=tostore1->startAddr;
	item->endAddr=item->startAddr+size;
	if (item->endAddr != tostore1->endAddr) {
		tostore1->startAddr=item->endAddr;
		tostore1->size=tostore1->endAddr-tostore1->startAddr;
		TreeRemove(MemFreeSize);
		TreeAdd(MemFreeSize, (TITEM) tostore1, (void *) orderSize);
	}
	else {
		TreeRemove(MemFreeSize);
		TreeRoot(MemFreeStart);
		tostore2=TreeKeySearch(MemFreeStart, (void *) compareStart, (TITEM) tostore1);
		TreeRemove(MemFreeStart);
	}
	
	TreeAdd(MemUsed, (TITEM) item, (void *) orderStart);
	flag2=0;
	currMemAlloc+=size;
	return (void *) item->startAddr;
}

/* orderSize(ITEM *, ITEM *)
 * This function takes 2 arguments which are both ITEMs.
 * This function returns 1 if the size of the first ITEM is larger than the size
 * Or if the start address of the first ITEM is larger than the start address
 * of the second.  Otherwise it returns 0.
 * This function should be O(1).
 */

int orderSize(ITEM *item1, ITEM *item2){
	if (item1->size > item2->size) return 1;
	else if (item1->size == item2->size) {
		if (item1->startAddr > item2->startAddr) return 1;
		else return 0;
	}
	else return 0;
}

/* orderStart(ITEM *, ITEM *)
 * This function takes 2 arguments which are both ITEMs.
 * This function returns 1 if the start address of the first ITEM is larger than
 * the start address of the second, otherwise it returns 0.
 * This function should be O(1).
 */

int orderStart(ITEM *item1, ITEM *item2){
	if (item1->startAddr > item2->startAddr) return 1;
	else return 0;
}

/* compareStart2End(ITEM *, ITEM *)
 * This function takes 2 arguments which are both ITEMs.
 * This function returns 1 if the end address of the first ITEM is smaller than
 * the start address of the second, a -1 if the end address of the first ITEM is
 * larger than the start address of the second, and a 0 if they are the same.
 * This function should be O(1).
 */

int compareStart2End(ITEM *item1, ITEM *item2){
	if (item1->endAddr < item2->startAddr) return 1;
	else if (item1->endAddr > item2->startAddr) return -1;
	else return 0;
}

/* compareEnd2Start(ITEM *, ITEM *)
 * This function takes 2 arguments which are both ITEMs.
 * This function returns 1 if the start address of the first ITEM is smaller 
 * than the end address of the second, a -1 if the start address of the first
 * ITEM is larger than the end address of the second, and a 0 if they are the 
 * same.
 * This function should be O(1).
 */

int compareEnd2Start(ITEM *item1, ITEM *item2){
	if (item1->startAddr < item2->endAddr) return 1;
	if (item1->startAddr > item2->endAddr) return -1;
	else return 0;
}

/* MyFree(void *)
 * This function takes 1 argument which is a pointer to the ITEM returned from 
 * myMalloc().
 * This function is supposed to set the memory that was requested by myMalloc()
 * for that particular ITEM to be free.  It does this by removing this ITEM from
 * MemUsed (if it is in there) and setting that memory space to free in both
 * free trees.
 * It has at most 3 calls to TreeKeySearch(), 4 calls to TreeRemove(), and 1 
 * call to TreeAdd().
 * This function should be O(logN).
 */

void MyFree(void *ptr){
	ITEM *toStore1,*toStore2, *toSearch;
	if (flag == 0) {
		meminit();
	}
	toSearch=malloc(sizeof(ITEM));
	toStore1=malloc(sizeof(ITEM));
	toStore2=malloc(sizeof(ITEM));
	toSearch->startAddr=(int) ptr;
	numFree=numFree + 1;
	while(flag2==1);
	flag2=1;
	TreeRoot(MemUsed);
	toStore1=TreeKeySearch(MemUsed, (void *) compareStart, (TITEM) toSearch);
	if (toStore1 == NULL) {
		printf("The memory address %d was not found and was either already freed, or not added to the tree.\n",toSearch->startAddr);
	}
	else {
		printf("the memory address %d was found in the tree.\n",toSearch->startAddr);
		currMemAlloc-=toStore1->size;
		/* remove from MemUsed as the memory is no longer used */
		toStore1= TreeRemove(MemUsed);
		/* find if previous memory address is free */
		TreeRoot(MemFreeStart);
		toStore2=TreeKeySearch(MemFreeStart,(void *) compareStart2End, (TITEM) toStore1);
		/* if found in MemFreeStart, change the end address to the end
		 * address of the one read from MemUsed (as that much is now 
		 * free), and remove from the MemFreeSize.
		 */
		if (toStore2 != NULL) {
			TreeRoot(MemFreeSize);
			toSearch=TreeKeySearch(MemFreeSize,(void *) compareSize, (TITEM) toStore2);
			toSearch=TreeRemove(MemFreeSize);
			toStore2->endAddr=toStore1->endAddr;
			toSearch=TreeNext(MemFreeStart);
			if (toSearch != NULL) {
			/* if next start address is equal to the end address 
			 * from the value read from MemUsed, add that value to
			 * the end of the value and remove that node
			 */
				if (toSearch->startAddr==toStore1->endAddr) {
					toStore2->endAddr=toSearch->endAddr;
					toStore2->size=(toStore2->endAddr - toStore2->startAddr);
					toStore1=TreeRemove(MemFreeStart);
					TreeRoot(MemFreeSize);
					toSearch=TreeKeySearch(MemFreeSize,(void *) compareSize, (TITEM) toStore1);
					toSearch=TreeRemove(MemFreeSize);
					TreeAdd(MemFreeSize, (TITEM) toStore2, (void *) orderSize);
				}
				else {
					toStore2->size=(toStore2->endAddr-toStore2->startAddr);
					TreeAdd(MemFreeSize, (TITEM) toStore2, (void *) orderSize);
				}
			}
			else {
				toStore2->size=(toStore2->endAddr - toStore2->startAddr);
				TreeAdd(MemFreeSize, (TITEM) toStore2, (void *) orderSize);
			}
		}
		/* if not found, then check the value after that to see if the 
		 * memory after the one found in memUsed is free
		 */
		else {
			TreeRoot(MemFreeStart);
			toStore2=TreeKeySearch(MemFreeStart,(void *) compareEnd2Start, (TITEM) toStore1);
			if (toStore2 != NULL) {
				TreeRoot(MemFreeSize);
				toSearch=TreeKeySearch(MemFreeSize,(void *) compareSize, (TITEM) toStore2);
				toSearch=TreeRemove(MemFreeSize);
				toStore2->startAddr=toStore1->startAddr;
				toStore2->size=(toStore2->endAddr - toStore2->startAddr);
				TreeAdd(MemFreeSize, (TITEM) toStore2, (void *) orderSize);
			}
			else {
				TreeAdd(MemFreeSize, (TITEM) toStore1, (void *)orderSize);
				TreeAdd(MemFreeStart, (TITEM) toStore1, (void *)orderStart);
			}
		}
	}
	flag2=0;
}

/* MyMemStats()
 * This function requires no arguments.
 * This function is supposed to simply display to the user the information about
 * the program, such as how many calls to myFree and myMalloc were made and how
 * much memory is still avaliable.  It does this by calling global variables.
 * This function should be O(1).
 */

void MyMemStats(){
	ITEM *toRead;
	int i;
	toRead=TreeLast(MemFreeSize);
	if (toRead==NULL) i=0;
	else i=toRead->size;
	printf("Current ammount of allocated memory: %d\nLargest allocateable memory: %d\nNumber of allocation calls: %d\nNumber of free calls: %d\n",currMemAlloc, i, numAlloc, numFree);
}