_bvector.h revision e46c9386c4f79aa40185f79a19fc5b2a7ef528b3
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 39_STLP_BEGIN_NAMESPACE 40_STLP_MOVE_TO_PRIV_NAMESPACE 41 42struct _Bit_reference { 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 48public: 49 _Bit_reference() : _M_p(0), _M_mask(0) {} 50 51 operator bool() const { 52 return !(!(*_M_p & _M_mask)); 53 } 54 _Bit_reference& operator = (bool __x) { 55 if (__x) *_M_p |= _M_mask; 56 else *_M_p &= ~_M_mask; 57 return *this; 58 } 59 _Bit_reference& operator = (const _Bit_reference& __x) { 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 69 _Bit_reference& operator |= (bool __x) { 70 if (__x) 71 *_M_p |= _M_mask; 72 return *this; 73 } 74 _Bit_reference& operator &= (bool __x) { 75 if (!__x) 76 *_M_p &= ~_M_mask; 77 return *this; 78 } 79 void flip() { *_M_p ^= _M_mask; } 80}; 81 82 83_STLP_MOVE_TO_STD_NAMESPACE 84 85inline void swap(_STLP_PRIV _Bit_reference& __x, _STLP_PRIV _Bit_reference& __y) { 86 bool __tmp = (bool)__x; 87 __x = __y; 88 __y = __tmp; 89} 90 91// Might not be very useful but costs nothing! 92_STLP_TEMPLATE_NULL 93struct __type_traits<_STLP_PRIV _Bit_reference> { 94 typedef __false_type has_trivial_default_constructor; 95 typedef __true_type has_trivial_copy_constructor; 96 typedef __false_type has_trivial_assignment_operator; 97 typedef __true_type has_trivial_destructor; 98 typedef __false_type is_POD_type; 99}; 100 101_STLP_MOVE_TO_PRIV_NAMESPACE 102 103struct _Bit_iterator_base { 104 typedef ptrdiff_t difference_type; 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) { 118 _M_offset = _STLP_WORD_BIT - 1; 119 --_M_p; 120 } 121 } 122 123 _Bit_iterator_base() : _M_p(0), _M_offset(0) {} 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) 127 _Bit_iterator_base( const _Bit_iterator_base& __x) : _M_p(__x._M_p), _M_offset(__x._M_offset) {} 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 131 void _M_advance (difference_type __i) { 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 142 difference_type _M_subtract(const _Bit_iterator_base& __x) const { 143 return _STLP_WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset; 144 } 145}; 146 147inline 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} 150inline 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 154inline 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 158inline bool _STLP_CALL operator>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { 159 return operator <(__y , __x); 160} 161inline bool _STLP_CALL operator<=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { 162 return !(__y < __x); 163} 164inline bool _STLP_CALL operator>=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { 165 return !(__x < __y); 166} 167 168template <class _Ref, class _Ptr> 169struct _Bit_iter : public _Bit_iterator_base { 170 typedef _Ref reference; 171 typedef _Ptr pointer; 172 typedef _Bit_iter<_Ref, _Ptr> _Self; 173 typedef random_access_iterator_tag iterator_category; 174 typedef bool value_type; 175 typedef ptrdiff_t difference_type; 176 typedef size_t size_type; 177 178 _Bit_iter(unsigned int* __x, unsigned int __y) : _Bit_iterator_base(__x, __y) {} 179 _Bit_iter() {} 180 181 _Bit_iter(const _Bit_iter<_Bit_reference, _Bit_reference*>& __x): 182 _Bit_iterator_base((const _Bit_iterator_base&)__x) {} 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 187 reference operator*() const { 188 return _Bit_reference(_M_p, 1UL << _M_offset); 189 } 190 _Self& operator++() { 191 _M_bump_up(); 192 return *this; 193 } 194 _Self operator++(int) { 195 _Self __tmp = *this; 196 _M_bump_up(); 197 return __tmp; 198 } 199 _Self& operator--() { 200 _M_bump_down(); 201 return *this; 202 } 203 _Self operator--(int) { 204 _Self __tmp = *this; 205 _M_bump_down(); 206 return __tmp; 207 } 208 _Self& operator+=(difference_type __i) { 209 _M_advance(__i); 210 return *this; 211 } 212 _Self& operator-=(difference_type __i) { 213 *this += -__i; 214 return *this; 215 } 216 _Self operator+(difference_type __i) const { 217 _Self __tmp = *this; 218 return __tmp += __i; 219 } 220 _Self operator-(difference_type __i) const { 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 230template <class _Ref, class _Ptr> 231inline _Bit_iter<_Ref,_Ptr> _STLP_CALL 232operator+(ptrdiff_t __n, const _Bit_iter<_Ref, _Ptr>& __x) { 233 return __x + __n; 234} 235 236_STLP_MOVE_TO_STD_NAMESPACE 237 238#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 239template <class _Ref, class _Ptr> 240struct __type_traits< _STLP_PRIV _Bit_iter<_Ref, _Ptr> > { 241 typedef __false_type has_trivial_default_constructor; 242 typedef __true_type has_trivial_copy_constructor; 243 typedef __true_type has_trivial_assignment_operator; 244 typedef __true_type has_trivial_destructor; 245 typedef __false_type is_POD_type; 246}; 247#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 248 249#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES) 250inline random_access_iterator_tag iterator_category(const _STLP_PRIV _Bit_iterator_base&) 251{ return random_access_iterator_tag(); } 252inline ptrdiff_t* distance_type(const _STLP_PRIV _Bit_iterator_base&) 253{ return (ptrdiff_t*)0; } 254inline bool* value_type(const _STLP_PRIV _Bit_iter<_STLP_PRIV _Bit_reference, _STLP_PRIV _Bit_reference*>&) 255{ return (bool*)0; } 256inline bool* value_type(const _STLP_PRIV _Bit_iter<bool, const bool*>&) 257{ return (bool*)0; } 258#endif 259 260_STLP_MOVE_TO_PRIV_NAMESPACE 261 262typedef _Bit_iter<bool, const bool*> _Bit_const_iterator; 263typedef _Bit_iter<_Bit_reference, _Bit_reference*> _Bit_iterator; 264 265// Bit-vector base class, which encapsulates the difference between 266// old SGI-style allocators and standard-conforming allocators. 267template <class _Alloc> 268class _Bvector_base { 269 typedef _Bvector_base<_Alloc> _Self; 270public: 271 _STLP_FORCE_ALLOCATORS(bool, _Alloc) 272 typedef _Alloc allocator_type; 273 typedef unsigned int __chunk_type; 274 typedef typename _Alloc_traits<__chunk_type, _Alloc>::allocator_type __chunk_allocator_type; 275 allocator_type get_allocator() const 276 { return _STLP_CONVERT_ALLOCATOR(__STATIC_CAST(const __chunk_allocator_type&, _M_end_of_storage), bool); } 277 278 _Bvector_base(const allocator_type& __a) 279 : _M_start(), _M_finish(), _M_end_of_storage(_STLP_CONVERT_ALLOCATOR(__a, __chunk_type), 280 (__chunk_type*)0) 281 {} 282#if !defined (_STLP_NO_MOVE_SEMANTIC) 283 _Bvector_base(__move_source<_Self> src) 284 : _M_start(src.get()._M_start), _M_finish(src.get()._M_finish), 285 _M_end_of_storage(src.get()._M_end_of_storage) { 286 //Make the source destroyable 287 src.get()._M_start._M_p = 0; 288 } 289#endif 290 291 ~_Bvector_base() { 292 _M_deallocate(); 293 } 294 295protected: 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 300 __chunk_type* _M_bit_alloc(size_t __n) 301 { return _M_end_of_storage.allocate(_M_bits_to_chunks(__n)); } 302 303 void _M_deallocate() { 304 if (_M_start._M_p) 305 _M_end_of_storage.deallocate(_M_start._M_p, 306 _M_end_of_storage._M_data - _M_start._M_p); 307 } 308 309 _Bit_iterator _M_start; 310 _Bit_iterator _M_finish; 311 _STLP_alloc_proxy<__chunk_type*, __chunk_type, __chunk_allocator_type> _M_end_of_storage; 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) 354_STLP_MOVE_TO_STD_NAMESPACE 355#endif 356 357__BVEC_TMPL_HEADER 358class __BVECTOR_QUALIFIED : public _STLP_PRIV _Bvector_base<_Alloc > 359#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_DEBUG) 360 , public __stlport_class< __BVECTOR_QUALIFIED > 361#endif 362{ 363 typedef _STLP_PRIV _Bvector_base<_Alloc > _Base; 364 typedef __BVECTOR_QUALIFIED _Self; 365public: 366 typedef bool value_type; 367 typedef size_t size_type; 368 typedef ptrdiff_t difference_type; 369 typedef _STLP_PRIV _Bit_reference reference; 370 typedef bool const_reference; 371 typedef _STLP_PRIV _Bit_reference* pointer; 372 typedef const bool* const_pointer; 373 typedef random_access_iterator_tag _Iterator_category; 374 375 typedef _STLP_PRIV _Bit_iterator iterator; 376 typedef _STLP_PRIV _Bit_const_iterator const_iterator; 377 378 _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS; 379 380#ifdef _STLP_VECBOOL_TEMPLATE 381 typedef _STLP_TYPENAME _STLP_PRIV _Bvector_base<_Alloc >::allocator_type allocator_type; 382 typedef _STLP_TYPENAME _STLP_PRIV _Bvector_base<_Alloc >::__chunk_type __chunk_type; 383#else 384 typedef _STLP_PRIV _Bvector_base<_Alloc >::allocator_type allocator_type; 385 typedef _STLP_PRIV _Bvector_base<_Alloc >::__chunk_type __chunk_type; 386#endif 387 388protected: 389 390 void _M_initialize(size_type __n) { 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, 399 random_access_iterator_tag(), (difference_type*)0 ); 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 &) { 429 size_type __n = _STLP_STD::distance(__first, __last); 430 _M_initialize(__n); 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) { 449 size_type __n = _STLP_STD::distance(__first, __last); 450 if (capacity() - size() >= __n) { 451 _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + difference_type(__n), 452 random_access_iterator_tag(), (difference_type*)0 ); 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 471public: 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 477 reverse_iterator rbegin() { return reverse_iterator(end()); } 478 const_reverse_iterator rbegin() const { 479 return const_reverse_iterator(end()); 480 } 481 reverse_iterator rend() { return reverse_iterator(begin()); } 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(); } 492 reference operator[](size_type __n) 493 { return *(begin() + difference_type(__n)); } 494 const_reference operator[](size_type __n) const 495 { return *(begin() + difference_type(__n)); } 496 497 void _M_range_check(size_type __n) const { 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]; } 504 const_reference at(size_type __n) const 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 510 __BVECTOR(size_type __n, bool __val, 511 const allocator_type& __a = allocator_type()) 512 : _STLP_PRIV _Bvector_base<_Alloc >(__a) { 513 _M_initialize(__n); 514 fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), __val ? ~0 : 0); 515 } 516 517 explicit __BVECTOR(size_type __n) 518 : _STLP_PRIV _Bvector_base<_Alloc >(allocator_type()) { 519 _M_initialize(__n); 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&) { 532 _M_initialize(__n); 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) 545 : _STLP_PRIV _Bvector_base<_Alloc >(allocator_type()) { 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, 552 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 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 */ 558 __BVECTOR(const_iterator __first, const_iterator __last, 559 const allocator_type& __a = allocator_type()) 560 : _STLP_PRIV _Bvector_base<_Alloc >(__a) { 561 size_type __n = _STLP_STD::distance(__first, __last); 562 _M_initialize(__n); 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) { 568 size_type __n = _STLP_STD::distance(__first, __last); 569 _M_initialize(__n); 570 _STLP_STD::copy(__first, __last, this->_M_start); 571 } 572#endif /* _STLP_MEMBER_TEMPLATES */ 573 574#if !defined (_STLP_NO_MOVE_SEMANTIC) 575 __BVECTOR(__move_source<_Self> src) 576 : _STLP_PRIV _Bvector_base<_Alloc >(__move_source<_Base>(src.get())) {} 577#endif 578 579 ~__BVECTOR() {} 580 581 __BVECTOR_QUALIFIED& operator=(const __BVECTOR_QUALIFIED& __x) { 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 651 void reserve(size_type __n) { 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 } 676 void swap(__BVECTOR_QUALIFIED& __x) { 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, 720 const_iterator __first, const_iterator __last) { 721 if (__first == __last) return; 722 size_type __n = _STLP_STD::distance(__first, __last); 723 if (capacity() - size() >= __n) { 724 _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + __n, 725 random_access_iterator_tag(), (difference_type*)0 ); 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; 743 size_type __n = _STLP_STD::distance(__first, __last); 744 if (capacity() - size() >= __n) { 745 _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + __n, 746 random_access_iterator_tag(), (difference_type*)0 ); 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), 767 random_access_iterator_tag(), (difference_type*)0 ); 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 } 796 iterator erase(iterator __first, iterator __last) { 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) 823_STLP_MOVE_TO_STD_NAMESPACE 824#endif 825 826_STLP_END_NAMESPACE 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: 842