首页 > 代码库 > stl空间配置器alloc
stl空间配置器alloc
SGI设计了双层级配置器，第一级配置器直接使用malloc()和free(),第二级配置器视情况采用不同的策略：当配置区块超过128bytes时，调用第一级配置器，当配置区块小于128bytes时，采用内存池方式
//SGI第一级配置器template<int inst>class __malloc_alloc_template{private: //处理内存不足的情况 //c++ new handler机制：系统在内存配置需求无法被满足时，调用一个指定函数,参见effective c++条款7 static void *oom_malloc(size_t); static void *oom_realloc(void *, size_t); static void(*__malloc_alloc_oom_handler)();//由客端设定public: //第一级配置器直接使用malloc() static void *allocate(size_t n) { void *result = malloc(n); if (result == 0) result = oom_malloc(n); return result; } //第一级配置器直接使用free() static void deallocate(void *p, size_t) { free(p); } //第一级配置器直接使用realloc static void *reallocate(void *p, size_t, size_t new_sz) { void *result = realloc(p, new_sz); if (result == 0) result = oom_realloc(p, new_sz); return result; } //仿真c++的set_new_handler() static void(*set_malloc_handler(void(*f)()))() { void(*old) = __malloc_alloc_oom_handler; __malloc_alloc_oom_handler = f; return old;//恢复全局new_handler }};//初值为0，由用户设定template<int inst>void(*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;template<int inst>void *__malloc_alloc_template<inst>::oom_malloc(size_t n){ void(*my_malloc_handler()); void *result; for (;;) { my_malloc_handler = __malloc_alloc_oom_handler; if (0 == my_malloc_handler) { throw bad_alloc; } (*my_malloc_handler)();//尝试释放内存 result = malloc(n);//再次尝试配置内存 if (result) return result; }}template<int inst>void *__malloc_alloc_template<inst>::oom_realloc(void *p, size_t n){ void(*my_malloc_handler()); void *result; //先设置处理例程，尝试释放内存，然后再次尝试分配内存 for (;;) { my_malloc_handler = __malloc_alloc_oom_handler; if (0 == my_malloc_handler) { throw bad_alloc; } (*my_malloc_handler)();//同上 result = realloc(p, n); if (result) return result; }}typedef __malloc_alloc_template<0> malloc_alloc;
-
使用16个链表来维护大小不同的空闲内存块，分配小块内存时，从free list中划拨相应的块即可
enum{ __ALLGN = 8 };//小块的上调边界enum{ __MAX_BYTES = 128 };//小块的上限大小enum{ __NFREELISTS = __MAX_BYTES / __ALLGN };//free_lists个数//第二级空间配置器，threads判断是否用于多线程，第二参数无用template<bool threads, int inst>class __default_alloc_template{private: //将请求内存大小上调至8的倍数,即将低三位加上7向高位进位，然后将低三位的余数变为0 static size_t ROUND_UP(size_t bytes) { return (((bytes)+__ALLGN - 1)&~(__ALLGN - 1));//最后三位为0一定是8的倍数 } //当区块已分配给用户后，free_list_link指针不再使用，不会浪费空间 union obj { union obj *free_list_link; char client_data[1]; }; static obj *volatile free_list[__NFREELISTS];//16个链表表头指针 //确定使用几号free-list static size_t FREELIST_INDEX(size_t bytes) { return (((bytes)+__ALLGN - 1) / __ALLGN - 1); } //当free-list没有可用区块时，为free-list重新填充空间，新的空间取自内存池,调用chunk_alloc函数 static void *refill(size_t n); //从内存池中取空间给freelist static char *chunk_alloc(size_t size, int &nobjs); static char *start_free;//内存池起始位置 static char *end_free;//内存池结束位置 static size_t heap_size;public: static void *allocate(size_t n); static void deallocate(void *p, size_t n); static void *reallocate(void *p, size_t old_sz, size_t new_sz);};template<bool threads, int inst>char *__default_alloc_template<threads, inst>::start_free = 0;template<bool threads, int inst>char *__default_alloc_template<threads, inst>::end_free = 0;template<bool threads, int inst>char *__default_alloc_template<threads, inst>::heap_size = 0;template<bool threads, int inst>char *__default_alloc_template<threads, inst>::free_list[__NFREELISTS] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };//空间配置函数allocate()template<bool threads, int inst>void *__default_alloc_template<threads, inst>::allocate(size_t n){ obj * volatile *my_free_list; obj *result; //大于128调用第一级配置器 if (n > __MAX_BYTES) { return (malloc_alloc::allocate(n)); } //寻找合适的free-list my_free_list = free_list + FREELIST_INDEX(n); result = *my_free_list;//free list中某链表的头指针 if (result == 0) { //没找到可用的free list，准备重新填充free list void *r = refill(RAND_MAX(n)); return r; } //调整free-list *my_free_list = result->free_list_link; return result;}//空间释放函数deallocate()template<bool threads, int inst>void __default_alloc_template<threads, inst>::deallocate(void *p, size_t n){ obj *q = (obj *)p; obj *volatile *my_free_list; if (n > (size_t)__MAX_BYTES) { malloc_alloc::deallocate(p, n); return; } my_free_list = free_list + FREELIST_INDEX(n); //*my_free_list为数组元素，链表头指针 q->free_list_link = *my_free_list; *my_free_list = q;}//当free list中没有可用区块时，refill()为free list重新填充空间template<bool threads, int inst>void *__default_alloc_template<threads, inst>::refill(size_t n){ //新的空间取自内存池，缺省取得20个新区块 int nobjs = 20; char *chunk = chunk_alloc(n, nobjs); obj * volatile *my_free_list; obj *result; obj *current_obj, *next_obj; int i; //只获得一个区块，这个区块分配给调用者 if (1 == nobjs) return chunk; my_free_list = free_list + FREELIST_INDEX(n); result = (obj *)chunk;//返回给用户 //在chunk空间内建立free list *my_free_list = next_obj = (obj *)(chunk + n); for (i = 1;; i++) { current_obj = next_obj; next_obj = (obj *)((char *)next_obj + n); if (nobjs - 1 == i) { current_obj->free_list_link = 0; break; } else { current_obj->free_list_link = next_obj; } } return result;}template<bool threads, int inst>char *__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int &nobjs){ char *result; size_t total_bytes = size*nobjs; size_t bytes_left = end_free - start_free; //内存池剩余空间完全满足需求 if (bytes_left >= total_bytes) { result = start_free; start_free += total_bytes; return result; } //内存池剩余空间足够供应一个以上的区块 else if (bytes_left >= size) { nobjs = bytes_left / size; total_bytes = size*nobjs; result = start_free; start_free += total_bytes; return result; } else { //内存池剩余空间连一个区块的大小都无法提供 //从堆中配置内存，大小为需求量的两倍再加上一个随着配置次数增加而愈来愈大的附加量 size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4); //尝试利用内存池残余 if (bytes_left > 0) { obj * volatile *my_free_list = free_list + FREELIST_INDEX(bytes_left); ((obj *)start_free)->free_list_link = *my_free_list; *my_free_list = (obj *)start_free; } //补充内存池 start_free = (char *)malloc(bytes_to_get); if (0 == start_free) { //heap空间不足 int i; obj *volatile *my_free_list, *p; //在free-list中搜寻未用且足够大的区块释放至内存池，然后再分配 for (i = size; i <= __MAX_BYTES; i += __ALLGN) { my_free_list = free_list + FREELIST_INDEX(i); p = *my_free_list; if (0 != p) { *my_free_list = p->free_list_link; start_free = (char *)p; end_free = start_free + i; //递归调用chunk_alloc,为了修正nobjs return (chunk_alloc(size, nobjs)); } } //到处都没内存可用 end_free = 0; //调用第一级配置器，要么抛出异常，要么改善内存不足的情况 start_free = (char *)malloc_alloc::allocate(bytes_to_get); } heap_size += bytes_to_get; end_free = start_free + bytes_to_get; return (chunk_alloc(size, nobjs)); }}//SGL为alloc包装一个接口,alloc为第一级或第二级配置器模板类,ＳＧＩＳＴＬ容器都使用simple_alloc接口template <class T,class Alloc>class simple_alloc{public: static T* allocate(size_t n) { return n == 0 ? 0 : (T*)Alloc::allocate(n*sizeof(T)); } static T*allocate(void) { return (T*)Alloc::allocate(sizeof(T)); } static void deallocate(T *p, size_t n) { if (n != 0) Alloc::deallocate(p, n*sizeof(T)); } static void deallocate(T *p) { Alloc::deallocate(p, sizeof(T)); }};//SGL容器使用配置器的方式：//第二个template参数所接受的缺省参数alloc，可以是第一级配置器，也可以是第二级配置器template<class T,class Alloc=alloc>class vector{public: typedef T value_type; //...protected: //专属的空间配置器 typedef simple_alloc<value_type, Alloc>data_allocator; //...};
stl空间配置器alloc
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。