内容
- 关联关系
- 一级配置器和二级配置器的关系
- 类型萃取
- allocator
__malloc_alloc_template
静态成员的类外初始化,其中函数指针尤为麻烦
关联关系
弱关联
1 2 3 4 5 6 7 8
| class Person { private: Book * pbook; public: Student(){} ~Student(){} }
|
强关联
1 2 3 4 5 6 7
| class Person { private: Book & book; public: Student(Book & book) : _book(book){} }
|
聚合/组合关系
1 2 3 4 5 6 7 8 9 10 11
| class Point { private: float _x; float _y; public: Point(float x = 0.0f, float y = 0.0f) : _x(x), _y(y){} Point(const Point&) = default; Point & operator=(const Point&) = default; ~Point(){} }
|
new
- sizeof
- 分配字节空间
- 构建 返回地址
delete
- 析构
- 空间释放
二级配置器
- 一级配置器的问题
- 直接的malloc后的数据上下各有一个越界标记。上越界标记之外还有信息,包括申请了多少字节,还有next域、prev域以便连接到链表中进行内存管理。除此之外可能还有有效/失效(是否释放)的标记。
- 除了包装信息占空间较多之外,还有malloc时花费的时间也多。这样就造成对于比较小的对象数据在malloc时入不敷出。
- 结论就是:对于较小数据,适用于内存池来进行内存管理。
- 对于客户端申请较小空间(128bytes)的具体处理流程:
- 每次配置一大块内存,并维护对应的自由链表(free-list)
- 下次如果再有相同大小的内存需求,直接从free-list中取出若干小块。
- 如果客户端释放小块内存,就由配置器回收到free-list中。所以配置器除了分配空间,还负责回收空间。
- 为了方便管理,SGI第二级配置器会主动按任何小块内存的内存需求量计算成8的倍数。(比如客户端要求30bytes,则计算为32bytes。
- 共维护16个free-lists,各自管理大小分别为8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128的小额区块。
- free-lists的单结点结构如下:
1 2 3 4 5
| union obj { union obj * free_list_link; char client_data[1]; }
|
总览
1 2 3
| enum { __ALIGN = 8}; enum { __MAX_BYTES = 128}; enum { __NFREELISTS = __MAX_BYTES / __ALIGN};
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| template<bool threads, int inst> class __default_alloc_template { private: union obj { union obj * free_list_link; char client_data[1]; }; private: static obj * volatile free_list[__NFREELISTS]; static char* start_free; static char* end_free; static size_t heap_size; static size_t ROUNT_UP(size_t bytes); static size_t FREELIST_INDEX(size_t bytes); static char* chunk_alloc(size_t size, int & nobjs); static void* refill(size_t size); public: static void* allocate(size_t size); static void deallocate(void* p, size_t n); static void* reallocate(void* p, size_t old_sz, size_t new_sz); };
|
成员初始化
1 2 3 4 5 6 7 8 9 10 11 12 13
| template<bool threads, int inst> typename __default_alloc_template<threads, inst>::obj * volatile __default_alloc_template<threads, inst>::free_list[__NFREELISTS] = {};
template<bool threads, int inst> char* __default_alloc_template<threads, inst>::start_free = nullptr;
template<bool threads, int inst> char* __default_alloc_template<threads, inst>::end_free = nullptr;
template<bool threads, int inst> size_t __default_alloc_template<threads, inst>::heap_size = 0;
|
函数实现
准备工作
1
| using malloc_alloc = __malloc_alloc_template<0>;
|
allocate
相当于单链表的头删法,返回删了的节点的地址给用户用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| static void * allocate(size_t size) { if(size > (size_t)__MAX_BYTES) { return malloc_alloc::allocate(size); } obj * result = nullptr; obj * volatile * my_free_list = nullptr; my_free_list = free_list + FREELIST_INDEX(size); result = *my_free_list; if(nullptr == result) { void * r = refill(ROUND_UP(size)); return r; } *my_free_list = result->free_list_link; return result; }
|
refill
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| static void * refill(size_t size) { int nobjs = 20; char * chunk = chunk_alloc(size, nobjs); if(1 == nobjs) { return chunk; } obj * volatile * my_free_list = NULL; obj * result = (obj*)chunk; obj * current_obj = NULL, * next_obj = NULL; my_free_list = free_list + FREELIST_INDEX(size); *my_free_list = next_obj = (obj*)(chunk+size); for(int i = 1; ; ++i) { current_obj = next_obj; next_obj = (obj*)((char*)next_obj + size); if(i == nobjs-1) { current_obj->free_list_link = NULL; break; } current_obj->free_list_link = next_obj; } return result; }
|
chunk_alloc
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| static char* chunk_alloc(size_t size, int & nobjs) { char * result = NULL; size_t total_bytes = size * nobjs; size_t bytes_left = end_free - start_free; if(bytes_left >= total_bytes) { result = start_free; start_free = start_free + total_bytes; return result; } else if(bytes_left >= size) { nobjs = bytes_left / size; total = size * nobjs; result = start_free; 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(NULL == start_free) { obj * volatile * my_free_list = NULL; for(int i = size; i <= __MAX_BYTES; i += __ALIGN) { my_free_list = free_list + FREELIST_INDEX(i); obj * p = NULL; if(NULL != p) { *my_free_list = (*my_free_list)->free_list_link; start_free = (char*)p; end_free = start_free + i; return chunk_alloc(size, nobjs); } } start_free = malloc_alloc::allocate(bytes_to_get); } end_free = start_free + bytes_to_get; heap_size += bytes_to_get; return chunk_alloc(size, nobjs); } }
|
ROUND_UP & INDEX
1 2 3 4 5 6 7 8 9 10
| static size_t ROUNT_UP(size_t bytes) { return (bytes+ __ALIGN-1) & ~(__ALIGN - 1); } static size_t FREELIST_INDEX(size_t bytes) { return ((bytes+ __ALIGN-1) / __ALIGN) - 1; }
|
测试allocate
1 2 3 4 5 6
| #ifdef __USE_MALLOC typedef __malloc_alloc_template<0> malloc_alloc; typedef malloc_alloc alloc; #else typedef __default_alloc_template<0, 0> alloc; #endif
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| template<class T, class Alloc> class simple_alloc { public: static T* allocate(size_t n) { return Alloc::allocate(sizeof(T)*n); } static T* allocate() { return Alloc::allocate(sizeof(T)); } void deallocate(T *p, size_t n) { if(NULL == p)return; Alloc::deallocate(p, sizeof(T)*n); } void deallocate(T* p) { if(NULL == p)return; Alloc::deallocate(p, sizeof(T)); } };
|
引入list进行测试
1 2 3 4 5 6 7 8 9 10 11 12
| #include"my_list.h" using namespace std; int main() { xcg::my_list<char> mylist; for(int i = 0; i < 23; ++i) { mylist.push_back(i + 'a'); } return 0; }
|
list构建流程:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| template<class _Ty, class _A = xcg::alloc> class my_list { public: typedef _Ty value_type; typedef _Ty& reference; typedef _Ty* pointer; typedef const _Ty& const_reference; typedef const _Ty* const_pointer; typedef _A allocator_type; typedef xcg::simple_alloc<_Node, _A> data_allocate; public: my_list() : _Head(_Buynode()), _Size(0) {} protected: _Nodeptr _Buynode(_Nodeptr _parg = NULL, _Nodeptr _narg = NULL) { _Nodeptr _S = data_allocate::allocate(); _Acc::_Prev(_S) = _parg == NULL ? _S : _parg; _Acc::_Next(_S) = _narg == NULL ? _S : _narg; return _S; } private: _Nodeptr _Head; size_t _Size; };
|
deallocate
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| static void deallocate(void * p, size_t size) { if(size > (size_t)__MAX_BYTES) { malloc_alloc::deallocate(p, size); return; } obj * q = (obj*)p; obj * volatile * my_free_list = free_list + FREELIST_INDEX(size); q->free_list_link = *my_free_list; *my_free_list = q; return; }
|
测试deallocate
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| iterator erase(iterator _P) { _Nodeptr _S = _P++._Mynode(); _Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S); _Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S); destroy(&_Acc::_Value(_S)); _Freenode(_); return _P; } void _Freenode(_Nodeptr _P) { data_allocate::deallocate(_P); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| class Object { private: int value; public: Object(int x = 0) : value(x) { cout << "create object" << this << endl; } ~Object() { cout << "destroy object" << this << endl; } }; int main() { xcg::my_list<Object> objlist; for(int i = 0; i < 10; ++i) { objlist.push_back(Object(i)); } objlist.pop_back(); return 0; }
|
reallocate
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| static void* reallocate(void * p, size_t old_sz, size_t new_sz) { if(old_sz > (size_t)__MAX_BYTES && new_sz > (size_t)__MAX_BYTES) { return malloc_alloc::reallocate(p, old_sz, new_sz); } if(ROUND_UP(old_sz) == ROUND_UP(new_sz)) { return p; } size_t sz = old_sz < new_sz ? old_sz : new_sz; void * s = allocate(new_sz); memmove(s, p ,sz); deallocate(p, old, sz); return s; }
|