首页 > 代码库 > STL 之 空间适配器
STL 之 空间适配器
1.sgi STL"标准"的空间适配器：
该适配器很简单，只是对new delete等内存分配释放函数的一层简单封装而已，所以sgi stl几乎没用上它（效率太低），代码位于defalloc.h.
2.sgi stl特殊适配器 std::alloc：
该版本作为stl中的默认适配器，主要分成两个部分：
#include <stl_alloc.h> //空间配置与释放
#include <stl_construct.h> //空间内对象的构造与析构
2.1.对象构造与析构：
1 template <class T> 2 inline void destroy(T* pointer) { 3 pointer->~T(); 4 } 5 6 template <class T1, class T2> 7 inline void construct(T1* p, const T2& value) { 8 new (p) T1(value); 9 } 10 11 template <class ForwardIterator> 12 inline void 13 __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) { 14 for ( ; first < last; ++first) 15 destroy(&*first); 16 } 17 18 template <class ForwardIterator> 19 inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {} 20 21 template <class ForwardIterator, class T> 22 inline void __destroy(ForwardIterator first, ForwardIterator last, T*) { 23 typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor; 24 __destroy_aux(first, last, trivial_destructor()); 25 } 26 27 template <class ForwardIterator> 28 inline void destroy(ForwardIterator first, ForwardIterator last) { 29 __destroy(first, last, value_type(first)); 30 } 31 32 inline void destroy(char*, char*) {} 33 inline void destroy(wchar_t*, wchar_t*) {}
2.2.空间配置与释放：
sgi中该部分有两个版本:
一级配置器：负责申请/释放的内存空间比较大时直接调用malloc / free完成。
二级配置器：解决当申请/释放的空间比较小的的内存碎片问题，用内存池完成。
2.2.1.一级配置器：
1 template <int inst> 2 class __malloc_alloc_template { 3 4 private: 5 6 static void *oom_malloc(size_t); 7 8 static void *oom_realloc(void *, size_t); 9 10 #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG 11 static void (* __malloc_alloc_oom_handler)(); 12 #endif 13 14 public: 15 16 static void * allocate(size_t n) 17 { 18 void *result = malloc(n); 19 if (0 == result) result = oom_malloc(n); 20 return result; 21 } 22 23 static void deallocate(void *p, size_t /* n */) 24 { 25 free(p); 26 } 27 28 static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz) 29 { 30 void * result = realloc(p, new_sz); 31 if (0 == result) result = oom_realloc(p, new_sz); 32 return result; 33 } 34 35 static void (* set_malloc_handler(void (*f)()))() 36 { 37 void (* old)() = __malloc_alloc_oom_handler; 38 __malloc_alloc_oom_handler = f; 39 return(old); 40 } 41 42 }; 43 44 // malloc_alloc out-of-memory handling 45 46 #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG 47 template <int inst> 48 void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0; 49 #endif 50 51 template <int inst> 52 void * __malloc_alloc_template<inst>::oom_malloc(size_t n) 53 { 54 void (* my_malloc_handler)(); 55 void *result; 56 57 for (;;) { 58 my_malloc_handler = __malloc_alloc_oom_handler; 59 if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; } 60 (*my_malloc_handler)(); 61 result = malloc(n); 62 if (result) return(result); 63 } 64 } 65 66 template <int inst> 67 void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n) 68 { 69 void (* my_malloc_handler)(); 70 void *result; 71 72 for (;;) { 73 my_malloc_handler = __malloc_alloc_oom_handler; 74 if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; } 75 (*my_malloc_handler)(); 76 result = realloc(p, n); 77 if (result) return(result); 78 } 79 } 80 81 typedef __malloc_alloc_template<0> malloc_alloc;
注：typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;
2.2.2.二级配置器:
1 template <bool threads, int inst> 2 class __default_alloc_template 3 { 4 5 private: 6 7 # ifndef __SUNPRO_CC 8 enum {__ALIGN = 8}; 9 enum {__MAX_BYTES = 128}; 10 enum {__NFREELISTS = __MAX_BYTES/__ALIGN}; 11 # endif 12 13 static size_t ROUND_UP(size_t bytes) { 14 return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1)); 15 } 16 17 __PRIVATE: 18 union obj { 19 union obj * free_list_link; 20 char client_data[1]; /* The client sees this.*/ 21 }; 22 23 private: 24 static obj * __VOLATILE free_list[__NFREELISTS]; 25 26 static size_t FREELIST_INDEX(size_t bytes) { 27 return (((bytes) + __ALIGN-1)/__ALIGN - 1); 28 } 29 30 // Returns an object of size n, and optionally adds to size n free list. 31 static void *refill(size_t n); 32 33 // Allocates a chunk for nobjs of size "size". nobjs may be reduced 34 // if it is inconvenient to allocate the requested number. 35 static char *chunk_alloc(size_t size, int &nobjs); 36 37 // Chunk allocation state. 38 static char *start_free; 39 static char *end_free; 40 static size_t heap_size; 41 42 43 44 public: 45 __default_alloc_template() 46 { 47 if (!__node_allocator_lock_initialized) { 48 InitializeCriticalSection(&__node_allocator_lock); 49 __node_allocator_lock_initialized = true; 50 } 51 } 52 53 54 55 static void * allocate(size_t n) 56 { 57 obj * __VOLATILE * my_free_list; 58 obj * __RESTRICT result; 59 60 if (n > (size_t) __MAX_BYTES) { 61 return(malloc_alloc::allocate(n)); 62 } 63 my_free_list = free_list + FREELIST_INDEX(n); 64 result = *my_free_list; 65 if (result == 0) { 66 void *r = refill(ROUND_UP(n)); 67 return r; 68 } 69 *my_free_list = result -> free_list_link; 70 return (result); 71 }; 72 73 74 75 static void deallocate(void *p, size_t n) 76 { 77 obj *q = (obj *)p; 78 obj * __VOLATILE * my_free_list; 79 80 if (n > (size_t) __MAX_BYTES) { 81 malloc_alloc::deallocate(p, n); 82 return; 83 } 84 my_free_list = free_list + FREELIST_INDEX(n); 85 q -> free_list_link = *my_free_list; 86 *my_free_list = q; 87 } 88 89 90 static void * reallocate(void *p, size_t old_sz, size_t new_sz); 91 } ; 92 93 94 95 96 //注： 97 typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc; 98 typedef __default_alloc_template<false, 0> single_client_alloc; 99 100 101 102 103 /* We allocate memory in large chunks in order to avoid fragmenting */ 104 /* the malloc heap too much. */ 105 /* We assume that size is properly aligned. */ 106 /* We hold the allocation lock. */ 107 template <bool threads, int inst> 108 char* 109 __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs) 110 { 111 char * result; 112 size_t total_bytes = size * nobjs; 113 size_t bytes_left = end_free - start_free; 114 115 if (bytes_left >= total_bytes) { 116 result = start_free; 117 start_free += total_bytes; 118 return(result); 119 } else if (bytes_left >= size) { 120 nobjs = bytes_left/size; 121 total_bytes = size * nobjs; 122 result = start_free; 123 start_free += total_bytes; 124 return(result); 125 } else { 126 size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4); 127 // Try to make use of the left-over piece. 128 if (bytes_left > 0) { 129 obj * __VOLATILE * my_free_list = 130 free_list + FREELIST_INDEX(bytes_left); 131 132 ((obj *)start_free) -> free_list_link = *my_free_list; 133 *my_free_list = (obj *)start_free; 134 } 135 start_free = (char *)malloc(bytes_to_get); 136 if (0 == start_free) { 137 int i; 138 obj * __VOLATILE * my_free_list, *p; 139 // Try to make do with what we have. That can‘t 140 // hurt. We do not try smaller requests, since that tends 141 // to result in disaster on multi-process machines. 142 for (i = size; i <= __MAX_BYTES; i += __ALIGN) { 143 my_free_list = free_list + FREELIST_INDEX(i); 144 p = *my_free_list; 145 if (0 != p) { 146 *my_free_list = p -> free_list_link; 147 start_free = (char *)p; 148 end_free = start_free + i; 149 return(chunk_alloc(size, nobjs)); 150 // Any leftover piece will eventually make it to the 151 // right free list. 152 } 153 } 154 end_free = 0; // In case of exception. 155 start_free = (char *)malloc_alloc::allocate(bytes_to_get); 156 // This should either throw an 157 // exception or remedy the situation. Thus we assume it 158 // succeeded. 159 } 160 heap_size += bytes_to_get; 161 end_free = start_free + bytes_to_get; 162 return(chunk_alloc(size, nobjs)); 163 } 164 } 165 166 167 /* Returns an object of size n, and optionally adds to size n free list.*/ 168 /* We assume that n is properly aligned. */ 169 /* We hold the allocation lock. */ 170 template <bool threads, int inst> 171 void* __default_alloc_template<threads, inst>::refill(size_t n) 172 { 173 int nobjs = 20; 174 char * chunk = chunk_alloc(n, nobjs); 175 obj * __VOLATILE * my_free_list; 176 obj * result; 177 obj * current_obj, * next_obj; 178 int i; 179 180 if (1 == nobjs) return(chunk); 181 my_free_list = free_list + FREELIST_INDEX(n); 182 183 /* Build free list in chunk */ 184 result = (obj *)chunk; 185 *my_free_list = next_obj = (obj *)(chunk + n); 186 for (i = 1; ; i++) { 187 current_obj = next_obj; 188 next_obj = (obj *)((char *)next_obj + n); 189 if (nobjs - 1 == i) { 190 current_obj -> free_list_link = 0; 191 break; 192 } else { 193 current_obj -> free_list_link = next_obj; 194 } 195 } 196 return(result); 197 } 198 199 template <bool threads, int inst> 200 void* 201 __default_alloc_template<threads, inst>::reallocate(void *p, 202 size_t old_sz, 203 size_t new_sz) 204 { 205 void * result; 206 size_t copy_sz; 207 208 if (old_sz > (size_t) __MAX_BYTES && new_sz > (size_t) __MAX_BYTES) { 209 return(realloc(p, new_sz)); 210 } 211 if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return(p); 212 result = allocate(new_sz); 213 copy_sz = new_sz > old_sz? old_sz : new_sz; 214 memcpy(result, p, copy_sz); 215 deallocate(p, old_sz); 216 return(result); 217 } 218 219 220 221 222 template <bool threads, int inst> 223 char *__default_alloc_template<threads, inst>::start_free = 0; 224 225 template <bool threads, int inst> 226 char *__default_alloc_template<threads, inst>::end_free = 0; 227 228 template <bool threads, int inst> 229 size_t __default_alloc_template<threads, inst>::heap_size = 0; 230 231 template <bool threads, int inst> 232 __default_alloc_template<threads, inst>::obj * __VOLATILE 233 __default_alloc_template<threads, inst> ::free_list[__default_alloc_template<threads, inst>::__NFREELISTS] = 234 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
注：typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
2.2.3.配置器接口层：
1 template<class T, class Alloc> 2 class simple_alloc 3 { 4 public: 5 static T *allocate(size_t n) 6 { return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); } 7 static T *allocate(void) 8 { return (T*) Alloc::allocate(sizeof (T)); } 9 static void deallocate(T *p, size_t n) 10 { if (0 != n) Alloc::deallocate(p, n * sizeof (T)); } 11 static void deallocate(T *p) 12 { Alloc::deallocate(p, sizeof (T)); } 13 };
接口用法示例：
1 template <class T, class Alloc = alloc> 2 class vector 3 { 4 public: 5 typedef T value_type; 6 typedef value_type* pointer; 7 typedef const value_type* const_pointer; 8 typedef value_type* iterator; 9 typedef const value_type* const_iterator; 10 typedef value_type& reference; 11 typedef const value_type& const_reference; 12 typedef size_t size_type; 13 typedef ptrdiff_t difference_type; 14 15 //.................... 16 17 protected: 18 typedef simple_alloc<value_type, Alloc> data_allocator; 19 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。