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
#if !defined _BITMAP_ALLOCATOR_H
00033
#define _BITMAP_ALLOCATOR_H 1
00034
00035
#include <cstddef>
00036
00037
#include <utility>
00038
00039
#include <algorithm>
00040
00041
#include <vector>
00042
00043
00044
00045
#include <functional>
00046
00047
#include <new>
00048
00049
#include <bits/gthr.h>
00050
00051
#include <ext/new_allocator.h>
00052
00053
00054
#include <cassert>
00055
#define NDEBUG
00056
00057
00058
00059
00060
namespace __gnu_cxx
00061 {
00062
namespace {
00063
#if defined __GTHREADS
00064
bool const __threads_enabled = __gthread_active_p();
00065
#endif
00066
00067 }
00068
00069
#if defined __GTHREADS
00070
class _Mutex {
00071 __gthread_mutex_t _M_mut;
00072
00073 _Mutex (_Mutex
const&);
00074 _Mutex& operator= (_Mutex
const&);
00075
public:
00076 _Mutex ()
00077 {
00078
if (__threads_enabled)
00079 {
00080
#if !defined __GTHREAD_MUTEX_INIT
00081
__GTHREAD_MUTEX_INIT_FUNCTION(&_M_mut);
00082
#else
00083
__gthread_mutex_t __mtemp = __GTHREAD_MUTEX_INIT;
00084 _M_mut = __mtemp;
00085
#endif
00086
}
00087 }
00088 ~_Mutex ()
00089 {
00090
00091 }
00092 __gthread_mutex_t *_M_get() {
return &_M_mut; }
00093 };
00094
00095
class _Lock {
00096 _Mutex* _M_pmt;
00097
bool _M_locked;
00098
00099 _Lock (_Lock
const&);
00100 _Lock& operator= (_Lock
const&);
00101
public:
00102 _Lock(_Mutex* __mptr)
00103 : _M_pmt(__mptr), _M_locked(false)
00104 { this->_M_lock(); }
00105
void _M_lock()
00106 {
00107
if (__threads_enabled)
00108 {
00109 _M_locked =
true;
00110 __gthread_mutex_lock(_M_pmt->_M_get());
00111 }
00112 }
00113
void _M_unlock()
00114 {
00115
if (__threads_enabled)
00116 {
00117
if (__builtin_expect(_M_locked,
true))
00118 {
00119 __gthread_mutex_unlock(_M_pmt->_M_get());
00120 _M_locked =
false;
00121 }
00122 }
00123 }
00124 ~_Lock() { this->_M_unlock(); }
00125 };
00126
#endif
00127
00128
00129
00130
namespace __aux_balloc {
00131
static const unsigned int _Bits_Per_Byte = 8;
00132
static const unsigned int _Bits_Per_Block =
sizeof(
unsigned int) * _Bits_Per_Byte;
00133
00134
template <
typename _Addr_Pair_t>
00135
inline size_t __balloc_num_blocks (_Addr_Pair_t __ap)
00136 {
00137
return (__ap.second - __ap.first) + 1;
00138 }
00139
00140
template <
typename _Addr_Pair_t>
00141
inline size_t __balloc_num_bit_maps (_Addr_Pair_t __ap)
00142 {
00143
return __balloc_num_blocks(__ap) / _Bits_Per_Block;
00144 }
00145
00146
00147
template <
typename _Tp>
00148
class _Inclusive_between :
public std::unary_function<typename std::pair<_Tp, _Tp>, bool> {
00149
typedef _Tp pointer;
00150 pointer _M_ptr_value;
00151
typedef typename std::pair<_Tp, _Tp> _Block_pair;
00152
00153
public:
00154 _Inclusive_between (pointer __ptr) : _M_ptr_value(__ptr) { }
00155
bool operator () (_Block_pair __bp)
const throw ()
00156 {
00157
if (
std::less_equal<pointer> ()(_M_ptr_value, __bp.second) &&
00158
std::greater_equal<pointer> ()(_M_ptr_value, __bp.first))
00159
return true;
00160
else
00161
return false;
00162 }
00163 };
00164
00165
00166
template <
typename _Functor>
00167
class _Functor_Ref :
00168
public std::unary_function<typename _Functor::argument_type, typename _Functor::result_type> {
00169 _Functor& _M_fref;
00170
00171
public:
00172
typedef typename _Functor::argument_type argument_type;
00173
typedef typename _Functor::result_type result_type;
00174
00175 _Functor_Ref (_Functor& __fref) : _M_fref(__fref) { }
00176 result_type operator() (argument_type __arg) {
return _M_fref (__arg); }
00177 };
00178
00179
00180
00181
template <
typename _Tp,
typename _Alloc>
00182
class _Ffit_finder
00183 :
public std::unary_function<typename std::pair<_Tp, _Tp>, bool> {
00184
typedef typename std::vector<std::pair<_Tp, _Tp>, _Alloc> _BPVector;
00185
typedef typename _BPVector::difference_type _Counter_type;
00186
typedef typename std::pair<_Tp, _Tp> _Block_pair;
00187
00188
unsigned int *_M_pbitmap;
00189
unsigned int _M_data_offset;
00190
00191
public:
00192 _Ffit_finder ()
00193 : _M_pbitmap (0), _M_data_offset (0)
00194 { }
00195
00196
bool operator() (_Block_pair __bp)
throw()
00197 {
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207 _Counter_type __diff = __gnu_cxx::__aux_balloc::__balloc_num_bit_maps (__bp);
00208
00209 assert (*(reinterpret_cast<unsigned int*>(__bp.first) - (__diff + 1)) <=
00210 __gnu_cxx::__aux_balloc::__balloc_num_blocks (__bp));
00211
00212
if (*(reinterpret_cast<unsigned int*>(__bp.first) - (__diff + 1)) ==
00213 __gnu_cxx::__aux_balloc::__balloc_num_blocks (__bp))
00214
return false;
00215
00216
unsigned int *__rover = reinterpret_cast<unsigned int*>(__bp.first) - 1;
00217
for (_Counter_type __i = 0; __i < __diff; ++__i)
00218 {
00219 _M_data_offset = __i;
00220
if (*__rover)
00221 {
00222 _M_pbitmap = __rover;
00223
return true;
00224 }
00225 --__rover;
00226 }
00227
return false;
00228 }
00229
00230
unsigned int *_M_get () {
return _M_pbitmap; }
00231
unsigned int _M_offset () {
return _M_data_offset * _Bits_Per_Block; }
00232 };
00233
00234
00235
template <
typename _Tp,
typename _Alloc>
00236
class _Bit_map_counter {
00237
00238
typedef typename std::vector<std::pair<_Tp, _Tp>, _Alloc> _BPVector;
00239
typedef typename _BPVector::size_type _Index_type;
00240
typedef _Tp pointer;
00241
00242 _BPVector& _M_vbp;
00243
unsigned int *_M_curr_bmap;
00244
unsigned int *_M_last_bmap_in_block;
00245 _Index_type _M_curr_index;
00246
00247
public:
00248
00249
00250
00251 _Bit_map_counter (_BPVector& Rvbp,
int __index = -1)
00252 : _M_vbp(Rvbp)
00253 {
00254 this->_M_reset(__index);
00255 }
00256
00257
void _M_reset (
int __index = -1)
throw()
00258 {
00259
if (__index == -1)
00260 {
00261 _M_curr_bmap = 0;
00262 _M_curr_index = (_Index_type)-1;
00263
return;
00264 }
00265
00266 _M_curr_index = __index;
00267 _M_curr_bmap = reinterpret_cast<unsigned int*>(_M_vbp[_M_curr_index].first) - 1;
00268
00269 assert (__index <= (
int)_M_vbp.size() - 1);
00270
00271 _M_last_bmap_in_block = _M_curr_bmap -
00272 ((_M_vbp[_M_curr_index].second - _M_vbp[_M_curr_index].first + 1) / _Bits_Per_Block - 1);
00273 }
00274
00275
00276
00277
00278
void _M_set_internal_bit_map (
unsigned int *__new_internal_marker)
throw()
00279 {
00280 _M_curr_bmap = __new_internal_marker;
00281 }
00282
00283
bool _M_finished () const throw()
00284 {
00285
return (_M_curr_bmap == 0);
00286 }
00287
00288 _Bit_map_counter& operator++ () throw()
00289 {
00290
if (_M_curr_bmap == _M_last_bmap_in_block)
00291 {
00292
if (++_M_curr_index == _M_vbp.size())
00293 {
00294 _M_curr_bmap = 0;
00295 }
00296
else
00297 {
00298 this->_M_reset (_M_curr_index);
00299 }
00300 }
00301
else
00302 {
00303 --_M_curr_bmap;
00304 }
00305
return *
this;
00306 }
00307
00308
unsigned int *_M_get ()
00309 {
00310
return _M_curr_bmap;
00311 }
00312
00313 pointer _M_base () {
return _M_vbp[_M_curr_index].first; }
00314
unsigned int _M_offset ()
00315 {
00316
return _Bits_Per_Block * ((reinterpret_cast<unsigned int*>(this->_M_base()) - _M_curr_bmap) - 1);
00317 }
00318
00319
unsigned int _M_where () {
return _M_curr_index; }
00320 };
00321 }
00322
00323
00324
typedef unsigned int _Bit_map_type;
00325
static inline unsigned int _Bit_scan_forward (
register _Bit_map_type __num)
00326 {
00327
return static_cast<unsigned int>(__builtin_ctz(__num));
00328 }
00329
00330
struct _OOM_handler {
00331
static std::new_handler _S_old_handler;
00332
static bool _S_handled_oom;
00333
typedef void (*_FL_clear_proc)(
void);
00334
static _FL_clear_proc _S_oom_fcp;
00335
00336 _OOM_handler (_FL_clear_proc __fcp)
00337 {
00338 _S_oom_fcp = __fcp;
00339 _S_old_handler =
std::set_new_handler (_S_handle_oom_proc);
00340 _S_handled_oom =
false;
00341 }
00342
00343
static void _S_handle_oom_proc()
00344 {
00345 _S_oom_fcp();
00346
std::set_new_handler (_S_old_handler);
00347 _S_handled_oom =
true;
00348 }
00349
00350 ~_OOM_handler ()
00351 {
00352
if (!_S_handled_oom)
00353
std::set_new_handler (_S_old_handler);
00354 }
00355 };
00356
00357
std::new_handler _OOM_handler::_S_old_handler;
00358
bool _OOM_handler::_S_handled_oom =
false;
00359 _OOM_handler::_FL_clear_proc _OOM_handler::_S_oom_fcp = 0;
00360
00361
00362
class _BA_free_list_store {
00363
struct _LT_pointer_compare {
00364
template <
typename _Tp>
00365
bool operator() (_Tp* __pt, _Tp
const& __crt)
const throw()
00366 {
00367
return *__pt < __crt;
00368 }
00369 };
00370
00371
#if defined __GTHREADS
00372
static _Mutex _S_bfl_mutex;
00373
#endif
00374
static std::vector<unsigned int*> _S_free_list;
00375
typedef std::vector<unsigned int*>::iterator _FLIter;
00376
00377
static void _S_validate_free_list(
unsigned int *__addr)
throw()
00378 {
00379
const unsigned int __max_size = 64;
00380
if (_S_free_list.size() >= __max_size)
00381 {
00382
00383
00384
00385
if (*__addr >= *_S_free_list.back())
00386 {
00387
00388
00389
00390
operator delete((
void*)__addr);
00391
return;
00392 }
00393
else
00394 {
00395
00396
00397
operator delete((
void*)_S_free_list.back());
00398 _S_free_list.pop_back();
00399 }
00400 }
00401
00402
00403
00404 _FLIter __temp =
std::lower_bound(_S_free_list.begin(), _S_free_list.end(),
00405 *__addr, _LT_pointer_compare ());
00406
00407 _S_free_list.insert(__temp, __addr);
00408 }
00409
00410
static bool _S_should_i_give(
unsigned int __block_size,
unsigned int __required_size)
throw()
00411 {
00412
const unsigned int __max_wastage_percentage = 36;
00413
if (__block_size >= __required_size &&
00414 (((__block_size - __required_size) * 100 / __block_size) < __max_wastage_percentage))
00415
return true;
00416
else
00417
return false;
00418 }
00419
00420
public:
00421
typedef _BA_free_list_store _BFL_type;
00422
00423
static inline void _S_insert_free_list(
unsigned int *__addr)
throw()
00424 {
00425
#if defined __GTHREADS
00426
_Lock __bfl_lock(&_S_bfl_mutex);
00427
#endif
00428
00429
00430 _S_validate_free_list(--__addr);
00431 }
00432
00433
static unsigned int *_S_get_free_list(
unsigned int __sz)
throw (
std::bad_alloc)
00434 {
00435
#if defined __GTHREADS
00436
_Lock __bfl_lock(&_S_bfl_mutex);
00437
#endif
00438
_FLIter __temp =
std::lower_bound(_S_free_list.begin(), _S_free_list.end(),
00439 __sz, _LT_pointer_compare());
00440
if (__temp == _S_free_list.end() || !_S_should_i_give (**__temp, __sz))
00441 {
00442
00443
00444 _OOM_handler __set_handler(_BFL_type::_S_clear);
00445
unsigned int *__ret_val = reinterpret_cast<unsigned int*>
00446 (
operator new (__sz +
sizeof(
unsigned int)));
00447 *__ret_val = __sz;
00448
return ++__ret_val;
00449 }
00450
else
00451 {
00452
unsigned int* __ret_val = *__temp;
00453 _S_free_list.erase (__temp);
00454
return ++__ret_val;
00455 }
00456 }
00457
00458
00459
00460
static void _S_clear()
00461 {
00462
#if defined __GTHREADS
00463
_Lock __bfl_lock(&_S_bfl_mutex);
00464
#endif
00465
_FLIter __iter = _S_free_list.begin();
00466
while (__iter != _S_free_list.end())
00467 {
00468
operator delete((
void*)*__iter);
00469 ++__iter;
00470 }
00471 _S_free_list.clear();
00472 }
00473
00474 };
00475
00476
#if defined __GTHREADS
00477
_Mutex _BA_free_list_store::_S_bfl_mutex;
00478
#endif
00479
std::vector<unsigned int*> _BA_free_list_store::_S_free_list;
00480
00481
template <
typename _Tp>
class bitmap_allocator;
00482
00483
template <>
class bitmap_allocator<void> {
00484
public:
00485
typedef void* pointer;
00486
typedef const void* const_pointer;
00487
00488
typedef void value_type;
00489
template <
typename _Tp1>
struct rebind {
typedef bitmap_allocator<_Tp1> other; };
00490 };
00491
00492
template <
typename _Tp>
class bitmap_allocator :
private _BA_free_list_store {
00493
public:
00494
typedef size_t size_type;
00495
typedef ptrdiff_t difference_type;
00496
typedef _Tp* pointer;
00497
typedef const _Tp* const_pointer;
00498
typedef _Tp& reference;
00499
typedef const _Tp& const_reference;
00500
typedef _Tp value_type;
00501
template <
typename _Tp1>
struct rebind {
typedef bitmap_allocator<_Tp1> other; };
00502
00503
private:
00504
static const unsigned int _Bits_Per_Byte = 8;
00505
static const unsigned int _Bits_Per_Block =
sizeof(
unsigned int) * _Bits_Per_Byte;
00506
00507
static inline void _S_bit_allocate(
unsigned int *__pbmap,
unsigned int __pos)
throw()
00508 {
00509
unsigned int __mask = 1 << __pos;
00510 __mask = ~__mask;
00511 *__pbmap &= __mask;
00512 }
00513
00514
static inline void _S_bit_free(
unsigned int *__pbmap,
unsigned int __pos)
throw()
00515 {
00516
unsigned int __mask = 1 << __pos;
00517 *__pbmap |= __mask;
00518 }
00519
00520
static inline void *_S_memory_get(size_t __sz)
throw (
std::bad_alloc)
00521 {
00522
return operator new(__sz);
00523 }
00524
00525
static inline void _S_memory_put(
void *__vptr)
throw ()
00526 {
00527
operator delete(__vptr);
00528 }
00529
00530
typedef typename std::pair<pointer, pointer> _Block_pair;
00531
typedef typename __gnu_cxx::new_allocator<_Block_pair> _BPVec_allocator_type;
00532
typedef typename std::vector<_Block_pair, _BPVec_allocator_type> _BPVector;
00533
00534
00535
#if defined CHECK_FOR_ERRORS
00536
00537
00538
static void _S_check_for_free_blocks() throw()
00539 {
00540
typedef typename __gnu_cxx::__aux_balloc::_Ffit_finder<pointer, _BPVec_allocator_type> _FFF;
00541 _FFF __fff;
00542
typedef typename _BPVector::iterator _BPiter;
00543 _BPiter __bpi =
std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(),
00544 __gnu_cxx::__aux_balloc::_Functor_Ref<_FFF>(__fff));
00545 assert(__bpi == _S_mem_blocks.end());
00546 }
00547
#endif
00548
00549
00550
00551
00552
00553
00554
00555
static void _S_refill_pool() throw (std::bad_alloc)
00556 {
00557
#if defined CHECK_FOR_ERRORS
00558
_S_check_for_free_blocks();
00559
#endif
00560
00561
const unsigned int __num_bit_maps = _S_block_size / _Bits_Per_Block;
00562
const unsigned int __size_to_allocate =
sizeof(
unsigned int) +
00563 _S_block_size *
sizeof(value_type) + __num_bit_maps*
sizeof(
unsigned int);
00564
00565
unsigned int *__temp =
00566 reinterpret_cast<unsigned int*>(_BA_free_list_store::_S_get_free_list(__size_to_allocate));
00567 *__temp = 0;
00568 ++__temp;
00569
00570
00571 _Block_pair __bp =
std::make_pair(reinterpret_cast<pointer>(__temp + __num_bit_maps),
00572 reinterpret_cast<pointer>(__temp + __num_bit_maps)
00573 + _S_block_size - 1);
00574
00575
00576 _S_mem_blocks.push_back(__bp);
00577
00578
unsigned int __bit_mask = 0;
00579 __bit_mask = ~__bit_mask;
00580
00581
for (
unsigned int __i = 0; __i < __num_bit_maps; ++__i)
00582 __temp[__i] = __bit_mask;
00583
00584
00585
00586
00587 _S_block_size *= 2;
00588 }
00589
00590
static _BPVector _S_mem_blocks;
00591
static unsigned int _S_block_size;
00592
static __gnu_cxx::__aux_balloc::_Bit_map_counter<pointer, _BPVec_allocator_type> _S_last_request;
00593
static typename _BPVector::size_type _S_last_dealloc_index;
00594
#if defined __GTHREADS
00595
static _Mutex _S_mut;
00596
#endif
00597
00598
00599
00600
00601
00602
00603
00604
static pointer _S_allocate_single_object()
00605 {
00606
#if defined __GTHREADS
00607
_Lock __bit_lock(&_S_mut);
00608
#endif
00609
00610
00611
00612
00613
00614
00615
00616
00617
00618
00619
00620
00621
00622
while (_S_last_request._M_finished() ==
false && (*(_S_last_request._M_get()) == 0))
00623 {
00624 _S_last_request.operator++();
00625 }
00626
00627
if (__builtin_expect(_S_last_request._M_finished() ==
true,
false))
00628 {
00629
00630
typedef typename __gnu_cxx::__aux_balloc::_Ffit_finder<pointer, _BPVec_allocator_type> _FFF;
00631 _FFF __fff;
00632
typedef typename _BPVector::iterator _BPiter;
00633 _BPiter __bpi =
std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(),
00634 __gnu_cxx::__aux_balloc::_Functor_Ref<_FFF>(__fff));
00635
00636
if (__bpi != _S_mem_blocks.end())
00637 {
00638
00639
00640
00641
unsigned int __nz_bit = _Bit_scan_forward(*__fff._M_get());
00642 _S_bit_allocate(__fff._M_get(), __nz_bit);
00643
00644 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
00645
00646
00647 pointer __ret_val = __bpi->first + __fff._M_offset() + __nz_bit;
00648
unsigned int *__puse_count = reinterpret_cast<unsigned int*>(__bpi->first) -
00649 (__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(*__bpi) + 1);
00650 ++(*__puse_count);
00651
return __ret_val;
00652 }
00653
else
00654 {
00655
00656
00657 _S_refill_pool();
00658
00659
00660
00661 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
00662
00663
00664 }
00665 }
00666
00667
00668
unsigned int __nz_bit = _Bit_scan_forward(*_S_last_request._M_get());
00669 _S_bit_allocate(_S_last_request._M_get(), __nz_bit);
00670
00671 pointer __ret_val = _S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit;
00672
00673
unsigned int *__puse_count = reinterpret_cast<unsigned int*>
00674 (_S_mem_blocks[_S_last_request._M_where()].first) -
00675 (__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
00676 ++(*__puse_count);
00677
return __ret_val;
00678 }
00679
00680
00681
00682
00683
static void _S_deallocate_single_object(pointer __p)
throw()
00684 {
00685
#if defined __GTHREADS
00686
_Lock __bit_lock(&_S_mut);
00687
#endif
00688
00689
typedef typename _BPVector::iterator _Iterator;
00690
typedef typename _BPVector::difference_type _Difference_type;
00691
00692 _Difference_type __diff;
00693
int __displacement;
00694
00695 assert(_S_last_dealloc_index >= 0);
00696
00697
if (__gnu_cxx::__aux_balloc::_Inclusive_between<pointer>(__p)(_S_mem_blocks[_S_last_dealloc_index]))
00698 {
00699 assert(_S_last_dealloc_index <= _S_mem_blocks.size() - 1);
00700
00701
00702 __diff = _S_last_dealloc_index;
00703 __displacement = __p - _S_mem_blocks[__diff].first;
00704 }
00705
else
00706 {
00707 _Iterator _iter = (
std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(),
00708 __gnu_cxx::__aux_balloc::_Inclusive_between<pointer>(__p)));
00709 assert(_iter != _S_mem_blocks.end());
00710
00711 __diff = _iter - _S_mem_blocks.begin();
00712 __displacement = __p - _S_mem_blocks[__diff].first;
00713 _S_last_dealloc_index = __diff;
00714 }
00715
00716
00717
const unsigned int __rotate = __displacement % _Bits_Per_Block;
00718
unsigned int *__bit_mapC = reinterpret_cast<unsigned int*>(_S_mem_blocks[__diff].first) - 1;
00719 __bit_mapC -= (__displacement / _Bits_Per_Block);
00720
00721 _S_bit_free(__bit_mapC, __rotate);
00722
unsigned int *__puse_count = reinterpret_cast<unsigned int*>
00723 (_S_mem_blocks[__diff].first) -
00724 (__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(_S_mem_blocks[__diff]) + 1);
00725
00726 assert(*__puse_count != 0);
00727
00728 --(*__puse_count);
00729
00730
if (__builtin_expect(*__puse_count == 0,
false))
00731 {
00732 _S_block_size /= 2;
00733
00734
00735 _Block_pair __bp = _S_mem_blocks[__diff];
00736 _S_insert_free_list(__puse_count);
00737 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
00738
00739
00740
00741
00742
00743
00744
00745
if ((_Difference_type)_S_last_request._M_where() >= __diff--)
00746 {
00747 _S_last_request._M_reset(__diff);
00748
00749 }
00750
00751
00752
00753
00754
00755
00756
if (_S_last_dealloc_index >= _S_mem_blocks.size())
00757 {
00758 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
00759 assert(_S_last_dealloc_index >= 0);
00760 }
00761 }
00762 }
00763
00764
public:
00765 bitmap_allocator() throw()
00766 { }
00767
00768 bitmap_allocator(
const bitmap_allocator&) { }
00769
00770
template <
typename _Tp1> bitmap_allocator(
const bitmap_allocator<_Tp1>&) throw()
00771 { }
00772
00773 ~bitmap_allocator() throw()
00774 { }
00775
00776
00777
00778
00779 pointer allocate(size_type __n)
00780 {
00781
if (__builtin_expect(__n == 1,
true))
00782
return _S_allocate_single_object();
00783
else
00784
return reinterpret_cast<pointer>(_S_memory_get(__n *
sizeof(value_type)));
00785 }
00786
00787
00788
00789
00790
00791
00792
00793
00794 pointer allocate(size_type __n,
typename bitmap_allocator<void>::const_pointer)
00795 {
00796
return allocate(__n);
00797 }
00798
00799
void deallocate(pointer __p, size_type __n)
throw()
00800 {
00801
if (__builtin_expect(__n == 1,
true))
00802 _S_deallocate_single_object(__p);
00803
else
00804 _S_memory_put(__p);
00805 }
00806
00807 pointer address(reference r)
const {
return &r; }
00808 const_pointer address(const_reference r)
const {
return &r; }
00809
00810 size_type max_size(
void) const throw() {
return (size_type()-1)/
sizeof(value_type); }
00811
00812
void construct (pointer p, const_reference __data)
00813 {
00814 ::new(p) value_type(__data);
00815 }
00816
00817
void destroy (pointer p)
00818 {
00819 p->~value_type();
00820 }
00821
00822 };
00823
00824
template <
typename _Tp>
00825
typename bitmap_allocator<_Tp>::_BPVector bitmap_allocator<_Tp>::_S_mem_blocks;
00826
00827
template <
typename _Tp>
00828
unsigned int bitmap_allocator<_Tp>::_S_block_size = bitmap_allocator<_Tp>::_Bits_Per_Block;
00829
00830
template <
typename _Tp>
00831
typename __gnu_cxx::bitmap_allocator<_Tp>::_BPVector::size_type
00832 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
00833
00834
template <
typename _Tp>
00835 __gnu_cxx::__aux_balloc::_Bit_map_counter
00836 <
typename bitmap_allocator<_Tp>::pointer,
typename bitmap_allocator<_Tp>::_BPVec_allocator_type>
00837 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
00838
00839
#if defined __GTHREADS
00840
template <
typename _Tp>
00841 __gnu_cxx::_Mutex
00842 bitmap_allocator<_Tp>::_S_mut;
00843
#endif
00844
00845
template <
typename _Tp1,
typename _Tp2>
00846
bool operator== (
const bitmap_allocator<_Tp1>&,
const bitmap_allocator<_Tp2>&) throw()
00847 {
00848
return true;
00849 }
00850
00851
template <
typename _Tp1,
typename _Tp2>
00852
bool operator!= (
const bitmap_allocator<_Tp1>&,
const bitmap_allocator<_Tp2>&) throw()
00853 {
00854
return false;
00855 }
00856 }
00857
00858
00859
#endif //_BITMAP_ALLOCATOR_H