实现一个动态存储分配

it2025-12-30 13

如何自己实现一个动态存储的分配机制，当然有很多的存储的分配方法，关键在于“堆”的管理。这里我们使用“隐式链表”的方法实现对“堆”的分配。而且分配的单位是“字”，这里的字是4个字节，而且我们分配的内存都按8字节（也就是双字）对齐。上图中一个空格代表一个字（4字节）也就是我们的堆开始三个字是堆的对齐和头部用的。最后是堆的尾。上图是我们堆的“分配块”的头部，由于我们的堆是以8字节对齐的，也就是分配的最小单位将是双字，于是我们知道对于长度来讲最后三个位是没用的。因为必须是8的倍数嘛，于是我们可以用这几位来作标记看是否己经分配了该块。块的头部和尾部是一样的。我们这里采用“首次匹配”策略进行块的分配。也就是说我们从“堆”的头部开始搜索合适的块，当有块的大小大于要求的块大小时，我们就将当空的空块分割一块出来分配给它。当整个“堆”没有合适的块时，我们在“堆”的后面申请新的块。

#ifndef DYNAMIC_MALLOC_H#define DYNAMIC_MALLOC_H#define NoFault 0#define OutofMemory 1#define NoRest 2class DynamicMalloc{protected: const static int WSIZE=4; const static int DSIZE=8; const static bool ALLOCED=1; const static bool UNALLOCED=0; private: static char* mem_heap; //指向堆首地址 static char* mem_brk; //指向目前分配的“堆”的最后一个字的下一个 static char* mem_max_addr; //一直指向最大所能分配的地址，“堆大小” static char* heap_listp; //一直指向序言块 const static unsigned int MAX_HEAP=2048; const static unsigned int CHUNKSIZE=30; const static unsigned int MINCHUNK=DSIZE*2+2*WSIZE; unsigned int pack(unsigned int size,unsigned int alloc){ return size|alloc; } void put_data(void *ptr,unsigned int val){ *((unsigned int*)ptr)=val; } unsigned int get_data(void *ptr){ return *((unsigned int*)(ptr)); } unsigned int get_size(void *ptr){//取出块大小 return get_data(ptr)&(~0x07); } bool get_alloced(void *ptr){//取出“分配”标志 return get_data(ptr)&0x01; } char* mem_head(void *ptr){//找到块的头部 return (char*)ptr-WSIZE; } char* mem_ftrp(void *ptr){ //找到块的尾部 return (char*)ptr+get_size((void*)mem_head(ptr)); } char* next_blkb(void *ptr){//找到下一块 return (char*)ptr+get_size((void*)mem_head(ptr))+DSIZE; } char *pre_blkb(void *ptr){//找到前面块 return (char*)ptr-get_size((void*)((char*)ptr-DSIZE))-DSIZE; } void *mem_sbrk(unsigned int inc); void mm_init(); void* extern_heap(unsigned int size); void coalesce(void *ptr); void clearBlock(void *ptr); void* find_fit(unsigned int size); public: int mem_errno; DynamicMalloc(); void* mm_malloc(unsigned int size); void mm_free(void *ptr); }; #endif

