实现一个动态存储分配

如何自己实现一个动态存储的分配机制，当然有很多的存储的分配方法，关键在于“堆”的管理。
这里我们使用“隐式链表”的方法实现对“堆”的分配。
而且分配的单位是“字”，这里的字是4个字节，而且我们分配的内存都按8字节（也就是双字）对齐。

上图中一个空格代表一个字（4字节）
也就是我们的堆开始三个字是堆的对齐和头部用的。最后是堆的尾。

上图是我们堆的“分配块”的头部，由于我们的堆是以8字节对齐的，也就是分配的最小单位将是双字，于是我们知道对于长度来讲
最后三个位是没用的。因为必须是8的倍数嘛，于是我们可以用这几位来作标记看是否己经分配了该块。

块的头部和尾部是一样的。

我们这里采用“首次匹配”策略进行块的分配。也就是说我们从“堆”的头部开始搜索合适的块，当有块的大小大于要求的块大小时，我们就将当空的空块分割一块出来分配给它。
当整个“堆”没有合适的块时，我们在“堆”的后面申请新的块。
  1. #ifndef  DYNAMIC_MALLOC_H
  2. #define  DYNAMIC_MALLOC_H
  3. #define	NoFault		0
  4. #define   OutofMemory	1
  5. #define   NoRest	     2
  6. class DynamicMalloc{
  7. protected:
  8. 	const static int WSIZE=4; 
  9. 	const static int DSIZE=8; 
  10. 	const static bool ALLOCED=1; 
  11. 	const static bool UNALLOCED=0; 
  12. private:
  13. 	static char* mem_heap;		//指向堆首地址
  14. 	static char* mem_brk;		//指向目前分配的“堆”的最后一个字的下一个
  15. 	static char* mem_max_addr;	//一直指向最大所能分配的地址，“堆大小”
  16. 	static char* heap_listp;		//一直指向序言块
  17. 	const static unsigned int MAX_HEAP=2048; 
  18. 	const static unsigned int CHUNKSIZE=30; 
  19. 	const static unsigned int MINCHUNK=DSIZE*2+2*WSIZE; 
  20. 	unsigned int pack(unsigned int size,unsigned int alloc){
  21. 		return size|alloc; 
  22. 	}
  23. 	void put_data(void *ptr,unsigned int val){
  24. 		*((unsigned int*)ptr)=val; 
  25. 	}
  26. 	unsigned int get_data(void *ptr){
  27. 		return *((unsigned int*)(ptr)); 
  28. 	}
  29. 	unsigned int get_size(void *ptr){//取出块大小
  30. 		return get_data(ptr)&(~0x07); 
  31. 	}
  32. 	bool get_alloced(void *ptr){//取出“分配”标志
  33. 		return get_data(ptr)&0x01; 
  34. 	}
  35. 	char* mem_head(void *ptr){//找到块的头部
  36. 		return (char*)ptr-WSIZE; 
  37. 	}
  38. 	char* mem_ftrp(void *ptr){ //找到块的尾部
  39. 		return (char*)ptr+get_size((void*)mem_head(ptr)); 
  40. 	}
  41. 	char* next_blkb(void *ptr){//找到下一块
  42. 		return (char*)ptr+get_size((void*)mem_head(ptr))+DSIZE; 
  43. 	}
  44. 	char *pre_blkb(void *ptr){//找到前面块
  45. 		return (char*)ptr-get_size((void*)((char*)ptr-DSIZE))-DSIZE;
  46. 	}
  48. 	void *mem_sbrk(unsigned int inc); 
  49. 	void mm_init(); 
  50. 	void* extern_heap(unsigned int size); 
  51. 	void coalesce(void *ptr);
  52. 	void clearBlock(void *ptr); 
  53. 	void* find_fit(unsigned int size); 
  54. public:
  55. 	int	mem_errno; 
  56. 	DynamicMalloc(); 
  57. 	void* mm_malloc(unsigned int size);
  58. 	void  mm_free(void *ptr); 
  59. };  
  60. #endif 
  1. #include<stdio.h>
  2. #include<memory>
  3. #include<iostream>
  4. #include"DynamicMalloc.h"
  6. char * DynamicMalloc::heap_listp=NULL; 
  7. char * DynamicMalloc::mem_heap=NULL; 
  8. char * DynamicMalloc::mem_brk=NULL; 
  9. char * DynamicMalloc::mem_max_addr=NULL; 
  11. DynamicMalloc::DynamicMalloc(){
  12. 	if(mem_heap==NULL){
  13. 		mem_errno=NoFault; 
  14. 		mem_heap=(char*)malloc(WSIZE*MAX_HEAP*sizeof(char)); 
  15. 		if(mem_heap==NULL){
  16. 			mem_errno=OutofMemory; 
  17. 			std::cout<<"overflow"<<std::endl;
  18. 		}
  19. 		mem_brk=mem_heap; 
  20. 		mem_max_addr=mem_heap+WSIZE*MAX_HEAP*sizeof(char); 
  21. 		mm_init(); 
  22. 	}
  23. }
  25. void * DynamicMalloc::mem_sbrk(unsigned int inc){
  26. 	if(inc<0||(mem_heap+inc>mem_max_addr)){
  27. 		mem_errno=OutofMemory; 
  28. 		std::cout<<"memory overflow!"<<std::endl; 
  29. 		return NULL ; 
  30. 	}
  31. 	char *old_mem_brk=mem_brk; 
  32. 	mem_brk+=inc+DSIZE; //预留空间，用于头和尾
  33. 	return (void*)old_mem_brk; 
  34. }
  36. void DynamicMalloc::mm_init(){
  37. 	if((heap_listp=(char*)mem_sbrk(2*WSIZE))==NULL){
  38. 		return; 
  39. 	}
  40. 	put_data(heap_listp,pack(0,ALLOCED)); 
  41. 	put_data(heap_listp+WSIZE,pack(0,ALLOCED)); 
  42. 	put_data(heap_listp+2*WSIZE,pack(0,ALLOCED)); 
  43. 	put_data(heap_listp+3*WSIZE,pack(0,ALLOCED)); 
  44. 	heap_listp+=2*WSIZE; 
  45. 	extern_heap(CHUNKSIZE); 
  46. }
  48. void* DynamicMalloc::extern_heap(unsigned int size){
  49. 	
  50. 	int words=(size%2)? (size+1)*WSIZE:(size)*WSIZE; 
  51. 	char *bp=NULL; 
  52. 	bp=(char*)mem_sbrk(words); 
  53. 	put_data(mem_head(bp),pack(words,UNALLOCED)); //块头
  54. 	put_data(mem_ftrp(bp),pack(words,UNALLOCED)); //块脚 
  55. 	put_data(mem_ftrp(bp)+WSIZE,pack(0,ALLOCED)); //新的“堆脚”,也是结束的标志
  56. 	coalesce(bp); 
  57. 	return bp; 
  58. }
  60. void DynamicMalloc::clearBlock(void *ptr){
  61. 	char *clear_ptr=(char*)ptr; 
  62. 	for(int i=0;i<WSIZE; i++){
  63. 		*(clear_ptr+i)=0; 
  64. 	}
  65. }
  67. void DynamicMalloc::coalesce(void *ptr){
  68. 	bool preAlloced=ALLOCED; 
  69. 	bool	nxtAlloced=ALLOCED; 
  70. 	preAlloced=get_alloced(mem_head(pre_blkb(ptr))); //获得前一块的状态
  71. 	nxtAlloced=get_alloced(mem_head(next_blkb(ptr))); //获得下一块的状态
  72. 	if(preAlloced&&nxtAlloced){//前后两块都分配了
  73. 		return; 
  74. 	}else if(preAlloced&&!nxtAlloced){//前一块己分配，后一块没有
  75. 		unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(next_blkb(ptr)))+DSIZE; 	
  76. 		put_data(mem_head(ptr),pack(new_size,UNALLOCED));//设置新块头部
  77. 		put_data(mem_ftrp(ptr),pack(new_size,UNALLOCED)); //新块的脚
  78. 		//clearBlock(mem_ftrp(ptr)); 
  79. 		//clearBlock(mem_head(next_blkb(ptr))); //清理门户
  80. 	}else if(!preAlloced&&nxtAlloced){//前面的未分配，后面的分配了
  81. 		unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(pre_blkb(ptr)))+DSIZE; 
  82. 		put_data(mem_head(pre_blkb(ptr)),pack(new_size,UNALLOCED)); 
  83. 		put_data(mem_ftrp(ptr),pack(new_size,UNALLOCED)); 
  84. 		//clearBlock(mem_head(ptr)); 
  85. 		//clearBlock(mem_ftrp(pre_blkb(ptr))); 
  86. 	}else if(!preAlloced&&!nxtAlloced){//前后都未分配
  87. 		unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(pre_blkb(ptr)))+get_size(mem_head(next_blkb(ptr))); 
  88. 		put_data(mem_head(pre_blkb(ptr)), pack(new_size,UNALLOCED)); 
  89. 		put_data(mem_ftrp(next_blkb(ptr)),pack(new_size,UNALLOCED)); 
  90. 		//clearBlock(mem_head(ptr)); 
  91. 		//clearBlock(mem_ftrp(ptr)); 
  92. 		//clearBlock(mem_ftrp(pre_blkb(ptr))); 
  93. 		//clearBlock(mem_head(next_blkb(ptr))); //清理门户
  94. 	}
  95. }
  97. void* DynamicMalloc::mm_malloc(unsigned int size){
  98. 	unsigned int malloc_size=0; 
  99. 	void *reptr=NULL; 
  100. 	if(size==0){
  101. 		return NULL; 
  102. 	}
  103. 	if(size<=DSIZE){
  104. 		malloc_size=DSIZE; 
  105. 	}else{
  106. 		malloc_size=DSIZE*((size+DSIZE+DSIZE-1)/DSIZE); 
  107. 	}
  108. 	if((reptr=find_fit(malloc_size))!=NULL){
  109. 		return (void*)reptr; 
  110. 	}else{
  111. 		reptr=(void*)extern_heap(malloc_size); 
  112. 		put_data(mem_head(reptr),pack(malloc_size,ALLOCED)); 
  113. 		put_data(mem_ftrp(reptr),pack(malloc_size,ALLOCED)); 
  114. 		return reptr;
  115. 	}
  116. }
  118. void* DynamicMalloc::find_fit(unsigned int size){
  119. 	char *ptr=next_blkb(heap_listp); //heap_listp一直指向序言块
  120. 	std::cout<<get_size(mem_head(ptr))<<std::endl;
  121. 	std::cout<<get_alloced(mem_head(ptr))<<std::endl; 
  123. 	while(((get_size(mem_head(ptr))!=0)||(get_alloced(mem_head(ptr)))!=ALLOCED)){//从前往后 “首次匹配”
  124. 		std::cout<<get_size(mem_head(ptr))<<std::endl; 
  125. 		std::cout<<get_alloced(mem_head(ptr))<<std::endl; 
  126. 		if(((get_size(mem_head(ptr))>=size)&&(get_alloced(mem_head(ptr)))==UNALLOCED)){
  127. 			break;; 
  128. 		}
  129. 		ptr=next_blkb(ptr); 
  130. 	}
  131. 	if(get_alloced(mem_head(ptr))==ALLOCED&&get_size(mem_head(ptr))==0){//没有合适的空间
  132. 		mem_errno=NoRest; 
  133. 		return NULL; 
  134. 	}else{
  135. 		if(get_size(mem_head(ptr))>=size+MINCHUNK){
  136. 			unsigned int old_size=get_size(mem_head(ptr)); 
  137. 			put_data(mem_head(ptr),pack(size,ALLOCED)); //待分配块“头”
  138. 			put_data(mem_ftrp(ptr),pack(size,ALLOCED)); //待分配块“尾”
  139. 			put_data(mem_head(next_blkb(ptr)),pack(old_size-size-2*WSIZE,UNALLOCED)); 
  140. 			put_data(mem_ftrp(next_blkb(ptr)),pack(old_size-size-2*WSIZE,UNALLOCED));
  141. 			return ptr; 
  142. 		}else{
  143. 			return ptr; 
  144. 		}	
  145. 	}
  146. }
  148. void DynamicMalloc::mm_free(void *ptr){
  150. 	put_data(mem_head(ptr),pack(get_size(mem_head(ptr)),UNALLOCED)); 
  151. 	put_data(mem_ftrp(ptr),pack(get_size(mem_head(ptr)),UNALLOCED)); 
  152. 	coalesce(ptr);
  153. }
    
  1. #include "DynamicMalloc.h"
  2. #include<iostream>
  3. int main(){
  4. 	DynamicMalloc dynamicMalloc; 
  5. 	char *ptr=(char*)dynamicMalloc.mm_malloc(10); 
  6. 	for(int i=0;i<10;i++){
  7. 		*(ptr+i)='a'; 
  8. 	}
  9. 	for(int i=0;i<10;i++){
  10. 		std::cout<<*(ptr+i)<<std::endl; 
  11. 	}
  12. 	
  13. 	char* p=(char*)dynamicMalloc.mm_malloc(20); 
  14. 	for(int i=0;i<20;i++){
  15. 		*(p+i)='a'; 
  16. 	}
  17. 	for(int i=0;i<20;i++){
  18. 		std::cout<<*(p+i)<<std::endl; 
  19. 	}
  20. 	char* pp=(char*)dynamicMalloc.mm_malloc(300); 
  21. 	dynamicMalloc.mm_free(p); 
  22. }


