STL内存管理的C实现

2022-01-08 01:01:54

  1. //STL 内存管理器的C实现

  3. #include stdio.h>
  4. #include stdlib.h>

  6. #define __ALIGN 8    //小型区块上调边界
  7. #define __MAX_BYTES 128    //小型区块大小的上限
  8. #define __NFREELISTS (__ALIGN/__MAX_BYTES)    //free-lists的个数

  10. typedef union obj{
  11.     union obj *free_list_link;
  12.     char client_data[1];
  13. }obj;
  14. obj *free_list[__NFREELISTS];
  15. char *start_free;    //mempool开始位置
  16. char *end_free;    //mempool结束位置
  17. size_t heapsize;

  19. size_t ROUND_UP(size_t bytes);
  20. size_t FREELIST_INDEX(size_t bytes);
  21. void *stl_malloc(size_t nbytes);
  22. void stl_free(void *p, size_t nbytes);
  23. void *refill(size_t n);
  24. char *chunk_alloc(size_t bytes, size_t *nobjs);


  27. int main(){
  28.     int len= 65;
  29.     void *ptr = stl_malloc(len);
  30.     printf("%p\n", ptr);
  31.     stl_free(ptr, len);
  32.     return 0;
  33. }

  35. //将bytes上调到__ALIGN的倍数
  36. size_t ROUND_UP(size_t bytes){
  37.     return ((bytes + __ALIGN - 1) & ~(__ALIGN - 1));
  38. }
  39. //返回bytes所对应的freelist索引号
  40. size_t FREELIST_INDEX(size_t bytes){
  41.     return ((bytes + __ALIGN - 1) / __ALIGN - 1);
  42. }
  43. void *stl_malloc(size_t nbytes){
  44.     if(nbytes > 128){
  45.         return malloc(nbytes);
  46.     }
  47.     obj **my_free_list;
  48.     obj *result;
  49.     my_free_list = free_list + FREELIST_INDEX(nbytes);
  50.     result = *my_free_list;
  51.     if(result == NULL){
  52.         void *r = refill(ROUND_UP(nbytes));
  53.         return r;
  54.     }
  55.     //取出空闲块
  56.     *my_free_list = result->free_list_link;
  57.     return result;
  58. }
  59. void stl_free(void *p, size_t nbytes){
  60.     obj *q = (obj *)p;
  61.     obj **my_free_list;
  62.     if(nbytes > (size_t)__MAX_BYTES){
  63.         free(p);
  64.         return;
  65.     }
  66.     my_free_list = free_list + FREELIST_INDEX(nbytes);
  67.     q->free_list_link = *my_free_list;
  68.     *my_free_list = q;
  69. }
  70. void *refill(size_t n){
  71.     //默认从内存池取得20个块，多个块构成一个chunk
  72.     size_t nobjs = 20;    //值-结果参数
  73.     char *chunk = chunk_alloc(n, &nobjs);    
  74.     if(!chunk){
  75.         return NULL;
  76.     }
  77.     obj **my_free_list;
  78.     obj *result, *cur_obj, *next_obj;
  79.     int i;
  80.     //内存池空间告急仅返回一个块，则直接返回给用户
  81.     if(nobjs == 1){
  82.         return chunk;
  83.     }
  84.     //否则准备向free_list中纳入新的节点
  85.     my_free_list = free_list + FREELIST_INDEX(n);
  86.     //以下在chunk的连续空间上建立free_list
  87.     result = (obj *)chunk;    //此块返回给用户
  88.     *my_free_list = next_obj = (obj *)(chunk + n);
  89.     for(i = 1; ; i++){
  90.         cur_obj = next_obj;
  91.         next_obj = (obj *)((char *)next_obj + n);
  92.         if(nobjs - 1 == i){
  93.             cur_obj->free_list_link = NULL;
  94.             break;
  95.         }else{
  96.             cur_obj->free_list_link = next_obj;    
  97.         }
  98.     }
  99.     return result;
  100. }
  101. //从内存池取连续的块空间
  102. char *chunk_alloc(size_t bytes, size_t *nobjs){
  103.     char *result;
  104.     size_t total_bytes = bytes * (*nobjs);    //要求的字节数
  105.     size_t bytes_left = end_free - start_free;    //

  107.     //内存池空间宽裕
  108.     if(bytes_left >= total_bytes){
  109.         result = start_free;
  110.         start_free += total_bytes;
  111.         return result;
  112.     }else if(bytes_left >= bytes){
  113.         //不够分配全部的，但是还可以分配一个或多个块
  114.         *nobjs = bytes_left/bytes;
  115.         total_bytes = *nobjs * bytes;
  116.         result = start_free;
  117.         start_free += total_bytes;
  118.         return result;
  119.     }else{
  120.         //内存池黔驴技穷了，连一个块的空间都没有了
  121.         size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heapsize >> 4);
  122.         if(bytes_left > 0){
  123.             //内存池中还有一些零头，先配给适当的free-list
  124.             obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);
  125.             ((obj *)start_free)->free_list_link = *my_free_list;
  126.             *my_free_list = (obj *)start_free;
  127.         }
  128.         start_free = (char *)malloc(bytes_to_get);
  129.         if(start_free == NULL){
  130.             //看看更大块的free_list有无可用块
  131.             int i;
  132.             obj **my_free_list, *p;
  133.             for(i = bytes; i = __MAX_BYTES; i += __ALIGN){
  134.                 my_free_list = free_list + FREELIST_INDEX(i);
  135.                 p = *my_free_list;
  136.                 if(p){
  137.                     *my_free_list = p->free_list_link;
  138.                     start_free = (char *)p;
  139.                     end_free = start_free + i;
  140.                     //递归调用自己，按新的状态重新分配，并修正nobjs;
  141.                     return chunk_alloc(bytes, nobjs);
  142.                 }
  143.             }
  144.             //实在没有空间了
  145.             end_free = 0;
  146.             return NULL;
  147.         }
  148.         heapsize += bytes_to_get;
  149.         end_free = start_free + bytes_to_get;
  150.         return chunk_alloc(bytes, nobjs);
  151.     }
  152.     
  153. }
上一篇：Android之拖动条(SeekBar和RatingBar)的功能和用法


下一篇：Learning Disentangled Representations for Recommendation | NIPS 2019 论文解读