#include<stdio.h>#include<memory>#include<iostream>#include"DynamicMalloc.h"char * DynamicMalloc::heap_listp=NULL; char * DynamicMalloc::mem_heap=NULL; char * DynamicMalloc::mem_brk=NULL; char * DynamicMalloc::mem_max_addr=NULL; DynamicMalloc::DynamicMalloc(){ if(mem_heap==NULL){ mem_errno=NoFault; mem_heap=(char*)malloc(WSIZE*MAX_HEAP*sizeof(char)); if(mem_heap==NULL){ mem_errno=OutofMemory; std::cout<<"overflow"<<std::endl; } mem_brk=mem_heap; mem_max_addr=mem_heap+WSIZE*MAX_HEAP*sizeof(char); mm_init(); }}void * DynamicMalloc::mem_sbrk(unsigned int inc){ if(inc<0||(mem_heap+inc>mem_max_addr)){ mem_errno=OutofMemory; std::cout<<"memory overflow!"<<std::endl; return NULL ; } char *old_mem_brk=mem_brk; mem_brk+=inc+DSIZE; //预留空间，用于头和尾 return (void*)old_mem_brk; }void DynamicMalloc::mm_init(){ if((heap_listp=(char*)mem_sbrk(2*WSIZE))==NULL){ return; } put_data(heap_listp,pack(0,ALLOCED)); put_data(heap_listp+WSIZE,pack(0,ALLOCED)); put_data(heap_listp+2*WSIZE,pack(0,ALLOCED)); put_data(heap_listp+3*WSIZE,pack(0,ALLOCED)); heap_listp+=2*WSIZE; extern_heap(CHUNKSIZE); }void* DynamicMalloc::extern_heap(unsigned int size){ int words=(size%2)? (size+1)*WSIZE:(size)*WSIZE; char *bp=NULL; bp=(char*)mem_sbrk(words); put_data(mem_head(bp),pack(words,UNALLOCED)); //块头 put_data(mem_ftrp(bp),pack(words,UNALLOCED)); //块脚 put_data(mem_ftrp(bp)+WSIZE,pack(0,ALLOCED)); //新的“堆脚”,也是结束的标志 coalesce(bp); return bp; }void DynamicMalloc::clearBlock(void *ptr){ char *clear_ptr=(char*)ptr; for(int i=0;i<WSIZE; i++){ *(clear_ptr+i)=0; }}void DynamicMalloc::coalesce(void *ptr){ bool preAlloced=ALLOCED; bool nxtAlloced=ALLOCED; preAlloced=get_alloced(mem_head(pre_blkb(ptr))); //获得前一块的状态 nxtAlloced=get_alloced(mem_head(next_blkb(ptr))); //获得下一块的状态 if(preAlloced&&nxtAlloced){//前后两块都分配了 return; }else if(preAlloced&&!nxtAlloced){//前一块己分配，后一块没有 unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(next_blkb(ptr)))+DSIZE; put_data(mem_head(ptr),pack(new_size,UNALLOCED));//设置新块头部 put_data(mem_ftrp(ptr),pack(new_size,UNALLOCED)); //新块的脚 //clearBlock(mem_ftrp(ptr)); //clearBlock(mem_head(next_blkb(ptr))); //清理门户 }else if(!preAlloced&&nxtAlloced){//前面的未分配，后面的分配了 unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(pre_blkb(ptr)))+DSIZE; put_data(mem_head(pre_blkb(ptr)),pack(new_size,UNALLOCED)); put_data(mem_ftrp(ptr),pack(new_size,UNALLOCED)); //clearBlock(mem_head(ptr)); //clearBlock(mem_ftrp(pre_blkb(ptr))); }else if(!preAlloced&&!nxtAlloced){//前后都未分配 unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(pre_blkb(ptr)))+get_size(mem_head(next_blkb(ptr))); put_data(mem_head(pre_blkb(ptr)), pack(new_size,UNALLOCED)); put_data(mem_ftrp(next_blkb(ptr)),pack(new_size,UNALLOCED)); //clearBlock(mem_head(ptr)); //clearBlock(mem_ftrp(ptr)); //clearBlock(mem_ftrp(pre_blkb(ptr))); //clearBlock(mem_head(next_blkb(ptr))); //清理门户 }}void* DynamicMalloc::mm_malloc(unsigned int size){ unsigned int malloc_size=0; void *reptr=NULL; if(size==0){ return NULL; } if(size<=DSIZE){ malloc_size=DSIZE; }else{ malloc_size=DSIZE*((size+DSIZE+DSIZE-1)/DSIZE); } if((reptr=find_fit(malloc_size))!=NULL){ return (void*)reptr; }else{ reptr=(void*)extern_heap(malloc_size); put_data(mem_head(reptr),pack(malloc_size,ALLOCED)); put_data(mem_ftrp(reptr),pack(malloc_size,ALLOCED)); return reptr; }}void* DynamicMalloc::find_fit(unsigned int size){ char *ptr=next_blkb(heap_listp); //heap_listp一直指向序言块 std::cout<<get_size(mem_head(ptr))<<std::endl; std::cout<<get_alloced(mem_head(ptr))<<std::endl; while(((get_size(mem_head(ptr))!=0)||(get_alloced(mem_head(ptr)))!=ALLOCED)){//从前往后 “首次匹配” std::cout<<get_size(mem_head(ptr))<<std::endl; std::cout<<get_alloced(mem_head(ptr))<<std::endl; if(((get_size(mem_head(ptr))>=size)&&(get_alloced(mem_head(ptr)))==UNALLOCED)){ break;; } ptr=next_blkb(ptr); } if(get_alloced(mem_head(ptr))==ALLOCED&&get_size(mem_head(ptr))==0){//没有合适的空间 mem_errno=NoRest; return NULL; }else{ if(get_size(mem_head(ptr))>=size+MINCHUNK){ unsigned int old_size=get_size(mem_head(ptr)); put_data(mem_head(ptr),pack(size,ALLOCED)); //待分配块“头” put_data(mem_ftrp(ptr),pack(size,ALLOCED)); //待分配块“尾” put_data(mem_head(next_blkb(ptr)),pack(old_size-size-2*WSIZE,UNALLOCED)); put_data(mem_ftrp(next_blkb(ptr)),pack(old_size-size-2*WSIZE,UNALLOCED)); return ptr; }else{ return ptr; } }}void DynamicMalloc::mm_free(void *ptr){ put_data(mem_head(ptr),pack(get_size(mem_head(ptr)),UNALLOCED)); put_data(mem_ftrp(ptr),pack(get_size(mem_head(ptr)),UNALLOCED)); coalesce(ptr);} 测试

