Memory Management

A. First edition
This is first edition of my memory management.
B.The problem
In the O.S. memory are just pieces of chunk of memory where several basic operations are implemented.
Allocate: a certain amount of memory are allocated by a certain searching policy. Release: memory are
returned to system and possibly needs to be merged with other consecutive free memory block.
Unused memory are chained up with doubly link list where a "tag" set at both beginning and end. Size
field appears at both ends, a pointer to previous and next unused memory. 
C.The idea of program
 
The manipulation of link list is a painful job! The simulation of memory is using an array. Actually
 
memory is considered to be linear.
 
The code is no good as there are countless "if else" which I hate most. And merge operation is a
 
little bit tricky! Suppose you have one used chunk of memory that you want to be released. It should
 
be merged with both side if they are free memory. Should I tell you the detail of each bugs I found?
D.The major functions
C.Further improvement
 
#include <iostream>
#include <time.h>
#include <iomanip>

using namespace std;

const int MemLength=70;
const int MinFree=6;
const int MinUsed=3;

enum SearchPolicy
{FirstFit, WorstFit, BestFit};

enum MemType
{Free, Used};

class Mem
{
private:
	int memory[MemLength];
	int freeHead;
//	int usedHead;
	SearchPolicy searchPolicy;
	void doPrint(int usedLength, int freeLength, int pos);
	void initialize();
	bool firstFit(int& index, int length);
	bool worstFit(int& index, int length);
	bool bestFit(int& index, int length);
	bool findFree(int& index, int length);
	void doAllocate(int index, int length);
	int findNext(int index);
	bool canMerge(int index);
	void doMerge(int index);
	void insert(int index);
	void leftMerge(int index);
	void rightMerge(int index);
	void doubleMerge(int index);
public:
	Mem(SearchPolicy search=FirstFit);
	int allocate(int length);
	void release(int index);
	void print();
	
};

void doTest(Mem& M, int lst[], int index)
{
	if (lst[index]!=-1)
	{
		M.release(lst[index]);
		cout<<"\nnow print result after releasing "<<index<<endl;
		M.print();
		lst[index]=-1;
	}
}

bool addTest(Mem& M, int lst[], int index)
{
	int num=rand()%12+1;
	if (lst[index]==-1)
	{
		lst[index]=M.allocate(num);
		if (lst[index]==-1)
		{
			return false;
		}
		cout<<"\nnow print for add size of"<<num<<endl;
		M.print();
		return true;
	}
	return false;
}

const int Length=10;

int usedList[Length]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};

int main()
{	
	srand(time(0));

	
	Mem M(BestFit);
	for (int i=0; i<Length;i++)
	{	
		addTest(M, usedList, i);		
	}
	cout<<"\nnow release one by one\n";

	doTest(M, usedList, 2);
	doTest(M, usedList, 5);
	doTest(M, usedList, 0);
	cout<<"\nnow show the best fit\n";
	while (!addTest(M, usedList, 2))
	{
	}

	/*
	for (i=0; i<15; i++)
	{
		int index=rand()%10;
		doTest(M, usedList, index);
		index=rand()%10;
		addTest(M, usedList, index);
	}

	/*
	for (i=Length; i>=0; i--)
	{
		int index=(i+4)%10;
		if (usedList[index]!=-1)
		{
			M.release(usedList[index]);
			cout<<"\nnow print for "<<i<<endl;
			M.print();
		}
	}
	*/
	cout<<endl;
	return 0;
}

void Mem::doubleMerge(int index)
{
	int leftSize=memory[index-2];
	int size=memory[index+1];
	int rightSize=memory[index+size+1];

	memory[index-leftSize+1]=memory[index+size+rightSize-2]=size+leftSize+rightSize;
	memory[index-leftSize+3]=memory[index+size+3];
}


bool Mem::canMerge(int index)
{
	bool result=false;
	int size=memory[index+1];//actual size
	if (index!=0)
	{
		result= result||memory[index-1]==Free;
	}
	if (index+size<MemLength-1)
	{
		result=result||memory[index+size]==Free;
	}

	return result;
}


