C/C++模拟内存分配（一）

一、思路
模拟编译系统的内存分配与释放的，实现一些简单的操作。首先用一个静态数组模拟内存空间（buf），当调用申请内存操作时，将从数组空间（buf）返回给调用者一定的空间，当调用释放内存的时候，将将指定部分的内存标记为未用。
   1.分配规则
     每块被分配或释放的内存由MemInfo记录，并保存于数组（buf）中作为内存空间的“头”，其后紧跟数据。MemInfo组成链表结构，表头不占用数组空间（buf）。当调用者申请内存时，将导致MemInfo链表的遍历，遍历的目的是找到“内存碎片”，如果“碎片”大小可用，则重新利用这个“碎片”，返回给调用者。
   2.释放规则
     每块内存块被释放时，仅仅是将数据区标记为无用，并不删除MemInfo链表节点，这样可以重复利用，避免多次MemInfo链表操作。

代码如下：

//1). mem.h

#ifndef __MEM_H__
#define __MEM_H__
#include
#include
#define _1K 1024
#define _1M 1024*_1K
#define _1G 1024*_1M
#define BUFSIZE _1M
char buf[BUFSIZE] ;
static unsigned int front = 0;
typedef struct tagMemInfo
{
   int token;
   int start;
   int end;
   int used;
   struct tagMemInfo *next;
}MemInfo;
MemInfo header;
MemInfo* current;

//interface
void* s_malloc(unsigned int size);
void s_free(void* memptr);
//private

void* alloc_header(unsigned int* nfront);
unsigned int gap(MemInfo* memptr1,MemInfo* memptr2);
void* memloc(MemInfo* ptr,unsigned int* pos,unsigned int size);
void* realloc(unsigned int size);

#endif

//2).mem.c

#include "mem.h"

void* alloc_header(unsigned int* nfront)
{ 
 if(*nfront + sizeof(MemInfo) < BUFSIZE)  
 {  
  *nfront +=  sizeof(MemInfo) ;      
  return &buf[(int)*nfront - sizeof(MemInfo)];
 }
 else
 {
  return NULL;
 }
}

unsigned int gap(MemInfo* memptr1,MemInfo* memptr2)
{
 if(memptr1 != NULL && memptr2 != NULL && memptr1->end != 0)
 {  
  return memptr2->start - memptr1->end - sizeof(MemInfo) -1 ;
 }
 else
 {
  return 0;
 }
}

void* memloc(MemInfo* ptr,unsigned int* pos,unsigned int size)
{ 
 MemInfo* memPtr = (MemInfo*)alloc_header(pos);  
 memPtr->start = *pos;
 memPtr->end = memPtr->start + size -1;
 memPtr->used = 1;     
 MemInfo* tmp = ptr->next;
 if(tmp != NULL)
 {
  ptr->next = memPtr;
  memPtr->next = tmp;  

 }
 else
 {
  ptr->next = memPtr;
  current = memPtr;
 }
 memPtr->token = (int)&buf[memPtr->start];
 *pos += size;
 return &buf[memPtr->start];
}

void* realloc(unsigned int size)
{
 unsigned int pos;
 unsigned int nGap = 0;
 MemInfo* ptr = &header; 
 while(ptr!= NULL) 
 {
  if((ptr->end - ptr->start >= size) && (ptr->used == 0))  
  {
   ptr->used = 1;
   ptr->end = ptr->start + size -1 ;   
   if( front < ptr->end)
   {
    front = ptr->end + 1;
   }
   return (char*)ptr + sizeof(MemInfo);
  }
  MemInfo* tmp = ptr;
  ptr = ptr->next;
  if(ptr != NULL)
  {
   printf("%d\n %d\n",ptr->start,tmp->end);
   nGap = gap(tmp,ptr);  
   printf("gap is %d\n",nGap);
  }
  if( nGap >= (size + sizeof(MemInfo)))
  {
   pos = tmp->end + 1 ;
   return memloc(tmp,&pos,size);
  }
 }  
 return NULL;
}

 

void* s_malloc(unsigned int size)
{
 if(current == NULL) 
 {
  header.next = NULL;
  current = &header;
 }
 void* ptr = realloc(size);
 if(ptr!=NULL)
 {
  return ptr;
 }
 else
 {
  if(front + sizeof(MemInfo) < BUFSIZE) 
  {          
      return memloc(current,&front,size);
  }
  else
  {
   return NULL;
  }
 
 }
 
}
void s_free(void* memptr)
{
 MemInfo* ptr = &header;
 while(ptr != NULL )
 {
  if(ptr->token == (int)memptr)
  {
   ptr->used = 0;
   if(ptr->next == NULL)
   {
    front -= (ptr->end - ptr->start) + 1;
   }
   break;
  }
  ptr = ptr->next;
 }
}

//3).main.c

 

#include "mem.h"

int main()
{ 
 int i;
 char* ptr;
 char* ptr3;
 char* ptr4;
 char* ptr5;
 char* ptr6;
 
 ptr = (char*)s_malloc(100);
        strcpy(ptr,"hello world!"); 
 printf("%s\n",ptr); 

 ptr3 = (char*)s_malloc(7);
 strcpy(ptr3,"sjshwy");
 
 printf("%s\n",ptr3); 
 

 s_free(ptr);

 ptr4 = (char*)s_malloc(5);
 strcpy(ptr4,"win!");
 printf("%s\n",ptr4);

 ptr5 = (char*)s_malloc(20);
 strcpy(ptr5,"i love you!");
 printf("%s\n",ptr5);

 ptr6 = (char*)s_malloc(100);
 strcpy(ptr6,"it is the end of demo!");
 printf("%s\n",ptr5);
 printf("...... heap info ......\n"); 
 for(i = 0; i< 400; ++i )
 {
  
  printf("%c",buf[i]);  
 }
 MemInfo* memptr = &header;
 while(memptr != NULL)
 {
  printf("%s\n",(char*)memptr + sizeof(MemInfo));
  memptr = memptr->next;
 }
 printf("\n");
 
 return 0;
}