请编写实现malloc()内存分配函数功能一样的代码。

#include <unistd.h>
 #include <stdlib.h> 
typedef long Align; //定义块首对其的类型：长整型
  union header {   //块首  
struct {  union header *next;   
  //指向下一空闲块的指针 unsigned int size;    
 //空闲块的大小 } s; Align x;    //对齐 };  
typedef union header Header; 
 #define NALLOC 1024 //请求的最小单位数，设每页大小为1KB 
static Header* Moresys(unsigned int nu);   //向系统申请一块内存
 void* Malloc(unsigned int nbytes);   //从用户管理区申请内存  
void Free(void *ap);    //释放内存，放入到用户管理区 
static Header base;   //定义空闲链头 
static Header *free_list = NULL;   //空闲链的起始查询指针 //用户管理区内存分配函数 void* Malloc(unsigned int nbytes) { Header *p, *prev; unsigned int nunits; //将申请的字节数nbytes转换成nunits个块首单位，多计算一个作为管理块首 nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1; if ((prev = free_list) == NULL) {   //如果无空闲链，定义空闲链 base.s.next = free_list = prev = &base; base.s.size = 1; //这里与实验提示中有点不同，这里的size包括 //了块首，实验提示中不包括块首，其实都可以， //只要在计算时注意就可以了 } for (p = prev->s.next; ; p = p->s.next, prev = p) {  //遍历空闲链，查找合适空闲块 if (p->s.size >= nunits) {    //空闲块够大 if (p->s.size <= (nunits + 1))   //正好或多一个（多一个的原因大家 //可以想一想） prev->s.next = p->s.next; else {    //偏大，切出需要的一块 p->s.size -= nunits; p += p->s.size; //被分配块的起始地址 p->s.size = nunits;    //填写被分配块大小 } free_list = prev;    //记录前一空块的地址 return(void *)(p+1);   //跳过管理块首，返回 } if(p == free_list) if((p = Moresys(nunits)) == NULL)    //无合适块，向系统申请 return NULL; } } //向系统申请内存空间 static Header* Moresys(unsigned int nu) { char *cp; Header *up; if(nu<NALLOC) nu = NALLOC;    //向系统申请的最小量 cp = sbrk(nu * sizeof(Header));  printf("sbrk: %X -- %X\n", cp, cp + nu * sizeof(Header)); //调试用 if(cp == (char *) -1) return NULL;   //无空闲页面，返回空地址 up = (Header *)cp; //强制转换成header结构 up->s.size = nu; Free(up + 1);   //将申请到的空闲块链如用户空闲链，指向第二 //个header指针（free函数的要求） return free_list;    //返回free_list指针 } //回收内存到空闲链上 void Free(void *ap) { Header *bp, *p; bp = (Header *)ap - 1; //指向块首 for(p = free_list; !(bp>p && bp<p->s.next); p = p->s.next)   //按地址定位空闲块在链表 //中的位置 if(p>=p->s.next && (bp>p || bp<p->s.next)) break;   //空闲块在两端 if(bp + bp->s.size == p->s.next) {  //看空闲块是否与已有的块相邻，相邻就合并 bp->s.size += p->s.next->s.size; bp->s.next = p->s.next->s.next; } else bp->s.next = p->s.next; if(p + p->s.size == bp) { p->s.size += bp->s.size; p->s.next = bp->s.next; } else  p->s.next = bp; free_list = p; } //打印内存分配结果函数 void print_list(void) { Header *p; int i = 0; printf("base: %X, base.next: %X, base.next.next: %X, free: %X\n",  &base, base.s.next, base.s.next->s.next, free_list); for (p = base.s.next; p != &base; p = p->s.next) { i++; printf("block %d, size=%d", i, p->s.size); if(p > free_list) printf(" It is not searched after this point. \n"); else printf(" It is a searched free block!\n"); } } //测试编写的malloc函数 main() { char *p[200]; int i; for(i = 0; i < 20; i++ ) { p[i] = (char *)Malloc(8); printf("malloc %d, %X\n", i , p[i]); print_list(); } for (i =0; i < 20; i++) 
{ Free(p[i]); printf("free %d\n", i); print_list(); } return; }

#include <unistd.h> #include <stdlib.h> typedef long Align;	//定义块首对其的类型：长整型  union header {	//块首  struct {  union header *next; 	//指向下一空闲块的指针 unsigned int size;  	//空闲块的大小 } s; Align x;	//对齐 };  typedef union header Header;  #define NALLOC 1024	//请求的最小单位数，设每页大小为1KB static Header* Moresys(unsigned int nu);	//向系统申请一块内存 void* Malloc(unsigned int nbytes);	//从用户管理区申请内存  void Free(void *ap);	//释放内存，放入到用户管理区 static Header base;	//定义空闲链头 static Header *free_list = NULL;	//空闲链的起始查询指针 //用户管理区内存分配函数 void* Malloc(unsigned int nbytes) { Header *p, *prev; unsigned int nunits; //将申请的字节数nbytes转换成nunits个块首单位，多计算一个作为管理块首 nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1; if ((prev = free_list) == NULL) {	//如果无空闲链，定义空闲链 base.s.next = free_list = prev = &base; base.s.size = 1;	//这里与实验提示中有点不同，这里的size包括 //了块首，实验提示中不包括块首，其实都可以， //只要在计算时注意就可以了 } for (p = prev->s.next; ; p = p->s.next, prev = p) {	//遍历空闲链，查找合适空闲块 if (p->s.size >= nunits) {	//空闲块够大 if (p->s.size <= (nunits + 1))	//正好或多一个（多一个的原因大家 //可以想一想） prev->s.next = p->s.next; else {	//偏大，切出需要的一块 p->s.size -= nunits; p += p->s.size;	//被分配块的起始地址 p->s.size = nunits;	//填写被分配块大小 } free_list = prev;	//记录前一空块的地址 return(void *)(p+1);	//跳过管理块首，返回 } if(p == free_list) if((p = Moresys(nunits)) == NULL)	//无合适块，向系统申请 return NULL; } } //向系统申请内存空间 static Header* Moresys(unsigned int nu) { char *cp; Header *up; if(nu<NALLOC) nu = NALLOC;	//向系统申请的最小量 cp = sbrk(nu * sizeof(Header));  printf("sbrk: %X -- %X\n", cp, cp + nu * sizeof(Header));	//调试用 if(cp == (char *) -1) return NULL;	//无空闲页面，返回空地址 up = (Header *)cp;	//强制转换成header结构 up->s.size = nu; Free(up + 1);	//将申请到的空闲块链如用户空闲链，指向第二 //个header指针（free函数的要求） return free_list;	//返回free_list指针 } //回收内存到空闲链上 void Free(void *ap) { Header *bp, *p; bp = (Header *)ap - 1;	//指向块首 for(p = free_list; !(bp>p && bp<p->s.next); p = p->s.next)	//按地址定位空闲块在链表 //中的位置 if(p>=p->s.next && (bp>p || bp<p->s.next)) break;	//空闲块在两端 if(bp + bp->s.size == p->s.next) {	//看空闲块是否与已有的块相邻，相邻就合并 bp->s.size += p->s.next->s.size; bp->s.next = p->s.next->s.next; } else bp->s.next = p->s.next; if(p + p->s.size == bp) { p->s.size += bp->s.size; p->s.next = bp->s.next; } else  p->s.next = bp; free_list = p; } //打印内存分配结果函数 void print_list(void) { Header *p; int i = 0; printf("base: %X, base.next: %X, base.next.next: %X, free: %X\n",  &base, base.s.next, base.s.next->s.next, free_list); for (p = base.s.next; p != &base; p = p->s.next) { i++; printf("block %d, size=%d", i, p->s.size); if(p > free_list) printf(" It is not searched after this point. \n"); else printf(" It is a searched free block!\n"); } } //测试编写的malloc函数 main() { char *p[200]; int i; for(i = 0; i < 20; i++ ) { p[i] = (char *)Malloc(8); printf("malloc %d, %X\n", i , p[i]); print_list(); } for (i =0; i < 20; i++) { Free(p[i]); printf("free %d\n", i); print_list(); } return; }

很早以前写过的... #include <stdio.h> #include "unistd.h" #define BLOCK_SIZE 40 typedef struct s_block *t_block; void *first_block=NULL;
t_block find_block(t_block *last,size_t size);
t_block extend_heap(t_block last, size_t s); void split_block(t_block b,size_t s);
size_t align8(size_t s); void *malloc(size_t size); void *calloc(size_t number, size_t size);
t_block get_block(void *p); int valid_addr(void *p);
t_block fusion(t_block b); void free(void *p); void copy_block(t_block src,t_block dst); void *realloc(void *p,size_t size); struct s_block{
    size_t size;//数据区大小 t_block prev;//指向上个块的指针 t_block next;//指向下个块的指针 int free;//判断是否是空闲块 int padding;//填充4字节，为了迎合结构体对齐，保证meta块长度为8的倍数 void *ptr;//Magic pointer,指向data //虚拟字段这个是真的巧妙！每个块的s_block后面都是数据区，但是这个data[]不算作s_block的内容 //不计作s_block的长度，所以在访问s_block的data字段时实际上访问的是数据区的第一个字节 char data[1];
}; int main(void){ return 0;
}
t_block find_block(t_block *last,size_t size){
    t_block b=first_block; while (b && !(b->free && b->size >= size)) {
        *last=b;//last用来表示最后一块可用的内存块(可能是刚刚被释放过之后的一个块) b=b->next;
    } return b;
}
t_block extend_heap(t_block last, size_t s){
    t_block b;//强制把新申请出来的内存看做是s_block类型的 b = sbrk(0); if (sbrk(BLOCK_SIZE + s) == (void *) -1) { return NULL;
    }
    b->size=s;
    b->next=NULL;
    b->ptr = &(b->data);//data是一个数组所以其实不用加& if(last){
        last->next=b;
    }
    b->free=0; return b;
} void split_block(t_block b,size_t s){
    t_block new; new=b->data+s; new->size = b->size - s - BLOCK_SIZE; new->next = b->next; new->free=1;
    b->size=s;
    b->next = new;
}
size_t align8(size_t s){ if (s & 0x7 == 0) {//满足该条件的s是可以被8整除的 return s;
    } //这样可以得到一个大于s且能够被8整除的最小的数 return ((s>>3)+1)<<3;
} void *malloc(size_t size){
    t_block b,last;
    size_t s = align8(size);//地址对齐 if (first_block) {
        last=first_block;// b = find_block(&last, s); if(b){ if ((b->size) >= (BLOCK_SIZE + 8)) {
                split_block(b, s);
            }
            b->free=0;
        } else {
            b = extend_heap(last, s); if (!b) { return NULL;
            }
        }
    }else{
        b = extend_heap(NULL, s); if(!b) { return NULL;
        }
        first_block=b;
    } return b->data;
} void *calloc(size_t number, size_t size){
    size_t *new;
    size_t s8; new = malloc(number * size); if (new) {
        s8=align8((number*size))>>3; for (int i = 0; i < s8; i++) { new[i]=0;
        }
    } return new;;
}
t_block get_block(void *p){ char *tmp;
    tmp=p; return (p = tmp -= BLOCK_SIZE);
} int valid_addr(void *p){ if (first_block) { if(p<sbrk(0)&&p>first_block){ return p==(get_block(p))->ptr;//？？？？？？ }
    } return 0;
}
t_block fusion(t_block b){ if (b->next && b->next->free) {
        b->size+=BLOCK_SIZE+b->next->size;
        b->next = b->next->next; if (b->next) {
            b->next->prev=b;
        }
    } return b;
} void free(void *p){//传进来的p实际上是那个block的数据区 t_block b; if(valid_addr(p)){
        b = get_block(p);//b此时指向那块block的起始地址 b->free=1;//只是标记为空闲，实际上data区还是有数据的 if (b->prev && b->prev->free) {
            b=fusion(b->prev);
        } if (b->next) {//检查当前block是否还有后继，即检查是否是最后一个block fusion(b);//如果有则尝试合并 }else{//如果没有后继则先检查是否是第一个block if (b->prev) {//检查是否有前驱，如果有前驱则表示该block不是第一个 b->prev->next = NULL;
            }else{//如果没有前驱那么该block既是第一个也是最后一个block first_block = NULL;//又回到了任何一次malloc之前 }
            brk(b);//用brk在heap上进行回退 }
    }
} void copy_block(t_block src,t_block dst){
    size_t *sdata, *ddata;
    sdata=src->ptr;
    ddata=dst->ptr; for (size_t i = 0;(i*8)<src->size&&(i*8)<dst->size; i++) {
        ddata[i] = sdata[i];
    }
} void *realloc(void *p,size_t size){
    size_t s;
    t_block b, new; void *newp; if(!p){ return malloc(size);
    } if(valid_addr(p)){
        s = align8(size);
        b = get_block(p);//p是数据区起始,此时b指向那整块内存的起始 if(b->size>=s){//如果这个块能直接放下原数据大小则对数据什么也不做 if(b->size-s>=(BLOCK_SIZE+8)){//并顺手检查一下是否可以切割内存 split_block(b, s);
            }
        }else{//如果放不下则检查一下是否可以合并，允许合并的条件的最后一条是合并之后能放下数据 if (b->next && b->next->free &&
                    b->next->size + b->size+BLOCK_SIZE >= s) {
                fusion(b); //如果可以合并则在合并完之后检查是否可以进行分裂 if(b->size-s>=(BLOCK_SIZE+8)){
                    split_block(b, s);
                }
            }else{//如果既放不下数据也不符合合并的条件 //那么就malloc一块新内存 newp = malloc(s); if(!newp){ return NULL;
                } new = get_block(newp);
                copy_block(b, new); free(p); return newp;
            }
        } return (p);
    } return NULL;
}