内存分配算法-（首次分配法和最佳分配法）
/* implement a memory allocation scheme by using algorithms first-fit, next-fit, and best-fit * freelist为空闲区链表的头，它的下一个节点才指向空闲缓冲区 * freelist是按首地址来排序的，而不是按size来排序。按首地址排序便于相邻空闲内存合并；按size大小来排序，便于分配内存 */#include<stdio.h>#include<stdlib.h>#define N 100typedef enum {FALSE, TRUE} bool;typedef struct node{char *ptr; //start addr 指向mem处开始的地址int size; //size of the free blockstruct node *next; //next free block}node;char mem[N]; //total memory poolnode freelist; //head of free list, no value/* init freelist to contain the whole mem */void init(){node *ptr = (node *)malloc(sizeof(node));ptr->ptr = mem;ptr->size = N;ptr->next = NULL;freelist.next = ptr;}/* remove a node ptr from the list whose previous node is prev */void removenode(node *ptr, node *prev){prev->next = ptr->next;free(ptr);}/* 首次适配法：从自由空闲区中选取第一个合适空闲区来分配 * 返回分配内存区首地址 */char *firstfit(int size) {node *ptr, *prev;char *memptr;for(prev=&freelist, ptr=prev->next; ptr; prev=ptr, ptr=ptr->next)if(ptr->size > size){memptr = ptr->ptr;ptr->size -= size; //从空闲区去掉size空间ptr->ptr += size; //空闲区首地址往后移size个单位return memptr; //返回申请到的空闲区 首地址}else if(ptr->size = size){memptr = ptr->ptr;removenode(ptr, prev);return memptr;}return NULL; //没有足够长的空闲内存}/* 最佳适配法：找到大小与size最接近的空闲区来分配 */char *bestfit(int size){node *ptr, *prev;char *memptr;int minwaste = N+1;node *minptr = NULL, *minprev;for(prev=&freelist, ptr=prev->next; ptr; prev=ptr, ptr=ptr->next)if(ptr->size >= size && ptr->size-size < minwaste){minwaste = ptr->size - size;minptr = ptr;minprev = prev;}if(minptr == NULL)//没有找到return NULL;ptr = minptr;prev = minptr;if(ptr->size > size){memptr = ptr->ptr;ptr->size -= size;ptr->ptr += size;return memptr;}else if(ptr->size == size){memptr = ptr->ptr;removenode(ptr, prev);return memptr;}return NULL;}/* add memptr of size to freelist, remember that block ptrs are stored on mem addr */void addtofreelist(char *memptr, int size){node *prev, *ptr, *newptr;for(prev=&freelist, ptr=prev->next; ptr && ptr->ptr < memptr; prev=ptr, ptr=ptr->next);newptr = (node *)malloc(sizeof(node));newptr->ptr = memptr;newptr->size = size;newptr->next = ptr;prev->next = newptr;}/* combine adj blocks of list if necessary */void coalesce(){node *prev, *ptr;for(prev=&freelist, ptr=prev->next; ptr; prev=ptr, ptr=ptr->next)if(prev != &freelist && prev->ptr+prev->size == ptr->ptr){prev->next = ptr->next;free(ptr);ptr = prev;}}/* prt: sizeof(int) contains size of the pool allocated * 返回分配的空间首地址(不包括最前面的长度的4个字节) */char *memalloc(int size){char *ptr = firstfit(size + sizeof(int)); //此处选择分配算法printf("allocating %d using firstfit...\n", size);if(ptr == NULL)return NULL;*(int *)ptr = size; //分配的空闲内存区前面几个字节用于存放分配数return ptr+sizeof(int);}void memfree(char *ptr){int size = *(int *)(ptr-sizeof(int));//找到已分配的空闲区大小(空闲区的前4个字节)printf("freeing %d...\n", size);addtofreelist(ptr-sizeof(int), size+sizeof(int));coalesce();}void printfreelist(){node *ptr;printf("\t");for(ptr=freelist.next; ptr; ptr=ptr->next)printf("{%u %d}", ptr->ptr, ptr->size);putchar('\n');}main(){char *p1, *p2, *p3, *p4, *p5;init();printfreelist();p1 = memalloc(10);//note：分配10个字节，但其前面还有4个字节用于指示长度的，所以共用了14字节printfreelist();p2 = memalloc(15);printfreelist();p3 = memalloc(23);printfreelist();p4 = memalloc(3);printfreelist();p5 = memalloc(8);printfreelist();memfree(p1);printfreelist();memfree(p5);printfreelist();memfree(p3);printfreelist();p1 = memalloc(23);printfreelist();p1 = memalloc(23);printfreelist();memfree(p2);printfreelist();p1 = memalloc(3);printfreelist();memfree(p4);printfreelist();p2 = memalloc(1);printfreelist();memfree(p1);printfreelist();memfree(p2);printfreelist();return 0;}