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