动态分区模拟.cpp

模拟内存的动态分配,可以选择首次适应算法或者最佳适应算法进行分配,结构小巧功能简单

// 动态分区模拟.cpp : 定义应用程序的入口点。
//

#include "stdafx.h"
#include "动态分区模拟.h"
#include<vector>

using namespace std;

#define MAX_LOADSTRING 100

// 全局变量:
HINSTANCE hInst;								// 当前实例
TCHAR szTitle[MAX_LOADSTRING];					// 标题栏文本
TCHAR szWindowClass[MAX_LOADSTRING];			// 主窗口类名


// 此代码模块中包含的函数的前向声明:
ATOM				MyRegisterClass(HINSTANCE hInstance);
BOOL				InitInstance(HINSTANCE, int);
LRESULT CALLBACK	WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK	About(HWND, UINT, WPARAM, LPARAM);


//自定义结构
struct WorkMessage//作业信息结构
{
	int num;//作业号
	int size;//作业大小
	HBRUSH hBrush;//画刷
}WorkMsg[7];

struct WorkProcess//工作过程结构
{
	int num;//作业号
	bool bIn;//进入或释放
}WorkPro[11];

struct sFixList
{
	int num;//作业号
	int start;//起始点
	int over;//结束点
	int size;//大小
}FixList;

struct sHoleList
{
	int start;//起始点
	int over;//结束点
	int size;//大小
};

void SetHoleList(sHoleList* lpHole,int start,int over)
{
	lpHole->start=start;
	lpHole->over=over;
	lpHole->size=lpHole->over-lpHole->start;
}
//自定义类
class cMemory
{
private:
	vector<sFixList*> m_FixList;//已分配页表
	vector<sHoleList*> m_HoleList;//孔页表
public:
	cMemory();
	void HoleMerger();//合并相邻孔
	//void WorkIn(sFixList* lpFixList);//进入内存
	void WorkOut(int num);//释放内存
	void FirstFix(int num);//首次适应算法
	void BestFix(int num);//最佳适应算法
	void Paint(HDC hdc);
	void Clear();//还原为初始化状态
}Memory;

