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
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
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
00188 template<bool _Thread>
00189 class __pool;
00190
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
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
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
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
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
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