1 #include <iostream>  2 #include<string>  3 #include <list>  4 using namespace std;  5   6 //一个简单的内存池，池中保存3块内存分别为1k,2k,4k  7 //实现池子的malloc（size）和free(void*)操作  8 //不考虑跨块申请内存情况  9  10 class node 11 { 12 public: 13     int offset;//相对于起始地址偏移 14     bool flag;//是有效地址还是已经分配地址 15     int len; 16     node() 17     { 18         offset=0; 19         flag=true; 20         len=0; 21     } 22     node(int sz) 23     { 24         offset=0; 25         flag=true; 26         len=sz; 27     } 28 }; 29  30 class memPool 31 { 32 public: 33     memPool() 34     { 35         m_First_Count= 1024; 36         m_Second_Count = 2*1024; 37         m_Third_Count = 4*1024; 38         m_First_Address = new char[m_First_Count]; 39         m_Second_Address = new char[m_Second_Count]; 40         m_Third_Address = new char[m_Third_Count]; 41          42         first.insert(first.begin(),new node(1024));         43         second.insert(second.begin(),new node(1024*2));         44         third.insert(third.begin(),new node(1024*4)); 45     } 46     ~memPool() 47     { 48         delete[]m_First_Address; 49         delete[]m_Second_Address; 50         delete[]m_Third_Address; 51         m_First_Address = NULL; 52         m_Second_Address = NULL; 53         m_Third_Address = NULL; 54  55     } 56     char* myMalloc(const int memSize) 57     { 58         //采用首次适应算法 59         list<node*>::iterator it; 60         if (memSize <= m_First_Count) 61         { 62             it = first.begin(); 63             while(it!=first.end()) 64             { 65                 if (((*it)->len)>= memSize &&(*it)->flag == true) 66                 { 67                     (*it)->flag = false; 68                     int temp = (*it)->len; 69                     (*it)->len = memSize; 70                     if (temp - memSize >0) 71                     { 72                         node *obj = new node; 73                         obj->flag=true; 74                         obj->len = temp - memSize; 75                         obj->offset = (*it)->offset + memSize; 76                         it++; 77                         first.insert(it,obj); 78                         it--; 79                         it--; 80                         m_First_Count-=memSize; 81                         cout << "malloc "<< memSize << " in first memery"<<endl; 82                         return m_First_Address+(*it)->offset; 83                     } 84                 } 85                 it++; 86             } 87              88         } 89  90         if (memSize <= m_Second_Count) 91         { 92             it = second.begin(); 93             while(it!=second.end()) 94             { 95                 if (((*it)->len)>= memSize&&(*it)->flag == true) 96                 { 97                     (*it)->flag = false; 98                     int temp = (*it)->len; 99                     (*it)->len = memSize;100                     if (temp - memSize >0)101                     {102                         node *obj = new node;103                         obj->flag=true;104                         obj->len = temp - memSize;105                         obj->offset = (*it)->offset + memSize;106                         it++;107                         second.insert(it,obj);108                         it--;109                         it--;110                         m_Second_Count-=memSize;111                         cout << "malloc "<< memSize << "in second memery"<<endl;112                         return m_Second_Address+(*it)->offset;113                     }114                 }115                 it++;116             }117             118         }119 120         if (memSize <= m_Third_Count)121         {122             it = third.begin();123             while(it!=third.end())124             {125                 if (((*it)->len)>= memSize&&(*it)->flag == true)126                 {127                     (*it)->flag = false;128                     int temp = (*it)->len;129                     (*it)->len = memSize;130                     if (temp - memSize >0)131                     {132                         node *obj=new node;133                         obj->flag=true;134                         obj->len = temp - memSize;135                         obj->offset = (*it)->offset + memSize;136                         it++;137                         third.insert(it,obj);138                         it--;139                         it--;140                         m_Third_Count-=memSize;141                         cout << "malloc "<< memSize << "in third memery"<<endl;142                         return m_Third_Address+(*it)->offset;143                     }144                 }145                 it++;146             }147             148         }149 150         cout<<"no memery\n";151         return NULL;152 153     }154 /************************************************************************/155 /* 算法思路是第一步定位这个指针位于哪一个内存块，第二步在对应内存块中找到*/156 /*其node，然后判断node前后是否都为有效内存，也就是没有被利用的内存块*/157 /************************************************************************/158     void memFree(void* address_arg)159     {160         char *freeAddress= static_cast<char*>(address_arg);161         int offset;162         list<node*>::iterator it;163         if (freeAddress >= m_First_Address && freeAddress < (m_First_Address+1024))//位于第一块164         {165             offset = freeAddress - m_First_Address;166             it = first.begin();167 168             while(it!= first.end())//定位offset169             {170                 if (offset == (*it)->offset)171                     break;172 173                 it++;174             }175             if (it == first.end())//没有找到offset176             {177                 cout << "In first memery,there is no memery of freeaddress"<<endl;178                 return;179             }180             181             if((*it)->flag == true)//找到offset，但是这块内存没有分配182             {183                 cout << "In first memery,the freeAddress is valid,you can‘t free it"<<endl;184                 return;185             }186             (*it)->flag = true;187             188             int len = (*it)->len;189             int count=0;190             if (it!=first.end())//判断it后继节点是否被分配191             {192                 it++;193                 if ((*it)->flag == true)194                 {195                     len+=(*it)->len;196                     count++;197                 }198                 it--;199             }200             if (it!=first.begin())201             {202                 it--;203                 if ((*it)->flag == true)204                 {205                     len+=(*it)->len;206                     count++;207                 }208                 else209                     it++;210             }211             (*it)->len = len;212             it++;213             while(count--)214             {215                 it = first.erase(it);//erase返回删除节点的后继节点        216                 217             }        218             219             cout << "free success"<<endl;220             return;221 222         }223         else if (freeAddress >= m_Second_Address && freeAddress < (m_Second_Address+1024*2))//位于第二块224         {225             offset = freeAddress - m_Second_Address;226             it = second.begin();227 228             while(it!= second.end())//定位offset229             {230                 if (offset == (*it)->offset)231                     break;232 233                 it++;234             }235             if (it == second.end())//没有找到offset236             {237                 cout << "In second memery,there is no memery of freeaddress"<<endl;238                 return;239             }240 241             if((*it)->flag == true)//找到offset，但是这块内存没有分配242             {243                 cout << "In second memery,the freeAddress is valid,you can‘t free it"<<endl;244                 return;245             }246             (*it)->flag = true;247 248             int len = (*it)->len;249             int count=0;250             if (it!=second.end())//判断it后继节点是否被分配251             {252                 it++;253                 if ((*it)->flag == true)254                 {255                     len+=(*it)->len;256                     count++;257                 }258                 it--;259             }260             if (it!=second.begin())261             {262                 it--;263                 if ((*it)->flag == true)264                 {265                     len+=(*it)->len;266                     count++;267                 }268                 else269                     it++;270             }271             (*it)->len = len;272             it++;273             while(count--)274             {275                 it = second.erase(it);276             }        277 278             cout << "free success"<<endl;279             return;280         }281         else if (freeAddress >= m_Third_Address && freeAddress < (m_Third_Address+1024*4))//位于第三块282         {283             offset = freeAddress - m_Third_Address;284             it = third.begin();285 286             while(it!= third.end())//定位offset287             {288                 if (offset == (*it)->offset)289                     break;290 291                 it++;292             }293             if (it == third.end())//没有找到offset294             {295                 cout << "In third memery,there is no memery of freeaddress"<<endl;296                 return;297             }298 299             if((*it)->flag == true)//找到offset，但是这块内存没有分配300             {301                 cout << "In third memery,the freeAddress is valid,you can‘t free it"<<endl;302                 return;303             }304             (*it)->flag = true;305 306             int len = (*it)->len;307             int count=0;308             if (it!=third.end())//判断it后继节点是否被分配309             {310                 it++;311                 if ((*it)->flag == true)312                 {313                     len+=(*it)->len;314                     count++;315                 }316                 it--;317             }318             if (it!=third.begin())319             {320                 it--;321                 if ((*it)->flag == true)322                 {323                     len+=(*it)->len;324                     count++;325                 }326                 else327                     it++;328             }329             (*it)->len = len;330             it++;331             while(count--)332             {333                 it = third.erase(it);334             }        335 336             cout << "free success"<<endl;337             return;338         }339         else340         {341             cout << "the memery to be freed is invalid\n";342         }343         return;344     }345 private:346     char *m_First_Address;//每一块内存起始地址347     char *m_Second_Address;348     char *m_Third_Address;349     int m_First_Count;//剩余有效地址大小，不一定是连续，是第一块内存中所有有效之和350     int m_Second_Count;351     int m_Third_Count;352     list<node*> first;353     list<node*> second;354     list<node*> third;355 356 };357 int main()358 {359     memPool obj;360     char *ptr1 = obj.myMalloc(10);    361     char *ptr2 = obj.myMalloc(100);362     char *ptr3 = obj.myMalloc(500);363     char *ptr4 = obj.myMalloc(4*1024+1);364     obj.memFree(ptr2);365     obj.memFree(ptr3);366 367     return 0;368 }