void cMemory::Clear()
{
	if(!m_FixList.empty())
	{
		for(vector<sFixList*>::iterator iter=m_FixList.begin();iter!=m_FixList.end();iter++)
		{
			delete (*iter);
		}
		m_FixList.clear();
	}
	if(!m_HoleList.empty())
	{
		for(vector<sHoleList*>::iterator iter=m_HoleList.begin();iter!=m_HoleList.end();iter++)
		{
			delete (*iter);
		}
		m_HoleList.clear();
	}
	
	sHoleList* lpHoleList=new sHoleList;
	SetHoleList(lpHoleList,0,600);
	m_HoleList.push_back(lpHoleList);
}
void cMemory::WorkOut(int num)
{
	for(vector<sFixList*>::iterator iter=m_FixList.begin();iter!=m_FixList.end();iter++)
	{
		if((*iter)->num==num)
		{
			sHoleList* lpHoleList=new sHoleList;
			SetHoleList(lpHoleList,(*iter)->start,(*iter)->over);
			m_HoleList.push_back(lpHoleList);
			HoleMerger();
			m_FixList.erase(iter);
			break;
		}
	}
	
}
void cMemory::BestFix(int num)
{
	HoleMerger();
	sFixList* lpFixList=new sFixList;
	lpFixList->num=num;
	lpFixList->size=WorkMsg[num].size;
	vector<sHoleList*>::iterator iter2=m_HoleList.end();
	
	for(vector<sHoleList*>::iterator iter1=m_HoleList.begin();iter1!=m_HoleList.end();iter1++)
	{
		if(lpFixList->size == (*iter1)->size)
		{
			iter2=iter1;
			break;
		}
		else if(lpFixList->size < (*iter1)->size)
		{
			if(iter2==m_HoleList.end())
				iter2=iter1;
			else
			{
				if((*iter1)->size<(*iter2)->size)
					iter2=iter1;
			}
		}
	}
	if(iter2!=m_HoleList.end() && ((*iter2)->size>=lpFixList->size))
	{
		lpFixList->start=(*iter2)->start;
		lpFixList->over=lpFixList->start+lpFixList->size;
		(*iter2)->start=lpFixList->over;
		(*iter2)->size=(*iter2)->over-(*iter2)->start;
	}
	m_FixList.push_back(lpFixList);
	/*TCHAR buffer[10];
	for(vector<sHoleList*>::iterator iter=m_HoleList.begin();iter!=m_HoleList.end();iter++)
	{
		wsprintf(buffer,TEXT("%d\n"),(*iter)->size);
		OutputDebugString(buffer);
	}*/
	HoleMerger();
}
void cMemory::FirstFix(int num)
{
	HoleMerger();
	sFixList* lpFixList=new sFixList;
	lpFixList->num=num;
	lpFixList->size=WorkMsg[num].size;
	for(vector<sHoleList*>::iterator iter=m_HoleList.begin();iter!=m_HoleList.end();iter++)
	{
		if(lpFixList->size <= (*iter)->size)
		{
			lpFixList->start=(*iter)->start;
			lpFixList->over=lpFixList->start+lpFixList->size;
			(*iter)->start=lpFixList->over;
			(*iter)->size=(*iter)->over-(*iter)->start;
			break;
		}
	}
	m_FixList.push_back(lpFixList);
	HoleMerger();
}
void cMemory::Paint(HDC hdc)
{	
	
	for(int i=0;i!=m_FixList.size();i++)
	{
		SelectObject(hdc,WorkMsg[m_FixList[i]->num].hBrush);
		Rectangle(hdc,20+m_FixList[i]->start,20,20+m_FixList[i]->over,150);
	}
	SelectObject(hdc,GetStockObject(WHITE_BRUSH));
}
cMemory::cMemory()
{
	sHoleList* lpHoleList=new sHoleList;
	SetHoleList(lpHoleList,0,600);
	m_HoleList.push_back(lpHoleList);
	/*lpHoleList=new sHoleList;
	SetHoleList(lpHoleList,0,100);
	m_HoleList.push_back(lpHoleList);
	lpHoleList=new sHoleList;
	SetHoleList(lpHoleList,100,300);
	m_HoleList.push_back(lpHoleList);
	lpHoleList=new sHoleList;
	SetHoleList(lpHoleList,350,500);
	m_HoleList.push_back(lpHoleList);
	lpHoleList=new sHoleList;
	SetHoleList(lpHoleList,0,0);
	m_HoleList.push_back(lpHoleList);*/
}
void cMemory::HoleMerger()
{
	for(vector<sHoleList*>::iterator iter=m_HoleList.begin();iter!=m_HoleList.end();)
	{
		if((*iter)->start==(*iter)->over)
			iter = m_HoleList.erase(iter);
		else
			iter++;
	}
	for(vector<sHoleList*>::iterator iter1=m_HoleList.begin();iter1!=m_HoleList.end();iter1++)
		for(vector<sHoleList*>::iterator iter2=iter1+1;iter2!=m_HoleList.end();iter2++)
		{
			if((*iter1)->start > (*iter2)->start)
			{
				sHoleList* lpHoleList=new sHoleList;
				lpHoleList->start=(*iter1)->start;
				lpHoleList->over=(*iter1)->over;
				lpHoleList->size=(*iter1)->size;

				(*iter1)->over=(*iter2)->over;
				(*iter1)->size=(*iter2)->size;
				(*iter1)->start=(*iter2)->start;

				(*iter2)->over=lpHoleList->over;
				(*iter2)->size=lpHoleList->size;
				(*iter2)->start=lpHoleList->start;

				delete lpHoleList;
			}
		}
	for(vector<sHoleList*>::iterator iter=m_HoleList.begin();iter!=m_HoleList.end()-1;)
	{
		if((*iter)->over==(*(iter+1))->start)
		{
			(*(iter+1))->start=(*iter)->start;
			(*(iter+1))->size=(*(iter+1))->over-(*(iter+1))->start;
			if(iter!=m_HoleList.end())
				iter=m_HoleList.erase(iter);
		}
		else
			iter++;
	}
}

