1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Permission to use, copy, modify, distribute and sell this software 7 * and its documentation for any purpose is hereby granted without fee, 8 * provided that the above copyright notice appear in all copies and 9 * that both that copyright notice and this permission notice appear 10 * in supporting documentation. Hewlett-Packard Company makes no 11 * representations about the suitability of this software for any 12 * purpose. It is provided "as is" without express or implied warranty. 13 * 14 * 15 * Copyright (c) 1996,1997 16 * Silicon Graphics Computer Systems, Inc. 17 * 18 * Permission to use, copy, modify, distribute and sell this software 19 * and its documentation for any purpose is hereby granted without fee, 20 * provided that the above copyright notice appear in all copies and 21 * that both that copyright notice and this permission notice appear 22 * in supporting documentation. Silicon Graphics makes no 23 * representations about the suitability of this software for any 24 * purpose. It is provided "as is" without express or implied warranty. 25 */ 26 27 /* NOTE: This is an internal header file, included by other STL headers. 28 * You should not attempt to use it directly. 29 */ 30 31 #ifndef __SGI_STL_INTERNAL_BVECTOR_H 32 #define __SGI_STL_INTERNAL_BVECTOR_H 33 34 __STL_BEGIN_NAMESPACE 35 36 static const int __WORD_BIT = int(CHAR_BIT*sizeof(unsigned int)); 37 38 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 39 #pragma set woff 1174 40 #pragma set woff 1375 41 #endif 42 43 struct _Bit_reference { 44 unsigned int* _M_p; 45 unsigned int _M_mask; 46 _Bit_reference(unsigned int* __x, unsigned int __y) 47 : _M_p(__x), _M_mask(__y) {} 48 49 public: 50 _Bit_reference() : _M_p(0), _M_mask(0) {} 51 operator bool() const { return !(!(*_M_p & _M_mask)); } 52 _Bit_reference& operator=(bool __x) 53 { 54 if (__x) *_M_p |= _M_mask; 55 else *_M_p &= ~_M_mask; 56 return *this; 57 } 58 _Bit_reference& operator=(const _Bit_reference& __x) 59 { return *this = bool(__x); } 60 bool operator==(const _Bit_reference& __x) const 61 { return bool(*this) == bool(__x); } 62 bool operator<(const _Bit_reference& __x) const { 63 return !bool(*this) && bool(__x); 64 } 65 void flip() { *_M_p ^= _M_mask; } 66 }; 67 68 inline void swap(_Bit_reference __x, _Bit_reference __y) 69 { 70 bool __tmp = __x; 71 __x = __y; 72 __y = __tmp; 73 } 74 75 struct _Bit_iterator : public random_access_iterator<bool, ptrdiff_t> { 76 typedef _Bit_reference reference; 77 typedef _Bit_reference* pointer; 78 typedef _Bit_iterator iterator; 79 80 unsigned int* _M_p; 81 unsigned int _M_offset; 82 void bump_up() { 83 if (_M_offset++ == __WORD_BIT - 1) { 84 _M_offset = 0; 85 ++_M_p; 86 } 87 } 88 void bump_down() { 89 if (_M_offset-- == 0) { 90 _M_offset = __WORD_BIT - 1; 91 --_M_p; 92 } 93 } 94 95 _Bit_iterator() : _M_p(0), _M_offset(0) {} 96 _Bit_iterator(unsigned int* __x, unsigned int __y) 97 : _M_p(__x), _M_offset(__y) {} 98 reference operator*() const { return reference(_M_p, 1U << _M_offset); } 99 iterator& operator++() { 100 bump_up(); 101 return *this; 102 } 103 iterator operator++(int) { 104 iterator __tmp = *this; 105 bump_up(); 106 return __tmp; 107 } 108 iterator& operator--() { 109 bump_down(); 110 return *this; 111 } 112 iterator operator--(int) { 113 iterator __tmp = *this; 114 bump_down(); 115 return __tmp; 116 } 117 iterator& operator+=(difference_type __i) { 118 difference_type __n = __i + _M_offset; 119 _M_p += __n / __WORD_BIT; 120 __n = __n % __WORD_BIT; 121 if (__n < 0) { 122 _M_offset = (unsigned int) __n + __WORD_BIT; 123 --_M_p; 124 } else 125 _M_offset = (unsigned int) __n; 126 return *this; 127 } 128 iterator& operator-=(difference_type __i) { 129 *this += -__i; 130 return *this; 131 } 132 iterator operator+(difference_type __i) const { 133 iterator __tmp = *this; 134 return __tmp += __i; 135 } 136 iterator operator-(difference_type __i) const { 137 iterator __tmp = *this; 138 return __tmp -= __i; 139 } 140 difference_type operator-(iterator __x) const { 141 return __WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset; 142 } 143 reference operator[](difference_type __i) { return *(*this + __i); } 144 bool operator==(const iterator& __x) const { 145 return _M_p == __x._M_p && _M_offset == __x._M_offset; 146 } 147 bool operator!=(const iterator& __x) const { 148 return _M_p != __x._M_p || _M_offset != __x._M_offset; 149 } 150 bool operator<(iterator __x) const { 151 return _M_p < __x._M_p || (_M_p == __x._M_p && _M_offset < __x._M_offset); 152 } 153 }; 154 155 struct _Bit_const_iterator 156 : public random_access_iterator<bool, ptrdiff_t> 157 { 158 typedef bool reference; 159 typedef bool const_reference; 160 typedef const bool* pointer; 161 typedef _Bit_const_iterator const_iterator; 162 163 unsigned int* _M_p; 164 unsigned int _M_offset; 165 void bump_up() { 166 if (_M_offset++ == __WORD_BIT - 1) { 167 _M_offset = 0; 168 ++_M_p; 169 } 170 } 171 void bump_down() { 172 if (_M_offset-- == 0) { 173 _M_offset = __WORD_BIT - 1; 174 --_M_p; 175 } 176 } 177 178 _Bit_const_iterator() : _M_p(0), _M_offset(0) {} 179 _Bit_const_iterator(unsigned int* __x, unsigned int __y) 180 : _M_p(__x), _M_offset(__y) {} 181 _Bit_const_iterator(const _Bit_iterator& __x) 182 : _M_p(__x._M_p), _M_offset(__x._M_offset) {} 183 const_reference operator*() const { 184 return _Bit_reference(_M_p, 1U << _M_offset); 185 } 186 const_iterator& operator++() { 187 bump_up(); 188 return *this; 189 } 190 const_iterator operator++(int) { 191 const_iterator __tmp = *this; 192 bump_up(); 193 return __tmp; 194 } 195 const_iterator& operator--() { 196 bump_down(); 197 return *this; 198 } 199 const_iterator operator--(int) { 200 const_iterator __tmp = *this; 201 bump_down(); 202 return __tmp; 203 } 204 const_iterator& operator+=(difference_type __i) { 205 difference_type __n = __i + _M_offset; 206 _M_p += __n / __WORD_BIT; 207 __n = __n % __WORD_BIT; 208 if (__n < 0) { 209 _M_offset = (unsigned int) __n + __WORD_BIT; 210 --_M_p; 211 } else 212 _M_offset = (unsigned int) __n; 213 return *this; 214 } 215 const_iterator& operator-=(difference_type __i) { 216 *this += -__i; 217 return *this; 218 } 219 const_iterator operator+(difference_type __i) const { 220 const_iterator __tmp = *this; 221 return __tmp += __i; 222 } 223 const_iterator operator-(difference_type __i) const { 224 const_iterator __tmp = *this; 225 return __tmp -= __i; 226 } 227 difference_type operator-(const_iterator __x) const { 228 return __WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset; 229 } 230 const_reference operator[](difference_type __i) { 231 return *(*this + __i); 232 } 233 bool operator==(const const_iterator& __x) const { 234 return _M_p == __x._M_p && _M_offset == __x._M_offset; 235 } 236 bool operator!=(const const_iterator& __x) const { 237 return _M_p != __x._M_p || _M_offset != __x._M_offset; 238 } 239 bool operator<(const_iterator __x) const { 240 return _M_p < __x._M_p || (_M_p == __x._M_p && _M_offset < __x._M_offset); 241 } 242 }; 243 244 // Bit-vector base class, which encapsulates the difference between 245 // old SGI-style allocators and standard-conforming allocators. 246 247 #ifdef __STL_USE_STD_ALLOCATORS 248 249 // Base class for ordinary allocators. 250 template <class _Allocator, bool __is_static> 251 class _Bvector_alloc_base { 252 public: 253 typedef typename _Alloc_traits<bool, _Allocator>::allocator_type 254 allocator_type; 255 allocator_type get_allocator() const { return _M_data_allocator; } 256 257 _Bvector_alloc_base(const allocator_type& __a) 258 : _M_data_allocator(__a), _M_start(), _M_finish(), _M_end_of_storage(0) {} 259 260 protected: 261 unsigned int* _M_bit_alloc(size_t __n) 262 { return _M_data_allocator.allocate((__n + __WORD_BIT - 1)/__WORD_BIT); } 263 void _M_deallocate() { 264 if (_M_start._M_p) 265 _M_data_allocator.deallocate(_M_start._M_p, 266 _M_end_of_storage - _M_start._M_p); 267 } 268 269 typename _Alloc_traits<unsigned int, _Allocator>::allocator_type 270 _M_data_allocator; 271 _Bit_iterator _M_start; 272 _Bit_iterator _M_finish; 273 unsigned int* _M_end_of_storage; 274 }; 275 276 // Specialization for instanceless allocators. 277 template <class _Allocator> 278 class _Bvector_alloc_base<_Allocator, true> { 279 public: 280 typedef typename _Alloc_traits<bool, _Allocator>::allocator_type 281 allocator_type; 282 allocator_type get_allocator() const { return allocator_type(); } 283 284 _Bvector_alloc_base(const allocator_type&) 285 : _M_start(), _M_finish(), _M_end_of_storage(0) {} 286 287 protected: 288 typedef typename _Alloc_traits<unsigned int, _Allocator>::_Alloc_type 289 _Alloc_type; 290 291 unsigned int* _M_bit_alloc(size_t __n) 292 { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); } 293 void _M_deallocate() { 294 if (_M_start._M_p) 295 _Alloc_type::deallocate(_M_start._M_p, 296 _M_end_of_storage - _M_start._M_p); 297 } 298 299 _Bit_iterator _M_start; 300 _Bit_iterator _M_finish; 301 unsigned int* _M_end_of_storage; 302 }; 303 304 template <class _Alloc> 305 class _Bvector_base 306 : public _Bvector_alloc_base<_Alloc, 307 _Alloc_traits<bool, _Alloc>::_S_instanceless> 308 { 309 typedef _Bvector_alloc_base<_Alloc, 310 _Alloc_traits<bool, _Alloc>::_S_instanceless> 311 _Base; 312 public: 313 typedef typename _Base::allocator_type allocator_type; 314 315 _Bvector_base(const allocator_type& __a) : _Base(__a) {} 316 ~_Bvector_base() { _Base::_M_deallocate(); } 317 }; 318 319 #else /* __STL_USE_STD_ALLOCATORS */ 320 321 template <class _Alloc> 322 class _Bvector_base 323 { 324 public: 325 typedef _Alloc allocator_type; 326 allocator_type get_allocator() const { return allocator_type(); } 327 328 _Bvector_base(const allocator_type&) 329 : _M_start(), _M_finish(), _M_end_of_storage(0) {} 330 ~_Bvector_base() { _M_deallocate(); } 331 332 protected: 333 typedef simple_alloc<unsigned int, _Alloc> _Alloc_type; 334 335 unsigned int* _M_bit_alloc(size_t __n) 336 { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); } 337 void _M_deallocate() { 338 if (_M_start._M_p) 339 _Alloc_type::deallocate(_M_start._M_p, 340 _M_end_of_storage - _M_start._M_p); 341 } 342 343 _Bit_iterator _M_start; 344 _Bit_iterator _M_finish; 345 unsigned int* _M_end_of_storage; 346 }; 347 348 #endif /* __STL_USE_STD_ALLOCATORS */ 349 350 // The next few lines are confusing. What we're doing is declaring a 351 // partial specialization of vector<T, Alloc> if we have the necessary 352 // compiler support. Otherwise, we define a class bit_vector which uses 353 // the default allocator. 354 355 #if defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && !defined(__STL_NO_BOOL) 356 #define __SGI_STL_VECBOOL_TEMPLATE 357 #define __BVECTOR vector 358 #else 359 #undef __SGI_STL_VECBOOL_TEMPLATE 360 #define __BVECTOR bit_vector 361 #endif 362 363 # ifdef __SGI_STL_VECBOOL_TEMPLATE 364 __STL_END_NAMESPACE 365 # include <stl_vector.h> 366 __STL_BEGIN_NAMESPACE 367 template<class _Alloc> class vector<bool,_Alloc> 368 : public _Bvector_base<_Alloc> 369 # else /* __SGI_STL_VECBOOL_TEMPLATE */ 370 class bit_vector 371 : public _Bvector_base<__STL_DEFAULT_ALLOCATOR(bool) > 372 # endif /* __SGI_STL_VECBOOL_TEMPLATE */ 373 { 374 # ifdef __SGI_STL_VECBOOL_TEMPLATE 375 typedef _Bvector_base<_Alloc> _Base; 376 # else /* __SGI_STL_VECBOOL_TEMPLATE */ 377 typedef _Bvector_base<__STL_DEFAULT_ALLOCATOR(bool) > _Base; 378 # endif /* __SGI_STL_VECBOOL_TEMPLATE */ 379 public: 380 typedef bool value_type; 381 typedef size_t size_type; 382 typedef ptrdiff_t difference_type; 383 typedef _Bit_reference reference; 384 typedef bool const_reference; 385 typedef _Bit_reference* pointer; 386 typedef const bool* const_pointer; 387 388 typedef _Bit_iterator iterator; 389 typedef _Bit_const_iterator const_iterator; 390 391 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 392 typedef reverse_iterator<const_iterator> const_reverse_iterator; 393 typedef reverse_iterator<iterator> reverse_iterator; 394 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 395 typedef reverse_iterator<const_iterator, value_type, const_reference, 396 difference_type> const_reverse_iterator; 397 typedef reverse_iterator<iterator, value_type, reference, difference_type> 398 reverse_iterator; 399 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 400 401 typedef typename _Base::allocator_type allocator_type; 402 allocator_type get_allocator() const { return _Base::get_allocator(); } 403 404 protected: 405 #ifdef __STL_USE_NAMESPACES 406 using _Base::_M_bit_alloc; 407 using _Base::_M_deallocate; 408 using _Base::_M_start; 409 using _Base::_M_finish; 410 using _Base::_M_end_of_storage; 411 #endif /* __STL_USE_NAMESPACES */ 412 413 protected: 414 void _M_initialize(size_type __n) { 415 unsigned int* __q = _M_bit_alloc(__n); 416 _M_end_of_storage = __q + (__n + __WORD_BIT - 1)/__WORD_BIT; 417 _M_start = iterator(__q, 0); 418 _M_finish = _M_start + difference_type(__n); 419 } 420 void _M_insert_aux(iterator __position, bool __x) { 421 if (_M_finish._M_p != _M_end_of_storage) { 422 copy_backward(__position, _M_finish, _M_finish + 1); 423 *__position = __x; 424 ++_M_finish; 425 } 426 else { 427 size_type __len = size() ? 2 * size() : __WORD_BIT; 428 unsigned int* __q = _M_bit_alloc(__len); 429 iterator __i = copy(begin(), __position, iterator(__q, 0)); 430 *__i++ = __x; 431 _M_finish = copy(__position, end(), __i); 432 _M_deallocate(); 433 _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT; 434 _M_start = iterator(__q, 0); 435 } 436 } 437 438 #ifdef __STL_MEMBER_TEMPLATES 439 template <class _InputIterator> 440 void _M_initialize_range(_InputIterator __first, _InputIterator __last, 441 input_iterator_tag) { 442 _M_start = iterator(); 443 _M_finish = iterator(); 444 _M_end_of_storage = 0; 445 for ( ; __first != __last; ++__first) 446 push_back(*__first); 447 } 448 449 template <class _ForwardIterator> 450 void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 451 forward_iterator_tag) { 452 size_type __n = 0; 453 distance(__first, __last, __n); 454 _M_initialize(__n); 455 copy(__first, __last, _M_start); 456 } 457 458 template <class _InputIterator> 459 void _M_insert_range(iterator __pos, 460 _InputIterator __first, _InputIterator __last, 461 input_iterator_tag) { 462 for ( ; __first != __last; ++__first) { 463 __pos = insert(__pos, *__first); 464 ++__pos; 465 } 466 } 467 468 template <class _ForwardIterator> 469 void _M_insert_range(iterator __position, 470 _ForwardIterator __first, _ForwardIterator __last, 471 forward_iterator_tag) { 472 if (__first != __last) { 473 size_type __n = 0; 474 distance(__first, __last, __n); 475 if (capacity() - size() >= __n) { 476 copy_backward(__position, end(), _M_finish + difference_type(__n)); 477 copy(__first, __last, __position); 478 _M_finish += difference_type(__n); 479 } 480 else { 481 size_type __len = size() + max(size(), __n); 482 unsigned int* __q = _M_bit_alloc(__len); 483 iterator __i = copy(begin(), __position, iterator(__q, 0)); 484 __i = copy(__first, __last, __i); 485 _M_finish = copy(__position, end(), __i); 486 _M_deallocate(); 487 _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT; 488 _M_start = iterator(__q, 0); 489 } 490 } 491 } 492 493 #endif /* __STL_MEMBER_TEMPLATES */ 494 495 public: 496 iterator begin() { return _M_start; } 497 const_iterator begin() const { return _M_start; } 498 iterator end() { return _M_finish; } 499 const_iterator end() const { return _M_finish; } 500 501 reverse_iterator rbegin() { return reverse_iterator(end()); } 502 const_reverse_iterator rbegin() const { 503 return const_reverse_iterator(end()); 504 } 505 reverse_iterator rend() { return reverse_iterator(begin()); } 506 const_reverse_iterator rend() const { 507 return const_reverse_iterator(begin()); 508 } 509 510 size_type size() const { return size_type(end() - begin()); } 511 size_type max_size() const { return size_type(-1); } 512 size_type capacity() const { 513 return size_type(const_iterator(_M_end_of_storage, 0) - begin()); 514 } 515 bool empty() const { return begin() == end(); } 516 reference operator[](size_type __n) { 517 return *(begin() + difference_type(__n)); 518 } 519 const_reference operator[](size_type __n) const { 520 return *(begin() + difference_type(__n)); 521 } 522 523 explicit __BVECTOR(const allocator_type& __a = allocator_type()) 524 : _Base(__a) {} 525 526 __BVECTOR(size_type __n, bool __value, 527 const allocator_type& __a = allocator_type()) 528 : _Base(__a) 529 { 530 _M_initialize(__n); 531 fill(_M_start._M_p, _M_end_of_storage, __value ? ~0 : 0); 532 } 533 534 explicit __BVECTOR(size_type __n) 535 : _Base(allocator_type()) 536 { 537 _M_initialize(__n); 538 fill(_M_start._M_p, _M_end_of_storage, 0); 539 } 540 541 __BVECTOR(const __BVECTOR& __x) : _Base(__x.get_allocator()) { 542 _M_initialize(__x.size()); 543 copy(__x.begin(), __x.end(), _M_start); 544 } 545 546 #ifdef __STL_MEMBER_TEMPLATES 547 // Check whether it's an integral type. If so, it's not an iterator. 548 template <class _InputIterator> 549 __BVECTOR(_InputIterator __first, _InputIterator __last, 550 const allocator_type& __a = allocator_type()) 551 : _Base(__a) 552 { 553 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 554 _M_initialize_dispatch(__first, __last, _Integral()); 555 } 556 557 template <class _Integer> 558 void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { 559 _M_initialize(__n); 560 fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); 561 } 562 563 template <class _InputIterator> 564 void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 565 __false_type) { 566 _M_initialize_range(__first, __last, __ITERATOR_CATEGORY(__first)); 567 } 568 #else /* __STL_MEMBER_TEMPLATES */ 569 __BVECTOR(const_iterator __first, const_iterator __last, 570 const allocator_type& __a = allocator_type()) 571 : _Base(__a) 572 { 573 size_type __n = 0; 574 distance(__first, __last, __n); 575 _M_initialize(__n); 576 copy(__first, __last, _M_start); 577 } 578 __BVECTOR(const bool* __first, const bool* __last, 579 const allocator_type& __a = allocator_type()) 580 : _Base(__a) 581 { 582 size_type __n = 0; 583 distance(__first, __last, __n); 584 _M_initialize(__n); 585 copy(__first, __last, _M_start); 586 } 587 #endif /* __STL_MEMBER_TEMPLATES */ 588 589 ~__BVECTOR() { } 590 591 __BVECTOR& operator=(const __BVECTOR& __x) { 592 if (&__x == this) return *this; 593 if (__x.size() > capacity()) { 594 _M_deallocate(); 595 _M_initialize(__x.size()); 596 } 597 copy(__x.begin(), __x.end(), begin()); 598 _M_finish = begin() + difference_type(__x.size()); 599 return *this; 600 } 601 602 // assign(), a generalized assignment member function. Two 603 // versions: one that takes a count, and one that takes a range. 604 // The range version is a member template, so we dispatch on whether 605 // or not the type is an integer. 606 607 void assign(size_t __n, bool __x) { 608 if (__n > size()) { 609 fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); 610 insert(end(), __n - size(), __x); 611 } 612 else { 613 erase(begin() + __n, end()); 614 fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); 615 } 616 } 617 618 #ifdef __STL_MEMBER_TEMPLATES 619 620 template <class _InputIterator> 621 void assign(_InputIterator __first, _InputIterator __last) { 622 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 623 _M_assign_dispatch(__first, __last, _Integral()); 624 } 625 626 template <class _Integer> 627 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 628 { assign((size_t) __n, (bool) __val); } 629 630 template <class _InputIter> 631 void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type) 632 { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); } 633 634 template <class _InputIterator> 635 void _M_assign_aux(_InputIterator __first, _InputIterator __last, 636 input_iterator_tag) { 637 iterator __cur = begin(); 638 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 639 *__cur = *__first; 640 if (__first == __last) 641 erase(__cur, end()); 642 else 643 insert(end(), __first, __last); 644 } 645 646 template <class _ForwardIterator> 647 void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 648 forward_iterator_tag) { 649 size_type __len = 0; 650 distance(__first, __last, __len); 651 if (__len < size()) 652 erase(copy(__first, __last, begin()), end()); 653 else { 654 _ForwardIterator __mid = __first; 655 advance(__mid, size()); 656 copy(__first, __mid, begin()); 657 insert(end(), __mid, __last); 658 } 659 } 660 661 #endif /* __STL_MEMBER_TEMPLATES */ 662 663 void reserve(size_type __n) { 664 if (capacity() < __n) { 665 unsigned int* __q = _M_bit_alloc(__n); 666 _M_finish = copy(begin(), end(), iterator(__q, 0)); 667 _M_deallocate(); 668 _M_start = iterator(__q, 0); 669 _M_end_of_storage = __q + (__n + __WORD_BIT - 1)/__WORD_BIT; 670 } 671 } 672 673 reference front() { return *begin(); } 674 const_reference front() const { return *begin(); } 675 reference back() { return *(end() - 1); } 676 const_reference back() const { return *(end() - 1); } 677 void push_back(bool __x) { 678 if (_M_finish._M_p != _M_end_of_storage) 679 *_M_finish++ = __x; 680 else 681 _M_insert_aux(end(), __x); 682 } 683 void swap(__BVECTOR& __x) { 684 __STD::swap(_M_start, __x._M_start); 685 __STD::swap(_M_finish, __x._M_finish); 686 __STD::swap(_M_end_of_storage, __x._M_end_of_storage); 687 } 688 iterator insert(iterator __position, bool __x = bool()) { 689 difference_type __n = __position - begin(); 690 if (_M_finish._M_p != _M_end_of_storage && __position == end()) 691 *_M_finish++ = __x; 692 else 693 _M_insert_aux(__position, __x); 694 return begin() + __n; 695 } 696 697 #ifdef __STL_MEMBER_TEMPLATES 698 // Check whether it's an integral type. If so, it's not an iterator. 699 template <class _InputIterator> 700 void insert(iterator __position, 701 _InputIterator __first, _InputIterator __last) { 702 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 703 _M_insert_dispatch(__position, __first, __last, _Integral()); 704 } 705 706 template <class _Integer> 707 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 708 __true_type) { 709 insert(__pos, (size_type) __n, (bool) __x); 710 } 711 712 template <class _InputIterator> 713 void _M_insert_dispatch(iterator __pos, 714 _InputIterator __first, _InputIterator __last, 715 __false_type) { 716 _M_insert_range(__pos, __first, __last, __ITERATOR_CATEGORY(__first)); 717 } 718 #else /* __STL_MEMBER_TEMPLATES */ 719 void insert(iterator __position, 720 const_iterator __first, const_iterator __last) { 721 if (__first == __last) return; 722 size_type __n = 0; 723 distance(__first, __last, __n); 724 if (capacity() - size() >= __n) { 725 copy_backward(__position, end(), _M_finish + __n); 726 copy(__first, __last, __position); 727 _M_finish += __n; 728 } 729 else { 730 size_type __len = size() + max(size(), __n); 731 unsigned int* __q = _M_bit_alloc(__len); 732 iterator __i = copy(begin(), __position, iterator(__q, 0)); 733 __i = copy(__first, __last, __i); 734 _M_finish = copy(__position, end(), __i); 735 _M_deallocate(); 736 _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT; 737 _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 = 0; 744 distance(__first, __last, __n); 745 if (capacity() - size() >= __n) { 746 copy_backward(__position, end(), _M_finish + __n); 747 copy(__first, __last, __position); 748 _M_finish += __n; 749 } 750 else { 751 size_type __len = size() + max(size(), __n); 752 unsigned int* __q = _M_bit_alloc(__len); 753 iterator __i = copy(begin(), __position, iterator(__q, 0)); 754 __i = copy(__first, __last, __i); 755 _M_finish = copy(__position, end(), __i); 756 _M_deallocate(); 757 _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT; 758 _M_start = iterator(__q, 0); 759 } 760 } 761 #endif /* __STL_MEMBER_TEMPLATES */ 762 763 void insert(iterator __position, size_type __n, bool __x) { 764 if (__n == 0) return; 765 if (capacity() - size() >= __n) { 766 copy_backward(__position, end(), _M_finish + difference_type(__n)); 767 fill(__position, __position + difference_type(__n), __x); 768 _M_finish += difference_type(__n); 769 } 770 else { 771 size_type __len = size() + max(size(), __n); 772 unsigned int* __q = _M_bit_alloc(__len); 773 iterator __i = copy(begin(), __position, iterator(__q, 0)); 774 fill_n(__i, __n, __x); 775 _M_finish = copy(__position, end(), __i + difference_type(__n)); 776 _M_deallocate(); 777 _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT; 778 _M_start = iterator(__q, 0); 779 } 780 } 781 782 void pop_back() { --_M_finish; } 783 iterator erase(iterator __position) { 784 if (__position + 1 != end()) 785 copy(__position + 1, end(), __position); 786 --_M_finish; 787 return __position; 788 } 789 iterator erase(iterator __first, iterator __last) { 790 _M_finish = copy(__last, end(), __first); 791 return __first; 792 } 793 void resize(size_type __new_size, bool __x = bool()) { 794 if (__new_size < size()) 795 erase(begin() + difference_type(__new_size), end()); 796 else 797 insert(end(), __new_size - size(), __x); 798 } 799 void clear() { erase(begin(), end()); } 800 }; 801 802 #ifdef __SGI_STL_VECBOOL_TEMPLATE 803 804 typedef vector<bool, alloc> bit_vector; 805 806 #else /* __SGI_STL_VECBOOL_TEMPLATE */ 807 808 inline bool 809 operator==(const bit_vector& __x, const bit_vector& __y) 810 { 811 return (__x.size() == __y.size() && 812 equal(__x.begin(), __x.end(), __y.begin())); 813 } 814 815 inline bool 816 operator<(const bit_vector& __x, const bit_vector& __y) 817 { 818 return lexicographical_compare(__x.begin(), __x.end(), 819 __y.begin(), __y.end()); 820 } 821 822 #endif /* __SGI_STL_VECBOOL_TEMPLATE */ 823 824 #undef __SGI_STL_VECBOOL_TEMPLATE 825 #undef __BVECTOR 826 827 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 828 #pragma reset woff 1174 829 #pragma reset woff 1375 830 #endif 831 832 __STL_END_NAMESPACE 833 834 #endif /* __SGI_STL_INTERNAL_BVECTOR_H */ 835 836 // Local Variables: 837 // mode:C++ 838 // End: 839