00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #ifndef _MT_ALLOCATOR_H
00031 #define _MT_ALLOCATOR_H 1
00032
00033 #include <new>
00034 #include <cstdlib>
00035 #include <bits/functexcept.h>
00036 #include <ext/atomicity.h>
00037 #include <bits/move.h>
00038
00039 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00040 {
00041 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00042
00043 using std::size_t;
00044 using std::ptrdiff_t;
00045
00046 typedef void (*__destroy_handler)(void*);
00047
00048
00049 struct __pool_base
00050 {
00051
00052
00053 typedef unsigned short int _Binmap_type;
00054
00055
00056
00057 struct _Tune
00058 {
00059
00060 enum { _S_align = 8 };
00061 enum { _S_max_bytes = 128 };
00062 enum { _S_min_bin = 8 };
00063 enum { _S_chunk_size = 4096 - 4 * sizeof(void*) };
00064 enum { _S_max_threads = 4096 };
00065 enum { _S_freelist_headroom = 10 };
00066
00067
00068
00069
00070 size_t _M_align;
00071
00072
00073
00074
00075
00076
00077 size_t _M_max_bytes;
00078
00079
00080
00081
00082 size_t _M_min_bin;
00083
00084
00085
00086
00087
00088
00089
00090 size_t _M_chunk_size;
00091
00092
00093
00094
00095
00096
00097
00098 size_t _M_max_threads;
00099
00100
00101
00102
00103
00104
00105
00106 size_t _M_freelist_headroom;
00107
00108
00109 bool _M_force_new;
00110
00111 explicit
00112 _Tune()
00113 : _M_align(_S_align), _M_max_bytes(_S_max_bytes), _M_min_bin(_S_min_bin),
00114 _M_chunk_size(_S_chunk_size), _M_max_threads(_S_max_threads),
00115 _M_freelist_headroom(_S_freelist_headroom),
00116 _M_force_new(std::getenv("GLIBCXX_FORCE_NEW") ? true : false)
00117 { }
00118
00119 explicit
00120 _Tune(size_t __align, size_t __maxb, size_t __minbin, size_t __chunk,
00121 size_t __maxthreads, size_t __headroom, bool __force)
00122 : _M_align(__align), _M_max_bytes(__maxb), _M_min_bin(__minbin),
00123 _M_chunk_size(__chunk), _M_max_threads(__maxthreads),
00124 _M_freelist_headroom(__headroom), _M_force_new(__force)
00125 { }
00126 };
00127
00128 struct _Block_address
00129 {
00130 void* _M_initial;
00131 _Block_address* _M_next;
00132 };
00133
00134 const _Tune&
00135 _M_get_options() const
00136 { return _M_options; }
00137
00138 void
00139 _M_set_options(_Tune __t)
00140 {
00141 if (!_M_init)
00142 _M_options = __t;
00143 }
00144
00145 bool
00146 _M_check_threshold(size_t __bytes)
00147 { return __bytes > _M_options._M_max_bytes || _M_options._M_force_new; }
00148
00149 size_t
00150 _M_get_binmap(size_t __bytes)
00151 { return _M_binmap[__bytes]; }
00152
00153 size_t
00154 _M_get_align()
00155 { return _M_options._M_align; }
00156
00157 explicit
00158 __pool_base()
00159 : _M_options(_Tune()), _M_binmap(0), _M_init(false) { }
00160
00161 explicit
00162 __pool_base(const _Tune& __options)
00163 : _M_options(__options), _M_binmap(0), _M_init(false) { }
00164
00165 private:
00166 explicit
00167 __pool_base(const __pool_base&);
00168
00169 __pool_base&
00170 operator=(const __pool_base&);
00171
00172 protected:
00173
00174 _Tune _M_options;
00175
00176 _Binmap_type* _M_binmap;
00177
00178
00179
00180
00181 bool _M_init;
00182 };
00183
00184
00185
00186
00187
00188
00189 template<bool _Thread>
00190 class __pool;
00191
00192
00193 template<>
00194 class __pool<false> : public __pool_base
00195 {
00196 public:
00197 union _Block_record
00198 {
00199
00200 _Block_record* _M_next;
00201 };
00202
00203 struct _Bin_record
00204 {
00205
00206 _Block_record** _M_first;
00207
00208
00209 _Block_address* _M_address;
00210 };
00211
00212 void
00213 _M_initialize_once()
00214 {
00215 if (__builtin_expect(_M_init == false, false))
00216 _M_initialize();
00217 }
00218
00219 void
00220 _M_destroy() throw();
00221
00222 char*
00223 _M_reserve_block(size_t __bytes, const size_t __thread_id);
00224
00225 void
00226 _M_reclaim_block(char* __p, size_t __bytes) throw ();
00227
00228 size_t
00229 _M_get_thread_id() { return 0; }
00230
00231 const _Bin_record&
00232 _M_get_bin(size_t __which)
00233 { return _M_bin[__which]; }
00234
00235 void
00236 _M_adjust_freelist(const _Bin_record&, _Block_record*, size_t)
00237 { }
00238
00239 explicit __pool()
00240 : _M_bin(0), _M_bin_size(1) { }
00241
00242 explicit __pool(const __pool_base::_Tune& __tune)
00243 : __pool_base(__tune), _M_bin(0), _M_bin_size(1) { }
00244
00245 private:
00246
00247
00248
00249 _Bin_record* _M_bin;
00250
00251
00252 size_t _M_bin_size;
00253
00254 void
00255 _M_initialize();
00256 };
00257
00258 #ifdef __GTHREADS
00259
00260 template<>
00261 class __pool<true> : public __pool_base
00262 {
00263 public:
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273 struct _Thread_record
00274 {
00275
00276 _Thread_record* _M_next;
00277
00278
00279 size_t _M_id;
00280 };
00281
00282 union _Block_record
00283 {
00284
00285 _Block_record* _M_next;
00286
00287
00288 size_t _M_thread_id;
00289 };
00290
00291 struct _Bin_record
00292 {
00293
00294
00295
00296 _Block_record** _M_first;
00297
00298
00299 _Block_address* _M_address;
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310 size_t* _M_free;
00311 size_t* _M_used;
00312
00313
00314
00315
00316 __gthread_mutex_t* _M_mutex;
00317 };
00318
00319
00320 void
00321 _M_initialize(__destroy_handler);
00322
00323 void
00324 _M_initialize_once()
00325 {
00326 if (__builtin_expect(_M_init == false, false))
00327 _M_initialize();
00328 }
00329
00330 void
00331 _M_destroy() throw();
00332
00333 char*
00334 _M_reserve_block(size_t __bytes, const size_t __thread_id);
00335
00336 void
00337 _M_reclaim_block(char* __p, size_t __bytes) throw ();
00338
00339 const _Bin_record&
00340 _M_get_bin(size_t __which)
00341 { return _M_bin[__which]; }
00342
00343 void
00344 _M_adjust_freelist(const _Bin_record& __bin, _Block_record* __block,
00345 size_t __thread_id)
00346 {
00347 if (__gthread_active_p())
00348 {
00349 __block->_M_thread_id = __thread_id;
00350 --__bin._M_free[__thread_id];
00351 ++__bin._M_used[__thread_id];
00352 }
00353 }
00354
00355
00356 _GLIBCXX_CONST void
00357 _M_destroy_thread_key(void*) throw ();
00358
00359 size_t
00360 _M_get_thread_id();
00361
00362 explicit __pool()
00363 : _M_bin(0), _M_bin_size(1), _M_thread_freelist(0)
00364 { }
00365
00366 explicit __pool(const __pool_base::_Tune& __tune)
00367 : __pool_base(__tune), _M_bin(0), _M_bin_size(1),
00368 _M_thread_freelist(0)
00369 { }
00370
00371 private:
00372
00373
00374
00375 _Bin_record* _M_bin;
00376
00377
00378 size_t _M_bin_size;
00379
00380 _Thread_record* _M_thread_freelist;
00381 void* _M_thread_freelist_initial;
00382
00383 void
00384 _M_initialize();
00385 };
00386 #endif
00387
00388 template<template <bool> class _PoolTp, bool _Thread>
00389 struct __common_pool
00390 {
00391 typedef _PoolTp<_Thread> pool_type;
00392
00393 static pool_type&
00394 _S_get_pool()
00395 {
00396 static pool_type _S_pool;
00397 return _S_pool;
00398 }
00399 };
00400
00401 template<template <bool> class _PoolTp, bool _Thread>
00402 struct __common_pool_base;
00403
00404 template<template <bool> class _PoolTp>
00405 struct __common_pool_base<_PoolTp, false>
00406 : public __common_pool<_PoolTp, false>
00407 {
00408 using __common_pool<_PoolTp, false>::_S_get_pool;
00409
00410 static void
00411 _S_initialize_once()
00412 {
00413 static bool __init;
00414 if (__builtin_expect(__init == false, false))
00415 {
00416 _S_get_pool()._M_initialize_once();
00417 __init = true;
00418 }
00419 }
00420 };
00421
00422 #ifdef __GTHREADS
00423 template<template <bool> class _PoolTp>
00424 struct __common_pool_base<_PoolTp, true>
00425 : public __common_pool<_PoolTp, true>
00426 {
00427 using __common_pool<_PoolTp, true>::_S_get_pool;
00428
00429 static void
00430 _S_initialize()
00431 { _S_get_pool()._M_initialize_once(); }
00432
00433 static void
00434 _S_initialize_once()
00435 {
00436 static bool __init;
00437 if (__builtin_expect(__init == false, false))
00438 {
00439 if (__gthread_active_p())
00440 {
00441
00442 static __gthread_once_t __once = __GTHREAD_ONCE_INIT;
00443 __gthread_once(&__once, _S_initialize);
00444 }
00445
00446
00447
00448
00449 _S_get_pool()._M_initialize_once();
00450 __init = true;
00451 }
00452 }
00453 };
00454 #endif
00455
00456
00457 template<template <bool> class _PoolTp, bool _Thread>
00458 struct __common_pool_policy : public __common_pool_base<_PoolTp, _Thread>
00459 {
00460 template<typename _Tp1, template <bool> class _PoolTp1 = _PoolTp,
00461 bool _Thread1 = _Thread>
00462 struct _M_rebind
00463 { typedef __common_pool_policy<_PoolTp1, _Thread1> other; };
00464
00465 using __common_pool_base<_PoolTp, _Thread>::_S_get_pool;
00466 using __common_pool_base<_PoolTp, _Thread>::_S_initialize_once;
00467 };
00468
00469
00470 template<typename _Tp, template <bool> class _PoolTp, bool _Thread>
00471 struct __per_type_pool
00472 {
00473 typedef _Tp value_type;
00474 typedef _PoolTp<_Thread> pool_type;
00475
00476 static pool_type&
00477 _S_get_pool()
00478 {
00479
00480 typedef typename pool_type::_Block_record _Block_record;
00481 const static size_t __a = (__alignof__(_Tp) >= sizeof(_Block_record)
00482 ? __alignof__(_Tp) : sizeof(_Block_record));
00483
00484 typedef typename __pool_base::_Tune _Tune;
00485 static _Tune _S_tune(__a, sizeof(_Tp) * 64,
00486 sizeof(_Tp) * 2 >= __a ? sizeof(_Tp) * 2 : __a,
00487 sizeof(_Tp) * size_t(_Tune::_S_chunk_size),
00488 _Tune::_S_max_threads,
00489 _Tune::_S_freelist_headroom,
00490 std::getenv("GLIBCXX_FORCE_NEW") ? true : false);
00491 static pool_type _S_pool(_S_tune);
00492 return _S_pool;
00493 }
00494 };
00495
00496 template<typename _Tp, template <bool> class _PoolTp, bool _Thread>
00497 struct __per_type_pool_base;
00498
00499 template<typename _Tp, template <bool> class _PoolTp>
00500 struct __per_type_pool_base<_Tp, _PoolTp, false>
00501 : public __per_type_pool<_Tp, _PoolTp, false>
00502 {
00503 using __per_type_pool<_Tp, _PoolTp, false>::_S_get_pool;
00504
00505 static void
00506 _S_initialize_once()
00507 {
00508 static bool __init;
00509 if (__builtin_expect(__init == false, false))
00510 {
00511 _S_get_pool()._M_initialize_once();
00512 __init = true;
00513 }
00514 }
00515 };
00516
00517 #ifdef __GTHREADS
00518 template<typename _Tp, template <bool> class _PoolTp>
00519 struct __per_type_pool_base<_Tp, _PoolTp, true>
00520 : public __per_type_pool<_Tp, _PoolTp, true>
00521 {
00522 using __per_type_pool<_Tp, _PoolTp, true>::_S_get_pool;
00523
00524 static void
00525 _S_initialize()
00526 { _S_get_pool()._M_initialize_once(); }
00527
00528 static void
00529 _S_initialize_once()
00530 {
00531 static bool __init;
00532 if (__builtin_expect(__init == false, false))
00533 {
00534 if (__gthread_active_p())
00535 {
00536
00537 static __gthread_once_t __once = __GTHREAD_ONCE_INIT;
00538 __gthread_once(&__once, _S_initialize);
00539 }
00540
00541
00542
00543
00544 _S_get_pool()._M_initialize_once();
00545 __init = true;
00546 }
00547 }
00548 };
00549 #endif
00550
00551
00552 template<typename _Tp, template <bool> class _PoolTp, bool _Thread>
00553 struct __per_type_pool_policy
00554 : public __per_type_pool_base<_Tp, _PoolTp, _Thread>
00555 {
00556 template<typename _Tp1, template <bool> class _PoolTp1 = _PoolTp,
00557 bool _Thread1 = _Thread>
00558 struct _M_rebind
00559 { typedef __per_type_pool_policy<_Tp1, _PoolTp1, _Thread1> other; };
00560
00561 using __per_type_pool_base<_Tp, _PoolTp, _Thread>::_S_get_pool;
00562 using __per_type_pool_base<_Tp, _PoolTp, _Thread>::_S_initialize_once;
00563 };
00564
00565
00566
00567 template<typename _Tp>
00568 class __mt_alloc_base
00569 {
00570 public:
00571 typedef size_t size_type;
00572 typedef ptrdiff_t difference_type;
00573 typedef _Tp* pointer;
00574 typedef const _Tp* const_pointer;
00575 typedef _Tp& reference;
00576 typedef const _Tp& const_reference;
00577 typedef _Tp value_type;
00578
00579 pointer
00580 address(reference __x) const
00581 { return std::__addressof(__x); }
00582
00583 const_pointer
00584 address(const_reference __x) const
00585 { return std::__addressof(__x); }
00586
00587 size_type
00588 max_size() const throw()
00589 { return size_t(-1) / sizeof(_Tp); }
00590
00591
00592
00593 void
00594 construct(pointer __p, const _Tp& __val)
00595 { ::new((void *)__p) _Tp(__val); }
00596
00597 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00598 template<typename... _Args>
00599 void
00600 construct(pointer __p, _Args&&... __args)
00601 { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); }
00602 #endif
00603
00604 void
00605 destroy(pointer __p) { __p->~_Tp(); }
00606 };
00607
00608 #ifdef __GTHREADS
00609 #define __thread_default true
00610 #else
00611 #define __thread_default false
00612 #endif
00613
00614
00615
00616
00617
00618
00619
00620
00621
00622
00623
00624
00625 template<typename _Tp,
00626 typename _Poolp = __common_pool_policy<__pool, __thread_default> >
00627 class __mt_alloc : public __mt_alloc_base<_Tp>
00628 {
00629 public:
00630 typedef size_t size_type;
00631 typedef ptrdiff_t difference_type;
00632 typedef _Tp* pointer;
00633 typedef const _Tp* const_pointer;
00634 typedef _Tp& reference;
00635 typedef const _Tp& const_reference;
00636 typedef _Tp value_type;
00637 typedef _Poolp __policy_type;
00638 typedef typename _Poolp::pool_type __pool_type;
00639
00640 template<typename _Tp1, typename _Poolp1 = _Poolp>
00641 struct rebind
00642 {
00643 typedef typename _Poolp1::template _M_rebind<_Tp1>::other pol_type;
00644 typedef __mt_alloc<_Tp1, pol_type> other;
00645 };
00646
00647 __mt_alloc() throw() { }
00648
00649 __mt_alloc(const __mt_alloc&) throw() { }
00650
00651 template<typename _Tp1, typename _Poolp1>
00652 __mt_alloc(const __mt_alloc<_Tp1, _Poolp1>&) throw() { }
00653
00654 ~__mt_alloc() throw() { }
00655
00656 pointer
00657 allocate(size_type __n, const void* = 0);
00658
00659 void
00660 deallocate(pointer __p, size_type __n);
00661
00662 const __pool_base::_Tune
00663 _M_get_options()
00664 {
00665
00666 return __policy_type::_S_get_pool()._M_get_options();
00667 }
00668
00669 void
00670 _M_set_options(__pool_base::_Tune __t)
00671 { __policy_type::_S_get_pool()._M_set_options(__t); }
00672 };
00673
00674 template<typename _Tp, typename _Poolp>
00675 typename __mt_alloc<_Tp, _Poolp>::pointer
00676 __mt_alloc<_Tp, _Poolp>::
00677 allocate(size_type __n, const void*)
00678 {
00679 if (__n > this->max_size())
00680 std::__throw_bad_alloc();
00681
00682 __policy_type::_S_initialize_once();
00683
00684
00685
00686 __pool_type& __pool = __policy_type::_S_get_pool();
00687 const size_t __bytes = __n * sizeof(_Tp);
00688 if (__pool._M_check_threshold(__bytes))
00689 {
00690 void* __ret = ::operator new(__bytes);
00691 return static_cast<_Tp*>(__ret);
00692 }
00693
00694
00695 const size_t __which = __pool._M_get_binmap(__bytes);
00696 const size_t __thread_id = __pool._M_get_thread_id();
00697
00698
00699
00700 char* __c;
00701 typedef typename __pool_type::_Bin_record _Bin_record;
00702 const _Bin_record& __bin = __pool._M_get_bin(__which);
00703 if (__bin._M_first[__thread_id])
00704 {
00705
00706 typedef typename __pool_type::_Block_record _Block_record;
00707 _Block_record* __block = __bin._M_first[__thread_id];
00708 __bin._M_first[__thread_id] = __block->_M_next;
00709
00710 __pool._M_adjust_freelist(__bin, __block, __thread_id);
00711 __c = reinterpret_cast<char*>(__block) + __pool._M_get_align();
00712 }
00713 else
00714 {
00715
00716 __c = __pool._M_reserve_block(__bytes, __thread_id);
00717 }
00718 return static_cast<_Tp*>(static_cast<void*>(__c));
00719 }
00720
00721 template<typename _Tp, typename _Poolp>
00722 void
00723 __mt_alloc<_Tp, _Poolp>::
00724 deallocate(pointer __p, size_type __n)
00725 {
00726 if (__builtin_expect(__p != 0, true))
00727 {
00728
00729
00730 __pool_type& __pool = __policy_type::_S_get_pool();
00731 const size_t __bytes = __n * sizeof(_Tp);
00732 if (__pool._M_check_threshold(__bytes))
00733 ::operator delete(__p);
00734 else
00735 __pool._M_reclaim_block(reinterpret_cast<char*>(__p), __bytes);
00736 }
00737 }
00738
00739 template<typename _Tp, typename _Poolp>
00740 inline bool
00741 operator==(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&)
00742 { return true; }
00743
00744 template<typename _Tp, typename _Poolp>
00745 inline bool
00746 operator!=(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&)
00747 { return false; }
00748
00749 #undef __thread_default
00750
00751 _GLIBCXX_END_NAMESPACE_VERSION
00752 }
00753
00754 #endif