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