OSDN Git Service

f6790d00043420dc644ba7c5e79cb107a58ab3b0
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / ext / bitmap_allocator.h
1 // Bitmap Allocator. -*- C++ -*-
2
3 // Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library.  This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 // GNU General Public License for more details.
16
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24 // <http://www.gnu.org/licenses/>.
25
26 /** @file ext/bitmap_allocator.h
27  *  This file is a GNU extension to the Standard C++ Library.
28  */
29
30 #ifndef _BITMAP_ALLOCATOR_H
31 #define _BITMAP_ALLOCATOR_H 1
32
33 #include <cstddef> // For std::size_t, and ptrdiff_t.
34 #include <bits/functexcept.h> // For __throw_bad_alloc().
35 #include <utility> // For std::pair.
36 #include <functional> // For greater_equal, and less_equal.
37 #include <new> // For operator new.
38 #include <debug/debug.h> // _GLIBCXX_DEBUG_ASSERT
39 #include <ext/concurrence.h>
40 #include <bits/move.h>
41
42 /** @brief The constant in the expression below is the alignment
43  * required in bytes.
44  */
45 #define _BALLOC_ALIGN_BYTES 8
46
47 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
48
49   using std::size_t;
50   using std::ptrdiff_t;
51
52   namespace __detail
53   {
54     /** @class  __mini_vector bitmap_allocator.h bitmap_allocator.h
55      *
56      *  @brief  __mini_vector<> is a stripped down version of the
57      *  full-fledged std::vector<>.
58      *
59      *  It is to be used only for built-in types or PODs. Notable
60      *  differences are:
61      * 
62      *  @detail
63      *  1. Not all accessor functions are present.
64      *  2. Used ONLY for PODs.
65      *  3. No Allocator template argument. Uses ::operator new() to get
66      *  memory, and ::operator delete() to free it.
67      *  Caveat: The dtor does NOT free the memory allocated, so this a
68      *  memory-leaking vector!
69      */
70     template<typename _Tp>
71       class __mini_vector
72       {
73         __mini_vector(const __mini_vector&);
74         __mini_vector& operator=(const __mini_vector&);
75
76       public:
77         typedef _Tp value_type;
78         typedef _Tp* pointer;
79         typedef _Tp& reference;
80         typedef const _Tp& const_reference;
81         typedef size_t size_type;
82         typedef ptrdiff_t difference_type;
83         typedef pointer iterator;
84
85       private:
86         pointer _M_start;
87         pointer _M_finish;
88         pointer _M_end_of_storage;
89
90         size_type
91         _M_space_left() const throw()
92         { return _M_end_of_storage - _M_finish; }
93
94         pointer
95         allocate(size_type __n)
96         { return static_cast<pointer>(::operator new(__n * sizeof(_Tp))); }
97
98         void
99         deallocate(pointer __p, size_type)
100         { ::operator delete(__p); }
101
102       public:
103         // Members used: size(), push_back(), pop_back(),
104         // insert(iterator, const_reference), erase(iterator),
105         // begin(), end(), back(), operator[].
106
107         __mini_vector() : _M_start(0), _M_finish(0), 
108                           _M_end_of_storage(0)
109         { }
110
111 #if 0
112         ~__mini_vector()
113         {
114           if (this->_M_start)
115             {
116               this->deallocate(this->_M_start, this->_M_end_of_storage 
117                                - this->_M_start);
118             }
119         }
120 #endif
121
122         size_type
123         size() const throw()
124         { return _M_finish - _M_start; }
125
126         iterator
127         begin() const throw()
128         { return this->_M_start; }
129
130         iterator
131         end() const throw()
132         { return this->_M_finish; }
133
134         reference
135         back() const throw()
136         { return *(this->end() - 1); }
137
138         reference
139         operator[](const size_type __pos) const throw()
140         { return this->_M_start[__pos]; }
141
142         void
143         insert(iterator __pos, const_reference __x);
144
145         void
146         push_back(const_reference __x)
147         {
148           if (this->_M_space_left())
149             {
150               *this->end() = __x;
151               ++this->_M_finish;
152             }
153           else
154             this->insert(this->end(), __x);
155         }
156
157         void
158         pop_back() throw()
159         { --this->_M_finish; }
160
161         void
162         erase(iterator __pos) throw();
163
164         void
165         clear() throw()
166         { this->_M_finish = this->_M_start; }
167       };
168
169     // Out of line function definitions.
170     template<typename _Tp>
171       void __mini_vector<_Tp>::
172       insert(iterator __pos, const_reference __x)
173       {
174         if (this->_M_space_left())
175           {
176             size_type __to_move = this->_M_finish - __pos;
177             iterator __dest = this->end();
178             iterator __src = this->end() - 1;
179
180             ++this->_M_finish;
181             while (__to_move)
182               {
183                 *__dest = *__src;
184                 --__dest; --__src; --__to_move;
185               }
186             *__pos = __x;
187           }
188         else
189           {
190             size_type __new_size = this->size() ? this->size() * 2 : 1;
191             iterator __new_start = this->allocate(__new_size);
192             iterator __first = this->begin();
193             iterator __start = __new_start;
194             while (__first != __pos)
195               {
196                 *__start = *__first;
197                 ++__start; ++__first;
198               }
199             *__start = __x;
200             ++__start;
201             while (__first != this->end())
202               {
203                 *__start = *__first;
204                 ++__start; ++__first;
205               }
206             if (this->_M_start)
207               this->deallocate(this->_M_start, this->size());
208
209             this->_M_start = __new_start;
210             this->_M_finish = __start;
211             this->_M_end_of_storage = this->_M_start + __new_size;
212           }
213       }
214
215     template<typename _Tp>
216       void __mini_vector<_Tp>::
217       erase(iterator __pos) throw()
218       {
219         while (__pos + 1 != this->end())
220           {
221             *__pos = __pos[1];
222             ++__pos;
223           }
224         --this->_M_finish;
225       }
226
227
228     template<typename _Tp>
229       struct __mv_iter_traits
230       {
231         typedef typename _Tp::value_type value_type;
232         typedef typename _Tp::difference_type difference_type;
233       };
234
235     template<typename _Tp>
236       struct __mv_iter_traits<_Tp*>
237       {
238         typedef _Tp value_type;
239         typedef ptrdiff_t difference_type;
240       };
241
242     enum 
243       { 
244         bits_per_byte = 8,
245         bits_per_block = sizeof(size_t) * size_t(bits_per_byte) 
246       };
247
248     template<typename _ForwardIterator, typename _Tp, typename _Compare>
249       _ForwardIterator
250       __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
251                     const _Tp& __val, _Compare __comp)
252       {
253         typedef typename __mv_iter_traits<_ForwardIterator>::value_type
254           _ValueType;
255         typedef typename __mv_iter_traits<_ForwardIterator>::difference_type
256           _DistanceType;
257
258         _DistanceType __len = __last - __first;
259         _DistanceType __half;
260         _ForwardIterator __middle;
261
262         while (__len > 0)
263           {
264             __half = __len >> 1;
265             __middle = __first;
266             __middle += __half;
267             if (__comp(*__middle, __val))
268               {
269                 __first = __middle;
270                 ++__first;
271                 __len = __len - __half - 1;
272               }
273             else
274               __len = __half;
275           }
276         return __first;
277       }
278
279     template<typename _InputIterator, typename _Predicate>
280       inline _InputIterator
281       __find_if(_InputIterator __first, _InputIterator __last, _Predicate __p)
282       {
283         while (__first != __last && !__p(*__first))
284           ++__first;
285         return __first;
286       }
287
288     /** @brief The number of Blocks pointed to by the address pair
289      *  passed to the function.
290      */
291     template<typename _AddrPair>
292       inline size_t
293       __num_blocks(_AddrPair __ap)
294       { return (__ap.second - __ap.first) + 1; }
295
296     /** @brief The number of Bit-maps pointed to by the address pair
297      *  passed to the function.
298      */
299     template<typename _AddrPair>
300       inline size_t
301       __num_bitmaps(_AddrPair __ap)
302       { return __num_blocks(__ap) / size_t(bits_per_block); }
303
304     // _Tp should be a pointer type.
305     template<typename _Tp>
306       class _Inclusive_between 
307       : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
308       {
309         typedef _Tp pointer;
310         pointer _M_ptr_value;
311         typedef typename std::pair<_Tp, _Tp> _Block_pair;
312         
313       public:
314         _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr) 
315         { }
316         
317         bool 
318         operator()(_Block_pair __bp) const throw()
319         {
320           if (std::less_equal<pointer>()(_M_ptr_value, __bp.second) 
321               && std::greater_equal<pointer>()(_M_ptr_value, __bp.first))
322             return true;
323           else
324             return false;
325         }
326       };
327   
328     // Used to pass a Functor to functions by reference.
329     template<typename _Functor>
330       class _Functor_Ref 
331       : public std::unary_function<typename _Functor::argument_type, 
332                                    typename _Functor::result_type>
333       {
334         _Functor& _M_fref;
335         
336       public:
337         typedef typename _Functor::argument_type argument_type;
338         typedef typename _Functor::result_type result_type;
339
340         _Functor_Ref(_Functor& __fref) : _M_fref(__fref) 
341         { }
342
343         result_type 
344         operator()(argument_type __arg) 
345         { return _M_fref(__arg); }
346       };
347
348     /** @class  _Ffit_finder bitmap_allocator.h bitmap_allocator.h
349      *
350      *  @brief  The class which acts as a predicate for applying the
351      *  first-fit memory allocation policy for the bitmap allocator.
352      */
353     // _Tp should be a pointer type, and _Alloc is the Allocator for
354     // the vector.
355     template<typename _Tp>
356       class _Ffit_finder 
357       : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
358       {
359         typedef typename std::pair<_Tp, _Tp> _Block_pair;
360         typedef typename __detail::__mini_vector<_Block_pair> _BPVector;
361         typedef typename _BPVector::difference_type _Counter_type;
362
363         size_t* _M_pbitmap;
364         _Counter_type _M_data_offset;
365
366       public:
367         _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0)
368         { }
369
370         bool 
371         operator()(_Block_pair __bp) throw()
372         {
373           // Set the _rover to the last physical location bitmap,
374           // which is the bitmap which belongs to the first free
375           // block. Thus, the bitmaps are in exact reverse order of
376           // the actual memory layout. So, we count down the bitmaps,
377           // which is the same as moving up the memory.
378
379           // If the used count stored at the start of the Bit Map headers
380           // is equal to the number of Objects that the current Block can
381           // store, then there is definitely no space for another single
382           // object, so just return false.
383           _Counter_type __diff = 
384             __gnu_cxx::__detail::__num_bitmaps(__bp);
385
386           if (*(reinterpret_cast<size_t*>
387                 (__bp.first) - (__diff + 1))
388               == __gnu_cxx::__detail::__num_blocks(__bp))
389             return false;
390
391           size_t* __rover = reinterpret_cast<size_t*>(__bp.first) - 1;
392
393           for (_Counter_type __i = 0; __i < __diff; ++__i)
394             {
395               _M_data_offset = __i;
396               if (*__rover)
397                 {
398                   _M_pbitmap = __rover;
399                   return true;
400                 }
401               --__rover;
402             }
403           return false;
404         }
405
406     
407         size_t*
408         _M_get() const throw()
409         { return _M_pbitmap; }
410
411         _Counter_type
412         _M_offset() const throw()
413         { return _M_data_offset * size_t(bits_per_block); }
414       };
415
416
417     /** @class  _Bitmap_counter bitmap_allocator.h bitmap_allocator.h
418      *
419      *  @brief  The bitmap counter which acts as the bitmap
420      *  manipulator, and manages the bit-manipulation functions and
421      *  the searching and identification functions on the bit-map.
422      */
423     // _Tp should be a pointer type.
424     template<typename _Tp>
425       class _Bitmap_counter
426       {
427         typedef typename __detail::__mini_vector<typename std::pair<_Tp, _Tp> >
428         _BPVector;
429         typedef typename _BPVector::size_type _Index_type;
430         typedef _Tp pointer;
431     
432         _BPVector& _M_vbp;
433         size_t* _M_curr_bmap;
434         size_t* _M_last_bmap_in_block;
435         _Index_type _M_curr_index;
436     
437       public:
438         // Use the 2nd parameter with care. Make sure that such an
439         // entry exists in the vector before passing that particular
440         // index to this ctor.
441         _Bitmap_counter(_BPVector& Rvbp, long __index = -1) : _M_vbp(Rvbp)
442         { this->_M_reset(__index); }
443     
444         void 
445         _M_reset(long __index = -1) throw()
446         {
447           if (__index == -1)
448             {
449               _M_curr_bmap = 0;
450               _M_curr_index = static_cast<_Index_type>(-1);
451               return;
452             }
453
454           _M_curr_index = __index;
455           _M_curr_bmap = reinterpret_cast<size_t*>
456             (_M_vbp[_M_curr_index].first) - 1;
457           
458           _GLIBCXX_DEBUG_ASSERT(__index <= (long)_M_vbp.size() - 1);
459         
460           _M_last_bmap_in_block = _M_curr_bmap
461             - ((_M_vbp[_M_curr_index].second 
462                 - _M_vbp[_M_curr_index].first + 1) 
463                / size_t(bits_per_block) - 1);
464         }
465     
466         // Dangerous Function! Use with extreme care. Pass to this
467         // function ONLY those values that are known to be correct,
468         // otherwise this will mess up big time.
469         void
470         _M_set_internal_bitmap(size_t* __new_internal_marker) throw()
471         { _M_curr_bmap = __new_internal_marker; }
472     
473         bool
474         _M_finished() const throw()
475         { return(_M_curr_bmap == 0); }
476     
477         _Bitmap_counter&
478         operator++() throw()
479         {
480           if (_M_curr_bmap == _M_last_bmap_in_block)
481             {
482               if (++_M_curr_index == _M_vbp.size())
483                 _M_curr_bmap = 0;
484               else
485                 this->_M_reset(_M_curr_index);
486             }
487           else
488             --_M_curr_bmap;
489           return *this;
490         }
491     
492         size_t*
493         _M_get() const throw()
494         { return _M_curr_bmap; }
495     
496         pointer 
497         _M_base() const throw()
498         { return _M_vbp[_M_curr_index].first; }
499
500         _Index_type
501         _M_offset() const throw()
502         {
503           return size_t(bits_per_block)
504             * ((reinterpret_cast<size_t*>(this->_M_base()) 
505                 - _M_curr_bmap) - 1);
506         }
507     
508         _Index_type
509         _M_where() const throw()
510         { return _M_curr_index; }
511       };
512
513     /** @brief  Mark a memory address as allocated by re-setting the
514      *  corresponding bit in the bit-map.
515      */
516     inline void 
517     __bit_allocate(size_t* __pbmap, size_t __pos) throw()
518     {
519       size_t __mask = 1 << __pos;
520       __mask = ~__mask;
521       *__pbmap &= __mask;
522     }
523   
524     /** @brief  Mark a memory address as free by setting the
525      *  corresponding bit in the bit-map.
526      */
527     inline void 
528     __bit_free(size_t* __pbmap, size_t __pos) throw()
529     {
530       size_t __mask = 1 << __pos;
531       *__pbmap |= __mask;
532     }
533   } // namespace __detail
534
535   /** @brief  Generic Version of the bsf instruction.
536    */
537   inline size_t 
538   _Bit_scan_forward(size_t __num)
539   { return static_cast<size_t>(__builtin_ctzl(__num)); }
540
541   /** @class  free_list bitmap_allocator.h bitmap_allocator.h
542    *
543    *  @brief  The free list class for managing chunks of memory to be
544    *  given to and returned by the bitmap_allocator.
545    */
546   class free_list
547   {
548   public:
549     typedef size_t*                             value_type;
550     typedef __detail::__mini_vector<value_type> vector_type;
551     typedef vector_type::iterator               iterator;
552     typedef __mutex                             __mutex_type;
553
554   private:
555     struct _LT_pointer_compare
556     {
557       bool
558       operator()(const size_t* __pui, 
559                  const size_t __cui) const throw()
560       { return *__pui < __cui; }
561     };
562
563 #if defined __GTHREADS
564     __mutex_type&
565     _M_get_mutex()
566     {
567       static __mutex_type _S_mutex;
568       return _S_mutex;
569     }
570 #endif
571
572     vector_type&
573     _M_get_free_list()
574     {
575       static vector_type _S_free_list;
576       return _S_free_list;
577     }
578
579     /** @brief  Performs validation of memory based on their size.
580      *
581      *  @param  __addr The pointer to the memory block to be
582      *  validated.
583      *
584      *  @detail  Validates the memory block passed to this function and
585      *  appropriately performs the action of managing the free list of
586      *  blocks by adding this block to the free list or deleting this
587      *  or larger blocks from the free list.
588      */
589     void
590     _M_validate(size_t* __addr) throw()
591     {
592       vector_type& __free_list = _M_get_free_list();
593       const vector_type::size_type __max_size = 64;
594       if (__free_list.size() >= __max_size)
595         {
596           // Ok, the threshold value has been reached.  We determine
597           // which block to remove from the list of free blocks.
598           if (*__addr >= *__free_list.back())
599             {
600               // Ok, the new block is greater than or equal to the
601               // last block in the list of free blocks. We just free
602               // the new block.
603               ::operator delete(static_cast<void*>(__addr));
604               return;
605             }
606           else
607             {
608               // Deallocate the last block in the list of free lists,
609               // and insert the new one in its correct position.
610               ::operator delete(static_cast<void*>(__free_list.back()));
611               __free_list.pop_back();
612             }
613         }
614           
615       // Just add the block to the list of free lists unconditionally.
616       iterator __temp = __gnu_cxx::__detail::__lower_bound
617         (__free_list.begin(), __free_list.end(), 
618          *__addr, _LT_pointer_compare());
619
620       // We may insert the new free list before _temp;
621       __free_list.insert(__temp, __addr);
622     }
623
624     /** @brief  Decides whether the wastage of memory is acceptable for
625      *  the current memory request and returns accordingly.
626      *
627      *  @param __block_size The size of the block available in the free
628      *  list.
629      *
630      *  @param __required_size The required size of the memory block.
631      *
632      *  @return true if the wastage incurred is acceptable, else returns
633      *  false.
634      */
635     bool 
636     _M_should_i_give(size_t __block_size, 
637                      size_t __required_size) throw()
638     {
639       const size_t __max_wastage_percentage = 36;
640       if (__block_size >= __required_size && 
641           (((__block_size - __required_size) * 100 / __block_size)
642            < __max_wastage_percentage))
643         return true;
644       else
645         return false;
646     }
647
648   public:
649     /** @brief This function returns the block of memory to the
650      *  internal free list.
651      *
652      *  @param  __addr The pointer to the memory block that was given
653      *  by a call to the _M_get function.
654      */
655     inline void 
656     _M_insert(size_t* __addr) throw()
657     {
658 #if defined __GTHREADS
659       __gnu_cxx::__scoped_lock __bfl_lock(_M_get_mutex());
660 #endif
661       // Call _M_validate to decide what should be done with
662       // this particular free list.
663       this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
664       // See discussion as to why this is 1!
665     }
666     
667     /** @brief  This function gets a block of memory of the specified
668      *  size from the free list.
669      *
670      *  @param  __sz The size in bytes of the memory required.
671      *
672      *  @return  A pointer to the new memory block of size at least
673      *  equal to that requested.
674      */
675     size_t*
676     _M_get(size_t __sz) throw(std::bad_alloc);
677
678     /** @brief  This function just clears the internal Free List, and
679      *  gives back all the memory to the OS.
680      */
681     void 
682     _M_clear();
683   };
684
685
686   // Forward declare the class.
687   template<typename _Tp> 
688     class bitmap_allocator;
689
690   // Specialize for void:
691   template<>
692     class bitmap_allocator<void>
693     {
694     public:
695       typedef void*       pointer;
696       typedef const void* const_pointer;
697
698       // Reference-to-void members are impossible.
699       typedef void  value_type;
700       template<typename _Tp1>
701         struct rebind
702         {
703           typedef bitmap_allocator<_Tp1> other;
704         };
705     };
706
707   /**
708    * @brief Bitmap Allocator, primary template.
709    * @ingroup allocators
710    */
711   template<typename _Tp>
712     class bitmap_allocator : private free_list
713     {
714     public:
715       typedef size_t                    size_type;
716       typedef ptrdiff_t                 difference_type;
717       typedef _Tp*                      pointer;
718       typedef const _Tp*                const_pointer;
719       typedef _Tp&                      reference;
720       typedef const _Tp&                const_reference;
721       typedef _Tp                       value_type;
722       typedef free_list::__mutex_type   __mutex_type;
723
724       template<typename _Tp1>
725         struct rebind
726         {
727           typedef bitmap_allocator<_Tp1> other;
728         };
729
730     private:
731       template<size_t _BSize, size_t _AlignSize>
732         struct aligned_size
733         {
734           enum
735             { 
736               modulus = _BSize % _AlignSize,
737               value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
738             };
739         };
740
741       struct _Alloc_block
742       {
743         char __M_unused[aligned_size<sizeof(value_type),
744                         _BALLOC_ALIGN_BYTES>::value];
745       };
746
747
748       typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair;
749
750       typedef typename 
751       __detail::__mini_vector<_Block_pair> _BPVector;
752
753 #if defined _GLIBCXX_DEBUG
754       // Complexity: O(lg(N)). Where, N is the number of block of size
755       // sizeof(value_type).
756       void 
757       _S_check_for_free_blocks() throw()
758       {
759         typedef typename 
760           __gnu_cxx::__detail::_Ffit_finder<_Alloc_block*> _FFF;
761         _FFF __fff;
762         typedef typename _BPVector::iterator _BPiter;
763         _BPiter __bpi = 
764           __gnu_cxx::__detail::__find_if
765           (_S_mem_blocks.begin(), _S_mem_blocks.end(), 
766            __gnu_cxx::__detail::_Functor_Ref<_FFF>(__fff));
767
768         _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end());
769       }
770 #endif
771
772       /** @brief  Responsible for exponentially growing the internal
773        *  memory pool.
774        *
775        *  @throw  std::bad_alloc. If memory can not be allocated.
776        *
777        *  @detail  Complexity: O(1), but internally depends upon the
778        *  complexity of the function free_list::_M_get. The part where
779        *  the bitmap headers are written has complexity: O(X),where X
780        *  is the number of blocks of size sizeof(value_type) within
781        *  the newly acquired block. Having a tight bound.
782        */
783       void 
784       _S_refill_pool() throw(std::bad_alloc)
785       {
786 #if defined _GLIBCXX_DEBUG
787         _S_check_for_free_blocks();
788 #endif
789
790         const size_t __num_bitmaps = (_S_block_size
791                                       / size_t(__detail::bits_per_block));
792         const size_t __size_to_allocate = sizeof(size_t) 
793           + _S_block_size * sizeof(_Alloc_block) 
794           + __num_bitmaps * sizeof(size_t);
795
796         size_t* __temp = 
797           reinterpret_cast<size_t*>
798           (this->_M_get(__size_to_allocate));
799         *__temp = 0;
800         ++__temp;
801
802         // The Header information goes at the Beginning of the Block.
803         _Block_pair __bp = 
804           std::make_pair(reinterpret_cast<_Alloc_block*>
805                          (__temp + __num_bitmaps), 
806                          reinterpret_cast<_Alloc_block*>
807                          (__temp + __num_bitmaps) 
808                          + _S_block_size - 1);
809         
810         // Fill the Vector with this information.
811         _S_mem_blocks.push_back(__bp);
812
813         size_t __bit_mask = 0; // 0 Indicates all Allocated.
814         __bit_mask = ~__bit_mask; // 1 Indicates all Free.
815
816         for (size_t __i = 0; __i < __num_bitmaps; ++__i)
817           __temp[__i] = __bit_mask;
818
819         _S_block_size *= 2;
820       }
821
822
823       static _BPVector _S_mem_blocks;
824       static size_t _S_block_size;
825       static __gnu_cxx::__detail::
826       _Bitmap_counter<_Alloc_block*> _S_last_request;
827       static typename _BPVector::size_type _S_last_dealloc_index;
828 #if defined __GTHREADS
829       static __mutex_type _S_mut;
830 #endif
831
832     public:
833
834       /** @brief  Allocates memory for a single object of size
835        *  sizeof(_Tp).
836        *
837        *  @throw  std::bad_alloc. If memory can not be allocated.
838        *
839        *  @detail  Complexity: Worst case complexity is O(N), but that
840        *  is hardly ever hit. If and when this particular case is
841        *  encountered, the next few cases are guaranteed to have a
842        *  worst case complexity of O(1)!  That's why this function
843        *  performs very well on average. You can consider this
844        *  function to have a complexity referred to commonly as:
845        *  Amortized Constant time.
846        */
847       pointer 
848       _M_allocate_single_object() throw(std::bad_alloc)
849       {
850 #if defined __GTHREADS
851         __gnu_cxx::__scoped_lock __bit_lock(_S_mut);
852 #endif
853
854         // The algorithm is something like this: The last_request
855         // variable points to the last accessed Bit Map. When such a
856         // condition occurs, we try to find a free block in the
857         // current bitmap, or succeeding bitmaps until the last bitmap
858         // is reached. If no free block turns up, we resort to First
859         // Fit method.
860
861         // WARNING: Do not re-order the condition in the while
862         // statement below, because it relies on C++'s short-circuit
863         // evaluation. The return from _S_last_request->_M_get() will
864         // NOT be dereference able if _S_last_request->_M_finished()
865         // returns true. This would inevitably lead to a NULL pointer
866         // dereference if tinkered with.
867         while (_S_last_request._M_finished() == false
868                && (*(_S_last_request._M_get()) == 0))
869           {
870             _S_last_request.operator++();
871           }
872
873         if (__builtin_expect(_S_last_request._M_finished() == true, false))
874           {
875             // Fall Back to First Fit algorithm.
876             typedef typename 
877               __gnu_cxx::__detail::_Ffit_finder<_Alloc_block*> _FFF;
878             _FFF __fff;
879             typedef typename _BPVector::iterator _BPiter;
880             _BPiter __bpi = 
881               __gnu_cxx::__detail::__find_if
882               (_S_mem_blocks.begin(), _S_mem_blocks.end(), 
883                __gnu_cxx::__detail::_Functor_Ref<_FFF>(__fff));
884
885             if (__bpi != _S_mem_blocks.end())
886               {
887                 // Search was successful. Ok, now mark the first bit from
888                 // the right as 0, meaning Allocated. This bit is obtained
889                 // by calling _M_get() on __fff.
890                 size_t __nz_bit = _Bit_scan_forward(*__fff._M_get());
891                 __detail::__bit_allocate(__fff._M_get(), __nz_bit);
892
893                 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
894
895                 // Now, get the address of the bit we marked as allocated.
896                 pointer __ret = reinterpret_cast<pointer>
897                   (__bpi->first + __fff._M_offset() + __nz_bit);
898                 size_t* __puse_count = 
899                   reinterpret_cast<size_t*>
900                   (__bpi->first) 
901                   - (__gnu_cxx::__detail::__num_bitmaps(*__bpi) + 1);
902                 
903                 ++(*__puse_count);
904                 return __ret;
905               }
906             else
907               {
908                 // Search was unsuccessful. We Add more memory to the
909                 // pool by calling _S_refill_pool().
910                 _S_refill_pool();
911
912                 // _M_Reset the _S_last_request structure to the first
913                 // free block's bit map.
914                 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
915
916                 // Now, mark that bit as allocated.
917               }
918           }
919
920         // _S_last_request holds a pointer to a valid bit map, that
921         // points to a free block in memory.
922         size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get());
923         __detail::__bit_allocate(_S_last_request._M_get(), __nz_bit);
924
925         pointer __ret = reinterpret_cast<pointer>
926           (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
927
928         size_t* __puse_count = reinterpret_cast<size_t*>
929           (_S_mem_blocks[_S_last_request._M_where()].first)
930           - (__gnu_cxx::__detail::
931              __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
932
933         ++(*__puse_count);
934         return __ret;
935       }
936
937       /** @brief  Deallocates memory that belongs to a single object of
938        *  size sizeof(_Tp).
939        *
940        *  @detail  Complexity: O(lg(N)), but the worst case is not hit
941        *  often!  This is because containers usually deallocate memory
942        *  close to each other and this case is handled in O(1) time by
943        *  the deallocate function.
944        */
945       void 
946       _M_deallocate_single_object(pointer __p) throw()
947       {
948 #if defined __GTHREADS
949         __gnu_cxx::__scoped_lock __bit_lock(_S_mut);
950 #endif
951         _Alloc_block* __real_p = reinterpret_cast<_Alloc_block*>(__p);
952
953         typedef typename _BPVector::iterator _Iterator;
954         typedef typename _BPVector::difference_type _Difference_type;
955
956         _Difference_type __diff;
957         long __displacement;
958
959         _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
960
961         
962         if (__gnu_cxx::__detail::_Inclusive_between<_Alloc_block*>
963             (__real_p) (_S_mem_blocks[_S_last_dealloc_index]))
964           {
965             _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index
966                                   <= _S_mem_blocks.size() - 1);
967
968             // Initial Assumption was correct!
969             __diff = _S_last_dealloc_index;
970             __displacement = __real_p - _S_mem_blocks[__diff].first;
971           }
972         else
973           {
974             _Iterator _iter = __gnu_cxx::__detail::
975               __find_if(_S_mem_blocks.begin(), 
976                         _S_mem_blocks.end(), 
977                         __gnu_cxx::__detail::
978                         _Inclusive_between<_Alloc_block*>(__real_p));
979
980             _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end());
981
982             __diff = _iter - _S_mem_blocks.begin();
983             __displacement = __real_p - _S_mem_blocks[__diff].first;
984             _S_last_dealloc_index = __diff;
985           }
986
987         // Get the position of the iterator that has been found.
988         const size_t __rotate = (__displacement
989                                  % size_t(__detail::bits_per_block));
990         size_t* __bitmapC = 
991           reinterpret_cast<size_t*>
992           (_S_mem_blocks[__diff].first) - 1;
993         __bitmapC -= (__displacement / size_t(__detail::bits_per_block));
994       
995         __detail::__bit_free(__bitmapC, __rotate);
996         size_t* __puse_count = reinterpret_cast<size_t*>
997           (_S_mem_blocks[__diff].first)
998           - (__gnu_cxx::__detail::__num_bitmaps(_S_mem_blocks[__diff]) + 1);
999         
1000         _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0);
1001
1002         --(*__puse_count);
1003
1004         if (__builtin_expect(*__puse_count == 0, false))
1005           {
1006             _S_block_size /= 2;
1007           
1008             // We can safely remove this block.
1009             // _Block_pair __bp = _S_mem_blocks[__diff];
1010             this->_M_insert(__puse_count);
1011             _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
1012
1013             // Reset the _S_last_request variable to reflect the
1014             // erased block. We do this to protect future requests
1015             // after the last block has been removed from a particular
1016             // memory Chunk, which in turn has been returned to the
1017             // free list, and hence had been erased from the vector,
1018             // so the size of the vector gets reduced by 1.
1019             if ((_Difference_type)_S_last_request._M_where() >= __diff--)
1020               _S_last_request._M_reset(__diff); 
1021
1022             // If the Index into the vector of the region of memory
1023             // that might hold the next address that will be passed to
1024             // deallocated may have been invalidated due to the above
1025             // erase procedure being called on the vector, hence we
1026             // try to restore this invariant too.
1027             if (_S_last_dealloc_index >= _S_mem_blocks.size())
1028               {
1029                 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
1030                 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
1031               }
1032           }
1033       }
1034
1035     public:
1036       bitmap_allocator() throw()
1037       { }
1038
1039       bitmap_allocator(const bitmap_allocator&)
1040       { }
1041
1042       template<typename _Tp1>
1043         bitmap_allocator(const bitmap_allocator<_Tp1>&) throw()
1044         { }
1045
1046       ~bitmap_allocator() throw()
1047       { }
1048
1049       pointer 
1050       allocate(size_type __n)
1051       {
1052         if (__n > this->max_size())
1053           std::__throw_bad_alloc();
1054
1055         if (__builtin_expect(__n == 1, true))
1056           return this->_M_allocate_single_object();
1057         else
1058           { 
1059             const size_type __b = __n * sizeof(value_type);
1060             return reinterpret_cast<pointer>(::operator new(__b));
1061           }
1062       }
1063
1064       pointer 
1065       allocate(size_type __n, typename bitmap_allocator<void>::const_pointer)
1066       { return allocate(__n); }
1067
1068       void 
1069       deallocate(pointer __p, size_type __n) throw()
1070       {
1071         if (__builtin_expect(__p != 0, true))
1072           {
1073             if (__builtin_expect(__n == 1, true))
1074               this->_M_deallocate_single_object(__p);
1075             else
1076               ::operator delete(__p);
1077           }
1078       }
1079
1080       pointer 
1081       address(reference __r) const
1082       { return &__r; }
1083
1084       const_pointer 
1085       address(const_reference __r) const
1086       { return &__r; }
1087
1088       size_type 
1089       max_size() const throw()
1090       { return size_type(-1) / sizeof(value_type); }
1091
1092       void 
1093       construct(pointer __p, const_reference __data)
1094       { ::new((void *)__p) value_type(__data); }
1095
1096 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1097       template<typename... _Args>
1098         void
1099         construct(pointer __p, _Args&&... __args)
1100         { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); }
1101 #endif
1102
1103       void 
1104       destroy(pointer __p)
1105       { __p->~value_type(); }
1106     };
1107
1108   template<typename _Tp1, typename _Tp2>
1109     bool 
1110     operator==(const bitmap_allocator<_Tp1>&, 
1111                const bitmap_allocator<_Tp2>&) throw()
1112     { return true; }
1113   
1114   template<typename _Tp1, typename _Tp2>
1115     bool 
1116     operator!=(const bitmap_allocator<_Tp1>&, 
1117                const bitmap_allocator<_Tp2>&) throw() 
1118   { return false; }
1119
1120   // Static member definitions.
1121   template<typename _Tp>
1122     typename bitmap_allocator<_Tp>::_BPVector
1123     bitmap_allocator<_Tp>::_S_mem_blocks;
1124
1125   template<typename _Tp>
1126     size_t bitmap_allocator<_Tp>::_S_block_size = 
1127     2 * size_t(__detail::bits_per_block);
1128
1129   template<typename _Tp>
1130     typename __gnu_cxx::bitmap_allocator<_Tp>::_BPVector::size_type 
1131     bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
1132
1133   template<typename _Tp>
1134     __gnu_cxx::__detail::_Bitmap_counter 
1135   <typename bitmap_allocator<_Tp>::_Alloc_block*>
1136     bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
1137
1138 #if defined __GTHREADS
1139   template<typename _Tp>
1140     typename bitmap_allocator<_Tp>::__mutex_type
1141     bitmap_allocator<_Tp>::_S_mut;
1142 #endif
1143
1144 _GLIBCXX_END_NAMESPACE
1145
1146 #endif 
1147