为了节省内存使用，使用 union
结构，这个设计很巧妙，每一个元素（内存区域对象）即可以当作下一个元素的指针，例如后面代码中的
result -> _M_free_list_link，也可以当作该元素的值，例如
*__my_free_list。整个 free lists
的结构便是一串使用后者的元素构成的节点，每个节点的值是使用前者构成的单向链表的首地址。
/* We allocate memory in large chunks in order to avoid fragmenting */ /* the malloc heap too much. */ /* We assume that size is properly aligned. */ /* We hold the allocation lock. */ template char* __default_alloc_template <__threads , __inst> ::_S_chunk_alloc(size_t __size, int& __nobjs) { char* __result; size_t __total_bytes = __size * __nobjs; size_t __bytes_left = _S_end_free - _S_start_free;
// 如果剩余空间满足需求，直接从 chunk 中分配 // _S_start_free 指向 chunk 空闲位置 if (__bytes_left >= __total_bytes) { __result = _S_start_free; _S_start_free += __total_bytes; return(__result); // 剩余空间不满足需求，但至少可用分配一个（含一个）区域以上 // 直接从 chunk 中分配，并更改分配区域个数 } elseif (__bytes_left >= __size) { __nobjs = (int)(__bytes_left/__size); __total_bytes = __size * __nobjs; __result = _S_start_free; _S_start_free += __total_bytes; return(__result); } else { // 如果连一个区域也无法分配 // 设置需要 malloc() 分配内存空间大小，为需求的两倍，再加上附加值 // _S_heap_size 是每一次 __bytes_to_get 的累加值 size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4); // Try to make use of the left-over piece. if (__bytes_left > 0) { // 将 chunk 中剩余的空间分配给对应的节点 // 因为剩余空间小于需求，所以直接分配给跟剩余空间大小相符的节点 _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__bytes_left); // 该空间插到节点对应链表的链首 ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list; // 再将节点值（对应链表地址）改成新链首 *__my_free_list = (_Obj*)_S_start_free; } // 通过 malloc 分配 _S_start_free = (char*)malloc(__bytes_to_get); // 如果 heap 空间不够导致 malloc 失败 if (0 == _S_start_free) { size_t __i; _Obj* __STL_VOLATILE* __my_free_list; _Obj* __p; // Try to make do with what we have. That can't // hurt. We do not try smaller requests, since that tends // to result in disaster on multi-process machines. // 从需要分配的节点开始，依次遍历所有的节点，找到有未用区域的 // 将其作为 chunk 的空闲区域，然后再次调用本函数进行分配 for (__i = __size; __i >= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN) { __my_free_list = _S_free_list + _S_freelist_index(__i); __p = *__my_free_list; if (0 != __p) { *__my_free_list = __p - > _M_free_list_link; // 置为 chunk 的空闲区域 _S_start_free = (char*)__p; _S_end_free = _S_start_free + __i; return(_S_chunk_alloc(__size, __nobjs)); // Any leftover piece will eventually make it to the // right free list. } } // 如果执行到这里，也就意味着最后的努力也以失败告终 _S_end_free = 0; // In case of exception. // 使用第一级 alloc 进行分配，因为其实第一级 alloc 也是调用 malloc() // 所以只是试试看内存分配失败处理函数或者抛出异常说不定有用或者内存使用得到缓解 _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get); // This should either throw an // exception or remedy the situation. Thus we assume it // succeeded. } _S_heap_size += __bytes_to_get; _S_end_free = _S_start_free + __bytes_to_get; // 重新进行分配，因为已经通过 malloc() 分配到了内存 return(_S_chunk_alloc(__size, __nobjs)); } }