C 工具库5：first fit pool-白红宇

C 工具库5：first fit pool

阅读量：6415 次

发布时间：2019-06-23

本文共 7448 字，大约阅读时间需要 24 分钟。

本篇介绍通用内存分配工具的另一个组件,first fit momery pool,也就是首次适应内存分配器。

相对于best fit 算法，通常来说first fit具有更好的平均性能，具体分析可参考kunth计算机程序设计

第一卷2.5的讨论.

我的通用内存分配器准备组合使用fix obj pool和first fit pool.fix obj pool用于处理1-1024字节的小内存请求.

这里分配的内存是对齐到4字节的.而对于1-1024字节以外的大内存块请求，将交给

first fit pool处理.

为了加快free时的处理效率，将对fix obj pool做一个小处理，具体将在下篇通用内存分配器中介绍.

下面贴出first fit 的代码

first_fit.h

#ifndef _FIRST_FIT_H #define _FIRST_FIT_H /* * 首次适应算法,添加tag,避免Free时的搜索,TAOCP动态内存分配算法C */ struct first_fit_pool; extern struct first_fit_pool* first_fit_create(unsigned int size); extern void first_fit_destroy(struct first_fit_pool **pool); extern void *first_fit_alloc(struct first_fit_pool *pool,int size); extern void first_fit_dealloc(struct first_fit_pool *pool,void *ptr); extern unsigned int first_fit_get_free_size(struct first_fit_pool *_pool); #endif

first_fit.c