void Mem::leftMerge(int index)
{
	int size=memory[index+1];
	int leftSize=memory[index-2];
	memory[index-leftSize+1]=memory[index+size-2]=size+leftSize;
	memory[index+size-1]=memory[index-leftSize]=Free;

}

void Mem::rightMerge(int index)
{
	int size=memory[index+1];
	int rightSize;
	int prev, next;

	index+=size;//pointing to right head
	rightSize=memory[index+1];

	if (memory[index-1]==Free)//already leftMerged!
	{
		size=memory[index-2];//in case leftmerged!
	}
	memory[index-size+1]=memory[index+rightSize-2]=size+rightSize;
	memory[index+rightSize-1]=memory[index-size]=Free;
	prev=memory[index+2];
	next=memory[index+3];
	memory[index-size+2]=prev;
	memory[index-size+3]=next;
	memory[prev+3]=index-size;
	memory[next+2]=index-size;
	if (index==freeHead)
	{
		freeHead-=size;
	}
}



void Mem::doMerge(int index)
{
	int size=memory[index+1];
	if (index!=0)//possible of double merge
	{
		if (memory[index-1]==Free&&memory[index+size]==Free)
		{
			doubleMerge(index);
		}
		else
		{

			if (memory[index-1]==Free)
			{
				leftMerge(index);
			}
			if (memory[index+size]==Free)
			{
				rightMerge(index);
			}
		}
	}
	else//only possible of right merge
	{
		if (memory[index+size]==Free)
		{
			rightMerge(index);
		}
	}	
}
	
void Mem::insert(int index)
{
	int size=memory[index+1];
	int start=freeHead;
	int next;
	//this won't change
	memory[index]=memory[index+size-1]=Free;
	memory[index+size-2]=size;

	//empty list
	if (freeHead==-1)
	{
		freeHead=index;
		memory[index+2]=0;//no prev
		memory[index+3]=0;
		return ;
	}
	next=memory[start+3];
	//right before everything
	if (start>index)
	{
		freeHead=index;
		memory[index+2]=0;//no prev
		memory[index+3]=start;
		memory[start+2]=index;
		return;
	}
	while(start<index&&next<index&&next!=0)
	{
		start=next;
		next=memory[start+3];
	}

	memory[start+3]=index;//next of prev
	if (next!=0)
	{
		memory[next+2]=index;//prev of next
	}

	memory[index+2]=start;
	memory[index+3]=next;
}

void Mem::release(int index)
{
	if (canMerge(index))
	{
		doMerge(index);
	}
	else
	{
		insert(index);
	}
}

int Mem::findNext(int index)
{
	return memory[index+3];
}

Mem::Mem(SearchPolicy search)
{
	searchPolicy = search;
	initialize();
}

bool Mem::firstFit(int& index, int length)
{
	index=freeHead;
	do 
	{
		if (memory[index+1]>length+MinUsed)
		{
			return true;
		}

	}while ((index=findNext(index))!=0);
	return false;
}


bool Mem::findFree(int& index, int length)
{
	switch (searchPolicy)
	{
	case FirstFit:
		return firstFit(index, length);
	case WorstFit:
		return worstFit(index, length);
	case BestFit:
		return bestFit(index, length);
	}
	return false;
}

void Mem::doAllocate(int index, int length)
{
	int prev, next, size;

	size=memory[index+1];//old size
	prev=memory[index+2];
	next=memory[index+3];

	//set up free old 
	if (size-length>MinFree)
	{
		memory[index+length]=Free;
		memory[index+length+1]=memory[index+size-2]=size-length;
		memory[index+length+2]=prev;
		memory[index+length+3]=next;
		memory[next+2]=index+length;//update next node

		memory[index]=memory[index+length-1]=Used;
		memory[index+1]=length;
		if (index==freeHead)
		{
			freeHead+=length;
		}
		else
		{
			memory[prev+3]=index+length;
		}
		if (next!=0)
		{
			memory[next+2]=index+length;
		}
	}
	else
	{
		//allocate all free mem
		memory[index+1]=size;
		memory[index]=memory[index+size-1]=Used;
		if (next!=0)
		{
			memory[next+2]=prev;//next has no prev
		


			if (index==freeHead)
			{
				freeHead=next;
			}
		}
		else
		{
			if (index==freeHead)//empty list
			{
				freeHead=-1;
			}
		}
		if (prev!=0)
		{
			memory[prev+3]=next;
		}

	}	

}

