xref: /dflybsd-src/contrib/gcc-4.7/libstdc++-v3/include/bits/stl_bvector.h (revision 04febcfb30580676d3e95f58a16c5137ee478b32)
1*e4b17023SJohn Marino // vector<bool> specialization -*- C++ -*-
2*e4b17023SJohn Marino 
3*e4b17023SJohn Marino // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4*e4b17023SJohn Marino // 2011 Free Software Foundation, Inc.
5*e4b17023SJohn Marino //
6*e4b17023SJohn Marino // This file is part of the GNU ISO C++ Library.  This library is free
7*e4b17023SJohn Marino // software; you can redistribute it and/or modify it under the
8*e4b17023SJohn Marino // terms of the GNU General Public License as published by the
9*e4b17023SJohn Marino // Free Software Foundation; either version 3, or (at your option)
10*e4b17023SJohn Marino // any later version.
11*e4b17023SJohn Marino 
12*e4b17023SJohn Marino // This library is distributed in the hope that it will be useful,
13*e4b17023SJohn Marino // but WITHOUT ANY WARRANTY; without even the implied warranty of
14*e4b17023SJohn Marino // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15*e4b17023SJohn Marino // GNU General Public License for more details.
16*e4b17023SJohn Marino 
17*e4b17023SJohn Marino // Under Section 7 of GPL version 3, you are granted additional
18*e4b17023SJohn Marino // permissions described in the GCC Runtime Library Exception, version
19*e4b17023SJohn Marino // 3.1, as published by the Free Software Foundation.
20*e4b17023SJohn Marino 
21*e4b17023SJohn Marino // You should have received a copy of the GNU General Public License and
22*e4b17023SJohn Marino // a copy of the GCC Runtime Library Exception along with this program;
23*e4b17023SJohn Marino // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24*e4b17023SJohn Marino // <http://www.gnu.org/licenses/>.
25*e4b17023SJohn Marino 
26*e4b17023SJohn Marino /*
27*e4b17023SJohn Marino  *
28*e4b17023SJohn Marino  * Copyright (c) 1994
29*e4b17023SJohn Marino  * Hewlett-Packard Company
30*e4b17023SJohn Marino  *
31*e4b17023SJohn Marino  * Permission to use, copy, modify, distribute and sell this software
32*e4b17023SJohn Marino  * and its documentation for any purpose is hereby granted without fee,
33*e4b17023SJohn Marino  * provided that the above copyright notice appear in all copies and
34*e4b17023SJohn Marino  * that both that copyright notice and this permission notice appear
35*e4b17023SJohn Marino  * in supporting documentation.  Hewlett-Packard Company makes no
36*e4b17023SJohn Marino  * representations about the suitability of this software for any
37*e4b17023SJohn Marino  * purpose.  It is provided "as is" without express or implied warranty.
38*e4b17023SJohn Marino  *
39*e4b17023SJohn Marino  *
40*e4b17023SJohn Marino  * Copyright (c) 1996-1999
41*e4b17023SJohn Marino  * Silicon Graphics Computer Systems, Inc.
42*e4b17023SJohn Marino  *
43*e4b17023SJohn Marino  * Permission to use, copy, modify, distribute and sell this software
44*e4b17023SJohn Marino  * and its documentation for any purpose is hereby granted without fee,
45*e4b17023SJohn Marino  * provided that the above copyright notice appear in all copies and
46*e4b17023SJohn Marino  * that both that copyright notice and this permission notice appear
47*e4b17023SJohn Marino  * in supporting documentation.  Silicon Graphics makes no
48*e4b17023SJohn Marino  * representations about the suitability of this software for any
49*e4b17023SJohn Marino  * purpose.  It is provided "as is" without express or implied warranty.
50*e4b17023SJohn Marino  */
51*e4b17023SJohn Marino 
52*e4b17023SJohn Marino /** @file bits/stl_bvector.h
53*e4b17023SJohn Marino  *  This is an internal header file, included by other library headers.
54*e4b17023SJohn Marino  *  Do not attempt to use it directly. @headername{vector}
55*e4b17023SJohn Marino  */
56*e4b17023SJohn Marino 
57*e4b17023SJohn Marino #ifndef _STL_BVECTOR_H
58*e4b17023SJohn Marino #define _STL_BVECTOR_H 1
59*e4b17023SJohn Marino 
60*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
61*e4b17023SJohn Marino #include <initializer_list>
62*e4b17023SJohn Marino #endif
63*e4b17023SJohn Marino 
_GLIBCXX_VISIBILITY(default)64*e4b17023SJohn Marino namespace std _GLIBCXX_VISIBILITY(default)
65*e4b17023SJohn Marino {
66*e4b17023SJohn Marino _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
67*e4b17023SJohn Marino 
68*e4b17023SJohn Marino   typedef unsigned long _Bit_type;
69*e4b17023SJohn Marino   enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) };
70*e4b17023SJohn Marino 
71*e4b17023SJohn Marino   struct _Bit_reference
72*e4b17023SJohn Marino   {
73*e4b17023SJohn Marino     _Bit_type * _M_p;
74*e4b17023SJohn Marino     _Bit_type _M_mask;
75*e4b17023SJohn Marino 
76*e4b17023SJohn Marino     _Bit_reference(_Bit_type * __x, _Bit_type __y)
77*e4b17023SJohn Marino     : _M_p(__x), _M_mask(__y) { }
78*e4b17023SJohn Marino 
79*e4b17023SJohn Marino     _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { }
80*e4b17023SJohn Marino 
81*e4b17023SJohn Marino     operator bool() const _GLIBCXX_NOEXCEPT
82*e4b17023SJohn Marino     { return !!(*_M_p & _M_mask); }
83*e4b17023SJohn Marino 
84*e4b17023SJohn Marino     _Bit_reference&
85*e4b17023SJohn Marino     operator=(bool __x) _GLIBCXX_NOEXCEPT
86*e4b17023SJohn Marino     {
87*e4b17023SJohn Marino       if (__x)
88*e4b17023SJohn Marino 	*_M_p |= _M_mask;
89*e4b17023SJohn Marino       else
90*e4b17023SJohn Marino 	*_M_p &= ~_M_mask;
91*e4b17023SJohn Marino       return *this;
92*e4b17023SJohn Marino     }
93*e4b17023SJohn Marino 
94*e4b17023SJohn Marino     _Bit_reference&
95*e4b17023SJohn Marino     operator=(const _Bit_reference& __x) _GLIBCXX_NOEXCEPT
96*e4b17023SJohn Marino     { return *this = bool(__x); }
97*e4b17023SJohn Marino 
98*e4b17023SJohn Marino     bool
99*e4b17023SJohn Marino     operator==(const _Bit_reference& __x) const
100*e4b17023SJohn Marino     { return bool(*this) == bool(__x); }
101*e4b17023SJohn Marino 
102*e4b17023SJohn Marino     bool
103*e4b17023SJohn Marino     operator<(const _Bit_reference& __x) const
104*e4b17023SJohn Marino     { return !bool(*this) && bool(__x); }
105*e4b17023SJohn Marino 
106*e4b17023SJohn Marino     void
107*e4b17023SJohn Marino     flip() _GLIBCXX_NOEXCEPT
108*e4b17023SJohn Marino     { *_M_p ^= _M_mask; }
109*e4b17023SJohn Marino   };
110*e4b17023SJohn Marino 
111*e4b17023SJohn Marino   struct _Bit_iterator_base
112*e4b17023SJohn Marino   : public std::iterator<std::random_access_iterator_tag, bool>
113*e4b17023SJohn Marino   {
114*e4b17023SJohn Marino     _Bit_type * _M_p;
115*e4b17023SJohn Marino     unsigned int _M_offset;
116*e4b17023SJohn Marino 
117*e4b17023SJohn Marino     _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
118*e4b17023SJohn Marino     : _M_p(__x), _M_offset(__y) { }
119*e4b17023SJohn Marino 
120*e4b17023SJohn Marino     void
121*e4b17023SJohn Marino     _M_bump_up()
122*e4b17023SJohn Marino     {
123*e4b17023SJohn Marino       if (_M_offset++ == int(_S_word_bit) - 1)
124*e4b17023SJohn Marino 	{
125*e4b17023SJohn Marino 	  _M_offset = 0;
126*e4b17023SJohn Marino 	  ++_M_p;
127*e4b17023SJohn Marino 	}
128*e4b17023SJohn Marino     }
129*e4b17023SJohn Marino 
130*e4b17023SJohn Marino     void
131*e4b17023SJohn Marino     _M_bump_down()
132*e4b17023SJohn Marino     {
133*e4b17023SJohn Marino       if (_M_offset-- == 0)
134*e4b17023SJohn Marino 	{
135*e4b17023SJohn Marino 	  _M_offset = int(_S_word_bit) - 1;
136*e4b17023SJohn Marino 	  --_M_p;
137*e4b17023SJohn Marino 	}
138*e4b17023SJohn Marino     }
139*e4b17023SJohn Marino 
140*e4b17023SJohn Marino     void
141*e4b17023SJohn Marino     _M_incr(ptrdiff_t __i)
142*e4b17023SJohn Marino     {
143*e4b17023SJohn Marino       difference_type __n = __i + _M_offset;
144*e4b17023SJohn Marino       _M_p += __n / int(_S_word_bit);
145*e4b17023SJohn Marino       __n = __n % int(_S_word_bit);
146*e4b17023SJohn Marino       if (__n < 0)
147*e4b17023SJohn Marino 	{
148*e4b17023SJohn Marino 	  __n += int(_S_word_bit);
149*e4b17023SJohn Marino 	  --_M_p;
150*e4b17023SJohn Marino 	}
151*e4b17023SJohn Marino       _M_offset = static_cast<unsigned int>(__n);
152*e4b17023SJohn Marino     }
153*e4b17023SJohn Marino 
154*e4b17023SJohn Marino     bool
155*e4b17023SJohn Marino     operator==(const _Bit_iterator_base& __i) const
156*e4b17023SJohn Marino     { return _M_p == __i._M_p && _M_offset == __i._M_offset; }
157*e4b17023SJohn Marino 
158*e4b17023SJohn Marino     bool
159*e4b17023SJohn Marino     operator<(const _Bit_iterator_base& __i) const
160*e4b17023SJohn Marino     {
161*e4b17023SJohn Marino       return _M_p < __i._M_p
162*e4b17023SJohn Marino 	     || (_M_p == __i._M_p && _M_offset < __i._M_offset);
163*e4b17023SJohn Marino     }
164*e4b17023SJohn Marino 
165*e4b17023SJohn Marino     bool
166*e4b17023SJohn Marino     operator!=(const _Bit_iterator_base& __i) const
167*e4b17023SJohn Marino     { return !(*this == __i); }
168*e4b17023SJohn Marino 
169*e4b17023SJohn Marino     bool
170*e4b17023SJohn Marino     operator>(const _Bit_iterator_base& __i) const
171*e4b17023SJohn Marino     { return __i < *this; }
172*e4b17023SJohn Marino 
173*e4b17023SJohn Marino     bool
174*e4b17023SJohn Marino     operator<=(const _Bit_iterator_base& __i) const
175*e4b17023SJohn Marino     { return !(__i < *this); }
176*e4b17023SJohn Marino 
177*e4b17023SJohn Marino     bool
178*e4b17023SJohn Marino     operator>=(const _Bit_iterator_base& __i) const
179*e4b17023SJohn Marino     { return !(*this < __i); }
180*e4b17023SJohn Marino   };
181*e4b17023SJohn Marino 
182*e4b17023SJohn Marino   inline ptrdiff_t
183*e4b17023SJohn Marino   operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
184*e4b17023SJohn Marino   {
185*e4b17023SJohn Marino     return (int(_S_word_bit) * (__x._M_p - __y._M_p)
186*e4b17023SJohn Marino 	    + __x._M_offset - __y._M_offset);
187*e4b17023SJohn Marino   }
188*e4b17023SJohn Marino 
189*e4b17023SJohn Marino   struct _Bit_iterator : public _Bit_iterator_base
190*e4b17023SJohn Marino   {
191*e4b17023SJohn Marino     typedef _Bit_reference  reference;
192*e4b17023SJohn Marino     typedef _Bit_reference* pointer;
193*e4b17023SJohn Marino     typedef _Bit_iterator   iterator;
194*e4b17023SJohn Marino 
195*e4b17023SJohn Marino     _Bit_iterator() : _Bit_iterator_base(0, 0) { }
196*e4b17023SJohn Marino 
197*e4b17023SJohn Marino     _Bit_iterator(_Bit_type * __x, unsigned int __y)
198*e4b17023SJohn Marino     : _Bit_iterator_base(__x, __y) { }
199*e4b17023SJohn Marino 
200*e4b17023SJohn Marino     reference
201*e4b17023SJohn Marino     operator*() const
202*e4b17023SJohn Marino     { return reference(_M_p, 1UL << _M_offset); }
203*e4b17023SJohn Marino 
204*e4b17023SJohn Marino     iterator&
205*e4b17023SJohn Marino     operator++()
206*e4b17023SJohn Marino     {
207*e4b17023SJohn Marino       _M_bump_up();
208*e4b17023SJohn Marino       return *this;
209*e4b17023SJohn Marino     }
210*e4b17023SJohn Marino 
211*e4b17023SJohn Marino     iterator
212*e4b17023SJohn Marino     operator++(int)
213*e4b17023SJohn Marino     {
214*e4b17023SJohn Marino       iterator __tmp = *this;
215*e4b17023SJohn Marino       _M_bump_up();
216*e4b17023SJohn Marino       return __tmp;
217*e4b17023SJohn Marino     }
218*e4b17023SJohn Marino 
219*e4b17023SJohn Marino     iterator&
220*e4b17023SJohn Marino     operator--()
221*e4b17023SJohn Marino     {
222*e4b17023SJohn Marino       _M_bump_down();
223*e4b17023SJohn Marino       return *this;
224*e4b17023SJohn Marino     }
225*e4b17023SJohn Marino 
226*e4b17023SJohn Marino     iterator
227*e4b17023SJohn Marino     operator--(int)
228*e4b17023SJohn Marino     {
229*e4b17023SJohn Marino       iterator __tmp = *this;
230*e4b17023SJohn Marino       _M_bump_down();
231*e4b17023SJohn Marino       return __tmp;
232*e4b17023SJohn Marino     }
233*e4b17023SJohn Marino 
234*e4b17023SJohn Marino     iterator&
235*e4b17023SJohn Marino     operator+=(difference_type __i)
236*e4b17023SJohn Marino     {
237*e4b17023SJohn Marino       _M_incr(__i);
238*e4b17023SJohn Marino       return *this;
239*e4b17023SJohn Marino     }
240*e4b17023SJohn Marino 
241*e4b17023SJohn Marino     iterator&
242*e4b17023SJohn Marino     operator-=(difference_type __i)
243*e4b17023SJohn Marino     {
244*e4b17023SJohn Marino       *this += -__i;
245*e4b17023SJohn Marino       return *this;
246*e4b17023SJohn Marino     }
247*e4b17023SJohn Marino 
248*e4b17023SJohn Marino     iterator
249*e4b17023SJohn Marino     operator+(difference_type __i) const
250*e4b17023SJohn Marino     {
251*e4b17023SJohn Marino       iterator __tmp = *this;
252*e4b17023SJohn Marino       return __tmp += __i;
253*e4b17023SJohn Marino     }
254*e4b17023SJohn Marino 
255*e4b17023SJohn Marino     iterator
256*e4b17023SJohn Marino     operator-(difference_type __i) const
257*e4b17023SJohn Marino     {
258*e4b17023SJohn Marino       iterator __tmp = *this;
259*e4b17023SJohn Marino       return __tmp -= __i;
260*e4b17023SJohn Marino     }
261*e4b17023SJohn Marino 
262*e4b17023SJohn Marino     reference
263*e4b17023SJohn Marino     operator[](difference_type __i) const
264*e4b17023SJohn Marino     { return *(*this + __i); }
265*e4b17023SJohn Marino   };
266*e4b17023SJohn Marino 
267*e4b17023SJohn Marino   inline _Bit_iterator
268*e4b17023SJohn Marino   operator+(ptrdiff_t __n, const _Bit_iterator& __x)
269*e4b17023SJohn Marino   { return __x + __n; }
270*e4b17023SJohn Marino 
271*e4b17023SJohn Marino   struct _Bit_const_iterator : public _Bit_iterator_base
272*e4b17023SJohn Marino   {
273*e4b17023SJohn Marino     typedef bool                 reference;
274*e4b17023SJohn Marino     typedef bool                 const_reference;
275*e4b17023SJohn Marino     typedef const bool*          pointer;
276*e4b17023SJohn Marino     typedef _Bit_const_iterator  const_iterator;
277*e4b17023SJohn Marino 
278*e4b17023SJohn Marino     _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
279*e4b17023SJohn Marino 
280*e4b17023SJohn Marino     _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
281*e4b17023SJohn Marino     : _Bit_iterator_base(__x, __y) { }
282*e4b17023SJohn Marino 
283*e4b17023SJohn Marino     _Bit_const_iterator(const _Bit_iterator& __x)
284*e4b17023SJohn Marino     : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
285*e4b17023SJohn Marino 
286*e4b17023SJohn Marino     const_reference
287*e4b17023SJohn Marino     operator*() const
288*e4b17023SJohn Marino     { return _Bit_reference(_M_p, 1UL << _M_offset); }
289*e4b17023SJohn Marino 
290*e4b17023SJohn Marino     const_iterator&
291*e4b17023SJohn Marino     operator++()
292*e4b17023SJohn Marino     {
293*e4b17023SJohn Marino       _M_bump_up();
294*e4b17023SJohn Marino       return *this;
295*e4b17023SJohn Marino     }
296*e4b17023SJohn Marino 
297*e4b17023SJohn Marino     const_iterator
298*e4b17023SJohn Marino     operator++(int)
299*e4b17023SJohn Marino     {
300*e4b17023SJohn Marino       const_iterator __tmp = *this;
301*e4b17023SJohn Marino       _M_bump_up();
302*e4b17023SJohn Marino       return __tmp;
303*e4b17023SJohn Marino     }
304*e4b17023SJohn Marino 
305*e4b17023SJohn Marino     const_iterator&
306*e4b17023SJohn Marino     operator--()
307*e4b17023SJohn Marino     {
308*e4b17023SJohn Marino       _M_bump_down();
309*e4b17023SJohn Marino       return *this;
310*e4b17023SJohn Marino     }
311*e4b17023SJohn Marino 
312*e4b17023SJohn Marino     const_iterator
313*e4b17023SJohn Marino     operator--(int)
314*e4b17023SJohn Marino     {
315*e4b17023SJohn Marino       const_iterator __tmp = *this;
316*e4b17023SJohn Marino       _M_bump_down();
317*e4b17023SJohn Marino       return __tmp;
318*e4b17023SJohn Marino     }
319*e4b17023SJohn Marino 
320*e4b17023SJohn Marino     const_iterator&
321*e4b17023SJohn Marino     operator+=(difference_type __i)
322*e4b17023SJohn Marino     {
323*e4b17023SJohn Marino       _M_incr(__i);
324*e4b17023SJohn Marino       return *this;
325*e4b17023SJohn Marino     }
326*e4b17023SJohn Marino 
327*e4b17023SJohn Marino     const_iterator&
328*e4b17023SJohn Marino     operator-=(difference_type __i)
329*e4b17023SJohn Marino     {
330*e4b17023SJohn Marino       *this += -__i;
331*e4b17023SJohn Marino       return *this;
332*e4b17023SJohn Marino     }
333*e4b17023SJohn Marino 
334*e4b17023SJohn Marino     const_iterator
335*e4b17023SJohn Marino     operator+(difference_type __i) const
336*e4b17023SJohn Marino     {
337*e4b17023SJohn Marino       const_iterator __tmp = *this;
338*e4b17023SJohn Marino       return __tmp += __i;
339*e4b17023SJohn Marino     }
340*e4b17023SJohn Marino 
341*e4b17023SJohn Marino     const_iterator
342*e4b17023SJohn Marino     operator-(difference_type __i) const
343*e4b17023SJohn Marino     {
344*e4b17023SJohn Marino       const_iterator __tmp = *this;
345*e4b17023SJohn Marino       return __tmp -= __i;
346*e4b17023SJohn Marino     }
347*e4b17023SJohn Marino 
348*e4b17023SJohn Marino     const_reference
349*e4b17023SJohn Marino     operator[](difference_type __i) const
350*e4b17023SJohn Marino     { return *(*this + __i); }
351*e4b17023SJohn Marino   };
352*e4b17023SJohn Marino 
353*e4b17023SJohn Marino   inline _Bit_const_iterator
354*e4b17023SJohn Marino   operator+(ptrdiff_t __n, const _Bit_const_iterator& __x)
355*e4b17023SJohn Marino   { return __x + __n; }
356*e4b17023SJohn Marino 
357*e4b17023SJohn Marino   inline void
358*e4b17023SJohn Marino   __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x)
359*e4b17023SJohn Marino   {
360*e4b17023SJohn Marino     for (; __first != __last; ++__first)
361*e4b17023SJohn Marino       *__first = __x;
362*e4b17023SJohn Marino   }
363*e4b17023SJohn Marino 
364*e4b17023SJohn Marino   inline void
365*e4b17023SJohn Marino   fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x)
366*e4b17023SJohn Marino   {
367*e4b17023SJohn Marino     if (__first._M_p != __last._M_p)
368*e4b17023SJohn Marino       {
369*e4b17023SJohn Marino 	std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0);
370*e4b17023SJohn Marino 	__fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x);
371*e4b17023SJohn Marino 	__fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x);
372*e4b17023SJohn Marino       }
373*e4b17023SJohn Marino     else
374*e4b17023SJohn Marino       __fill_bvector(__first, __last, __x);
375*e4b17023SJohn Marino   }
376*e4b17023SJohn Marino 
377*e4b17023SJohn Marino   template<typename _Alloc>
378*e4b17023SJohn Marino     struct _Bvector_base
379*e4b17023SJohn Marino     {
380*e4b17023SJohn Marino       typedef typename _Alloc::template rebind<_Bit_type>::other
381*e4b17023SJohn Marino         _Bit_alloc_type;
382*e4b17023SJohn Marino 
383*e4b17023SJohn Marino       struct _Bvector_impl
384*e4b17023SJohn Marino       : public _Bit_alloc_type
385*e4b17023SJohn Marino       {
386*e4b17023SJohn Marino 	_Bit_iterator 	_M_start;
387*e4b17023SJohn Marino 	_Bit_iterator 	_M_finish;
388*e4b17023SJohn Marino 	_Bit_type* 	_M_end_of_storage;
389*e4b17023SJohn Marino 
390*e4b17023SJohn Marino 	_Bvector_impl()
391*e4b17023SJohn Marino 	: _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0)
392*e4b17023SJohn Marino 	{ }
393*e4b17023SJohn Marino 
394*e4b17023SJohn Marino 	_Bvector_impl(const _Bit_alloc_type& __a)
395*e4b17023SJohn Marino 	: _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
396*e4b17023SJohn Marino 	{ }
397*e4b17023SJohn Marino 
398*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
399*e4b17023SJohn Marino 	_Bvector_impl(_Bit_alloc_type&& __a)
400*e4b17023SJohn Marino 	: _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(),
401*e4b17023SJohn Marino 	  _M_end_of_storage(0)
402*e4b17023SJohn Marino 	{ }
403*e4b17023SJohn Marino #endif
404*e4b17023SJohn Marino       };
405*e4b17023SJohn Marino 
406*e4b17023SJohn Marino     public:
407*e4b17023SJohn Marino       typedef _Alloc allocator_type;
408*e4b17023SJohn Marino 
409*e4b17023SJohn Marino       _Bit_alloc_type&
410*e4b17023SJohn Marino       _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
411*e4b17023SJohn Marino       { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); }
412*e4b17023SJohn Marino 
413*e4b17023SJohn Marino       const _Bit_alloc_type&
414*e4b17023SJohn Marino       _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
415*e4b17023SJohn Marino       { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
416*e4b17023SJohn Marino 
417*e4b17023SJohn Marino       allocator_type
418*e4b17023SJohn Marino       get_allocator() const _GLIBCXX_NOEXCEPT
419*e4b17023SJohn Marino       { return allocator_type(_M_get_Bit_allocator()); }
420*e4b17023SJohn Marino 
421*e4b17023SJohn Marino       _Bvector_base()
422*e4b17023SJohn Marino       : _M_impl() { }
423*e4b17023SJohn Marino 
424*e4b17023SJohn Marino       _Bvector_base(const allocator_type& __a)
425*e4b17023SJohn Marino       : _M_impl(__a) { }
426*e4b17023SJohn Marino 
427*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
428*e4b17023SJohn Marino       _Bvector_base(_Bvector_base&& __x) noexcept
429*e4b17023SJohn Marino       : _M_impl(std::move(__x._M_get_Bit_allocator()))
430*e4b17023SJohn Marino       {
431*e4b17023SJohn Marino 	this->_M_impl._M_start = __x._M_impl._M_start;
432*e4b17023SJohn Marino 	this->_M_impl._M_finish = __x._M_impl._M_finish;
433*e4b17023SJohn Marino 	this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
434*e4b17023SJohn Marino 	__x._M_impl._M_start = _Bit_iterator();
435*e4b17023SJohn Marino 	__x._M_impl._M_finish = _Bit_iterator();
436*e4b17023SJohn Marino 	__x._M_impl._M_end_of_storage = 0;
437*e4b17023SJohn Marino       }
438*e4b17023SJohn Marino #endif
439*e4b17023SJohn Marino 
440*e4b17023SJohn Marino       ~_Bvector_base()
441*e4b17023SJohn Marino       { this->_M_deallocate(); }
442*e4b17023SJohn Marino 
443*e4b17023SJohn Marino     protected:
444*e4b17023SJohn Marino       _Bvector_impl _M_impl;
445*e4b17023SJohn Marino 
446*e4b17023SJohn Marino       _Bit_type*
447*e4b17023SJohn Marino       _M_allocate(size_t __n)
448*e4b17023SJohn Marino       { return _M_impl.allocate(_S_nword(__n)); }
449*e4b17023SJohn Marino 
450*e4b17023SJohn Marino       void
451*e4b17023SJohn Marino       _M_deallocate()
452*e4b17023SJohn Marino       {
453*e4b17023SJohn Marino 	if (_M_impl._M_start._M_p)
454*e4b17023SJohn Marino 	  _M_impl.deallocate(_M_impl._M_start._M_p,
455*e4b17023SJohn Marino 			     _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
456*e4b17023SJohn Marino       }
457*e4b17023SJohn Marino 
458*e4b17023SJohn Marino       static size_t
459*e4b17023SJohn Marino       _S_nword(size_t __n)
460*e4b17023SJohn Marino       { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
461*e4b17023SJohn Marino     };
462*e4b17023SJohn Marino 
463*e4b17023SJohn Marino _GLIBCXX_END_NAMESPACE_CONTAINER
464*e4b17023SJohn Marino } // namespace std
465*e4b17023SJohn Marino 
466*e4b17023SJohn Marino // Declare a partial specialization of vector<T, Alloc>.
467*e4b17023SJohn Marino #include <bits/stl_vector.h>
468*e4b17023SJohn Marino 
_GLIBCXX_VISIBILITY(default)469*e4b17023SJohn Marino namespace std _GLIBCXX_VISIBILITY(default)
470*e4b17023SJohn Marino {
471*e4b17023SJohn Marino _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
472*e4b17023SJohn Marino 
473*e4b17023SJohn Marino   /**
474*e4b17023SJohn Marino    *  @brief  A specialization of vector for booleans which offers fixed time
475*e4b17023SJohn Marino    *  access to individual elements in any order.
476*e4b17023SJohn Marino    *
477*e4b17023SJohn Marino    *  Note that vector<bool> does not actually meet the requirements for being
478*e4b17023SJohn Marino    *  a container.  This is because the reference and pointer types are not
479*e4b17023SJohn Marino    *  really references and pointers to bool.  See DR96 for details.  @see
480*e4b17023SJohn Marino    *  vector for function documentation.
481*e4b17023SJohn Marino    *
482*e4b17023SJohn Marino    *  @ingroup sequences
483*e4b17023SJohn Marino    *
484*e4b17023SJohn Marino    *  In some terminology a %vector can be described as a dynamic
485*e4b17023SJohn Marino    *  C-style array, it offers fast and efficient access to individual
486*e4b17023SJohn Marino    *  elements in any order and saves the user from worrying about
487*e4b17023SJohn Marino    *  memory and size allocation.  Subscripting ( @c [] ) access is
488*e4b17023SJohn Marino    *  also provided as with C-style arrays.
489*e4b17023SJohn Marino   */
490*e4b17023SJohn Marino template<typename _Alloc>
491*e4b17023SJohn Marino   class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
492*e4b17023SJohn Marino   {
493*e4b17023SJohn Marino     typedef _Bvector_base<_Alloc>			 _Base;
494*e4b17023SJohn Marino 
495*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
496*e4b17023SJohn Marino     template<typename> friend class hash;
497*e4b17023SJohn Marino #endif
498*e4b17023SJohn Marino 
499*e4b17023SJohn Marino   public:
500*e4b17023SJohn Marino     typedef bool                                         value_type;
501*e4b17023SJohn Marino     typedef size_t                                       size_type;
502*e4b17023SJohn Marino     typedef ptrdiff_t                                    difference_type;
503*e4b17023SJohn Marino     typedef _Bit_reference                               reference;
504*e4b17023SJohn Marino     typedef bool                                         const_reference;
505*e4b17023SJohn Marino     typedef _Bit_reference*                              pointer;
506*e4b17023SJohn Marino     typedef const bool*                                  const_pointer;
507*e4b17023SJohn Marino     typedef _Bit_iterator                                iterator;
508*e4b17023SJohn Marino     typedef _Bit_const_iterator                          const_iterator;
509*e4b17023SJohn Marino     typedef std::reverse_iterator<const_iterator>        const_reverse_iterator;
510*e4b17023SJohn Marino     typedef std::reverse_iterator<iterator>              reverse_iterator;
511*e4b17023SJohn Marino     typedef _Alloc                        		 allocator_type;
512*e4b17023SJohn Marino 
513*e4b17023SJohn Marino     allocator_type get_allocator() const
514*e4b17023SJohn Marino     { return _Base::get_allocator(); }
515*e4b17023SJohn Marino 
516*e4b17023SJohn Marino   protected:
517*e4b17023SJohn Marino     using _Base::_M_allocate;
518*e4b17023SJohn Marino     using _Base::_M_deallocate;
519*e4b17023SJohn Marino     using _Base::_S_nword;
520*e4b17023SJohn Marino     using _Base::_M_get_Bit_allocator;
521*e4b17023SJohn Marino 
522*e4b17023SJohn Marino   public:
523*e4b17023SJohn Marino     vector()
524*e4b17023SJohn Marino     : _Base() { }
525*e4b17023SJohn Marino 
526*e4b17023SJohn Marino     explicit
527*e4b17023SJohn Marino     vector(const allocator_type& __a)
528*e4b17023SJohn Marino     : _Base(__a) { }
529*e4b17023SJohn Marino 
530*e4b17023SJohn Marino     explicit
531*e4b17023SJohn Marino     vector(size_type __n, const bool& __value = bool(),
532*e4b17023SJohn Marino 	   const allocator_type& __a = allocator_type())
533*e4b17023SJohn Marino     : _Base(__a)
534*e4b17023SJohn Marino     {
535*e4b17023SJohn Marino       _M_initialize(__n);
536*e4b17023SJohn Marino       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage,
537*e4b17023SJohn Marino 		__value ? ~0 : 0);
538*e4b17023SJohn Marino     }
539*e4b17023SJohn Marino 
540*e4b17023SJohn Marino     vector(const vector& __x)
541*e4b17023SJohn Marino     : _Base(__x._M_get_Bit_allocator())
542*e4b17023SJohn Marino     {
543*e4b17023SJohn Marino       _M_initialize(__x.size());
544*e4b17023SJohn Marino       _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
545*e4b17023SJohn Marino     }
546*e4b17023SJohn Marino 
547*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
548*e4b17023SJohn Marino     vector(vector&& __x) noexcept
549*e4b17023SJohn Marino     : _Base(std::move(__x)) { }
550*e4b17023SJohn Marino 
551*e4b17023SJohn Marino     vector(initializer_list<bool> __l,
552*e4b17023SJohn Marino 	   const allocator_type& __a = allocator_type())
553*e4b17023SJohn Marino     : _Base(__a)
554*e4b17023SJohn Marino     {
555*e4b17023SJohn Marino       _M_initialize_range(__l.begin(), __l.end(),
556*e4b17023SJohn Marino 			  random_access_iterator_tag());
557*e4b17023SJohn Marino     }
558*e4b17023SJohn Marino #endif
559*e4b17023SJohn Marino 
560*e4b17023SJohn Marino     template<typename _InputIterator>
561*e4b17023SJohn Marino       vector(_InputIterator __first, _InputIterator __last,
562*e4b17023SJohn Marino 	     const allocator_type& __a = allocator_type())
563*e4b17023SJohn Marino       : _Base(__a)
564*e4b17023SJohn Marino       {
565*e4b17023SJohn Marino 	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
566*e4b17023SJohn Marino 	_M_initialize_dispatch(__first, __last, _Integral());
567*e4b17023SJohn Marino       }
568*e4b17023SJohn Marino 
569*e4b17023SJohn Marino     ~vector() _GLIBCXX_NOEXCEPT { }
570*e4b17023SJohn Marino 
571*e4b17023SJohn Marino     vector&
572*e4b17023SJohn Marino     operator=(const vector& __x)
573*e4b17023SJohn Marino     {
574*e4b17023SJohn Marino       if (&__x == this)
575*e4b17023SJohn Marino 	return *this;
576*e4b17023SJohn Marino       if (__x.size() > capacity())
577*e4b17023SJohn Marino 	{
578*e4b17023SJohn Marino 	  this->_M_deallocate();
579*e4b17023SJohn Marino 	  _M_initialize(__x.size());
580*e4b17023SJohn Marino 	}
581*e4b17023SJohn Marino       this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
582*e4b17023SJohn Marino 						begin());
583*e4b17023SJohn Marino       return *this;
584*e4b17023SJohn Marino     }
585*e4b17023SJohn Marino 
586*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
587*e4b17023SJohn Marino     vector&
588*e4b17023SJohn Marino     operator=(vector&& __x)
589*e4b17023SJohn Marino     {
590*e4b17023SJohn Marino       // NB: DR 1204.
591*e4b17023SJohn Marino       // NB: DR 675.
592*e4b17023SJohn Marino       this->clear();
593*e4b17023SJohn Marino       this->swap(__x);
594*e4b17023SJohn Marino       return *this;
595*e4b17023SJohn Marino     }
596*e4b17023SJohn Marino 
597*e4b17023SJohn Marino     vector&
598*e4b17023SJohn Marino     operator=(initializer_list<bool> __l)
599*e4b17023SJohn Marino     {
600*e4b17023SJohn Marino       this->assign (__l.begin(), __l.end());
601*e4b17023SJohn Marino       return *this;
602*e4b17023SJohn Marino     }
603*e4b17023SJohn Marino #endif
604*e4b17023SJohn Marino 
605*e4b17023SJohn Marino     // assign(), a generalized assignment member function.  Two
606*e4b17023SJohn Marino     // versions: one that takes a count, and one that takes a range.
607*e4b17023SJohn Marino     // The range version is a member template, so we dispatch on whether
608*e4b17023SJohn Marino     // or not the type is an integer.
609*e4b17023SJohn Marino     void
610*e4b17023SJohn Marino     assign(size_type __n, const bool& __x)
611*e4b17023SJohn Marino     { _M_fill_assign(__n, __x); }
612*e4b17023SJohn Marino 
613*e4b17023SJohn Marino     template<typename _InputIterator>
614*e4b17023SJohn Marino       void
615*e4b17023SJohn Marino       assign(_InputIterator __first, _InputIterator __last)
616*e4b17023SJohn Marino       {
617*e4b17023SJohn Marino 	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
618*e4b17023SJohn Marino 	_M_assign_dispatch(__first, __last, _Integral());
619*e4b17023SJohn Marino       }
620*e4b17023SJohn Marino 
621*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
622*e4b17023SJohn Marino     void
623*e4b17023SJohn Marino     assign(initializer_list<bool> __l)
624*e4b17023SJohn Marino     { this->assign(__l.begin(), __l.end()); }
625*e4b17023SJohn Marino #endif
626*e4b17023SJohn Marino 
627*e4b17023SJohn Marino     iterator
628*e4b17023SJohn Marino     begin() _GLIBCXX_NOEXCEPT
629*e4b17023SJohn Marino     { return this->_M_impl._M_start; }
630*e4b17023SJohn Marino 
631*e4b17023SJohn Marino     const_iterator
632*e4b17023SJohn Marino     begin() const _GLIBCXX_NOEXCEPT
633*e4b17023SJohn Marino     { return this->_M_impl._M_start; }
634*e4b17023SJohn Marino 
635*e4b17023SJohn Marino     iterator
636*e4b17023SJohn Marino     end() _GLIBCXX_NOEXCEPT
637*e4b17023SJohn Marino     { return this->_M_impl._M_finish; }
638*e4b17023SJohn Marino 
639*e4b17023SJohn Marino     const_iterator
640*e4b17023SJohn Marino     end() const _GLIBCXX_NOEXCEPT
641*e4b17023SJohn Marino     { return this->_M_impl._M_finish; }
642*e4b17023SJohn Marino 
643*e4b17023SJohn Marino     reverse_iterator
644*e4b17023SJohn Marino     rbegin() _GLIBCXX_NOEXCEPT
645*e4b17023SJohn Marino     { return reverse_iterator(end()); }
646*e4b17023SJohn Marino 
647*e4b17023SJohn Marino     const_reverse_iterator
648*e4b17023SJohn Marino     rbegin() const _GLIBCXX_NOEXCEPT
649*e4b17023SJohn Marino     { return const_reverse_iterator(end()); }
650*e4b17023SJohn Marino 
651*e4b17023SJohn Marino     reverse_iterator
652*e4b17023SJohn Marino     rend() _GLIBCXX_NOEXCEPT
653*e4b17023SJohn Marino     { return reverse_iterator(begin()); }
654*e4b17023SJohn Marino 
655*e4b17023SJohn Marino     const_reverse_iterator
656*e4b17023SJohn Marino     rend() const _GLIBCXX_NOEXCEPT
657*e4b17023SJohn Marino     { return const_reverse_iterator(begin()); }
658*e4b17023SJohn Marino 
659*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
660*e4b17023SJohn Marino     const_iterator
661*e4b17023SJohn Marino     cbegin() const noexcept
662*e4b17023SJohn Marino     { return this->_M_impl._M_start; }
663*e4b17023SJohn Marino 
664*e4b17023SJohn Marino     const_iterator
665*e4b17023SJohn Marino     cend() const noexcept
666*e4b17023SJohn Marino     { return this->_M_impl._M_finish; }
667*e4b17023SJohn Marino 
668*e4b17023SJohn Marino     const_reverse_iterator
669*e4b17023SJohn Marino     crbegin() const noexcept
670*e4b17023SJohn Marino     { return const_reverse_iterator(end()); }
671*e4b17023SJohn Marino 
672*e4b17023SJohn Marino     const_reverse_iterator
673*e4b17023SJohn Marino     crend() const noexcept
674*e4b17023SJohn Marino     { return const_reverse_iterator(begin()); }
675*e4b17023SJohn Marino #endif
676*e4b17023SJohn Marino 
677*e4b17023SJohn Marino     size_type
678*e4b17023SJohn Marino     size() const _GLIBCXX_NOEXCEPT
679*e4b17023SJohn Marino     { return size_type(end() - begin()); }
680*e4b17023SJohn Marino 
681*e4b17023SJohn Marino     size_type
682*e4b17023SJohn Marino     max_size() const _GLIBCXX_NOEXCEPT
683*e4b17023SJohn Marino     {
684*e4b17023SJohn Marino       const size_type __isize =
685*e4b17023SJohn Marino 	__gnu_cxx::__numeric_traits<difference_type>::__max
686*e4b17023SJohn Marino 	- int(_S_word_bit) + 1;
687*e4b17023SJohn Marino       const size_type __asize = _M_get_Bit_allocator().max_size();
688*e4b17023SJohn Marino       return (__asize <= __isize / int(_S_word_bit)
689*e4b17023SJohn Marino 	      ? __asize * int(_S_word_bit) : __isize);
690*e4b17023SJohn Marino     }
691*e4b17023SJohn Marino 
692*e4b17023SJohn Marino     size_type
693*e4b17023SJohn Marino     capacity() const _GLIBCXX_NOEXCEPT
694*e4b17023SJohn Marino     { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
695*e4b17023SJohn Marino 		       - begin()); }
696*e4b17023SJohn Marino 
697*e4b17023SJohn Marino     bool
698*e4b17023SJohn Marino     empty() const _GLIBCXX_NOEXCEPT
699*e4b17023SJohn Marino     { return begin() == end(); }
700*e4b17023SJohn Marino 
701*e4b17023SJohn Marino     reference
702*e4b17023SJohn Marino     operator[](size_type __n)
703*e4b17023SJohn Marino     {
704*e4b17023SJohn Marino       return *iterator(this->_M_impl._M_start._M_p
705*e4b17023SJohn Marino 		       + __n / int(_S_word_bit), __n % int(_S_word_bit));
706*e4b17023SJohn Marino     }
707*e4b17023SJohn Marino 
708*e4b17023SJohn Marino     const_reference
709*e4b17023SJohn Marino     operator[](size_type __n) const
710*e4b17023SJohn Marino     {
711*e4b17023SJohn Marino       return *const_iterator(this->_M_impl._M_start._M_p
712*e4b17023SJohn Marino 			     + __n / int(_S_word_bit), __n % int(_S_word_bit));
713*e4b17023SJohn Marino     }
714*e4b17023SJohn Marino 
715*e4b17023SJohn Marino   protected:
716*e4b17023SJohn Marino     void
717*e4b17023SJohn Marino     _M_range_check(size_type __n) const
718*e4b17023SJohn Marino     {
719*e4b17023SJohn Marino       if (__n >= this->size())
720*e4b17023SJohn Marino         __throw_out_of_range(__N("vector<bool>::_M_range_check"));
721*e4b17023SJohn Marino     }
722*e4b17023SJohn Marino 
723*e4b17023SJohn Marino   public:
724*e4b17023SJohn Marino     reference
725*e4b17023SJohn Marino     at(size_type __n)
726*e4b17023SJohn Marino     { _M_range_check(__n); return (*this)[__n]; }
727*e4b17023SJohn Marino 
728*e4b17023SJohn Marino     const_reference
729*e4b17023SJohn Marino     at(size_type __n) const
730*e4b17023SJohn Marino     { _M_range_check(__n); return (*this)[__n]; }
731*e4b17023SJohn Marino 
732*e4b17023SJohn Marino     void
733*e4b17023SJohn Marino     reserve(size_type __n)
734*e4b17023SJohn Marino     {
735*e4b17023SJohn Marino       if (__n > max_size())
736*e4b17023SJohn Marino 	__throw_length_error(__N("vector::reserve"));
737*e4b17023SJohn Marino       if (capacity() < __n)
738*e4b17023SJohn Marino 	_M_reallocate(__n);
739*e4b17023SJohn Marino     }
740*e4b17023SJohn Marino 
741*e4b17023SJohn Marino     reference
742*e4b17023SJohn Marino     front()
743*e4b17023SJohn Marino     { return *begin(); }
744*e4b17023SJohn Marino 
745*e4b17023SJohn Marino     const_reference
746*e4b17023SJohn Marino     front() const
747*e4b17023SJohn Marino     { return *begin(); }
748*e4b17023SJohn Marino 
749*e4b17023SJohn Marino     reference
750*e4b17023SJohn Marino     back()
751*e4b17023SJohn Marino     { return *(end() - 1); }
752*e4b17023SJohn Marino 
753*e4b17023SJohn Marino     const_reference
754*e4b17023SJohn Marino     back() const
755*e4b17023SJohn Marino     { return *(end() - 1); }
756*e4b17023SJohn Marino 
757*e4b17023SJohn Marino     // _GLIBCXX_RESOLVE_LIB_DEFECTS
758*e4b17023SJohn Marino     // DR 464. Suggestion for new member functions in standard containers.
759*e4b17023SJohn Marino     // N.B. DR 464 says nothing about vector<bool> but we need something
760*e4b17023SJohn Marino     // here due to the way we are implementing DR 464 in the debug-mode
761*e4b17023SJohn Marino     // vector class.
762*e4b17023SJohn Marino     void
763*e4b17023SJohn Marino     data() _GLIBCXX_NOEXCEPT { }
764*e4b17023SJohn Marino 
765*e4b17023SJohn Marino     void
766*e4b17023SJohn Marino     push_back(bool __x)
767*e4b17023SJohn Marino     {
768*e4b17023SJohn Marino       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
769*e4b17023SJohn Marino         *this->_M_impl._M_finish++ = __x;
770*e4b17023SJohn Marino       else
771*e4b17023SJohn Marino         _M_insert_aux(end(), __x);
772*e4b17023SJohn Marino     }
773*e4b17023SJohn Marino 
774*e4b17023SJohn Marino     void
775*e4b17023SJohn Marino     swap(vector& __x)
776*e4b17023SJohn Marino     {
777*e4b17023SJohn Marino       std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
778*e4b17023SJohn Marino       std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
779*e4b17023SJohn Marino       std::swap(this->_M_impl._M_end_of_storage,
780*e4b17023SJohn Marino 		__x._M_impl._M_end_of_storage);
781*e4b17023SJohn Marino 
782*e4b17023SJohn Marino       // _GLIBCXX_RESOLVE_LIB_DEFECTS
783*e4b17023SJohn Marino       // 431. Swapping containers with unequal allocators.
784*e4b17023SJohn Marino       std::__alloc_swap<typename _Base::_Bit_alloc_type>::
785*e4b17023SJohn Marino 	_S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator());
786*e4b17023SJohn Marino     }
787*e4b17023SJohn Marino 
788*e4b17023SJohn Marino     // [23.2.5]/1, third-to-last entry in synopsis listing
789*e4b17023SJohn Marino     static void
790*e4b17023SJohn Marino     swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
791*e4b17023SJohn Marino     {
792*e4b17023SJohn Marino       bool __tmp = __x;
793*e4b17023SJohn Marino       __x = __y;
794*e4b17023SJohn Marino       __y = __tmp;
795*e4b17023SJohn Marino     }
796*e4b17023SJohn Marino 
797*e4b17023SJohn Marino     iterator
798*e4b17023SJohn Marino     insert(iterator __position, const bool& __x = bool())
799*e4b17023SJohn Marino     {
800*e4b17023SJohn Marino       const difference_type __n = __position - begin();
801*e4b17023SJohn Marino       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
802*e4b17023SJohn Marino 	  && __position == end())
803*e4b17023SJohn Marino         *this->_M_impl._M_finish++ = __x;
804*e4b17023SJohn Marino       else
805*e4b17023SJohn Marino         _M_insert_aux(__position, __x);
806*e4b17023SJohn Marino       return begin() + __n;
807*e4b17023SJohn Marino     }
808*e4b17023SJohn Marino 
809*e4b17023SJohn Marino     template<typename _InputIterator>
810*e4b17023SJohn Marino       void
811*e4b17023SJohn Marino       insert(iterator __position,
812*e4b17023SJohn Marino 	     _InputIterator __first, _InputIterator __last)
813*e4b17023SJohn Marino       {
814*e4b17023SJohn Marino 	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
815*e4b17023SJohn Marino 	_M_insert_dispatch(__position, __first, __last, _Integral());
816*e4b17023SJohn Marino       }
817*e4b17023SJohn Marino 
818*e4b17023SJohn Marino     void
819*e4b17023SJohn Marino     insert(iterator __position, size_type __n, const bool& __x)
820*e4b17023SJohn Marino     { _M_fill_insert(__position, __n, __x); }
821*e4b17023SJohn Marino 
822*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
823*e4b17023SJohn Marino     void insert(iterator __p, initializer_list<bool> __l)
824*e4b17023SJohn Marino     { this->insert(__p, __l.begin(), __l.end()); }
825*e4b17023SJohn Marino #endif
826*e4b17023SJohn Marino 
827*e4b17023SJohn Marino     void
828*e4b17023SJohn Marino     pop_back()
829*e4b17023SJohn Marino     { --this->_M_impl._M_finish; }
830*e4b17023SJohn Marino 
831*e4b17023SJohn Marino     iterator
832*e4b17023SJohn Marino     erase(iterator __position)
833*e4b17023SJohn Marino     {
834*e4b17023SJohn Marino       if (__position + 1 != end())
835*e4b17023SJohn Marino         std::copy(__position + 1, end(), __position);
836*e4b17023SJohn Marino       --this->_M_impl._M_finish;
837*e4b17023SJohn Marino       return __position;
838*e4b17023SJohn Marino     }
839*e4b17023SJohn Marino 
840*e4b17023SJohn Marino     iterator
841*e4b17023SJohn Marino     erase(iterator __first, iterator __last)
842*e4b17023SJohn Marino     {
843*e4b17023SJohn Marino       if (__first != __last)
844*e4b17023SJohn Marino 	_M_erase_at_end(std::copy(__last, end(), __first));
845*e4b17023SJohn Marino       return __first;
846*e4b17023SJohn Marino     }
847*e4b17023SJohn Marino 
848*e4b17023SJohn Marino     void
849*e4b17023SJohn Marino     resize(size_type __new_size, bool __x = bool())
850*e4b17023SJohn Marino     {
851*e4b17023SJohn Marino       if (__new_size < size())
852*e4b17023SJohn Marino         _M_erase_at_end(begin() + difference_type(__new_size));
853*e4b17023SJohn Marino       else
854*e4b17023SJohn Marino         insert(end(), __new_size - size(), __x);
855*e4b17023SJohn Marino     }
856*e4b17023SJohn Marino 
857*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
858*e4b17023SJohn Marino     void
859*e4b17023SJohn Marino     shrink_to_fit()
860*e4b17023SJohn Marino     { _M_shrink_to_fit(); }
861*e4b17023SJohn Marino #endif
862*e4b17023SJohn Marino 
863*e4b17023SJohn Marino     void
864*e4b17023SJohn Marino     flip() _GLIBCXX_NOEXCEPT
865*e4b17023SJohn Marino     {
866*e4b17023SJohn Marino       for (_Bit_type * __p = this->_M_impl._M_start._M_p;
867*e4b17023SJohn Marino 	   __p != this->_M_impl._M_end_of_storage; ++__p)
868*e4b17023SJohn Marino         *__p = ~*__p;
869*e4b17023SJohn Marino     }
870*e4b17023SJohn Marino 
871*e4b17023SJohn Marino     void
872*e4b17023SJohn Marino     clear() _GLIBCXX_NOEXCEPT
873*e4b17023SJohn Marino     { _M_erase_at_end(begin()); }
874*e4b17023SJohn Marino 
875*e4b17023SJohn Marino 
876*e4b17023SJohn Marino   protected:
877*e4b17023SJohn Marino     // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
878*e4b17023SJohn Marino     iterator
879*e4b17023SJohn Marino     _M_copy_aligned(const_iterator __first, const_iterator __last,
880*e4b17023SJohn Marino 		    iterator __result)
881*e4b17023SJohn Marino     {
882*e4b17023SJohn Marino       _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
883*e4b17023SJohn Marino       return std::copy(const_iterator(__last._M_p, 0), __last,
884*e4b17023SJohn Marino 		       iterator(__q, 0));
885*e4b17023SJohn Marino     }
886*e4b17023SJohn Marino 
887*e4b17023SJohn Marino     void
888*e4b17023SJohn Marino     _M_initialize(size_type __n)
889*e4b17023SJohn Marino     {
890*e4b17023SJohn Marino       _Bit_type* __q = this->_M_allocate(__n);
891*e4b17023SJohn Marino       this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
892*e4b17023SJohn Marino       this->_M_impl._M_start = iterator(__q, 0);
893*e4b17023SJohn Marino       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
894*e4b17023SJohn Marino     }
895*e4b17023SJohn Marino 
896*e4b17023SJohn Marino     void
897*e4b17023SJohn Marino     _M_reallocate(size_type __n);
898*e4b17023SJohn Marino 
899*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
900*e4b17023SJohn Marino     bool
901*e4b17023SJohn Marino     _M_shrink_to_fit();
902*e4b17023SJohn Marino #endif
903*e4b17023SJohn Marino 
904*e4b17023SJohn Marino     // Check whether it's an integral type.  If so, it's not an iterator.
905*e4b17023SJohn Marino 
906*e4b17023SJohn Marino     // _GLIBCXX_RESOLVE_LIB_DEFECTS
907*e4b17023SJohn Marino     // 438. Ambiguity in the "do the right thing" clause
908*e4b17023SJohn Marino     template<typename _Integer>
909*e4b17023SJohn Marino       void
910*e4b17023SJohn Marino       _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
911*e4b17023SJohn Marino       {
912*e4b17023SJohn Marino 	_M_initialize(static_cast<size_type>(__n));
913*e4b17023SJohn Marino 	std::fill(this->_M_impl._M_start._M_p,
914*e4b17023SJohn Marino 		  this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
915*e4b17023SJohn Marino       }
916*e4b17023SJohn Marino 
917*e4b17023SJohn Marino     template<typename _InputIterator>
918*e4b17023SJohn Marino       void
919*e4b17023SJohn Marino       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
920*e4b17023SJohn Marino 			     __false_type)
921*e4b17023SJohn Marino       { _M_initialize_range(__first, __last,
922*e4b17023SJohn Marino 			    std::__iterator_category(__first)); }
923*e4b17023SJohn Marino 
924*e4b17023SJohn Marino     template<typename _InputIterator>
925*e4b17023SJohn Marino       void
926*e4b17023SJohn Marino       _M_initialize_range(_InputIterator __first, _InputIterator __last,
927*e4b17023SJohn Marino 			  std::input_iterator_tag)
928*e4b17023SJohn Marino       {
929*e4b17023SJohn Marino 	for (; __first != __last; ++__first)
930*e4b17023SJohn Marino 	  push_back(*__first);
931*e4b17023SJohn Marino       }
932*e4b17023SJohn Marino 
933*e4b17023SJohn Marino     template<typename _ForwardIterator>
934*e4b17023SJohn Marino       void
935*e4b17023SJohn Marino       _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
936*e4b17023SJohn Marino 			  std::forward_iterator_tag)
937*e4b17023SJohn Marino       {
938*e4b17023SJohn Marino 	const size_type __n = std::distance(__first, __last);
939*e4b17023SJohn Marino 	_M_initialize(__n);
940*e4b17023SJohn Marino 	std::copy(__first, __last, this->_M_impl._M_start);
941*e4b17023SJohn Marino       }
942*e4b17023SJohn Marino 
943*e4b17023SJohn Marino     // _GLIBCXX_RESOLVE_LIB_DEFECTS
944*e4b17023SJohn Marino     // 438. Ambiguity in the "do the right thing" clause
945*e4b17023SJohn Marino     template<typename _Integer>
946*e4b17023SJohn Marino       void
947*e4b17023SJohn Marino       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
948*e4b17023SJohn Marino       { _M_fill_assign(__n, __val); }
949*e4b17023SJohn Marino 
950*e4b17023SJohn Marino     template<class _InputIterator>
951*e4b17023SJohn Marino       void
952*e4b17023SJohn Marino       _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
953*e4b17023SJohn Marino 			 __false_type)
954*e4b17023SJohn Marino       { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
955*e4b17023SJohn Marino 
956*e4b17023SJohn Marino     void
957*e4b17023SJohn Marino     _M_fill_assign(size_t __n, bool __x)
958*e4b17023SJohn Marino     {
959*e4b17023SJohn Marino       if (__n > size())
960*e4b17023SJohn Marino 	{
961*e4b17023SJohn Marino 	  std::fill(this->_M_impl._M_start._M_p,
962*e4b17023SJohn Marino 		    this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
963*e4b17023SJohn Marino 	  insert(end(), __n - size(), __x);
964*e4b17023SJohn Marino 	}
965*e4b17023SJohn Marino       else
966*e4b17023SJohn Marino 	{
967*e4b17023SJohn Marino 	  _M_erase_at_end(begin() + __n);
968*e4b17023SJohn Marino 	  std::fill(this->_M_impl._M_start._M_p,
969*e4b17023SJohn Marino 		    this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
970*e4b17023SJohn Marino 	}
971*e4b17023SJohn Marino     }
972*e4b17023SJohn Marino 
973*e4b17023SJohn Marino     template<typename _InputIterator>
974*e4b17023SJohn Marino       void
975*e4b17023SJohn Marino       _M_assign_aux(_InputIterator __first, _InputIterator __last,
976*e4b17023SJohn Marino 		    std::input_iterator_tag)
977*e4b17023SJohn Marino       {
978*e4b17023SJohn Marino 	iterator __cur = begin();
979*e4b17023SJohn Marino 	for (; __first != __last && __cur != end(); ++__cur, ++__first)
980*e4b17023SJohn Marino 	  *__cur = *__first;
981*e4b17023SJohn Marino 	if (__first == __last)
982*e4b17023SJohn Marino 	  _M_erase_at_end(__cur);
983*e4b17023SJohn Marino 	else
984*e4b17023SJohn Marino 	  insert(end(), __first, __last);
985*e4b17023SJohn Marino       }
986*e4b17023SJohn Marino 
987*e4b17023SJohn Marino     template<typename _ForwardIterator>
988*e4b17023SJohn Marino       void
989*e4b17023SJohn Marino       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
990*e4b17023SJohn Marino 		    std::forward_iterator_tag)
991*e4b17023SJohn Marino       {
992*e4b17023SJohn Marino 	const size_type __len = std::distance(__first, __last);
993*e4b17023SJohn Marino 	if (__len < size())
994*e4b17023SJohn Marino 	  _M_erase_at_end(std::copy(__first, __last, begin()));
995*e4b17023SJohn Marino 	else
996*e4b17023SJohn Marino 	  {
997*e4b17023SJohn Marino 	    _ForwardIterator __mid = __first;
998*e4b17023SJohn Marino 	    std::advance(__mid, size());
999*e4b17023SJohn Marino 	    std::copy(__first, __mid, begin());
1000*e4b17023SJohn Marino 	    insert(end(), __mid, __last);
1001*e4b17023SJohn Marino 	  }
1002*e4b17023SJohn Marino       }
1003*e4b17023SJohn Marino 
1004*e4b17023SJohn Marino     // Check whether it's an integral type.  If so, it's not an iterator.
1005*e4b17023SJohn Marino 
1006*e4b17023SJohn Marino     // _GLIBCXX_RESOLVE_LIB_DEFECTS
1007*e4b17023SJohn Marino     // 438. Ambiguity in the "do the right thing" clause
1008*e4b17023SJohn Marino     template<typename _Integer>
1009*e4b17023SJohn Marino       void
1010*e4b17023SJohn Marino       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1011*e4b17023SJohn Marino 			 __true_type)
1012*e4b17023SJohn Marino       { _M_fill_insert(__pos, __n, __x); }
1013*e4b17023SJohn Marino 
1014*e4b17023SJohn Marino     template<typename _InputIterator>
1015*e4b17023SJohn Marino       void
1016*e4b17023SJohn Marino       _M_insert_dispatch(iterator __pos,
1017*e4b17023SJohn Marino 			 _InputIterator __first, _InputIterator __last,
1018*e4b17023SJohn Marino 			 __false_type)
1019*e4b17023SJohn Marino       { _M_insert_range(__pos, __first, __last,
1020*e4b17023SJohn Marino 			std::__iterator_category(__first)); }
1021*e4b17023SJohn Marino 
1022*e4b17023SJohn Marino     void
1023*e4b17023SJohn Marino     _M_fill_insert(iterator __position, size_type __n, bool __x);
1024*e4b17023SJohn Marino 
1025*e4b17023SJohn Marino     template<typename _InputIterator>
1026*e4b17023SJohn Marino       void
1027*e4b17023SJohn Marino       _M_insert_range(iterator __pos, _InputIterator __first,
1028*e4b17023SJohn Marino 		      _InputIterator __last, std::input_iterator_tag)
1029*e4b17023SJohn Marino       {
1030*e4b17023SJohn Marino 	for (; __first != __last; ++__first)
1031*e4b17023SJohn Marino 	  {
1032*e4b17023SJohn Marino 	    __pos = insert(__pos, *__first);
1033*e4b17023SJohn Marino 	    ++__pos;
1034*e4b17023SJohn Marino 	  }
1035*e4b17023SJohn Marino       }
1036*e4b17023SJohn Marino 
1037*e4b17023SJohn Marino     template<typename _ForwardIterator>
1038*e4b17023SJohn Marino       void
1039*e4b17023SJohn Marino       _M_insert_range(iterator __position, _ForwardIterator __first,
1040*e4b17023SJohn Marino 		      _ForwardIterator __last, std::forward_iterator_tag);
1041*e4b17023SJohn Marino 
1042*e4b17023SJohn Marino     void
1043*e4b17023SJohn Marino     _M_insert_aux(iterator __position, bool __x);
1044*e4b17023SJohn Marino 
1045*e4b17023SJohn Marino     size_type
1046*e4b17023SJohn Marino     _M_check_len(size_type __n, const char* __s) const
1047*e4b17023SJohn Marino     {
1048*e4b17023SJohn Marino       if (max_size() - size() < __n)
1049*e4b17023SJohn Marino 	__throw_length_error(__N(__s));
1050*e4b17023SJohn Marino 
1051*e4b17023SJohn Marino       const size_type __len = size() + std::max(size(), __n);
1052*e4b17023SJohn Marino       return (__len < size() || __len > max_size()) ? max_size() : __len;
1053*e4b17023SJohn Marino     }
1054*e4b17023SJohn Marino 
1055*e4b17023SJohn Marino     void
1056*e4b17023SJohn Marino     _M_erase_at_end(iterator __pos)
1057*e4b17023SJohn Marino     { this->_M_impl._M_finish = __pos; }
1058*e4b17023SJohn Marino   };
1059*e4b17023SJohn Marino 
1060*e4b17023SJohn Marino _GLIBCXX_END_NAMESPACE_CONTAINER
1061*e4b17023SJohn Marino } // namespace std
1062*e4b17023SJohn Marino 
1063*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
1064*e4b17023SJohn Marino 
1065*e4b17023SJohn Marino #include <bits/functional_hash.h>
1066*e4b17023SJohn Marino 
_GLIBCXX_VISIBILITY(default)1067*e4b17023SJohn Marino namespace std _GLIBCXX_VISIBILITY(default)
1068*e4b17023SJohn Marino {
1069*e4b17023SJohn Marino _GLIBCXX_BEGIN_NAMESPACE_VERSION
1070*e4b17023SJohn Marino 
1071*e4b17023SJohn Marino   // DR 1182.
1072*e4b17023SJohn Marino   /// std::hash specialization for vector<bool>.
1073*e4b17023SJohn Marino   template<typename _Alloc>
1074*e4b17023SJohn Marino     struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
1075*e4b17023SJohn Marino     : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1076*e4b17023SJohn Marino     {
1077*e4b17023SJohn Marino       size_t
1078*e4b17023SJohn Marino       operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
1079*e4b17023SJohn Marino     };
1080*e4b17023SJohn Marino 
1081*e4b17023SJohn Marino _GLIBCXX_END_NAMESPACE_VERSION
1082*e4b17023SJohn Marino }// namespace std
1083*e4b17023SJohn Marino 
1084*e4b17023SJohn Marino #endif // __GXX_EXPERIMENTAL_CXX0X__
1085*e4b17023SJohn Marino 
1086*e4b17023SJohn Marino #endif
1087