//自定义函数
void WorkMsgPaint(HDC hdc,int xOrigin,int yOrigin)//画作业信息
{
	TEXTMETRIC tm;
	int cxChar,cyChar;
	TCHAR szNum[7],szSize[7];

	GetTextMetrics(hdc,&tm);
	cxChar=tm.tmAveCharWidth;//获取字符宽度
	cyChar=tm.tmHeight+tm.tmExternalLeading;//获取字符高度
	for(int i=0;i<7;i++)
	{
		TextOut(hdc,xOrigin,yOrigin+i*cyChar,szNum,wsprintf(szNum,TEXT("作业%d"),i+1));

		SetTextAlign(hdc,TA_RIGHT | TA_TOP);

		TextOut(hdc,xOrigin+12*cxChar,yOrigin+i*cyChar,szSize,
			wsprintf(szSize,TEXT("%3d K"),WorkMsg[i].size));
		
		SetTextAlign(hdc,TA_LEFT | TA_TOP);
		
		SelectObject(hdc,WorkMsg[i].hBrush);
		Rectangle(hdc,xOrigin+15*cxChar,yOrigin+i*cyChar,xOrigin+20*cxChar,yOrigin+i*cyChar+tm.tmHeight);
		SelectObject(hdc,GetStockObject(WHITE_BRUSH));
	}
}

void WorkProPaint(HDC hdc,int xOrigin,int yOrigin,int iProcess)//画工作过程
{
	TEXTMETRIC tm;
	int cxChar,cyChar;
	TCHAR szNum[11],szSize[11];

	GetTextMetrics(hdc,&tm);
	cxChar=tm.tmAveCharWidth;//获取字符宽度
	cyChar=tm.tmHeight+tm.tmExternalLeading;//获取字符高度
	for(int i=0;i<11;i++)
	{
		TextOut(hdc,xOrigin,yOrigin+i*cyChar,szNum,wsprintf(szNum,TEXT("作业%d"),WorkPro[i].num));

		if(WorkPro[i].bIn)
		{
			TextOut(hdc,xOrigin+7*cxChar,yOrigin+i*cyChar,TEXT("进入"),2);
		}
		else
		{
			TextOut(hdc,xOrigin+7*cxChar,yOrigin+i*cyChar,TEXT("释放"),2);
		}

		SetTextAlign(hdc,TA_RIGHT | TA_TOP);

		TextOut(hdc,xOrigin+18*cxChar,yOrigin+i*cyChar,szSize,
			wsprintf(szSize,TEXT("%3d K"),WorkMsg[WorkPro[i].num-1].size));
		
		SetTextAlign(hdc,TA_LEFT | TA_TOP);
	}
	
	if(iProcess)
		TextOut(hdc,xOrigin+19*cxChar,yOrigin+(iProcess-1)*cyChar,TEXT("<=="),3);
}

int APIENTRY _tWinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPTSTR    lpCmdLine,
                     int       nCmdShow)
{
	UNREFERENCED_PARAMETER(hPrevInstance);
	UNREFERENCED_PARAMETER(lpCmdLine);

 	// TODO: 在此放置代码。
	MSG msg;
	HACCEL hAccelTable;

	// 初始化全局字符串
	LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
	LoadString(hInstance, IDC_MY, szWindowClass, MAX_LOADSTRING);
	MyRegisterClass(hInstance);

	// 执行应用程序初始化:
	if (!InitInstance (hInstance, nCmdShow))
	{
		return FALSE;
	}

	hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_MY));

	// 主消息循环:
	while (GetMessage(&msg, NULL, 0, 0))
	{
		if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
		{
			TranslateMessage(&msg);
			DispatchMessage(&msg);
		}
	}

	return (int) msg.wParam;
}