对于空相邻空闲块的管理策略：
    


也就是这部分的代码：
  1. void DynamicMalloc::coalesce(void *ptr){
  2. 	bool preAlloced=ALLOCED; 
  3. 	bool	nxtAlloced=ALLOCED; 
  4. 	preAlloced=get_alloced(mem_head(pre_blkb(ptr))); //获得前一块的状态
  5. 	nxtAlloced=get_alloced(mem_head(next_blkb(ptr))); //获得下一块的状态
  6. 	if(preAlloced&&nxtAlloced){//前后两块都分配了
  7. 		return; 
  8. 	}else if(preAlloced&&!nxtAlloced){//前一块己分配，后一块没有
  9. 		unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(next_blkb(ptr)))+DSIZE; 	
  10. 		put_data(mem_head(ptr),pack(new_size,UNALLOCED));//设置新块头部
  11. 		put_data(mem_ftrp(ptr),pack(new_size,UNALLOCED)); //新块的脚
  12. 		//clearBlock(mem_ftrp(ptr)); 
  13. 		//clearBlock(mem_head(next_blkb(ptr))); //清理门户
  14. 	}else if(!preAlloced&&nxtAlloced){//前面的未分配，后面的分配了
  15. 		unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(pre_blkb(ptr)))+DSIZE; 
  16. 		put_data(mem_head(pre_blkb(ptr)),pack(new_size,UNALLOCED)); 
  17. 		put_data(mem_ftrp(ptr),pack(new_size,UNALLOCED)); 
  18. 		//clearBlock(mem_head(ptr)); 
  19. 		//clearBlock(mem_ftrp(pre_blkb(ptr))); 
  20. 	}else if(!preAlloced&&!nxtAlloced){//前后都未分配
  21. 		unsigned int new_size=get_size(mem_head(ptr))+get_size(mem_head(pre_blkb(ptr)))+get_size(mem_head(next_blkb(ptr))); 
  22. 		put_data(mem_head(pre_blkb(ptr)), pack(new_size,UNALLOCED)); 
  23. 		put_data(mem_ftrp(next_blkb(ptr)),pack(new_size,UNALLOCED)); 
  24. 		//clearBlock(mem_head(ptr)); 
  25. 		//clearBlock(mem_ftrp(ptr)); 
  26. 		//clearBlock(mem_ftrp(pre_blkb(ptr))); 
  27. 		//clearBlock(mem_head(next_blkb(ptr))); //清理门户
  28. 	}
  29. }


这是开始的一些字段初使化：
  1.     static char* mem_heap;		//指向堆首地址
  2. 	static char* mem_brk;		//指向目前分配的“堆”的最后一个字的下一个
  3. 	static char* mem_max_addr;	//一直指向最大所能分配的地址，“堆大小”
  4. 	static char* heap_listp;		//一直指向序言块












【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yml435/p/4690933.html