00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00018 #ifndef LIBCWD_PRIVATE_ALLOCATOR_H
00019 #define LIBCWD_PRIVATE_ALLOCATOR_H
00020
00021 #ifndef LIBCWD_CONFIG_H
00022 #include <libcwd/config.h>
00023 #endif
00024
00025 #if CWDEBUG_ALLOC // This file is not used when --disable-alloc was used.
00026
00027 #ifndef LIBCWD_PRIVATE_MUTEX_INSTANCES_H
00028 #include <libcwd/private_mutex_instances.h>
00029 #endif
00030 #ifndef LIBCWD_CORE_DUMP_H
00031 #include <libcwd/core_dump.h>
00032 #endif
00033 #ifndef LIBCW_CSTDDEF
00034 #define LIBCW_CSTDDEF
00035 #include <cstddef>
00036 #endif
00037 #if __GNUC__ > 3 && LIBCWD_THREAD_SAFE
00038 #include <libcwd/private_mutex.h>
00039 #endif
00040 #include <memory>
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088 #if __GNUC__ == 3 && __GNUC_MINOR__ == 4
00089 #include <ext/pool_allocator.h>
00090 #endif
00091
00092 namespace libcwd {
00093 namespace _private_ {
00094
00095
00096 int const random_salt = 327665;
00097
00098
00099 int const multi_threaded_internal_instance = -1;
00100 int const single_threaded_internal_instance = -2;
00101 int const userspace_instance = -3;
00102
00103
00104 #if __GNUC__ == 3 && __GNUC_MINOR__ < 4
00105 template<bool needs_lock, int pool_instance>
00106 struct CharPoolAlloc : public std::__default_alloc_template<needs_lock, random_salt + pool_instance> {
00107 typedef char* pointer;
00108 };
00109 #elif __GNUC__ == 3 && __GNUC_MINOR__ == 4 && __GNUC_PATCHLEVEL__ == 0
00110 template<bool needs_lock, int pool_instance>
00111 struct CharPoolAlloc : public __gnu_cxx::__pool_alloc<needs_lock, random_salt + pool_instance> {
00112 typedef char* pointer;
00113 };
00114 #elif __GNUC__ == 3
00115
00116 template<int pool_instance>
00117 struct char_wrapper {
00118 char c;
00119 };
00120
00121 template<bool needs_lock, int pool_instance>
00122 class CharPoolAlloc : public __gnu_cxx::__pool_alloc<char_wrapper<pool_instance> > { };
00123 #else // gcc 4.0 and higher.
00124
00125
00126 static size_t const maximum_size_exp = 10;
00127
00128
00129 static size_t const maximum_size = (1U << maximum_size_exp);
00130
00131 struct Node {
00132 Node* M_next;
00133 Node* M_prev;
00134
00135 Node* next(void) const { return M_next; }
00136 Node* prev(void) const { return M_prev; }
00137
00138 void unlink(void)
00139 {
00140 M_prev->M_next = M_next;
00141 M_next->M_prev = M_prev;
00142 }
00143 };
00144
00145
00146 template <unsigned int N> struct log2 { enum { result = 1 + log2<N/2>::result }; };
00147 template<> struct log2<0> { enum { result = -1 }; };
00148 static size_t const minimum_size_exp = log2<sizeof(Node) - 1>::result + 1;
00149
00150 static size_t const minimum_size = (1U << minimum_size_exp);
00151
00152 static int const bucket_sizes = maximum_size_exp - minimum_size_exp + 1;
00153
00154 struct List : public Node {
00155 bool empty(void) const { return M_next == this; }
00156 void insert(Node* node)
00157 {
00158 node->M_prev = this;
00159 node->M_next = M_next;
00160 M_next->M_prev = node;
00161 M_next = node;
00162 }
00163 void insert_back(Node* node)
00164 {
00165 node->M_prev = M_prev;
00166 node->M_next = this;
00167 M_prev->M_next = node;
00168 M_prev = node;
00169 }
00170 private:
00171 using Node::next;
00172 using Node::prev;
00173 };
00174
00175 struct ChunkNode : public Node {
00176
00177
00178
00179 ChunkNode* next(void) const { return static_cast<ChunkNode*>(M_next); }
00180 ChunkNode* prev(void) const { return static_cast<ChunkNode*>(M_prev); }
00181 };
00182
00183 struct ChunkList : public List {
00184 unsigned int M_used_count;
00185 ChunkNode* begin(void) const { return static_cast<ChunkNode*>(M_next); }
00186 Node const* end(void) const { return this; }
00187 };
00188
00189 struct BlockNode : public Node {
00190 ChunkList M_chunks;
00191 ChunkNode M_data[1];
00192
00193 BlockNode* next(void) const { return static_cast<BlockNode*>(M_next); }
00194 BlockNode* prev(void) const { return static_cast<BlockNode*>(M_prev); }
00195 };
00196
00197 struct BlockList : public List {
00198 unsigned int* M_count_ptr;
00199 unsigned short M_internal;
00200
00201 BlockNode* begin(void) const { return static_cast<BlockNode*>(M_next); }
00202 Node const* end(void) const { return this; }
00203
00204 void initialize(unsigned int* count_ptr, unsigned short internal);
00205 void uninitialize(void);
00206 ~BlockList() { uninitialize(); }
00207 #if CWDEBUG_DEBUG
00208 void consistency_check(void);
00209 #endif
00210 };
00211
00212 struct TSD_st;
00213
00214 struct FreeList {
00215 #if LIBCWD_THREAD_SAFE
00216 pthread_mutex_t M_mutex;
00217 #endif
00218 bool M_initialized;
00219 unsigned int M_count[bucket_sizes];
00220 unsigned short M_keep[bucket_sizes];
00221 BlockList M_list_notfull[bucket_sizes];
00222 BlockList M_list_full[bucket_sizes];
00223
00224 #if LIBCWD_THREAD_SAFE
00225 void initialize(TSD_st& __libcwd_tsd);
00226 #else
00227 void initialize(void);
00228 #endif
00229 void uninitialize(void);
00230 ~FreeList() { uninitialize(); }
00231 char* allocate(int power, size_t size);
00232 void deallocate(char* p, int power, size_t size);
00233 #if CWDEBUG_DEBUG
00234 void consistency_check(void);
00235 #endif
00236 };
00237
00238 template<bool needs_lock, int pool_instance>
00239 class CharPoolAlloc {
00240 private:
00241 static FreeList S_freelist;
00242
00243 public:
00244
00245 typedef char value_type;
00246 typedef size_t size_type;
00247 typedef ptrdiff_t difference_type;
00248 typedef char* pointer;
00249 typedef char const* const_pointer;
00250 typedef char& reference;
00251 typedef char const& const_reference;
00252
00253
00254 #if LIBCWD_THREAD_SAFE
00255 pointer allocate(size_type num, TSD_st&);
00256 #else
00257 pointer allocate(size_type num);
00258 #endif
00259
00260
00261 #if LIBCWD_THREAD_SAFE
00262 void deallocate(pointer p, size_type num, TSD_st&);
00263 #else
00264 void deallocate(pointer p, size_type num);
00265 #endif
00266
00267 template <bool needs_lock1, int pool_instance1,
00268 bool needs_lock2, int pool_instance2>
00269 friend inline
00270 bool operator==(CharPoolAlloc<needs_lock1, pool_instance1> const&,
00271 CharPoolAlloc<needs_lock2, pool_instance2> const&);
00272 template <bool needs_lock1, int pool_instance1,
00273 bool needs_lock2, int pool_instance2>
00274 friend inline
00275 bool operator!=(CharPoolAlloc<needs_lock1, pool_instance1> const&,
00276 CharPoolAlloc<needs_lock2, pool_instance2> const&);
00277 };
00278 #endif // gcc 4.0 and higher.
00279
00280
00281 #if CWDEBUG_DEBUG
00282 #define LIBCWD_COMMA_INT_INSTANCE , int instance
00283 #define LIBCWD_COMMA_INSTANCE , instance
00284 #define LIBCWD_DEBUGDEBUG_COMMA(x) , x
00285 #else
00286 #define LIBCWD_COMMA_INT_INSTANCE
00287 #define LIBCWD_COMMA_INSTANCE
00288 #define LIBCWD_DEBUGDEBUG_COMMA(x)
00289 #endif
00290
00291 enum pool_nt {
00292 userspace_pool,
00293 internal_pool,
00294 auto_internal_pool
00295 };
00296
00297
00298
00299
00300
00301 template<typename T, class CharAlloc, pool_nt internal LIBCWD_COMMA_INT_INSTANCE>
00302 class allocator_adaptor {
00303 private:
00304
00305 CharAlloc M_char_allocator;
00306
00307 public:
00308
00309 typedef T value_type;
00310 typedef size_t size_type;
00311 typedef ptrdiff_t difference_type;
00312 typedef T* pointer;
00313 typedef T const* const_pointer;
00314 typedef T& reference;
00315 typedef T const& const_reference;
00316
00317
00318 template <class U>
00319 struct rebind {
00320 typedef allocator_adaptor<U, CharAlloc, internal LIBCWD_COMMA_INSTANCE> other;
00321 };
00322
00323
00324 pointer address(reference value) const { return &value; }
00325 const_pointer address(const_reference value) const { return &value; }
00326
00327
00328 allocator_adaptor(void) throw() { }
00329 allocator_adaptor(allocator_adaptor const& a) : M_char_allocator(a.M_char_allocator) { }
00330 template<class U>
00331 allocator_adaptor(allocator_adaptor<U, CharAlloc, internal LIBCWD_COMMA_INSTANCE> const& a) :
00332 M_char_allocator(a.M_char_allocator) { }
00333 template<class T2, class CharAlloc2, pool_nt internal2 LIBCWD_DEBUGDEBUG_COMMA(int instance2)>
00334 friend class allocator_adaptor;
00335 ~allocator_adaptor() throw() { }
00336
00337
00338 size_type max_size(void) const { return M_char_allocator.max_size() / sizeof(T); }
00339
00340
00341 pointer allocate(size_type num);
00342 pointer allocate(size_type num, void const* hint);
00343
00344
00345 void deallocate(pointer p, size_type num);
00346
00347
00348 void construct(pointer p, T const& value) { new ((void*)p) T(value); }
00349
00350
00351 void destroy(pointer p) { p->~T(); }
00352
00353 #if CWDEBUG_DEBUG || CWDEBUG_DEBUGM
00354 private:
00355 static void sanity_check(void);
00356 #endif
00357
00358 template <class T1, class CharAlloc1, pool_nt internal1 LIBCWD_DEBUGDEBUG_COMMA(int inst1),
00359 class T2, class CharAlloc2, pool_nt internal2 LIBCWD_DEBUGDEBUG_COMMA(int inst2)>
00360 friend inline
00361 bool operator==(allocator_adaptor<T1, CharAlloc1, internal1 LIBCWD_DEBUGDEBUG_COMMA(inst1)> const& a1,
00362 allocator_adaptor<T2, CharAlloc2, internal2 LIBCWD_DEBUGDEBUG_COMMA(inst2)> const& a2);
00363 template <class T1, class CharAlloc1, pool_nt internal1 LIBCWD_DEBUGDEBUG_COMMA(int inst1),
00364 class T2, class CharAlloc2, pool_nt internal2 LIBCWD_DEBUGDEBUG_COMMA(int inst2)>
00365 friend inline
00366 bool operator!=(allocator_adaptor<T1, CharAlloc1, internal1 LIBCWD_DEBUGDEBUG_COMMA(inst1)> const& a1,
00367 allocator_adaptor<T2, CharAlloc2, internal2 LIBCWD_DEBUGDEBUG_COMMA(inst2)> const& a2);
00368 };
00369
00370 #if LIBCWD_THREAD_SAFE
00371
00372
00373
00374
00375 #define LIBCWD_CHARALLOCATOR_USERSPACE(instance) ::libcwd::_private_:: \
00376 allocator_adaptor<char, \
00377 CharPoolAlloc<true, userspace_instance>, \
00378 userspace_pool \
00379 LIBCWD_DEBUGDEBUG_COMMA(::libcwd::_private_::instance)>
00380 #endif
00381
00382
00383
00384
00385
00386
00387
00388 #if LIBCWD_THREAD_SAFE
00389 #define LIBCWD_ALLOCATOR_POOL_NEEDS_LOCK(instance) \
00390 ::libcwd::_private_::instance == \
00391 ::libcwd::_private_::multi_threaded_internal_instance || \
00392 ::libcwd::_private_::instance == \
00393 ::libcwd::_private_::memblk_map_instance
00394 #else // !LIBCWD_THREAD_SAFE
00395 #define LIBCWD_ALLOCATOR_POOL_NEEDS_LOCK(instance) false
00396 #endif // !LIBCWD_THREAD_SAFE
00397
00398 #define LIBCWD_CHARALLOCATOR_INTERNAL(instance) ::libcwd::_private_:: \
00399 allocator_adaptor<char, \
00400 CharPoolAlloc<LIBCWD_ALLOCATOR_POOL_NEEDS_LOCK(instance), \
00401 ::libcwd::_private_::instance >, \
00402 internal_pool \
00403 LIBCWD_DEBUGDEBUG_COMMA(::libcwd::_private_::instance)>
00404
00405 #define LIBCWD_CHARALLOCATOR_AUTO_INTERNAL(instance) ::libcwd::_private_:: \
00406 allocator_adaptor<char, \
00407 CharPoolAlloc<LIBCWD_ALLOCATOR_POOL_NEEDS_LOCK(instance), \
00408 ::libcwd::_private_::instance >, \
00409 auto_internal_pool \
00410 LIBCWD_DEBUGDEBUG_COMMA(::libcwd::_private_::instance)>
00411
00412 #if LIBCWD_THREAD_SAFE
00413
00414
00415
00416 #define LIBCWD_NS_INTERNAL_ALLOCATOR(instance) LIBCWD_CHARALLOCATOR_INTERNAL(instance)
00417 #else // !LIBCWD_THREAD_SAFE
00418
00419 #define LIBCWD_NS_INTERNAL_ALLOCATOR(instance) LIBCWD_CHARALLOCATOR_INTERNAL(single_threaded_internal_instance)
00420 #endif // !LIBCWD_THREAD_SAFE
00421
00422 #if LIBCWD_THREAD_SAFE
00423
00424
00425
00426 #define LIBCWD_MT_USERSPACE_ALLOCATOR LIBCWD_CHARALLOCATOR_USERSPACE(userspace_instance)
00427 #define LIBCWD_MT_INTERNAL_ALLOCATOR LIBCWD_CHARALLOCATOR_INTERNAL(multi_threaded_internal_instance)
00428 #define LIBCWD_MT_AUTO_INTERNAL_ALLOCATOR LIBCWD_CHARALLOCATOR_AUTO_INTERNAL(multi_threaded_internal_instance)
00429 #else // !LIBCWD_THREAD_SAFE
00430
00431
00432
00433 #define LIBCWD_MT_USERSPACE_ALLOCATOR std::allocator<char>
00434 #define LIBCWD_MT_INTERNAL_ALLOCATOR LIBCWD_CHARALLOCATOR_INTERNAL(single_threaded_internal_instance)
00435 #define LIBCWD_MT_AUTO_INTERNAL_ALLOCATOR LIBCWD_CHARALLOCATOR_AUTO_INTERNAL(single_threaded_internal_instance)
00436 #endif // !LIBCWD_THREAD_SAFE
00437
00438
00439
00440
00441
00442 typedef LIBCWD_NS_INTERNAL_ALLOCATOR(memblk_map_instance) memblk_map_allocator;
00443
00444
00445 typedef LIBCWD_NS_INTERNAL_ALLOCATOR(object_files_instance) object_files_allocator;
00446
00447
00448
00449 typedef LIBCWD_MT_INTERNAL_ALLOCATOR internal_allocator;
00450
00451
00452
00453 typedef LIBCWD_MT_AUTO_INTERNAL_ALLOCATOR auto_internal_allocator;
00454
00455
00456
00457
00458
00459 typedef LIBCWD_MT_USERSPACE_ALLOCATOR userspace_allocator;
00460
00461 }
00462 }
00463
00464 #endif
00465 #endif
00466