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