#include "first_fit.h" #include 
     
       #include 
      
        #include 
       
         struct first_fit_chunk {
   //状态1为保留,0为自由     int tag;               //当前块的状态     unsigned int size;     //当前块的大小     union{
   struct{
   struct first_fit_chunk *next;//下一个空闲块             struct first_fit_chunk *pre; //前一个空闲块         }; char buf[1];     }; }; struct first_fit_pool {
   struct first_fit_chunk ava_head;     unsigned int pool_size; char *begin; char *end; char buf[1]; }; #define FREE_TAG 0XFEDCBA98 #define CHUNK_HEAD 8 #define RESERVESIZE (sizeof(struct first_fit_chunk) + CHUNK_HEAD + 4) inline struct first_fit_chunk *GetPreChunk(struct first_fit_chunk *_chunk) {
   int *tmp = (int*)_chunk - 2;     unsigned int presize = (unsigned int)tmp[1]; struct first_fit_chunk *pre = (struct first_fit_chunk*)((char*)_chunk - presize - CHUNK_HEAD); return pre; } inline struct first_fit_chunk *GetNextChunk(struct first_fit_chunk *_chunk) {
   struct first_fit_chunk *next = (struct first_fit_chunk*)&_chunk->buf[_chunk->size]; return next; } inline void SetEndSize(struct first_fit_chunk *_chunk) {
       unsigned int size = _chunk->size;     unsigned int *tmp = (unsigned int*)&_chunk->buf[size];     tmp -= 1;     *tmp = size; } inline void SetEndTag(struct first_fit_chunk *_chunk) {
       unsigned int size = _chunk->size; int tag = _chunk->tag; int *tmp = (int*)&_chunk->buf[size];     tmp -= 2;     *tmp = tag; } inline int GetPreChunkTag(struct first_fit_chunk *_chunk) {
   int *tmp = (int*)_chunk - 2; return tmp[0]; } inline inline int GetNextChunkTag(struct first_fit_chunk *_chunk) {
   struct first_fit_chunk *next = GetNextChunk(_chunk); return next->tag; } struct first_fit_pool* first_fit_create(unsigned int size) {
   struct first_fit_pool *pool = malloc(sizeof(*pool)+size-1); if(pool)     {
           pool->pool_size = size;         pool->begin = pool->buf;         pool->end = &pool->buf[size]; struct first_fit_chunk *first_chunk = (struct first_fit_chunk*)pool->buf;         first_chunk->tag = FREE_TAG;         first_chunk->size = size-CHUNK_HEAD;         first_chunk->next = first_chunk->pre = &pool->ava_head;         SetEndTag(first_chunk);         SetEndSize(first_chunk);         pool->ava_head.next = pool->ava_head.pre = first_chunk;     } return pool; } void first_fit_destroy(struct first_fit_pool **pool) {
       assert(pool);     assert(*pool);     free(*pool);     *pool = 0; } void *first_fit_alloc(struct first_fit_pool *pool,int size) {
       assert(pool); if(size <= 0) return 0;     unsigned int alloc_size = (unsigned int)size; struct first_fit_chunk *cur = pool->ava_head.next; void *addr = 0; while(cur != &pool->ava_head)     {
   if(cur->size >= alloc_size)         {
               cur->tag = 1;             addr = (void*)cur->buf;             unsigned int size_remain = cur->size - alloc_size; if(size_remain >= RESERVESIZE)             {
   //拆分                 struct first_fit_chunk *other = (struct first_fit_chunk *)&cur->buf[alloc_size];                 other->size = size_remain - CHUNK_HEAD;                 other->tag = FREE_TAG;                 SetEndSize(other);                 SetEndTag(other);                 cur->size = alloc_size;                                cur->pre->next = other;                 cur->next->pre = other;                 other->next = cur->next;                 other->pre = cur->pre;             } else             {
   //从ava中移除cur                 cur->pre->next = cur->next;                 cur->next->pre = cur->pre;             } break;         }                cur = cur->next;     } return addr; } void first_fit_dealloc(struct first_fit_pool *pool,void *ptr) {
       assert(pool); if(!ptr) return; char *_ptr = (char*)ptr; struct first_fit_chunk *P0 = (struct first_fit_chunk *)(_ptr - CHUNK_HEAD);     P0->next = P0->pre = 0; if((char*)P0 < pool->begin || &P0->buf[P0->size] > pool->end) return;//不是pool分配出去的                 struct first_fit_chunk *P = 0; if(GetPreChunkTag(P0) == FREE_TAG)     {
           P = GetPreChunk(P0); //检查前置块的首地址是否合法         if((char*)P >= pool->begin)         {
   //C2 //将P从链表中脱离             struct first_fit_chunk *P1 = P->next; struct first_fit_chunk *P2 = P->pre;             P1->pre = P2;             P2->next = P1;                //P0,P合并             P->size += (P0->size + CHUNK_HEAD);             P0 = P;             printf("合并前块\n");         }     }    if(GetNextChunkTag(P0) == FREE_TAG)     {
           P = GetNextChunk(P0); //检查后续块的尾地址是否合法         if(&P->buf[P->size] <= pool->end)         {
   //C4 //将P从链表中脱离             struct first_fit_chunk *P1 = P->next; struct first_fit_chunk *P2 = P->pre;             P1->pre = P2;             P2->next = P1; //P0,P合并             P0->size += (P->size + CHUNK_HEAD);             printf("合并后块\n");                    }     }    //将P0插入可用链表首部     P0->next = pool->ava_head.next;     P0->pre = &pool->ava_head;     pool->ava_head.next->pre = P0;     pool->ava_head.next = P0;     P0->tag = FREE_TAG;     SetEndSize(P0);     SetEndTag(P0); } unsigned int first_fit_get_free_size(struct first_fit_pool *_pool) {
       assert(_pool); struct first_fit_chunk *cur = _pool->ava_head.next;     unsigned total_size = 0; while(cur != &_pool->ava_head)     {
           total_size += (cur->size + CHUNK_HEAD);         cur = cur->next;         printf("do here\n");     } return total_size; }

test.c

#include "first_fit.h" #include 
     
       #include 
      
        #include 
       
         int main() {
       srand(time(0)); struct first_fit_pool *pool = first_fit_create(1024); void *ptr1 = first_fit_alloc(pool,50); void *ptr2 = first_fit_alloc(pool,50); void *ptr3 = first_fit_alloc(pool,50); void *ptr4 = first_fit_alloc(pool,50); void *ptr5 = first_fit_alloc(pool,50); void *ptr6 = first_fit_alloc(pool,50); void *ptr7 = first_fit_alloc(pool,50); void *ptr8 = first_fit_alloc(pool,50); void *ptr9 = first_fit_alloc(pool,50); void *ptr10 = first_fit_alloc(pool,50);     printf("%d\n",first_fit_get_free_size(pool)); void *array[10] = {ptr1,ptr2,ptr3,ptr4,ptr5,ptr6,ptr7,ptr8,ptr9,ptr10}; int size = 10; int i = 0; int indexs[10] = {
   0,1,2,3,4,5,6,7,8,9}; int tmp[10]; for( ; i < 10; ++i)     {
   int index = rand()%size;         tmp[i] = indexs[index];         indexs[index]= indexs[size-1];         --size;     } for(i = 0; i < 10; ++i)     {
           printf("%d\n",i);         first_fit_dealloc(pool,array[tmp[i]]); //Free(pool,array[i]);     }     printf("%d\n",first_fit_get_free_size(pool));     first_fit_destroy(&pool);    return 0; }