#include "DynamicMalloc.h"#include<iostream>int main(){ DynamicMalloc dynamicMalloc; char *ptr=(char*)dynamicMalloc.mm_malloc(10); for(int i=0;i<10;i++){ *(ptr+i)='a'; } for(int i=0;i<10;i++){ std::cout<<*(ptr+i)<<std::endl; } char* p=(char*)dynamicMalloc.mm_malloc(20); for(int i=0;i<20;i++){ *(p+i)='a'; } for(int i=0;i<20;i++){ std::cout<<*(p+i)<<std::endl; } char* pp=(char*)dynamicMalloc.mm_malloc(300); dynamicMalloc.mm_free(p); }

对于空相邻空闲块的管理策略：也就是这部分的代码： void DynamicMalloc::coalesce(void *ptr){ bool preAlloced=ALLOCED; bool nxtAlloced=ALLOCED; preAlloced=get_alloced(mem_head(pre_blkb(ptr))); //获得前一块的状态 nxtAlloced=get_alloced(mem_head(next_blkb(ptr))); //获得下一块的状态 if(preAlloced&&nxtAlloced){//前后两块都分配了 return; }else if(preAlloced&&!nxtAlloced){//前一块己分配，后一块没有 unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(next_blkb(ptr)))+DSIZE; put_data(mem_head(ptr),pack(new_size,UNALLOCED));//设置新块头部 put_data(mem_ftrp(ptr),pack(new_size,UNALLOCED)); //新块的脚 //clearBlock(mem_ftrp(ptr)); //clearBlock(mem_head(next_blkb(ptr))); //清理门户 }else if(!preAlloced&&nxtAlloced){//前面的未分配，后面的分配了 unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(pre_blkb(ptr)))+DSIZE; put_data(mem_head(pre_blkb(ptr)),pack(new_size,UNALLOCED)); put_data(mem_ftrp(ptr),pack(new_size,UNALLOCED)); //clearBlock(mem_head(ptr)); //clearBlock(mem_ftrp(pre_blkb(ptr))); }else if(!preAlloced&&!nxtAlloced){//前后都未分配 unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(pre_blkb(ptr)))+get_size(mem_head(next_blkb(ptr))); put_data(mem_head(pre_blkb(ptr)), pack(new_size,UNALLOCED)); put_data(mem_ftrp(next_blkb(ptr)),pack(new_size,UNALLOCED)); //clearBlock(mem_head(ptr)); //clearBlock(mem_ftrp(ptr)); //clearBlock(mem_ftrp(pre_blkb(ptr))); //clearBlock(mem_head(next_blkb(ptr))); //清理门户 }}

这是开始的一些字段初使化： static char* mem_heap; //指向堆首地址 static char* mem_brk; //指向目前分配的“堆”的最后一个字的下一个 static char* mem_max_addr; //一直指向最大所能分配的地址，“堆大小” static char* heap_listp; //一直指向序言块来自为知笔记(Wiz)

转载于:https://www.cnblogs.com/yml435/p/4690933.html

最新回复(0)