做这个内存池主要是为了完成一道面试题，题目在代码中。
代码
#include <iostream>
#include<string>
#include <list>
using namespace std; //一个简单的内存池，池中保存3块内存分别为1k,2k,4k
//实现池子的malloc（size）和free(void*)操作
//不考虑跨块申请内存情况 class node
{
public:
int offset;//相对于起始地址偏移
bool flag;//是有效地址还是已经分配地址
int len;
node()
{
offset=;
flag=true;
len=;
}
node(int sz)
{
offset=;
flag=true;
len=sz;
}
}; class memPool
{
public:
memPool()
{
m_First_Count= ;
m_Second_Count = *;
m_Third_Count = *;
m_First_Address = new char[m_First_Count];
m_Second_Address = new char[m_Second_Count];
m_Third_Address = new char[m_Third_Count]; first.insert(first.begin(),new node());
second.insert(second.begin(),new node(*));
third.insert(third.begin(),new node(*));
}
~memPool()
{
delete[]m_First_Address;
delete[]m_Second_Address;
delete[]m_Third_Address;
m_First_Address = NULL;
m_Second_Address = NULL;
m_Third_Address = NULL; }
char* myMalloc(const int memSize)
{
//采用首次适应算法
list<node*>::iterator it;
if (memSize <= m_First_Count)
{
it = first.begin();
while(it!=first.end())
{
if (((*it)->len)>= memSize &&(*it)->flag == true)
{
(*it)->flag = false;
int temp = (*it)->len;
(*it)->len = memSize;
if (temp - memSize >)
{
node *obj = new node;
obj->flag=true;
obj->len = temp - memSize;
obj->offset = (*it)->offset + memSize;
it++;
first.insert(it,obj);
it--;
it--;
m_First_Count-=memSize;
cout << "malloc "<< memSize << " in first memery"<<endl;
return m_First_Address+(*it)->offset;
}
}
it++;
} } if (memSize <= m_Second_Count)
{
it = second.begin();
while(it!=second.end())
{
if (((*it)->len)>= memSize&&(*it)->flag == true)
{
(*it)->flag = false;
int temp = (*it)->len;
(*it)->len = memSize;
if (temp - memSize >)
{
node *obj = new node;
obj->flag=true;
obj->len = temp - memSize;
obj->offset = (*it)->offset + memSize;
it++;
second.insert(it,obj);
it--;
it--;
m_Second_Count-=memSize;
cout << "malloc "<< memSize << "in second memery"<<endl;
return m_Second_Address+(*it)->offset;
}
}
it++;
} } if (memSize <= m_Third_Count)
{
it = third.begin();
while(it!=third.end())
{
if (((*it)->len)>= memSize&&(*it)->flag == true)
{
(*it)->flag = false;
int temp = (*it)->len;
(*it)->len = memSize;
if (temp - memSize >)
{
node *obj=new node;
obj->flag=true;
obj->len = temp - memSize;
obj->offset = (*it)->offset + memSize;
it++;
third.insert(it,obj);
it--;
it--;
m_Third_Count-=memSize;
cout << "malloc "<< memSize << "in third memery"<<endl;
return m_Third_Address+(*it)->offset;
}
}
it++;
} } cout<<"no memery\n";
return NULL; }
/************************************************************************/
/* 算法思路是第一步定位这个指针位于哪一个内存块，第二步在对应内存块中找到*/
/*其node，然后判断node前后是否都为有效内存，也就是没有被利用的内存块*/
/************************************************************************/
void memFree(void* address_arg)
{
char *freeAddress= static_cast<char*>(address_arg);
int offset;
list<node*>::iterator it;
if (freeAddress >= m_First_Address && freeAddress < (m_First_Address+))//位于第一块
{
offset = freeAddress - m_First_Address;
it = first.begin(); while(it!= first.end())//定位offset
{
if (offset == (*it)->offset)
break; it++;
}
if (it == first.end())//没有找到offset
{
cout << "In first memery,there is no memery of freeaddress"<<endl;
return;
} if((*it)->flag == true)//找到offset，但是这块内存没有分配
{
cout << "In first memery,the freeAddress is valid,you can't free it"<<endl;
return;
}
(*it)->flag = true; int len = (*it)->len;
int count=;
if (it!=first.end())//判断it后继节点是否被分配
{
it++;
if ((*it)->flag == true)
{
len+=(*it)->len;
count++;
}
it--;
}
if (it!=first.begin())
{
it--;
if ((*it)->flag == true)
{
len+=(*it)->len;
count++;
}
else
it++;
}
(*it)->len = len;
it++;
while(count--)
{
it = first.erase(it);//erase返回删除节点的后继节点 } cout << "free success"<<endl;
return; }
else if (freeAddress >= m_Second_Address && freeAddress < (m_Second_Address+*))//位于第二块
{
offset = freeAddress - m_Second_Address;
it = second.begin(); while(it!= second.end())//定位offset
{
if (offset == (*it)->offset)
break; it++;
}
if (it == second.end())//没有找到offset
{
cout << "In second memery,there is no memery of freeaddress"<<endl;
return;
} if((*it)->flag == true)//找到offset，但是这块内存没有分配
{
cout << "In second memery,the freeAddress is valid,you can't free it"<<endl;
return;
}
(*it)->flag = true; int len = (*it)->len;
int count=;
if (it!=second.end())//判断it后继节点是否被分配
{
it++;
if ((*it)->flag == true)
{
len+=(*it)->len;
count++;
}
it--;
}
if (it!=second.begin())
{
it--;
if ((*it)->flag == true)
{
len+=(*it)->len;
count++;
}
else
it++;
}
(*it)->len = len;
it++;
while(count--)
{
it = second.erase(it);
} cout << "free success"<<endl;
return;
}
else if (freeAddress >= m_Third_Address && freeAddress < (m_Third_Address+*))//位于第三块
{
offset = freeAddress - m_Third_Address;
it = third.begin(); while(it!= third.end())//定位offset
{
if (offset == (*it)->offset)
break; it++;
}
if (it == third.end())//没有找到offset
{
cout << "In third memery,there is no memery of freeaddress"<<endl;
return;
} if((*it)->flag == true)//找到offset，但是这块内存没有分配
{
cout << "In third memery,the freeAddress is valid,you can't free it"<<endl;
return;
}
(*it)->flag = true; int len = (*it)->len;
int count=;
if (it!=third.end())//判断it后继节点是否被分配
{
it++;
if ((*it)->flag == true)
{
len+=(*it)->len;
count++;
}
it--;
}
if (it!=third.begin())
{
it--;
if ((*it)->flag == true)
{
len+=(*it)->len;
count++;
}
else
it++;
}
(*it)->len = len;
it++;
while(count--)
{
it = third.erase(it);
} cout << "free success"<<endl;
return;
}
else
{
cout << "the memery to be freed is invalid\n";
}
return;
}
private:
char *m_First_Address;//每一块内存起始地址
char *m_Second_Address;
char *m_Third_Address;
int m_First_Count;//剩余有效地址大小，不一定是连续，是第一块内存中所有有效之和
int m_Second_Count;
int m_Third_Count;
list<node*> first;
list<node*> second;
list<node*> third; };
int main()
{
memPool obj;
char *ptr1 = obj.myMalloc();
char *ptr2 = obj.myMalloc();
char *ptr3 = obj.myMalloc();
char *ptr4 = obj.myMalloc(*+);
obj.memFree(ptr2);
obj.memFree(ptr3); return ;
}