1169691Skan// Bitmap Allocator. -*- C++ -*- 2132720Skan 3169691Skan// Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. 4132720Skan// 5132720Skan// This file is part of the GNU ISO C++ Library. This library is free 6132720Skan// software; you can redistribute it and/or modify it under the 7132720Skan// terms of the GNU General Public License as published by the 8132720Skan// Free Software Foundation; either version 2, or (at your option) 9132720Skan// any later version. 10132720Skan 11132720Skan// This library is distributed in the hope that it will be useful, 12132720Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 13132720Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14132720Skan// GNU General Public License for more details. 15132720Skan 16132720Skan// You should have received a copy of the GNU General Public License along 17132720Skan// with this library; see the file COPYING. If not, write to the Free 18169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19132720Skan// USA. 20132720Skan 21132720Skan// As a special exception, you may use this file as part of a free software 22132720Skan// library without restriction. Specifically, if other files instantiate 23132720Skan// templates or use macros or inline functions from this file, or you compile 24132720Skan// this file and link it with other files to produce an executable, this 25132720Skan// file does not by itself cause the resulting executable to be covered by 26132720Skan// the GNU General Public License. This exception does not however 27132720Skan// invalidate any other reasons why the executable file might be covered by 28132720Skan// the GNU General Public License. 29132720Skan 30169691Skan/** @file ext/bitmap_allocator.h 31169691Skan * This file is a GNU extension to the Standard C++ Library. 32169691Skan */ 33132720Skan 34169691Skan#ifndef _BITMAP_ALLOCATOR_H 35132720Skan#define _BITMAP_ALLOCATOR_H 1 36132720Skan 37169691Skan#include <cstddef> // For std::size_t, and ptrdiff_t. 38169691Skan#include <bits/functexcept.h> // For __throw_bad_alloc(). 39169691Skan#include <utility> // For std::pair. 40169691Skan#include <functional> // For greater_equal, and less_equal. 41169691Skan#include <new> // For operator new. 42169691Skan#include <debug/debug.h> // _GLIBCXX_DEBUG_ASSERT 43169691Skan#include <ext/concurrence.h> 44132720Skan 45132720Skan 46169691Skan/** @brief The constant in the expression below is the alignment 47169691Skan * required in bytes. 48169691Skan */ 49169691Skan#define _BALLOC_ALIGN_BYTES 8 50132720Skan 51169691Skan_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 52132720Skan 53169691Skan using std::size_t; 54169691Skan using std::ptrdiff_t; 55132720Skan 56169691Skan namespace __detail 57169691Skan { 58169691Skan /** @class __mini_vector bitmap_allocator.h bitmap_allocator.h 59169691Skan * 60169691Skan * @brief __mini_vector<> is a stripped down version of the 61169691Skan * full-fledged std::vector<>. 62169691Skan * 63169691Skan * It is to be used only for built-in types or PODs. Notable 64169691Skan * differences are: 65169691Skan * 66169691Skan * @detail 67169691Skan * 1. Not all accessor functions are present. 68169691Skan * 2. Used ONLY for PODs. 69169691Skan * 3. No Allocator template argument. Uses ::operator new() to get 70169691Skan * memory, and ::operator delete() to free it. 71169691Skan * Caveat: The dtor does NOT free the memory allocated, so this a 72169691Skan * memory-leaking vector! 73169691Skan */ 74169691Skan template<typename _Tp> 75169691Skan class __mini_vector 76169691Skan { 77169691Skan __mini_vector(const __mini_vector&); 78169691Skan __mini_vector& operator=(const __mini_vector&); 79132720Skan 80169691Skan public: 81169691Skan typedef _Tp value_type; 82169691Skan typedef _Tp* pointer; 83169691Skan typedef _Tp& reference; 84169691Skan typedef const _Tp& const_reference; 85169691Skan typedef size_t size_type; 86169691Skan typedef ptrdiff_t difference_type; 87169691Skan typedef pointer iterator; 88169691Skan 89169691Skan private: 90169691Skan pointer _M_start; 91169691Skan pointer _M_finish; 92169691Skan pointer _M_end_of_storage; 93169691Skan 94169691Skan size_type 95169691Skan _M_space_left() const throw() 96169691Skan { return _M_end_of_storage - _M_finish; } 97169691Skan 98169691Skan pointer 99169691Skan allocate(size_type __n) 100169691Skan { return static_cast<pointer>(::operator new(__n * sizeof(_Tp))); } 101169691Skan 102169691Skan void 103169691Skan deallocate(pointer __p, size_type) 104169691Skan { ::operator delete(__p); } 105169691Skan 106169691Skan public: 107169691Skan // Members used: size(), push_back(), pop_back(), 108169691Skan // insert(iterator, const_reference), erase(iterator), 109169691Skan // begin(), end(), back(), operator[]. 110169691Skan 111169691Skan __mini_vector() : _M_start(0), _M_finish(0), 112169691Skan _M_end_of_storage(0) 113169691Skan { } 114169691Skan 115169691Skan#if 0 116169691Skan ~__mini_vector() 117132720Skan { 118169691Skan if (this->_M_start) 119132720Skan { 120169691Skan this->deallocate(this->_M_start, this->_M_end_of_storage 121169691Skan - this->_M_start); 122132720Skan } 123132720Skan } 124132720Skan#endif 125132720Skan 126169691Skan size_type 127169691Skan size() const throw() 128169691Skan { return _M_finish - _M_start; } 129132720Skan 130169691Skan iterator 131169691Skan begin() const throw() 132169691Skan { return this->_M_start; } 133132720Skan 134169691Skan iterator 135169691Skan end() const throw() 136169691Skan { return this->_M_finish; } 137132720Skan 138169691Skan reference 139169691Skan back() const throw() 140169691Skan { return *(this->end() - 1); } 141132720Skan 142169691Skan reference 143169691Skan operator[](const size_type __pos) const throw() 144169691Skan { return this->_M_start[__pos]; } 145132720Skan 146169691Skan void 147169691Skan insert(iterator __pos, const_reference __x); 148132720Skan 149169691Skan void 150169691Skan push_back(const_reference __x) 151169691Skan { 152169691Skan if (this->_M_space_left()) 153169691Skan { 154169691Skan *this->end() = __x; 155169691Skan ++this->_M_finish; 156169691Skan } 157169691Skan else 158169691Skan this->insert(this->end(), __x); 159169691Skan } 160169691Skan 161169691Skan void 162169691Skan pop_back() throw() 163169691Skan { --this->_M_finish; } 164169691Skan 165169691Skan void 166169691Skan erase(iterator __pos) throw(); 167169691Skan 168169691Skan void 169169691Skan clear() throw() 170169691Skan { this->_M_finish = this->_M_start; } 171169691Skan }; 172169691Skan 173169691Skan // Out of line function definitions. 174169691Skan template<typename _Tp> 175169691Skan void __mini_vector<_Tp>:: 176169691Skan insert(iterator __pos, const_reference __x) 177132720Skan { 178169691Skan if (this->_M_space_left()) 179169691Skan { 180169691Skan size_type __to_move = this->_M_finish - __pos; 181169691Skan iterator __dest = this->end(); 182169691Skan iterator __src = this->end() - 1; 183169691Skan 184169691Skan ++this->_M_finish; 185169691Skan while (__to_move) 186169691Skan { 187169691Skan *__dest = *__src; 188169691Skan --__dest; --__src; --__to_move; 189169691Skan } 190169691Skan *__pos = __x; 191169691Skan } 192132720Skan else 193169691Skan { 194169691Skan size_type __new_size = this->size() ? this->size() * 2 : 1; 195169691Skan iterator __new_start = this->allocate(__new_size); 196169691Skan iterator __first = this->begin(); 197169691Skan iterator __start = __new_start; 198169691Skan while (__first != __pos) 199169691Skan { 200169691Skan *__start = *__first; 201169691Skan ++__start; ++__first; 202169691Skan } 203169691Skan *__start = __x; 204169691Skan ++__start; 205169691Skan while (__first != this->end()) 206169691Skan { 207169691Skan *__start = *__first; 208169691Skan ++__start; ++__first; 209169691Skan } 210169691Skan if (this->_M_start) 211169691Skan this->deallocate(this->_M_start, this->size()); 212169691Skan 213169691Skan this->_M_start = __new_start; 214169691Skan this->_M_finish = __start; 215169691Skan this->_M_end_of_storage = this->_M_start + __new_size; 216169691Skan } 217132720Skan } 218132720Skan 219169691Skan template<typename _Tp> 220169691Skan void __mini_vector<_Tp>:: 221169691Skan erase(iterator __pos) throw() 222169691Skan { 223169691Skan while (__pos + 1 != this->end()) 224169691Skan { 225169691Skan *__pos = __pos[1]; 226169691Skan ++__pos; 227169691Skan } 228169691Skan --this->_M_finish; 229169691Skan } 230132720Skan 231132720Skan 232169691Skan template<typename _Tp> 233169691Skan struct __mv_iter_traits 234169691Skan { 235169691Skan typedef typename _Tp::value_type value_type; 236169691Skan typedef typename _Tp::difference_type difference_type; 237169691Skan }; 238132720Skan 239169691Skan template<typename _Tp> 240169691Skan struct __mv_iter_traits<_Tp*> 241169691Skan { 242169691Skan typedef _Tp value_type; 243169691Skan typedef ptrdiff_t difference_type; 244169691Skan }; 245132720Skan 246169691Skan enum 247169691Skan { 248169691Skan bits_per_byte = 8, 249169691Skan bits_per_block = sizeof(size_t) * size_t(bits_per_byte) 250169691Skan }; 251132720Skan 252169691Skan template<typename _ForwardIterator, typename _Tp, typename _Compare> 253169691Skan _ForwardIterator 254169691Skan __lower_bound(_ForwardIterator __first, _ForwardIterator __last, 255169691Skan const _Tp& __val, _Compare __comp) 256132720Skan { 257169691Skan typedef typename __mv_iter_traits<_ForwardIterator>::value_type 258169691Skan _ValueType; 259169691Skan typedef typename __mv_iter_traits<_ForwardIterator>::difference_type 260169691Skan _DistanceType; 261132720Skan 262169691Skan _DistanceType __len = __last - __first; 263169691Skan _DistanceType __half; 264169691Skan _ForwardIterator __middle; 265132720Skan 266169691Skan while (__len > 0) 267132720Skan { 268169691Skan __half = __len >> 1; 269169691Skan __middle = __first; 270169691Skan __middle += __half; 271169691Skan if (__comp(*__middle, __val)) 272132720Skan { 273169691Skan __first = __middle; 274169691Skan ++__first; 275169691Skan __len = __len - __half - 1; 276132720Skan } 277169691Skan else 278169691Skan __len = __half; 279132720Skan } 280169691Skan return __first; 281132720Skan } 282169691Skan 283169691Skan template<typename _InputIterator, typename _Predicate> 284169691Skan inline _InputIterator 285169691Skan __find_if(_InputIterator __first, _InputIterator __last, _Predicate __p) 286169691Skan { 287169691Skan while (__first != __last && !__p(*__first)) 288169691Skan ++__first; 289169691Skan return __first; 290169691Skan } 291169691Skan 292169691Skan /** @brief The number of Blocks pointed to by the address pair 293169691Skan * passed to the function. 294169691Skan */ 295169691Skan template<typename _AddrPair> 296169691Skan inline size_t 297169691Skan __num_blocks(_AddrPair __ap) 298169691Skan { return (__ap.second - __ap.first) + 1; } 299169691Skan 300169691Skan /** @brief The number of Bit-maps pointed to by the address pair 301169691Skan * passed to the function. 302169691Skan */ 303169691Skan template<typename _AddrPair> 304169691Skan inline size_t 305169691Skan __num_bitmaps(_AddrPair __ap) 306169691Skan { return __num_blocks(__ap) / size_t(bits_per_block); } 307169691Skan 308169691Skan // _Tp should be a pointer type. 309169691Skan template<typename _Tp> 310169691Skan class _Inclusive_between 311169691Skan : public std::unary_function<typename std::pair<_Tp, _Tp>, bool> 312169691Skan { 313169691Skan typedef _Tp pointer; 314169691Skan pointer _M_ptr_value; 315169691Skan typedef typename std::pair<_Tp, _Tp> _Block_pair; 316169691Skan 317169691Skan public: 318169691Skan _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr) 319169691Skan { } 320169691Skan 321169691Skan bool 322169691Skan operator()(_Block_pair __bp) const throw() 323169691Skan { 324169691Skan if (std::less_equal<pointer>()(_M_ptr_value, __bp.second) 325169691Skan && std::greater_equal<pointer>()(_M_ptr_value, __bp.first)) 326169691Skan return true; 327169691Skan else 328169691Skan return false; 329169691Skan } 330169691Skan }; 331132720Skan 332169691Skan // Used to pass a Functor to functions by reference. 333169691Skan template<typename _Functor> 334169691Skan class _Functor_Ref 335169691Skan : public std::unary_function<typename _Functor::argument_type, 336169691Skan typename _Functor::result_type> 337169691Skan { 338169691Skan _Functor& _M_fref; 339169691Skan 340169691Skan public: 341169691Skan typedef typename _Functor::argument_type argument_type; 342169691Skan typedef typename _Functor::result_type result_type; 343169691Skan 344169691Skan _Functor_Ref(_Functor& __fref) : _M_fref(__fref) 345169691Skan { } 346169691Skan 347169691Skan result_type 348169691Skan operator()(argument_type __arg) 349169691Skan { return _M_fref(__arg); } 350169691Skan }; 351169691Skan 352169691Skan /** @class _Ffit_finder bitmap_allocator.h bitmap_allocator.h 353169691Skan * 354169691Skan * @brief The class which acts as a predicate for applying the 355169691Skan * first-fit memory allocation policy for the bitmap allocator. 356169691Skan */ 357169691Skan // _Tp should be a pointer type, and _Alloc is the Allocator for 358169691Skan // the vector. 359169691Skan template<typename _Tp> 360169691Skan class _Ffit_finder 361169691Skan : public std::unary_function<typename std::pair<_Tp, _Tp>, bool> 362169691Skan { 363169691Skan typedef typename std::pair<_Tp, _Tp> _Block_pair; 364169691Skan typedef typename __detail::__mini_vector<_Block_pair> _BPVector; 365169691Skan typedef typename _BPVector::difference_type _Counter_type; 366169691Skan 367169691Skan size_t* _M_pbitmap; 368169691Skan _Counter_type _M_data_offset; 369169691Skan 370169691Skan public: 371169691Skan _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0) 372169691Skan { } 373169691Skan 374169691Skan bool 375169691Skan operator()(_Block_pair __bp) throw() 376169691Skan { 377169691Skan // Set the _rover to the last physical location bitmap, 378169691Skan // which is the bitmap which belongs to the first free 379169691Skan // block. Thus, the bitmaps are in exact reverse order of 380169691Skan // the actual memory layout. So, we count down the bimaps, 381169691Skan // which is the same as moving up the memory. 382169691Skan 383169691Skan // If the used count stored at the start of the Bit Map headers 384169691Skan // is equal to the number of Objects that the current Block can 385169691Skan // store, then there is definitely no space for another single 386169691Skan // object, so just return false. 387169691Skan _Counter_type __diff = 388169691Skan __gnu_cxx::__detail::__num_bitmaps(__bp); 389169691Skan 390169691Skan if (*(reinterpret_cast<size_t*> 391169691Skan (__bp.first) - (__diff + 1)) 392169691Skan == __gnu_cxx::__detail::__num_blocks(__bp)) 393169691Skan return false; 394169691Skan 395169691Skan size_t* __rover = reinterpret_cast<size_t*>(__bp.first) - 1; 396169691Skan 397169691Skan for (_Counter_type __i = 0; __i < __diff; ++__i) 398169691Skan { 399169691Skan _M_data_offset = __i; 400169691Skan if (*__rover) 401169691Skan { 402169691Skan _M_pbitmap = __rover; 403169691Skan return true; 404169691Skan } 405169691Skan --__rover; 406169691Skan } 407169691Skan return false; 408169691Skan } 409169691Skan 410132720Skan 411169691Skan size_t* 412169691Skan _M_get() const throw() 413169691Skan { return _M_pbitmap; } 414169691Skan 415169691Skan _Counter_type 416169691Skan _M_offset() const throw() 417169691Skan { return _M_data_offset * size_t(bits_per_block); } 418169691Skan }; 419169691Skan 420169691Skan 421169691Skan /** @class _Bitmap_counter bitmap_allocator.h bitmap_allocator.h 422169691Skan * 423169691Skan * @brief The bitmap counter which acts as the bitmap 424169691Skan * manipulator, and manages the bit-manipulation functions and 425169691Skan * the searching and identification functions on the bit-map. 426169691Skan */ 427169691Skan // _Tp should be a pointer type. 428169691Skan template<typename _Tp> 429169691Skan class _Bitmap_counter 430169691Skan { 431169691Skan typedef typename __detail::__mini_vector<typename std::pair<_Tp, _Tp> > 432169691Skan _BPVector; 433169691Skan typedef typename _BPVector::size_type _Index_type; 434169691Skan typedef _Tp pointer; 435132720Skan 436169691Skan _BPVector& _M_vbp; 437169691Skan size_t* _M_curr_bmap; 438169691Skan size_t* _M_last_bmap_in_block; 439169691Skan _Index_type _M_curr_index; 440132720Skan 441169691Skan public: 442169691Skan // Use the 2nd parameter with care. Make sure that such an 443169691Skan // entry exists in the vector before passing that particular 444169691Skan // index to this ctor. 445169691Skan _Bitmap_counter(_BPVector& Rvbp, long __index = -1) : _M_vbp(Rvbp) 446169691Skan { this->_M_reset(__index); } 447132720Skan 448169691Skan void 449169691Skan _M_reset(long __index = -1) throw() 450169691Skan { 451169691Skan if (__index == -1) 452169691Skan { 453169691Skan _M_curr_bmap = 0; 454169691Skan _M_curr_index = static_cast<_Index_type>(-1); 455169691Skan return; 456169691Skan } 457132720Skan 458169691Skan _M_curr_index = __index; 459169691Skan _M_curr_bmap = reinterpret_cast<size_t*> 460169691Skan (_M_vbp[_M_curr_index].first) - 1; 461169691Skan 462169691Skan _GLIBCXX_DEBUG_ASSERT(__index <= (long)_M_vbp.size() - 1); 463132720Skan 464169691Skan _M_last_bmap_in_block = _M_curr_bmap 465169691Skan - ((_M_vbp[_M_curr_index].second 466169691Skan - _M_vbp[_M_curr_index].first + 1) 467169691Skan / size_t(bits_per_block) - 1); 468169691Skan } 469132720Skan 470169691Skan // Dangerous Function! Use with extreme care. Pass to this 471169691Skan // function ONLY those values that are known to be correct, 472169691Skan // otherwise this will mess up big time. 473169691Skan void 474169691Skan _M_set_internal_bitmap(size_t* __new_internal_marker) throw() 475169691Skan { _M_curr_bmap = __new_internal_marker; } 476132720Skan 477169691Skan bool 478169691Skan _M_finished() const throw() 479169691Skan { return(_M_curr_bmap == 0); } 480132720Skan 481169691Skan _Bitmap_counter& 482169691Skan operator++() throw() 483169691Skan { 484169691Skan if (_M_curr_bmap == _M_last_bmap_in_block) 485169691Skan { 486169691Skan if (++_M_curr_index == _M_vbp.size()) 487132720Skan _M_curr_bmap = 0; 488169691Skan else 489169691Skan this->_M_reset(_M_curr_index); 490169691Skan } 491169691Skan else 492132720Skan --_M_curr_bmap; 493169691Skan return *this; 494169691Skan } 495132720Skan 496169691Skan size_t* 497169691Skan _M_get() const throw() 498169691Skan { return _M_curr_bmap; } 499132720Skan 500169691Skan pointer 501169691Skan _M_base() const throw() 502169691Skan { return _M_vbp[_M_curr_index].first; } 503169691Skan 504169691Skan _Index_type 505169691Skan _M_offset() const throw() 506169691Skan { 507169691Skan return size_t(bits_per_block) 508169691Skan * ((reinterpret_cast<size_t*>(this->_M_base()) 509169691Skan - _M_curr_bmap) - 1); 510169691Skan } 511132720Skan 512169691Skan _Index_type 513169691Skan _M_where() const throw() 514169691Skan { return _M_curr_index; } 515169691Skan }; 516132720Skan 517169691Skan /** @brief Mark a memory address as allocated by re-setting the 518169691Skan * corresponding bit in the bit-map. 519169691Skan */ 520169691Skan inline void 521169691Skan __bit_allocate(size_t* __pbmap, size_t __pos) throw() 522132720Skan { 523169691Skan size_t __mask = 1 << __pos; 524169691Skan __mask = ~__mask; 525169691Skan *__pbmap &= __mask; 526132720Skan } 527169691Skan 528169691Skan /** @brief Mark a memory address as free by setting the 529169691Skan * corresponding bit in the bit-map. 530169691Skan */ 531169691Skan inline void 532169691Skan __bit_free(size_t* __pbmap, size_t __pos) throw() 533132720Skan { 534169691Skan size_t __mask = 1 << __pos; 535169691Skan *__pbmap |= __mask; 536132720Skan } 537169691Skan } // namespace __detail 538132720Skan 539169691Skan /** @brief Generic Version of the bsf instruction. 540169691Skan */ 541169691Skan inline size_t 542169691Skan _Bit_scan_forward(size_t __num) 543169691Skan { return static_cast<size_t>(__builtin_ctzl(__num)); } 544169691Skan 545169691Skan /** @class free_list bitmap_allocator.h bitmap_allocator.h 546169691Skan * 547169691Skan * @brief The free list class for managing chunks of memory to be 548169691Skan * given to and returned by the bitmap_allocator. 549169691Skan */ 550169691Skan class free_list 551169691Skan { 552211755Srpaulo public: 553169691Skan typedef size_t* value_type; 554169691Skan typedef __detail::__mini_vector<value_type> vector_type; 555169691Skan typedef vector_type::iterator iterator; 556169691Skan typedef __mutex __mutex_type; 557169691Skan 558211755Srpaulo private: 559169691Skan struct _LT_pointer_compare 560132720Skan { 561169691Skan bool 562169691Skan operator()(const size_t* __pui, 563169691Skan const size_t __cui) const throw() 564169691Skan { return *__pui < __cui; } 565132720Skan }; 566132720Skan 567132720Skan#if defined __GTHREADS 568169691Skan __mutex_type& 569169691Skan _M_get_mutex() 570169691Skan { 571169691Skan static __mutex_type _S_mutex; 572169691Skan return _S_mutex; 573169691Skan } 574132720Skan#endif 575132720Skan 576169691Skan vector_type& 577169691Skan _M_get_free_list() 578132720Skan { 579169691Skan static vector_type _S_free_list; 580169691Skan return _S_free_list; 581169691Skan } 582169691Skan 583169691Skan /** @brief Performs validation of memory based on their size. 584169691Skan * 585169691Skan * @param __addr The pointer to the memory block to be 586169691Skan * validated. 587169691Skan * 588169691Skan * @detail Validates the memory block passed to this function and 589169691Skan * appropriately performs the action of managing the free list of 590169691Skan * blocks by adding this block to the free list or deleting this 591169691Skan * or larger blocks from the free list. 592169691Skan */ 593169691Skan void 594169691Skan _M_validate(size_t* __addr) throw() 595169691Skan { 596169691Skan vector_type& __free_list = _M_get_free_list(); 597169691Skan const vector_type::size_type __max_size = 64; 598169691Skan if (__free_list.size() >= __max_size) 599132720Skan { 600169691Skan // Ok, the threshold value has been reached. We determine 601169691Skan // which block to remove from the list of free blocks. 602169691Skan if (*__addr >= *__free_list.back()) 603132720Skan { 604169691Skan // Ok, the new block is greater than or equal to the 605169691Skan // last block in the list of free blocks. We just free 606169691Skan // the new block. 607169691Skan ::operator delete(static_cast<void*>(__addr)); 608132720Skan return; 609132720Skan } 610132720Skan else 611132720Skan { 612169691Skan // Deallocate the last block in the list of free lists, 613169691Skan // and insert the new one in it's correct position. 614169691Skan ::operator delete(static_cast<void*>(__free_list.back())); 615169691Skan __free_list.pop_back(); 616132720Skan } 617132720Skan } 618132720Skan 619169691Skan // Just add the block to the list of free lists unconditionally. 620169691Skan iterator __temp = __gnu_cxx::__detail::__lower_bound 621169691Skan (__free_list.begin(), __free_list.end(), 622169691Skan *__addr, _LT_pointer_compare()); 623169691Skan 624169691Skan // We may insert the new free list before _temp; 625169691Skan __free_list.insert(__temp, __addr); 626132720Skan } 627132720Skan 628169691Skan /** @brief Decides whether the wastage of memory is acceptable for 629169691Skan * the current memory request and returns accordingly. 630169691Skan * 631169691Skan * @param __block_size The size of the block available in the free 632169691Skan * list. 633169691Skan * 634169691Skan * @param __required_size The required size of the memory block. 635169691Skan * 636169691Skan * @return true if the wastage incurred is acceptable, else returns 637169691Skan * false. 638169691Skan */ 639169691Skan bool 640169691Skan _M_should_i_give(size_t __block_size, 641169691Skan size_t __required_size) throw() 642132720Skan { 643169691Skan const size_t __max_wastage_percentage = 36; 644132720Skan if (__block_size >= __required_size && 645169691Skan (((__block_size - __required_size) * 100 / __block_size) 646169691Skan < __max_wastage_percentage)) 647132720Skan return true; 648132720Skan else 649132720Skan return false; 650132720Skan } 651132720Skan 652132720Skan public: 653169691Skan /** @brief This function returns the block of memory to the 654169691Skan * internal free list. 655169691Skan * 656169691Skan * @param __addr The pointer to the memory block that was given 657169691Skan * by a call to the _M_get function. 658169691Skan */ 659169691Skan inline void 660169691Skan _M_insert(size_t* __addr) throw() 661132720Skan { 662132720Skan#if defined __GTHREADS 663169691Skan __gnu_cxx::__scoped_lock __bfl_lock(_M_get_mutex()); 664132720Skan#endif 665169691Skan // Call _M_validate to decide what should be done with 666169691Skan // this particular free list. 667169691Skan this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1); 668169691Skan // See discussion as to why this is 1! 669132720Skan } 670132720Skan 671169691Skan /** @brief This function gets a block of memory of the specified 672169691Skan * size from the free list. 673169691Skan * 674169691Skan * @param __sz The size in bytes of the memory required. 675169691Skan * 676169691Skan * @return A pointer to the new memory block of size at least 677169691Skan * equal to that requested. 678169691Skan */ 679169691Skan size_t* 680169691Skan _M_get(size_t __sz) throw(std::bad_alloc); 681132720Skan 682169691Skan /** @brief This function just clears the internal Free List, and 683169691Skan * gives back all the memory to the OS. 684169691Skan */ 685169691Skan void 686169691Skan _M_clear(); 687132720Skan }; 688132720Skan 689132720Skan 690169691Skan // Forward declare the class. 691169691Skan template<typename _Tp> 692169691Skan class bitmap_allocator; 693132720Skan 694169691Skan // Specialize for void: 695169691Skan template<> 696169691Skan class bitmap_allocator<void> 697169691Skan { 698169691Skan public: 699169691Skan typedef void* pointer; 700169691Skan typedef const void* const_pointer; 701132720Skan 702169691Skan // Reference-to-void members are impossible. 703169691Skan typedef void value_type; 704169691Skan template<typename _Tp1> 705169691Skan struct rebind 706169691Skan { 707169691Skan typedef bitmap_allocator<_Tp1> other; 708169691Skan }; 709169691Skan }; 710132720Skan 711169691Skan template<typename _Tp> 712169691Skan class bitmap_allocator : private free_list 713132720Skan { 714169691Skan public: 715169691Skan typedef size_t size_type; 716169691Skan typedef ptrdiff_t difference_type; 717169691Skan typedef _Tp* pointer; 718169691Skan typedef const _Tp* const_pointer; 719169691Skan typedef _Tp& reference; 720169691Skan typedef const _Tp& const_reference; 721169691Skan typedef _Tp value_type; 722169691Skan typedef free_list::__mutex_type __mutex_type; 723132720Skan 724169691Skan template<typename _Tp1> 725169691Skan struct rebind 726169691Skan { 727169691Skan typedef bitmap_allocator<_Tp1> other; 728169691Skan }; 729132720Skan 730169691Skan private: 731169691Skan template<size_t _BSize, size_t _AlignSize> 732169691Skan struct aligned_size 733169691Skan { 734169691Skan enum 735169691Skan { 736169691Skan modulus = _BSize % _AlignSize, 737169691Skan value = _BSize + (modulus ? _AlignSize - (modulus) : 0) 738169691Skan }; 739169691Skan }; 740132720Skan 741169691Skan struct _Alloc_block 742169691Skan { 743169691Skan char __M_unused[aligned_size<sizeof(value_type), 744169691Skan _BALLOC_ALIGN_BYTES>::value]; 745169691Skan }; 746132720Skan 747132720Skan 748169691Skan typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair; 749132720Skan 750169691Skan typedef typename 751169691Skan __detail::__mini_vector<_Block_pair> _BPVector; 752132720Skan 753169691Skan#if defined _GLIBCXX_DEBUG 754169691Skan // Complexity: O(lg(N)). Where, N is the number of block of size 755169691Skan // sizeof(value_type). 756169691Skan void 757169691Skan _S_check_for_free_blocks() throw() 758169691Skan { 759169691Skan typedef typename 760169691Skan __gnu_cxx::__detail::_Ffit_finder<_Alloc_block*> _FFF; 761169691Skan _FFF __fff; 762169691Skan typedef typename _BPVector::iterator _BPiter; 763169691Skan _BPiter __bpi = 764169691Skan __gnu_cxx::__detail::__find_if 765169691Skan (_S_mem_blocks.begin(), _S_mem_blocks.end(), 766169691Skan __gnu_cxx::__detail::_Functor_Ref<_FFF>(__fff)); 767169691Skan 768169691Skan _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end()); 769169691Skan } 770132720Skan#endif 771132720Skan 772169691Skan /** @brief Responsible for exponentially growing the internal 773169691Skan * memory pool. 774169691Skan * 775169691Skan * @throw std::bad_alloc. If memory can not be allocated. 776169691Skan * 777169691Skan * @detail Complexity: O(1), but internally depends upon the 778169691Skan * complexity of the function free_list::_M_get. The part where 779169691Skan * the bitmap headers are written has complexity: O(X),where X 780169691Skan * is the number of blocks of size sizeof(value_type) within 781169691Skan * the newly acquired block. Having a tight bound. 782169691Skan */ 783169691Skan void 784169691Skan _S_refill_pool() throw(std::bad_alloc) 785169691Skan { 786169691Skan#if defined _GLIBCXX_DEBUG 787169691Skan _S_check_for_free_blocks(); 788169691Skan#endif 789132720Skan 790169691Skan const size_t __num_bitmaps = (_S_block_size 791169691Skan / size_t(__detail::bits_per_block)); 792169691Skan const size_t __size_to_allocate = sizeof(size_t) 793169691Skan + _S_block_size * sizeof(_Alloc_block) 794169691Skan + __num_bitmaps * sizeof(size_t); 795132720Skan 796169691Skan size_t* __temp = 797169691Skan reinterpret_cast<size_t*> 798169691Skan (this->_M_get(__size_to_allocate)); 799169691Skan *__temp = 0; 800169691Skan ++__temp; 801132720Skan 802169691Skan // The Header information goes at the Beginning of the Block. 803169691Skan _Block_pair __bp = 804169691Skan std::make_pair(reinterpret_cast<_Alloc_block*> 805169691Skan (__temp + __num_bitmaps), 806169691Skan reinterpret_cast<_Alloc_block*> 807169691Skan (__temp + __num_bitmaps) 808169691Skan + _S_block_size - 1); 809169691Skan 810169691Skan // Fill the Vector with this information. 811169691Skan _S_mem_blocks.push_back(__bp); 812132720Skan 813169691Skan size_t __bit_mask = 0; // 0 Indicates all Allocated. 814169691Skan __bit_mask = ~__bit_mask; // 1 Indicates all Free. 815132720Skan 816169691Skan for (size_t __i = 0; __i < __num_bitmaps; ++__i) 817169691Skan __temp[__i] = __bit_mask; 818132720Skan 819169691Skan _S_block_size *= 2; 820169691Skan } 821132720Skan 822169691Skan 823169691Skan static _BPVector _S_mem_blocks; 824169691Skan static size_t _S_block_size; 825169691Skan static __gnu_cxx::__detail:: 826169691Skan _Bitmap_counter<_Alloc_block*> _S_last_request; 827169691Skan static typename _BPVector::size_type _S_last_dealloc_index; 828132720Skan#if defined __GTHREADS 829169691Skan static __mutex_type _S_mut; 830132720Skan#endif 831132720Skan 832169691Skan public: 833169691Skan 834169691Skan /** @brief Allocates memory for a single object of size 835169691Skan * sizeof(_Tp). 836169691Skan * 837169691Skan * @throw std::bad_alloc. If memory can not be allocated. 838169691Skan * 839169691Skan * @detail Complexity: Worst case complexity is O(N), but that 840169691Skan * is hardly ever hit. If and when this particular case is 841169691Skan * encountered, the next few cases are guaranteed to have a 842169691Skan * worst case complexity of O(1)! That's why this function 843169691Skan * performs very well on average. You can consider this 844169691Skan * function to have a complexity referred to commonly as: 845169691Skan * Amortized Constant time. 846169691Skan */ 847169691Skan pointer 848169691Skan _M_allocate_single_object() throw(std::bad_alloc) 849169691Skan { 850132720Skan#if defined __GTHREADS 851169691Skan __gnu_cxx::__scoped_lock __bit_lock(_S_mut); 852132720Skan#endif 853132720Skan 854169691Skan // The algorithm is something like this: The last_request 855169691Skan // variable points to the last accessed Bit Map. When such a 856169691Skan // condition occurs, we try to find a free block in the 857169691Skan // current bitmap, or succeeding bitmaps until the last bitmap 858169691Skan // is reached. If no free block turns up, we resort to First 859169691Skan // Fit method. 860132720Skan 861169691Skan // WARNING: Do not re-order the condition in the while 862169691Skan // statement below, because it relies on C++'s short-circuit 863169691Skan // evaluation. The return from _S_last_request->_M_get() will 864169691Skan // NOT be dereference able if _S_last_request->_M_finished() 865169691Skan // returns true. This would inevitably lead to a NULL pointer 866169691Skan // dereference if tinkered with. 867169691Skan while (_S_last_request._M_finished() == false 868169691Skan && (*(_S_last_request._M_get()) == 0)) 869169691Skan { 870169691Skan _S_last_request.operator++(); 871169691Skan } 872132720Skan 873169691Skan if (__builtin_expect(_S_last_request._M_finished() == true, false)) 874169691Skan { 875169691Skan // Fall Back to First Fit algorithm. 876169691Skan typedef typename 877169691Skan __gnu_cxx::__detail::_Ffit_finder<_Alloc_block*> _FFF; 878169691Skan _FFF __fff; 879169691Skan typedef typename _BPVector::iterator _BPiter; 880169691Skan _BPiter __bpi = 881169691Skan __gnu_cxx::__detail::__find_if 882169691Skan (_S_mem_blocks.begin(), _S_mem_blocks.end(), 883169691Skan __gnu_cxx::__detail::_Functor_Ref<_FFF>(__fff)); 884132720Skan 885169691Skan if (__bpi != _S_mem_blocks.end()) 886169691Skan { 887169691Skan // Search was successful. Ok, now mark the first bit from 888169691Skan // the right as 0, meaning Allocated. This bit is obtained 889169691Skan // by calling _M_get() on __fff. 890169691Skan size_t __nz_bit = _Bit_scan_forward(*__fff._M_get()); 891169691Skan __detail::__bit_allocate(__fff._M_get(), __nz_bit); 892132720Skan 893169691Skan _S_last_request._M_reset(__bpi - _S_mem_blocks.begin()); 894132720Skan 895169691Skan // Now, get the address of the bit we marked as allocated. 896169691Skan pointer __ret = reinterpret_cast<pointer> 897169691Skan (__bpi->first + __fff._M_offset() + __nz_bit); 898169691Skan size_t* __puse_count = 899169691Skan reinterpret_cast<size_t*> 900169691Skan (__bpi->first) 901169691Skan - (__gnu_cxx::__detail::__num_bitmaps(*__bpi) + 1); 902169691Skan 903169691Skan ++(*__puse_count); 904169691Skan return __ret; 905169691Skan } 906169691Skan else 907169691Skan { 908169691Skan // Search was unsuccessful. We Add more memory to the 909169691Skan // pool by calling _S_refill_pool(). 910169691Skan _S_refill_pool(); 911132720Skan 912169691Skan // _M_Reset the _S_last_request structure to the first 913169691Skan // free block's bit map. 914169691Skan _S_last_request._M_reset(_S_mem_blocks.size() - 1); 915132720Skan 916169691Skan // Now, mark that bit as allocated. 917169691Skan } 918169691Skan } 919132720Skan 920169691Skan // _S_last_request holds a pointer to a valid bit map, that 921169691Skan // points to a free block in memory. 922169691Skan size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get()); 923169691Skan __detail::__bit_allocate(_S_last_request._M_get(), __nz_bit); 924132720Skan 925169691Skan pointer __ret = reinterpret_cast<pointer> 926169691Skan (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit); 927132720Skan 928169691Skan size_t* __puse_count = reinterpret_cast<size_t*> 929169691Skan (_S_mem_blocks[_S_last_request._M_where()].first) 930169691Skan - (__gnu_cxx::__detail:: 931169691Skan __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1); 932169691Skan 933169691Skan ++(*__puse_count); 934169691Skan return __ret; 935169691Skan } 936169691Skan 937169691Skan /** @brief Deallocates memory that belongs to a single object of 938169691Skan * size sizeof(_Tp). 939169691Skan * 940169691Skan * @detail Complexity: O(lg(N)), but the worst case is not hit 941169691Skan * often! This is because containers usually deallocate memory 942169691Skan * close to each other and this case is handled in O(1) time by 943169691Skan * the deallocate function. 944169691Skan */ 945169691Skan void 946169691Skan _M_deallocate_single_object(pointer __p) throw() 947169691Skan { 948132720Skan#if defined __GTHREADS 949169691Skan __gnu_cxx::__scoped_lock __bit_lock(_S_mut); 950132720Skan#endif 951169691Skan _Alloc_block* __real_p = reinterpret_cast<_Alloc_block*>(__p); 952132720Skan 953169691Skan typedef typename _BPVector::iterator _Iterator; 954169691Skan typedef typename _BPVector::difference_type _Difference_type; 955132720Skan 956169691Skan _Difference_type __diff; 957169691Skan long __displacement; 958132720Skan 959169691Skan _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0); 960132720Skan 961169691Skan 962169691Skan if (__gnu_cxx::__detail::_Inclusive_between<_Alloc_block*> 963169691Skan (__real_p) (_S_mem_blocks[_S_last_dealloc_index])) 964169691Skan { 965169691Skan _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index 966169691Skan <= _S_mem_blocks.size() - 1); 967132720Skan 968169691Skan // Initial Assumption was correct! 969169691Skan __diff = _S_last_dealloc_index; 970169691Skan __displacement = __real_p - _S_mem_blocks[__diff].first; 971169691Skan } 972169691Skan else 973169691Skan { 974169691Skan _Iterator _iter = __gnu_cxx::__detail:: 975169691Skan __find_if(_S_mem_blocks.begin(), 976169691Skan _S_mem_blocks.end(), 977169691Skan __gnu_cxx::__detail:: 978169691Skan _Inclusive_between<_Alloc_block*>(__real_p)); 979132720Skan 980169691Skan _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end()); 981132720Skan 982169691Skan __diff = _iter - _S_mem_blocks.begin(); 983169691Skan __displacement = __real_p - _S_mem_blocks[__diff].first; 984169691Skan _S_last_dealloc_index = __diff; 985169691Skan } 986169691Skan 987169691Skan // Get the position of the iterator that has been found. 988169691Skan const size_t __rotate = (__displacement 989169691Skan % size_t(__detail::bits_per_block)); 990169691Skan size_t* __bitmapC = 991169691Skan reinterpret_cast<size_t*> 992169691Skan (_S_mem_blocks[__diff].first) - 1; 993169691Skan __bitmapC -= (__displacement / size_t(__detail::bits_per_block)); 994132720Skan 995169691Skan __detail::__bit_free(__bitmapC, __rotate); 996169691Skan size_t* __puse_count = reinterpret_cast<size_t*> 997169691Skan (_S_mem_blocks[__diff].first) 998169691Skan - (__gnu_cxx::__detail::__num_bitmaps(_S_mem_blocks[__diff]) + 1); 999169691Skan 1000169691Skan _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0); 1001132720Skan 1002169691Skan --(*__puse_count); 1003132720Skan 1004169691Skan if (__builtin_expect(*__puse_count == 0, false)) 1005169691Skan { 1006169691Skan _S_block_size /= 2; 1007132720Skan 1008169691Skan // We can safely remove this block. 1009169691Skan // _Block_pair __bp = _S_mem_blocks[__diff]; 1010169691Skan this->_M_insert(__puse_count); 1011169691Skan _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff); 1012132720Skan 1013169691Skan // Reset the _S_last_request variable to reflect the 1014169691Skan // erased block. We do this to protect future requests 1015169691Skan // after the last block has been removed from a particular 1016169691Skan // memory Chunk, which in turn has been returned to the 1017169691Skan // free list, and hence had been erased from the vector, 1018169691Skan // so the size of the vector gets reduced by 1. 1019169691Skan if ((_Difference_type)_S_last_request._M_where() >= __diff--) 1020169691Skan _S_last_request._M_reset(__diff); 1021132720Skan 1022169691Skan // If the Index into the vector of the region of memory 1023169691Skan // that might hold the next address that will be passed to 1024169691Skan // deallocated may have been invalidated due to the above 1025169691Skan // erase procedure being called on the vector, hence we 1026169691Skan // try to restore this invariant too. 1027169691Skan if (_S_last_dealloc_index >= _S_mem_blocks.size()) 1028169691Skan { 1029169691Skan _S_last_dealloc_index =(__diff != -1 ? __diff : 0); 1030169691Skan _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0); 1031169691Skan } 1032169691Skan } 1033169691Skan } 1034132720Skan 1035169691Skan public: 1036169691Skan bitmap_allocator() throw() 1037169691Skan { } 1038132720Skan 1039169691Skan bitmap_allocator(const bitmap_allocator&) 1040169691Skan { } 1041132720Skan 1042169691Skan template<typename _Tp1> 1043169691Skan bitmap_allocator(const bitmap_allocator<_Tp1>&) throw() 1044169691Skan { } 1045132720Skan 1046169691Skan ~bitmap_allocator() throw() 1047169691Skan { } 1048132720Skan 1049169691Skan pointer 1050169691Skan allocate(size_type __n) 1051169691Skan { 1052169691Skan if (__builtin_expect(__n > this->max_size(), false)) 1053169691Skan std::__throw_bad_alloc(); 1054132720Skan 1055169691Skan if (__builtin_expect(__n == 1, true)) 1056169691Skan return this->_M_allocate_single_object(); 1057169691Skan else 1058169691Skan { 1059169691Skan const size_type __b = __n * sizeof(value_type); 1060169691Skan return reinterpret_cast<pointer>(::operator new(__b)); 1061169691Skan } 1062169691Skan } 1063132720Skan 1064169691Skan pointer 1065169691Skan allocate(size_type __n, typename bitmap_allocator<void>::const_pointer) 1066169691Skan { return allocate(__n); } 1067132720Skan 1068169691Skan void 1069169691Skan deallocate(pointer __p, size_type __n) throw() 1070169691Skan { 1071169691Skan if (__builtin_expect(__p != 0, true)) 1072169691Skan { 1073169691Skan if (__builtin_expect(__n == 1, true)) 1074169691Skan this->_M_deallocate_single_object(__p); 1075169691Skan else 1076169691Skan ::operator delete(__p); 1077169691Skan } 1078169691Skan } 1079132720Skan 1080169691Skan pointer 1081169691Skan address(reference __r) const 1082169691Skan { return &__r; } 1083132720Skan 1084169691Skan const_pointer 1085169691Skan address(const_reference __r) const 1086169691Skan { return &__r; } 1087132720Skan 1088169691Skan size_type 1089169691Skan max_size() const throw() 1090169691Skan { return size_type(-1) / sizeof(value_type); } 1091132720Skan 1092169691Skan void 1093169691Skan construct(pointer __p, const_reference __data) 1094169691Skan { ::new(__p) value_type(__data); } 1095132720Skan 1096169691Skan void 1097169691Skan destroy(pointer __p) 1098169691Skan { __p->~value_type(); } 1099169691Skan }; 1100132720Skan 1101169691Skan template<typename _Tp1, typename _Tp2> 1102169691Skan bool 1103169691Skan operator==(const bitmap_allocator<_Tp1>&, 1104169691Skan const bitmap_allocator<_Tp2>&) throw() 1105169691Skan { return true; } 1106169691Skan 1107169691Skan template<typename _Tp1, typename _Tp2> 1108169691Skan bool 1109169691Skan operator!=(const bitmap_allocator<_Tp1>&, 1110169691Skan const bitmap_allocator<_Tp2>&) throw() 1111169691Skan { return false; } 1112132720Skan 1113169691Skan // Static member definitions. 1114169691Skan template<typename _Tp> 1115169691Skan typename bitmap_allocator<_Tp>::_BPVector 1116169691Skan bitmap_allocator<_Tp>::_S_mem_blocks; 1117132720Skan 1118169691Skan template<typename _Tp> 1119169691Skan size_t bitmap_allocator<_Tp>::_S_block_size = 1120169691Skan 2 * size_t(__detail::bits_per_block); 1121132720Skan 1122169691Skan template<typename _Tp> 1123169691Skan typename __gnu_cxx::bitmap_allocator<_Tp>::_BPVector::size_type 1124169691Skan bitmap_allocator<_Tp>::_S_last_dealloc_index = 0; 1125169691Skan 1126169691Skan template<typename _Tp> 1127169691Skan __gnu_cxx::__detail::_Bitmap_counter 1128169691Skan <typename bitmap_allocator<_Tp>::_Alloc_block*> 1129169691Skan bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks); 1130169691Skan 1131132720Skan#if defined __GTHREADS 1132169691Skan template<typename _Tp> 1133169691Skan typename bitmap_allocator<_Tp>::__mutex_type 1134169691Skan bitmap_allocator<_Tp>::_S_mut; 1135132720Skan#endif 1136132720Skan 1137169691Skan_GLIBCXX_END_NAMESPACE 1138132720Skan 1139169691Skan#endif 1140132720Skan 1141