//
//  函数: MyRegisterClass()
//
//  目的: 注册窗口类。
//
//  注释:
//
//    仅当希望
//    此代码与添加到 Windows 95 中的“RegisterClassEx”
//    函数之前的 Win32 系统兼容时，才需要此函数及其用法。调用此函数十分重要，
//    这样应用程序就可以获得关联的
//    “格式正确的”小图标。
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
	WNDCLASSEX wcex;

	wcex.cbSize = sizeof(WNDCLASSEX);

	wcex.style			= CS_HREDRAW | CS_VREDRAW;
	wcex.lpfnWndProc	= WndProc;
	wcex.cbClsExtra		= 0;
	wcex.cbWndExtra		= 0;
	wcex.hInstance		= hInstance;
	wcex.hIcon			= LoadIcon(hInstance, MAKEINTRESOURCE(IDI_MY));
	wcex.hCursor		= LoadCursor(NULL, IDC_ARROW);
	wcex.hbrBackground	= (HBRUSH)(COLOR_WINDOW+1);
	wcex.lpszMenuName	= MAKEINTRESOURCE(IDC_MY);
	wcex.lpszClassName	= szWindowClass;
	wcex.hIconSm		= LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));

	return RegisterClassEx(&wcex);
}

//
//   函数: InitInstance(HINSTANCE, int)
//
//   目的: 保存实例句柄并创建主窗口
//
//   注释:
//
//        在此函数中，我们在全局变量中保存实例句柄并
//        创建和显示主程序窗口。
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
   HWND hWnd;

   hInst = hInstance; // 将实例句柄存储在全局变量中

   hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPED   |   WS_SYSMENU   |WS_MINIMIZEBOX,
      CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);

   if (!hWnd)
   {
      return FALSE;
   }

   ShowWindow(hWnd, nCmdShow);
   UpdateWindow(hWnd);

   return TRUE;
}