bool Mem::bestFit(int& index, int length)
{	
	int min=-1, size, result=freeHead;
	index=freeHead;
	if (index==-1)
	{
		return false;
	}
	do 
	{
		if ((size=memory[index+1]-length-MinUsed)>=0)
		{
			if (min>=0&&size<min)
			{
				min=size;
				result=index;
			}
			else
			{
				if (min<0)//not initialized
				{
					min = size;//first time
					result=index;
				}
			}		
		}
	}while ((index=findNext(index))!=0);
	if (min>=0)
	{
		index=result;
		return true;
	}
	else
	{
		return false;
	}
}

bool Mem::worstFit(int& index, int length)
{
	int max=-1, size, result;
	index=freeHead;
	if (index==-1)
	{
		return false;
	}
	do 
	{
		if ((size=memory[index+1]-length-MinUsed)>=0)
		{
			if (max>=0&&size>max)
			{
				max=size;
				result=index;
			}
			else
			{
				if (max<0)//not initialized
				{
					max = size;//first time
					result=index;
				}
			}		
		}
	}while ((index=findNext(index))!=0);
	if (max>=0)
	{
		index=result;
		return true;
	}
	else
	{
		return false;
	}
}

int Mem::allocate(int length)
{
	int index=freeHead;
	if (findFree(index, length))
	{
		doAllocate(index, length+MinUsed);//allocate more

		return index;
	}
	else
	{
		return -1;
	}
}

void Mem::doPrint(int usedLength, int freeLength, int pos)
{
	int limit=pos+usedLength;
	int length=memory[pos+1];
	while (pos<limit)
	{
		cout<<setw(2)<<memory[pos+1];
		for (int i=2; i<length; i++)
		{		
			cout<<'*';		
		}
		pos+=length;
		length=memory[pos+1];
	}
	if (freeLength!=0)
	{
		cout<<setw(2)<<memory[pos+1];
		for (int i=2; i<freeLength; i++)
		{
			cout<<' ';	
		}
	}
}

void Mem::print()
{
	int index=freeHead;
	int pos=0;
	int usedLength;
	int freeLength;
	if (freeHead==-1)
	{
		doPrint(MemLength, 0, 0);
		return;
	}
	while (true)
	{		
		usedLength=index-pos;
		freeLength=memory[index+1];
		doPrint(usedLength, freeLength, pos);
		pos+=usedLength;
		pos+=freeLength;
		if (memory[index+3]==0||pos==MemLength)
		{
			if (pos<MemLength-1)//print extra used chunk
			{
				freeLength=0;
				usedLength=MemLength-pos-1;
				doPrint(usedLength, freeLength, pos);
			}
			return;
		}
		else
		{
			index=memory[index+3];
		}
	}

}

void Mem::initialize()
{
	memory[0]=memory[MemLength-1]=Free;
	memory[1]=memory[MemLength-2]=MemLength;
	memory[2]=0;//the prev
	memory[3]=0;//the next
	freeHead=0;//pointing to the head;	
}





Here is the result:(Note DFS and BFS gives almost opposite result.)
now print for add size of10
13***********57
now print for add size of2
13*********** 5***52
now print for add size of2
13*********** 5*** 5***47
now print for add size of10
13*********** 5*** 5***13***********34
now print for add size of2
13*********** 5*** 5***13*********** 5***29
now print for add size of5
13*********** 5*** 5***13*********** 5*** 8******21
now print for add size of3
13*********** 5*** 5***13*********** 5*** 8****** 6****15
now print for add size of7
13*********** 5*** 5***13*********** 5*** 8****** 6****15*************
now release one by one

now print result after releasing 2
13*********** 5*** 5 13*********** 5*** 8****** 6****15*************
now print result after releasing 5
13*********** 5*** 5 13*********** 5*** 8 6****15*************
now print result after releasing 0
13 5*** 5 13*********** 5*** 8 6****15*************
now show the best fit

now print for add size of4
13 5*** 5 13*********** 5*** 8****** 6****15*************
Press any key to continue



	


                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)