ReactOS  0.4.14-dev-49-gfb4591c
_bvector.h
Go to the documentation of this file.
1 /*
2  *
3  * Copyright (c) 1994
4  * Hewlett-Packard Company
5  *
6  * Copyright (c) 1996,1997
7  * Silicon Graphics Computer Systems, Inc.
8  *
9  * Copyright (c) 1997
10  * Moscow Center for SPARC Technology
11  *
12  * Copyright (c) 1999
13  * Boris Fomitchev
14  *
15  * This material is provided "as is", with absolutely no warranty expressed
16  * or implied. Any use is at your own risk.
17  *
18  * Permission to use or copy this software for any purpose is hereby granted
19  * without fee, provided the above notices are retained on all copies.
20  * Permission to modify the code and to distribute modified code is granted,
21  * provided the above notices are retained, and a notice that the code was
22  * modified is included with the above copyright notice.
23  *
24  */
25 
26 /* NOTE: This is an internal header file, included by other STL headers.
27  * You should not attempt to use it directly.
28  */
29 
30 #ifndef _STLP_INTERNAL_BVECTOR_H
31 #define _STLP_INTERNAL_BVECTOR_H
32 
33 #ifndef _STLP_INTERNAL_VECTOR_H
34 # include <stl/_vector.h>
35 #endif
36 
37 #define _STLP_WORD_BIT (int(CHAR_BIT * sizeof(unsigned int)))
38 
41 
43  unsigned int* _M_p;
44  unsigned int _M_mask;
45  _Bit_reference(unsigned int* __x, unsigned int __y)
46  : _M_p(__x), _M_mask(__y) {}
47 
48 public:
49  _Bit_reference() : _M_p(0), _M_mask(0) {}
50 
51  operator bool() const {
52  return !(!(*_M_p & _M_mask));
53  }
55  if (__x) *_M_p |= _M_mask;
56  else *_M_p &= ~_M_mask;
57  return *this;
58  }
60  return *this = bool(__x);
61  }
62  bool operator == (const _Bit_reference& __x) const {
63  return bool(*this) == bool(__x);
64  }
65  bool operator < (const _Bit_reference& __x) const {
66  return !bool(*this) && bool(__x);
67  }
68 
70  if (__x)
71  *_M_p |= _M_mask;
72  return *this;
73  }
75  if (!__x)
76  *_M_p &= ~_M_mask;
77  return *this;
78  }
79  void flip() { *_M_p ^= _M_mask; }
80 };
81 
82 
84 
86  bool __tmp = (bool)__x;
87  __x = __y;
88  __y = __tmp;
89 }
90 
91 // Might not be very useful but costs nothing!
99 };
100 
102 
105 
106  unsigned int* _M_p;
107  unsigned int _M_offset;
108 
109  void _M_bump_up() {
110  if (_M_offset++ == _STLP_WORD_BIT - 1) {
111  _M_offset = 0;
112  ++_M_p;
113  }
114  }
115 
116  void _M_bump_down() {
117  if (_M_offset-- == 0) {
119  --_M_p;
120  }
121  }
122 
124  _Bit_iterator_base(unsigned int* __x, unsigned int __y) : _M_p(__x), _M_offset(__y) {}
125 // see comment in doc/README.evc4 and doc/README.evc8
126 #if defined(_MSC_VER) && _MSC_VER<=1401 && defined(MIPS) && defined(NDEBUG)
128 #endif
129  // _Bit_iterator_base& operator = ( const _Bit_iterator_base& __x) { _M_p = __x._M_p ; _M_offset = __x._M_offset ; return *this; }
130 
132  difference_type __n = __i + _M_offset;
133  _M_p += __n / _STLP_WORD_BIT;
134  __n = __n % _STLP_WORD_BIT;
135  if (__n < 0) {
136  _M_offset = (unsigned int) __n + _STLP_WORD_BIT;
137  --_M_p;
138  } else
139  _M_offset = (unsigned int) __n;
140  }
141 
143  return _STLP_WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset;
144  }
145 };
146 
147 inline bool _STLP_CALL operator==(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
148  return __y._M_p == __x._M_p && __y._M_offset == __x._M_offset;
149 }
150 inline bool _STLP_CALL operator!=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
151  return __y._M_p != __x._M_p || __y._M_offset != __x._M_offset;
152 }
153 
154 inline bool _STLP_CALL operator<(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
155  return __x._M_p < __y._M_p || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset);
156 }
157 
158 inline bool _STLP_CALL operator>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
159  return operator <(__y , __x);
160 }
161 inline bool _STLP_CALL operator<=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
162  return !(__y < __x);
163 }
164 inline bool _STLP_CALL operator>=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
165  return !(__x < __y);
166 }
167 
168 template <class _Ref, class _Ptr>
169 struct _Bit_iter : public _Bit_iterator_base {
170  typedef _Ref reference;
171  typedef _Ptr pointer;
174  typedef bool value_type;
176  typedef size_t size_type;
177 
178  _Bit_iter(unsigned int* __x, unsigned int __y) : _Bit_iterator_base(__x, __y) {}
180 
183 
184  // _Self& operator = (const _Bit_iter<_Bit_reference, _Bit_reference*>& __x)
185  // { (_Bit_iterator_base&)*this = (const _Bit_iterator_base&)__x; return *this; }
186 
188  return _Bit_reference(_M_p, 1UL << _M_offset);
189  }
191  _M_bump_up();
192  return *this;
193  }
195  _Self __tmp = *this;
196  _M_bump_up();
197  return __tmp;
198  }
200  _M_bump_down();
201  return *this;
202  }
204  _Self __tmp = *this;
205  _M_bump_down();
206  return __tmp;
207  }
209  _M_advance(__i);
210  return *this;
211  }
213  *this += -__i;
214  return *this;
215  }
217  _Self __tmp = *this;
218  return __tmp += __i;
219  }
221  _Self __tmp = *this;
222  return __tmp -= __i;
223  }
224  difference_type operator-(const _Self& __x) const {
225  return _M_subtract(__x);
226  }
227  reference operator[](difference_type __i) { return *(*this + __i); }
228 };
229 
230 template <class _Ref, class _Ptr>
233  return __x + __n;
234 }
235 
237 
238 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
239 template <class _Ref, class _Ptr>
240 struct __type_traits< _STLP_PRIV _Bit_iter<_Ref, _Ptr> > {
245  typedef __false_type is_POD_type;
246 };
247 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
248 
249 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
250 inline random_access_iterator_tag iterator_category(const _STLP_PRIV _Bit_iterator_base&)
251 { return random_access_iterator_tag(); }
252 inline ptrdiff_t* distance_type(const _STLP_PRIV _Bit_iterator_base&)
253 { return (ptrdiff_t*)0; }
255 { return (bool*)0; }
256 inline bool* value_type(const _STLP_PRIV _Bit_iter<bool, const bool*>&)
257 { return (bool*)0; }
258 #endif
259 
261 
264 
265 // Bit-vector base class, which encapsulates the difference between
266 // old SGI-style allocators and standard-conforming allocators.
267 template <class _Alloc>
270 public:
273  typedef unsigned int __chunk_type;
277 
280  (__chunk_type*)0)
281  {}
282 #if !defined (_STLP_NO_MOVE_SEMANTIC)
286  //Make the source destroyable
287  src.get()._M_start._M_p = 0;
288  }
289 #endif
290 
292  _M_deallocate();
293  }
294 
295 protected:
296 
297  static size_t _M_bits_to_chunks(size_t __n_bits)
298  { return (__n_bits + _STLP_WORD_BIT - 1) / _STLP_WORD_BIT; }
299 
302 
303  void _M_deallocate() {
304  if (_M_start._M_p)
305  _M_end_of_storage.deallocate(_M_start._M_p,
307  }
308 
312 };
313 
314 
315 // The next few lines are confusing. What we're doing is declaring a
316 // partial specialization of vector<T, Alloc> if we have the necessary
317 // compiler support. Otherwise, we define a class bit_vector which uses
318 // the default allocator.
319 
320 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_BOOL) && !defined (__SUNPRO_CC)
321 # define _STLP_VECBOOL_TEMPLATE
322 # define __BVEC_TMPL_HEADER template <class _Alloc>
323 #else
324 # undef _STLP_VECBOOL_TEMPLATE
325 # ifdef _STLP_NO_BOOL
326 # define __BVEC_TMPL_HEADER
327 # else
328 # define __BVEC_TMPL_HEADER _STLP_TEMPLATE_NULL
329 # endif
330 # define _Alloc allocator<bool>
331 #endif
332 
333 #if defined (_STLP_DEBUG)
334 # define vector _STLP_NON_DBG_NAME(vector)
335 #endif
336 
337 #ifdef _STLP_NO_BOOL
338 # define __BVECTOR_QUALIFIED bit_vector
339 # define __BVECTOR bit_vector
340 #else
341 # ifdef _STLP_VECBOOL_TEMPLATE
342 # define __BVECTOR_QUALIFIED vector<bool, _Alloc>
343 # else
344 # define __BVECTOR_QUALIFIED vector<bool, allocator<bool> >
345 # endif
346 # if defined (_STLP_PARTIAL_SPEC_NEEDS_TEMPLATE_ARGS)
347 # define __BVECTOR __BVECTOR_QUALIFIED
348 # else
349 # define __BVECTOR vector
350 # endif
351 #endif
352 
353 #if !defined (_STLP_DEBUG) || defined (_STLP_NO_BOOL)
355 #endif
356 
359 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_DEBUG)
360  , public __stlport_class< __BVECTOR_QUALIFIED >
361 #endif
362 {
365 public:
366  typedef bool value_type;
367  typedef size_t size_type;
370  typedef bool const_reference;
372  typedef const bool* const_pointer;
374 
377 
379 
380 #ifdef _STLP_VECBOOL_TEMPLATE
383 #else
386 #endif
387 
388 protected:
389 
391  __chunk_type* __q = this->_M_bit_alloc(__n);
392  this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__n);
393  this->_M_start = iterator(__q, 0);
394  this->_M_finish = this->_M_start + difference_type(__n);
395  }
396  void _M_insert_aux(iterator __position, bool __x) {
397  if (this->_M_finish._M_p != this->_M_end_of_storage._M_data) {
398  _STLP_PRIV __copy_backward(__position, this->_M_finish, this->_M_finish + 1,
400  *__position = __x;
401  ++this->_M_finish;
402  }
403  else {
404  size_type __len = size() ? 2 * size() : _STLP_WORD_BIT;
405  __chunk_type* __q = this->_M_bit_alloc(__len);
406  iterator __i = _STLP_STD::copy(begin(), __position, iterator(__q, 0));
407  *__i++ = __x;
408  this->_M_finish = _STLP_STD::copy(__position, end(), __i);
409  this->_M_deallocate();
410  this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__len);
411  this->_M_start = iterator(__q, 0);
412  }
413  }
414 
415 #if defined (_STLP_MEMBER_TEMPLATES)
416  template <class _InputIterator>
417  void _M_initialize_range(_InputIterator __first, _InputIterator __last,
418  const input_iterator_tag &) {
419  this->_M_start = iterator();
420  this->_M_finish = iterator();
421  this->_M_end_of_storage._M_data = 0;
422  for ( ; __first != __last; ++__first)
423  push_back(*__first);
424  }
425 
426  template <class _ForwardIterator>
427  void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
428  const forward_iterator_tag &) {
431  _STLP_STD::copy(__first, __last, this->_M_start);
432  }
433 
434  template <class _InputIterator>
435  void _M_insert_range(iterator __pos,
436  _InputIterator __first, _InputIterator __last,
437  const input_iterator_tag &) {
438  for ( ; __first != __last; ++__first) {
439  __pos = insert(__pos, *__first);
440  ++__pos;
441  }
442  }
443 
444  template <class _ForwardIterator>
445  void _M_insert_range(iterator __position,
446  _ForwardIterator __first, _ForwardIterator __last,
447  const forward_iterator_tag &) {
448  if (__first != __last) {
450  if (capacity() - size() >= __n) {
451  _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + difference_type(__n),
453  _STLP_STD::copy(__first, __last, __position);
454  this->_M_finish += difference_type(__n);
455  }
456  else {
457  size_type __len = size() + (max)(size(), __n);
458  __chunk_type* __q = this->_M_bit_alloc(__len);
459  iterator __i = _STLP_STD::copy(begin(), __position, iterator(__q, 0));
460  __i = _STLP_STD::copy(__first, __last, __i);
461  this->_M_finish = _STLP_STD::copy(__position, end(), __i);
462  this->_M_deallocate();
463  this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__len);
464  this->_M_start = iterator(__q, 0);
465  }
466  }
467  }
468 
469 #endif /* _STLP_MEMBER_TEMPLATES */
470 
471 public:
472  iterator begin() { return this->_M_start; }
473  const_iterator begin() const { return this->_M_start; }
474  iterator end() { return this->_M_finish; }
475  const_iterator end() const { return this->_M_finish; }
476 
478  const_reverse_iterator rbegin() const {
479  return const_reverse_iterator(end());
480  }
482  const_reverse_iterator rend() const {
483  return const_reverse_iterator(begin());
484  }
485 
486  size_type size() const { return size_type(end() - begin()); }
487  size_type max_size() const { return size_type(-1); }
488  size_type capacity() const {
489  return size_type(const_iterator(this->_M_end_of_storage._M_data, 0) - begin());
490  }
491  bool empty() const { return begin() == end(); }
493  { return *(begin() + difference_type(__n)); }
495  { return *(begin() + difference_type(__n)); }
496 
498  if (__n >= this->size())
499  __stl_throw_range_error("vector<bool>");
500  }
501 
502  reference at(size_type __n)
503  { _M_range_check(__n); return (*this)[__n]; }
505  { _M_range_check(__n); return (*this)[__n]; }
506 
507  explicit __BVECTOR(const allocator_type& __a = allocator_type())
508  : _STLP_PRIV _Bvector_base<_Alloc >(__a) {}
509 
511  const allocator_type& __a = allocator_type())
512  : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
514  fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), __val ? ~0 : 0);
515  }
516 
520  fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), 0);
521  }
522 
523  __BVECTOR(const _Self& __x)
524  : _STLP_PRIV _Bvector_base<_Alloc >(__x.get_allocator()) {
525  _M_initialize(__x.size());
526  _STLP_STD::copy(__x.begin(), __x.end(), this->_M_start);
527  }
528 
529 #if defined (_STLP_MEMBER_TEMPLATES)
530  template <class _Integer>
531  void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type&) {
533  fill(this->_M_start._M_p, this->_M_end_of_storage._M_data, __x ? ~0 : 0);
534  }
535 
536  template <class _InputIterator>
537  void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
538  const __false_type&) {
539  _M_initialize_range(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
540  }
541 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
542  // Check whether it's an integral type. If so, it's not an iterator.
543  template <class _InputIterator>
544  __BVECTOR(_InputIterator __first, _InputIterator __last)
546  typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
547  _M_initialize_dispatch(__first, __last, _Integral());
548  }
549 # endif
550  template <class _InputIterator>
551  __BVECTOR(_InputIterator __first, _InputIterator __last,
553  : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
554  typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
555  _M_initialize_dispatch(__first, __last, _Integral());
556  }
557 #else /* _STLP_MEMBER_TEMPLATES */
559  const allocator_type& __a = allocator_type())
560  : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
563  _STLP_STD::copy(__first, __last, this->_M_start);
564  }
565  __BVECTOR(const bool* __first, const bool* __last,
566  const allocator_type& __a = allocator_type())
567  : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
570  _STLP_STD::copy(__first, __last, this->_M_start);
571  }
572 #endif /* _STLP_MEMBER_TEMPLATES */
573 
574 #if !defined (_STLP_NO_MOVE_SEMANTIC)
577 #endif
578 
580 
582  if (&__x == this) return *this;
583  if (__x.size() > capacity()) {
584  this->_M_deallocate();
585  _M_initialize(__x.size());
586  }
587  _STLP_STD::copy(__x.begin(), __x.end(), begin());
588  this->_M_finish = begin() + difference_type(__x.size());
589  return *this;
590  }
591 
592  // assign(), a generalized assignment member function. Two
593  // versions: one that takes a count, and one that takes a range.
594  // The range version is a member template, so we dispatch on whether
595  // or not the type is an integer.
596 
597  void _M_fill_assign(size_t __n, bool __x) {
598  if (__n > size()) {
599  fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), __x ? ~0 : 0);
600  insert(end(), __n - size(), __x);
601  }
602  else {
603  erase(begin() + __n, end());
604  fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), __x ? ~0 : 0);
605  }
606  }
607  void assign(size_t __n, bool __x) { _M_fill_assign(__n, __x); }
608 
609 #if defined (_STLP_MEMBER_TEMPLATES)
610  template <class _InputIterator>
611  void assign(_InputIterator __first, _InputIterator __last) {
612  typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
613  _M_assign_dispatch(__first, __last, _Integral());
614  }
615 
616  template <class _Integer>
617  void _M_assign_dispatch(_Integer __n, _Integer __val, const __true_type&)
618  { _M_fill_assign((size_t) __n, (bool) __val); }
619 
620  template <class _InputIter>
621  void _M_assign_dispatch(_InputIter __first, _InputIter __last, const __false_type&)
622  { _M_assign_aux(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); }
623 
624  template <class _InputIterator>
625  void _M_assign_aux(_InputIterator __first, _InputIterator __last,
626  const input_iterator_tag &) {
627  iterator __cur = begin();
628  for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
629  *__cur = *__first;
630  if (__first == __last)
631  erase(__cur, end());
632  else
633  insert(end(), __first, __last);
634  }
635 
636  template <class _ForwardIterator>
637  void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
638  const forward_iterator_tag &) {
639  size_type __len = _STLP_STD::distance(__first, __last);
640  if (__len < size())
641  erase(_STLP_STD::copy(__first, __last, begin()), end());
642  else {
643  _ForwardIterator __mid = __first;
644  _STLP_STD::advance(__mid, size());
645  _STLP_STD::copy(__first, __mid, begin());
646  insert(end(), __mid, __last);
647  }
648  }
649 #endif /* _STLP_MEMBER_TEMPLATES */
650 
652  if (capacity() < __n) {
653  if (max_size() < __n)
654  __stl_throw_length_error("vector<bool>");
655  __chunk_type* __q = this->_M_bit_alloc(__n);
656  _STLP_PRIV _Bit_iterator __z(__q, 0);
657  this->_M_finish = _STLP_STD::copy(begin(), end(), __z);
658  this->_M_deallocate();
659  this->_M_start = iterator(__q, 0);
660  this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__n);
661  }
662  }
663 
664  reference front() { return *begin(); }
665  const_reference front() const { return *begin(); }
666  reference back() { return *(end() - 1); }
667  const_reference back() const { return *(end() - 1); }
668  void push_back(bool __x) {
669  if (this->_M_finish._M_p != this->_M_end_of_storage._M_data) {
670  *(this->_M_finish) = __x;
671  ++this->_M_finish;
672  }
673  else
674  _M_insert_aux(end(), __x);
675  }
677  _STLP_STD::swap(this->_M_start, __x._M_start);
678  _STLP_STD::swap(this->_M_finish, __x._M_finish);
679  this->_M_end_of_storage.swap(__x._M_end_of_storage);
680  }
681 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
682  void _M_swap_workaround(__BVECTOR_QUALIFIED& __x) { swap(__x); }
683 #endif
684 
685  iterator insert(iterator __position, bool __x = bool()) {
686  difference_type __n = __position - begin();
687  if (this->_M_finish._M_p != this->_M_end_of_storage._M_data && __position == end()) {
688  *(this->_M_finish) = __x;
689  ++this->_M_finish;
690  }
691  else
692  _M_insert_aux(__position, __x);
693  return begin() + __n;
694  }
695 
696 #if defined (_STLP_MEMBER_TEMPLATES)
697 
698  template <class _Integer>
699  void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
700  const __true_type&) {
701  _M_fill_insert(__pos, (size_type) __n, (bool) __x);
702  }
703 
704  template <class _InputIterator>
705  void _M_insert_dispatch(iterator __pos,
706  _InputIterator __first, _InputIterator __last,
707  const __false_type&) {
708  _M_insert_range(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
709  }
710 
711  // Check whether it's an integral type. If so, it's not an iterator.
712  template <class _InputIterator>
713  void insert(iterator __position,
714  _InputIterator __first, _InputIterator __last) {
715  typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
716  _M_insert_dispatch(__position, __first, __last, _Integral());
717  }
718 #else /* _STLP_MEMBER_TEMPLATES */
719  void insert(iterator __position,
721  if (__first == __last) return;
723  if (capacity() - size() >= __n) {
724  _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + __n,
726  _STLP_STD::copy(__first, __last, __position);
727  this->_M_finish += __n;
728  }
729  else {
730  size_type __len = size() + (max)(size(), __n);
731  __chunk_type* __q = this->_M_bit_alloc(__len);
732  iterator __i = _STLP_STD::copy(begin(), __position, iterator(__q, 0));
733  __i = _STLP_STD::copy(__first, __last, __i);
734  this->_M_finish = _STLP_STD::copy(__position, end(), __i);
735  this->_M_deallocate();
736  this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__len);
737  this->_M_start = iterator(__q, 0);
738  }
739  }
740 
741  void insert(iterator __position, const bool* __first, const bool* __last) {
742  if (__first == __last) return;
744  if (capacity() - size() >= __n) {
745  _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + __n,
747  _STLP_STD::copy(__first, __last, __position);
748  this->_M_finish += __n;
749  }
750  else {
751  size_type __len = size() + (max)(size(), __n);
752  __chunk_type* __q = this->_M_bit_alloc(__len);
753  iterator __i = _STLP_STD::copy(begin(), __position, iterator(__q, 0));
754  __i = _STLP_STD::copy(__first, __last, __i);
755  this->_M_finish = _STLP_STD::copy(__position, end(), __i);
756  this->_M_deallocate();
757  this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__len);
758  this->_M_start = iterator(__q, 0);
759  }
760  }
761 #endif /* _STLP_MEMBER_TEMPLATES */
762 
763  void _M_fill_insert(iterator __position, size_type __n, bool __x) {
764  if (__n == 0) return;
765  if (capacity() - size() >= __n) {
766  _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + difference_type(__n),
768  fill(__position, __position + difference_type(__n), __x);
769  this->_M_finish += difference_type(__n);
770  }
771  else {
772  size_type __len = size() + (max)(size(), __n);
773  __chunk_type* __q = this->_M_bit_alloc(__len);
774  iterator __i = _STLP_STD::copy(begin(), __position, iterator(__q, 0));
775  fill_n(__i, __n, __x);
776  this->_M_finish = _STLP_STD::copy(__position, end(), __i + difference_type(__n));
777  this->_M_deallocate();
778  this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__len);
779  this->_M_start = iterator(__q, 0);
780  }
781  }
782 
783  void insert(iterator __position, size_type __n, bool __x) {
784  _M_fill_insert(__position, __n, __x);
785  }
786 
787  void pop_back() {
788  --this->_M_finish;
789  }
790  iterator erase(iterator __position) {
791  if (__position + 1 != end())
792  _STLP_STD::copy(__position + 1, end(), __position);
793  --this->_M_finish;
794  return __position;
795  }
797  this->_M_finish = _STLP_STD::copy(__last, end(), __first);
798  return __first;
799  }
800  void resize(size_type __new_size, bool __x = bool()) {
801  if (__new_size < size())
802  erase(begin() + difference_type(__new_size), end());
803  else
804  insert(end(), __new_size - size(), __x);
805  }
806  void flip() {
807  for (__chunk_type* __p = this->_M_start._M_p; __p != this->_M_end_of_storage._M_data; ++__p)
808  *__p = ~*__p;
809  }
810 
811  void clear() { erase(begin(), end()); }
812 };
813 
814 #if defined (_STLP_NO_BOOL) || defined (__HP_aCC) // fixed soon (03/17/2000)
815 # define _STLP_TEMPLATE_HEADER __BVEC_TMPL_HEADER
816 # define _STLP_TEMPLATE_CONTAINER __BVECTOR_QUALIFIED
817 # include <stl/_relops_cont.h>
818 # undef _STLP_TEMPLATE_CONTAINER
819 # undef _STLP_TEMPLATE_HEADER
820 #endif /* NO_BOOL */
821 
822 #if defined (_STLP_DEBUG) && !defined (_STLP_NO_BOOL)
824 #endif
825 
827 
828 #undef vector
829 #undef _Alloc
830 #undef _STLP_VECBOOL_TEMPLATE
831 #undef __BVECTOR
832 #undef __BVECTOR_QUALIFIED
833 #undef __BVEC_TMPL_HEADER
834 
835 #undef _STLP_WORD_BIT
836 
837 #endif /* _STLP_INTERNAL_BVECTOR_H */
838 
839 // Local Variables:
840 // mode:C++
841 // End:
#define _STLP_CONVERT_ALLOCATOR(__a, _Tp)
Definition: _alloc.h:183
_Bit_iterator_base(unsigned int *__x, unsigned int __y)
Definition: _bvector.h:124
const_iterator begin() const
Definition: _bvector.h:473
__chunk_type * _M_bit_alloc(size_t __n)
Definition: _bvector.h:300
random_access_iterator_tag iterator_category
Definition: _bvector.h:173
#define max(a, b)
Definition: svc.c:63
void _M_fill_insert(iterator __position, size_type __n, bool __x)
Definition: _bvector.h:763
_Bit_iter()
Definition: _bvector.h:179
unsigned int _M_mask
Definition: _bvector.h:44
__BVECTOR_QUALIFIED & operator=(const __BVECTOR_QUALIFIED &__x)
Definition: _bvector.h:581
return __n
Definition: _algo.h:75
_STLP_PRIV _Bit_reference * pointer
Definition: _bvector.h:371
_Bit_iter(unsigned int *__x, unsigned int __y)
Definition: _bvector.h:178
__BVECTOR(const_iterator __first, const_iterator __last, const allocator_type &__a=allocator_type())
Definition: _bvector.h:558
__BVECTOR(__move_source< _Self > src)
Definition: _bvector.h:575
char typename[32]
Definition: main.c:84
#define random_access_iterator_tag
Definition: _abbrevs.h:28
__bool2type< pod >::_Ret is_POD_type
#define _Alloc
Definition: _bvector.h:330
#define _STLP_TYPENAME
Definition: features.h:612
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
void swap(__BVECTOR_QUALIFIED &__x)
Definition: _bvector.h:676
#define reverse_iterator
Definition: _abbrevs.h:34
unsigned int _M_offset
Definition: _bvector.h:107
unsigned int * _M_p
Definition: _bvector.h:43
allocator_type get_allocator() const
Definition: _bvector.h:275
size_type capacity() const
Definition: _bvector.h:488
void insert(iterator __position, const_iterator __first, const_iterator __last)
Definition: _bvector.h:719
_Self & operator-=(difference_type __i)
Definition: _bvector.h:212
_STLP_alloc_proxy< __chunk_type *, __chunk_type, __chunk_allocator_type > _M_end_of_storage
Definition: _bvector.h:311
size_t size_type
Definition: _bvector.h:176
_Ref reference
Definition: _bvector.h:170
_BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first, _BidirectionalIter1 __last, _BidirectionalIter2 __result, const bidirectional_iterator_tag &, _Distance *)
Definition: _algobase.h:232
void resize(size_type __new_size, bool __x=bool())
Definition: _bvector.h:800
_STLP_MOVE_TO_STD_NAMESPACE void swap(_STLP_PRIV _Bit_reference &__x, _STLP_PRIV _Bit_reference &__y)
Definition: _bvector.h:85
void insert(iterator __position, const bool *__first, const bool *__last)
Definition: _bvector.h:741
_Self operator++(int)
Definition: _bvector.h:194
_Self & operator--()
Definition: _bvector.h:199
_Bit_iterator _M_finish
Definition: _bvector.h:310
_Bit_reference & operator &=(bool __x)
Definition: _bvector.h:74
void _M_bump_down()
Definition: _bvector.h:116
GLuint GLuint end
Definition: gl.h:1545
const bool * const_pointer
Definition: _bvector.h:372
const_reverse_iterator rbegin() const
Definition: _bvector.h:478
iterator begin()
Definition: _bvector.h:472
_Self operator-(difference_type __i) const
Definition: _bvector.h:220
_STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS
Definition: _bvector.h:378
#define _STLP_ITERATOR_CATEGORY(_It, _Tp)
_Alloc_traits< __chunk_type, _Alloc >::allocator_type __chunk_allocator_type
Definition: _bvector.h:274
reverse_iterator rbegin()
Definition: _bvector.h:477
GLsizei GLsizei GLfloat distance
Definition: glext.h:11755
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
_Value _M_data
Definition: _alloc.h:478
reference operator *() const
Definition: _bvector.h:187
_Bit_reference & operator|=(bool __x)
Definition: _bvector.h:69
reverse_iterator rend()
Definition: _bvector.h:481
_Tp * allocate(size_type __n, size_type &__allocated_n)
Definition: _alloc.h:525
difference_type operator-(const _Self &__x) const
Definition: _bvector.h:224
reference front()
Definition: _bvector.h:664
bool operator==(const _Bit_reference &__x) const
Definition: _bvector.h:62
size_type size() const
Definition: _bvector.h:486
_STLP_PRIV _Bit_reference reference
Definition: _bvector.h:369
iterator erase(iterator __first, iterator __last)
Definition: _bvector.h:796
const_reference operator[](size_type __n) const
Definition: _bvector.h:494
iterator erase(iterator __position)
Definition: _bvector.h:790
_STLP_THROW_FUNCT_SPEC _STLP_CALL __stl_throw_range_error(const char *__msg)
Definition: _range_errors.c:66
ptrdiff_t difference_type
Definition: _bvector.h:175
_STLP_PRIV _Bvector_base< _Alloc >::__chunk_type __chunk_type
Definition: _bvector.h:385
void reserve(size_type __n)
Definition: _bvector.h:651
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_Bvector_base(__move_source< _Self > src)
Definition: _bvector.h:283
void _M_initialize(size_type __n)
Definition: _bvector.h:390
unsigned int * _M_p
Definition: _bvector.h:106
typedef bool(CARDLIBPROC *pCanDragProc)(CardRegion &stackobj
__BVECTOR(const _Self &__x)
Definition: _bvector.h:523
random_access_iterator_tag _Iterator_category
Definition: _bvector.h:373
difference_type _M_subtract(const _Bit_iterator_base &__x) const
Definition: _bvector.h:142
const_reference front() const
Definition: _bvector.h:665
reference back()
Definition: _bvector.h:666
_Self & operator++()
Definition: _bvector.h:190
_Alloc allocator_type
Definition: _bvector.h:272
void assign(size_t __n, bool __x)
Definition: _bvector.h:607
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
void get(int argc, const char *argv[])
Definition: cmds.c:480
void _M_range_check(size_type __n) const
Definition: _bvector.h:497
bool _STLP_CALL operator>=(const _Bit_iterator_base &__x, const _Bit_iterator_base &__y)
Definition: _bvector.h:164
bool _STLP_CALL operator==(const _Bit_iterator_base &__x, const _Bit_iterator_base &__y)
Definition: _bvector.h:147
unsigned int __chunk_type
Definition: _bvector.h:273
_Self operator--(int)
Definition: _bvector.h:203
_Bit_iter< _Bit_reference, _Bit_reference * > _Bit_iterator
Definition: _bvector.h:263
_STLP_MOVE_TO_STD_NAMESPACE void fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val)
Definition: _algobase.h:449
void push_back(bool __x)
Definition: _bvector.h:668
static size_t _M_bits_to_chunks(size_t __n_bits)
Definition: _bvector.h:297
#define _STLP_ALLOCATOR_TYPE_DFL
Definition: features.h:691
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
_Bvector_base(const allocator_type &__a)
Definition: _bvector.h:278
_Self operator+(difference_type __i) const
Definition: _bvector.h:216
bool _STLP_CALL operator<=(const _Bit_iterator_base &__x, const _Bit_iterator_base &__y)
Definition: _bvector.h:161
__bool2type< trivial_constructor >::_Ret has_trivial_default_constructor
void flip()
Definition: _bvector.h:79
#define __BVEC_TMPL_HEADER
Definition: _bvector.h:328
__BVECTOR(const allocator_type &__a=allocator_type())
Definition: _bvector.h:507
_STLP_THROW_FUNCT_SPEC _STLP_CALL __stl_throw_length_error(const char *__msg)
Definition: _range_errors.c:72
void insert(iterator __position, size_type __n, bool __x)
Definition: _bvector.h:783
bool value_type
Definition: _bvector.h:174
iterator end()
Definition: _bvector.h:474
_STLP_PRIV _Bvector_base< _Alloc >::allocator_type allocator_type
Definition: _bvector.h:384
size_type max_size() const
Definition: _bvector.h:487
#define _STLP_PRIV
Definition: _dm.h:70
reference at(size_type __n)
Definition: _bvector.h:502
_Bit_reference(unsigned int *__x, unsigned int __y)
Definition: _bvector.h:45
__BVECTOR(size_type __n, bool __val, const allocator_type &__a=allocator_type())
Definition: _bvector.h:510
_STLP_MOVE_TO_STD_NAMESPACE void _STLP_CALL advance(_InputIterator &__i, _Distance __n)
GLenum src
Definition: glext.h:6340
bool _STLP_CALL operator<(const _Bit_iterator_base &__x, const _Bit_iterator_base &__y)
Definition: _bvector.h:154
#define _STLP_TEMPLATE_NULL
Definition: features.h:652
_STLP_MOVE_TO_STD_NAMESPACE void fill_n(_OutputIter __first, _Size __n, const _Tp &__val)
Definition: _algobase.h:511
const_reverse_iterator rend() const
Definition: _bvector.h:482
_STLP_PRIV _Bit_iterator iterator
Definition: _bvector.h:375
void _M_advance(difference_type __i)
Definition: _bvector.h:131
_STLP_PRIV _Bit_const_iterator const_iterator
Definition: _bvector.h:376
bool _STLP_CALL operator!=(const _Bit_iterator_base &__x, const _Bit_iterator_base &__y)
Definition: _bvector.h:150
bool _STLP_CALL operator>(const _Bit_iterator_base &__x, const _Bit_iterator_base &__y)
Definition: _bvector.h:158
_STLP_MOVE_TO_STD_NAMESPACE _STLP_MOVE_TO_PRIV_NAMESPACE typedef _Bit_iter< bool, const bool * > _Bit_const_iterator
Definition: _bvector.h:262
iterator insert(iterator __position, bool __x=bool())
Definition: _bvector.h:685
_Self & operator+=(difference_type __i)
Definition: _bvector.h:208
__bool2type< trivial_assign >::_Ret has_trivial_assignment_operator
#define _STLP_END_NAMESPACE
Definition: features.h:503
reference operator[](size_type __n)
Definition: _bvector.h:492
__BVECTOR(size_type __n)
Definition: _bvector.h:517
INT copy(TCHAR source[MAX_PATH], TCHAR dest[MAX_PATH], INT append, DWORD lpdwFlags, BOOL bTouch)
Definition: copy.c:51
__bool2type< trivial_copy >::_Ret has_trivial_copy_constructor
_Bit_iterator _M_start
Definition: _bvector.h:309
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
_STLP_PRIV _Bvector_base< _Alloc > _Base
Definition: _bvector.h:363
const_iterator end() const
Definition: _bvector.h:475
void _M_insert_aux(iterator __position, bool __x)
Definition: _bvector.h:396
const_reference at(size_type __n) const
Definition: _bvector.h:504
void _M_deallocate()
Definition: _bvector.h:303
#define const
Definition: zconf.h:230
#define _STLP_WORD_BIT
Definition: _bvector.h:37
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
const_reference back() const
Definition: _bvector.h:667
reference operator[](difference_type __i)
Definition: _bvector.h:227
_Bit_iter< _Ref, _Ptr > _Self
Definition: _bvector.h:172
_Bit_iter< _Ref, _Ptr > _STLP_CALL operator+(ptrdiff_t __n, const _Bit_iter< _Ref, _Ptr > &__x)
Definition: _bvector.h:232
_Bvector_base< _Alloc > _Self
Definition: _bvector.h:269
#define UL
Definition: tui.h:83
#define _STLP_CALL
Definition: _bc.h:131
bool empty() const
Definition: _bvector.h:491
__BVECTOR_QUALIFIED _Self
Definition: _bvector.h:364
__bool2type< trivial_destructor >::_Ret has_trivial_destructor
bool operator<(const _Bit_reference &__x) const
Definition: _bvector.h:65
_Bit_iter(const _Bit_iter< _Bit_reference, _Bit_reference * > &__x)
Definition: _bvector.h:181
ptrdiff_t difference_type
Definition: _bvector.h:368
ptrdiff_t difference_type
Definition: _bvector.h:104
void _M_fill_assign(size_t __n, bool __x)
Definition: _bvector.h:597
_Ptr pointer
Definition: _bvector.h:171
__BVECTOR(const bool *__first, const bool *__last, const allocator_type &__a=allocator_type())
Definition: _bvector.h:565
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
_Bit_reference & operator=(bool __x)
Definition: _bvector.h:54
#define _STLP_FORCE_ALLOCATORS(a, y)
Definition: _alloc.h:436