//
//  函数: WndProc(HWND, UINT, WPARAM, LPARAM)
//
//  目的: 处理主窗口的消息。
//
//  WM_COMMAND	- 处理应用程序菜单
//  WM_PAINT	- 绘制主窗口
//  WM_DESTROY	- 发送退出消息并返回
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	int wmId, wmEvent;
	PAINTSTRUCT ps;
	HDC hdc;
	static bool bFirstFix=true;//选择首次适应或最佳适应
	static int iProcess=0;//标志程序进行的步骤
	static RECT rc;//保存开始按扭的位置（用于判断按纽是否被点击）
	static POINT pt[3];//画开始按纽的三角形
	static POINT ptMouse;//鼠标当前位置

	switch (message)
	{
	case WM_CREATE:
		//初始化WorkMsg数组
		for(int i=0;i<7;i++)
			WorkMsg[i].num=i;

		WorkMsg[0].size=130;
		WorkMsg[1].size=60;
		WorkMsg[2].size=100;
		WorkMsg[3].size=200;
		WorkMsg[4].size=140;
		WorkMsg[5].size=60;
		WorkMsg[6].size=50;

		WorkMsg[0].hBrush=CreateSolidBrush(RGB(0,0,0));
		WorkMsg[1].hBrush=CreateSolidBrush(RGB(255,0,0));
		WorkMsg[2].hBrush=CreateSolidBrush(RGB(0,255,0));
		WorkMsg[3].hBrush=CreateSolidBrush(RGB(0,0,255));
		WorkMsg[4].hBrush=CreateSolidBrush(RGB(255,255,0));
		WorkMsg[5].hBrush=CreateSolidBrush(RGB(255,0,255));
		WorkMsg[6].hBrush=CreateSolidBrush(RGB(0,255,255));
		
		//初始化工作过程
		WorkPro[0].num=1;WorkPro[0].bIn=true;
		WorkPro[1].num=2;WorkPro[1].bIn=true;
		WorkPro[2].num=3;WorkPro[2].bIn=true;
		WorkPro[3].num=2;WorkPro[3].bIn=false;
		WorkPro[4].num=4;WorkPro[4].bIn=true;
		WorkPro[5].num=3;WorkPro[5].bIn=false;
		WorkPro[6].num=1;WorkPro[6].bIn=false;
		WorkPro[7].num=5;WorkPro[7].bIn=true;
		WorkPro[8].num=6;WorkPro[8].bIn=true;
		WorkPro[9].num=7;WorkPro[9].bIn=true;
		WorkPro[10].num=6;WorkPro[10].bIn=false;

		//初始化按纽矩形和三角形
		SetRect(&rc,450,200,600,300);
		pt[0].x=490;
		pt[0].y=210;
		pt[1].x=580;
		pt[1].y=250;
		pt[2].x=490;
		pt[2].y=290;
		
		break;
	case WM_RBUTTONDOWN:
		ptMouse.x=LOWORD(lParam);
		ptMouse.y=HIWORD(lParam);
		if(PtInRect(&rc,ptMouse))
		{
			iProcess=0;
			Memory.Clear();
			InvalidateRect(hWnd,NULL,true);
		}
		break;
	case WM_LBUTTONDOWN:
		ptMouse.x=LOWORD(lParam);
		ptMouse.y=HIWORD(lParam);
		if(PtInRect(&rc,ptMouse))
		{
			if(iProcess==11)
			{
				iProcess=0;
				Memory.Clear();
			}
			else
			{
				if(WorkPro[iProcess].bIn)
				{
					if(bFirstFix)
						Memory.FirstFix(WorkPro[iProcess].num-1);
					else
						Memory.BestFix(WorkPro[iProcess].num-1);
				}
				else
				{
					Memory.WorkOut(WorkPro[iProcess].num-1);
				}
				iProcess++;
			}
			InvalidateRect(hWnd,NULL,true);
		}
		break;
	case WM_COMMAND:
		wmId    = LOWORD(wParam);
		wmEvent = HIWORD(wParam);
		// 分析菜单选择:
		switch (wmId)
		{
		case IDM_ABOUT:
			DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
			break;
		case IDM_EXIT:
			DestroyWindow(hWnd);
			break;
		case IDM_FIRST:
			bFirstFix=true;
			InvalidateRect(hWnd,NULL,true);
			break;
		case IDM_BEST:
			bFirstFix=false;
			InvalidateRect(hWnd,NULL,true);
			break;
		default:
			return DefWindowProc(hWnd, message, wParam, lParam);
		}
		break;
	case WM_PAINT:
		hdc = BeginPaint(hWnd, &ps);
		// TODO: 在此添加任意绘图代码...
		if(bFirstFix)
			TextOut(hdc,485,320,TEXT("首次适应算法"),6);
		else
			TextOut(hdc,485,320,TEXT("最佳适应算法"),6);

		WorkMsgPaint(hdc,20,200);
		WorkProPaint(hdc,220,200,iProcess);

		SelectObject(hdc,WorkMsg[6].hBrush);
		Rectangle(hdc,rc.left,rc.top,rc.right,rc.bottom);

		SelectObject(hdc,WorkMsg[1].hBrush);
		SetPolyFillMode(hdc,WINDING);
		Polygon(hdc,pt,3);
		SelectObject(hdc,GetStockObject(WHITE_BRUSH));

		Rectangle(hdc,20,20,620,150);
		Memory.Paint(hdc);

		//OutputDebugString(TEXT("abdk"));

		EndPaint(hWnd, &ps);
		break;
	case WM_DESTROY:
		for(int i=0;i<7;i++)
			DeleteObject(WorkMsg[i].hBrush);
		PostQuitMessage(0);
		break;
	default:
		return DefWindowProc(hWnd, message, wParam, lParam);
	}
	return 0;
}

// “关于”框的消息处理程序。
INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
	UNREFERENCED_PARAMETER(lParam);
	switch (message)
	{
	case WM_INITDIALOG:
		return (INT_PTR)TRUE;

	case WM_COMMAND:
		if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
		{
			EndDialog(hDlg, LOWORD(wParam));
			return (INT_PTR)TRUE;
		}
		break;
	}
	return (INT_PTR)FALSE;
}