链表法页框的分配和去配

采用链表的方法模拟分页式存储空间的分配和去配,

MemManager.h

#pragma once

#define MAX_MEM_LEN 512

class CMemManager
{
private:
	struct MemItem {
		struct MemItem* prior;
		struct MemItem* next;
		bool bFree;
		int nPos;
		int nLen;
		int nOwner;
		MemItem(MemItem* pri, MemItem* nxt, bool bfree, int nPosition, int nLength)
		{
			prior = pri;
			next = nxt;
			bFree = bfree;
			nPos = nPosition;
			nLen = nLength;
			nOwner = -1;
		}
	};	
public:
	CMemManager(void);
	~CMemManager(void);
private:
	const static int m_csnMemBlock = MAX_MEM_LEN;
	int m_MemBlocks[MAX_MEM_LEN];
	MemItem* m_pBase;
public:
	void* GetMem(int nSize, int nOwner);
	void FreeMem(void* p);
	void Show(void);
};

 
MemManager.cpp

#include <iostream>
#include "MemManager.h"

using namespace std;

CMemManager::CMemManager(void)
{
	m_pBase = new MemItem(0, 0, true, 0, m_csnMemBlock);
}

CMemManager::~CMemManager(void)
{
	delete m_pBase;
	m_pBase = 0;
}
void* CMemManager::GetMem(int nSize, int nOwner)
{
	MemItem* p = 0;
	for (MemItem* pTemp = m_pBase; pTemp; pTemp = pTemp->next) 
	{
		if (pTemp->bFree && pTemp->nLen >= nSize)
		{
			int nLeft = pTemp->nLen - nSize;
			if (0 == nLeft) 
			{
				pTemp->bFree = false;
				p = pTemp;
			}
			else 
			{
				p = new MemItem(pTemp, pTemp->next, true, pTemp->nPos+nSize, nLeft);
				if (!p) {
					break;
				}
				if (pTemp->next) {
					pTemp->next->prior = p;
				}
				pTemp->next = p;
				pTemp->bFree = false;
				pTemp->nLen = nSize;
				p = pTemp;
			}
			p->nOwner = nOwner;
			break;
		}
	}
	
	return p; // fail
}
void CMemManager::FreeMem(void* p)
{
	MemItem* pItem = static_cast<MemItem*>(p);
	pItem->bFree = true;
	bool bDelete = false;
	if (pItem->next && pItem->next->bFree) {
		MemItem* pTemp = pItem->next;
		pItem->next = pTemp->next;
		if (pTemp->next) {
			pTemp->next->prior = pItem;
		}
		pItem->nLen += pTemp->nLen;
		delete pTemp;
	}
	if (pItem->prior && pItem->prior->bFree) {
		pItem->prior->next = pItem->next;
		if (pItem->next) {
			pItem->next->prior = pItem->prior;
		}
		pItem->prior->nLen += pItem->nLen;
		delete pItem;
	}
}
void CMemManager::Show(void)
{
	cout << endl << "------------------------------------" << endl;
	for (MemItem* p = m_pBase; p; p = p->next) 
	{
		cout << "Free: " << (p->bFree ? "true          " : "false") << "  ";
		if (!p->bFree) {
			cout << "Owner: " << p->nOwner << " ";
		}
		cout << "Pos: " << p->nPos << "  "
			<< "Length: " << p->nLen << endl;
	}
	
}

 

测试代码

#include <iostream>
#include <ctime>
#include "MemManager.h"

using namespace std;

CMemManager g_mem;

int main()
{	
	int a;
	void* pArray[10] = {0};
	srand((unsigned int)time(0));
	while (cin >> a)
	{
		int i = rand() % 10;
		cout << "i = " << i;
		
		if (pArray[i]) {
			g_mem.FreeMem(pArray[i]);
			pArray[i] = 0;
		} else {
			int nLen = rand() % 128;
			cout << "  nLen = " << nLen;
			pArray[i] = g_mem.GetMem(nLen, i);
		}
		g_mem.Show();
	}

	return 0;
}