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;
_Bit_reference_Bit_reference46 _Bit_reference(unsigned int* __x, unsigned int __y)
47 : _M_p(__x), _M_mask(__y) {}
48
49 public:
_Bit_reference_Bit_reference50 _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 }
flip_Bit_reference65 void flip() { *_M_p ^= _M_mask; }
66 };
67
swap(_Bit_reference __x,_Bit_reference __y)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;
bump_up_Bit_iterator82 void bump_up() {
83 if (_M_offset++ == __WORD_BIT - 1) {
84 _M_offset = 0;
85 ++_M_p;
86 }
87 }
bump_down_Bit_iterator88 void bump_down() {
89 if (_M_offset-- == 0) {
90 _M_offset = __WORD_BIT - 1;
91 --_M_p;
92 }
93 }
94
_Bit_iterator_Bit_iterator95 _Bit_iterator() : _M_p(0), _M_offset(0) {}
_Bit_iterator_Bit_iterator96 _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;
bump_up_Bit_const_iterator165 void bump_up() {
166 if (_M_offset++ == __WORD_BIT - 1) {
167 _M_offset = 0;
168 ++_M_p;
169 }
170 }
bump_down_Bit_const_iterator171 void bump_down() {
172 if (_M_offset-- == 0) {
173 _M_offset = __WORD_BIT - 1;
174 --_M_p;
175 }
176 }
177
_Bit_const_iterator_Bit_const_iterator178 _Bit_const_iterator() : _M_p(0), _M_offset(0) {}
_Bit_const_iterator_Bit_const_iterator179 _Bit_const_iterator(unsigned int* __x, unsigned int __y)
180 : _M_p(__x), _M_offset(__y) {}
_Bit_const_iterator_Bit_const_iterator181 _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;
get_allocator()255 allocator_type get_allocator() const { return _M_data_allocator; }
256
_Bvector_alloc_base(const allocator_type & __a)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:
_M_bit_alloc(size_t __n)261 unsigned int* _M_bit_alloc(size_t __n)
262 { return _M_data_allocator.allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
_M_deallocate()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;
get_allocator()282 allocator_type get_allocator() const { return allocator_type(); }
283
_Bvector_alloc_base(const allocator_type &)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
_M_bit_alloc(size_t __n)291 unsigned int* _M_bit_alloc(size_t __n)
292 { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
_M_deallocate()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
_Bvector_base(const allocator_type & __a)315 _Bvector_base(const allocator_type& __a) : _Base(__a) {}
~_Bvector_base()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;
get_allocator()326 allocator_type get_allocator() const { return allocator_type(); }
327
_Bvector_base(const allocator_type &)328 _Bvector_base(const allocator_type&)
329 : _M_start(), _M_finish(), _M_end_of_storage(0) {}
~_Bvector_base()330 ~_Bvector_base() { _M_deallocate(); }
331
332 protected:
333 typedef simple_alloc<unsigned int, _Alloc> _Alloc_type;
334
_M_bit_alloc(size_t __n)335 unsigned int* _M_bit_alloc(size_t __n)
336 { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
_M_deallocate()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;
get_allocator()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:
_M_initialize(size_type __n)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 }
_M_insert_aux(iterator __position,bool __x)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>
_M_initialize_range(_InputIterator __first,_InputIterator __last,input_iterator_tag)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>
_M_initialize_range(_ForwardIterator __first,_ForwardIterator __last,forward_iterator_tag)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>
_M_insert_range(iterator __pos,_InputIterator __first,_InputIterator __last,input_iterator_tag)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>
_M_insert_range(iterator __position,_ForwardIterator __first,_ForwardIterator __last,forward_iterator_tag)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:
begin()496 iterator begin() { return _M_start; }
begin()497 const_iterator begin() const { return _M_start; }
end()498 iterator end() { return _M_finish; }
end()499 const_iterator end() const { return _M_finish; }
500
rbegin()501 reverse_iterator rbegin() { return reverse_iterator(end()); }
rbegin()502 const_reverse_iterator rbegin() const {
503 return const_reverse_iterator(end());
504 }
rend()505 reverse_iterator rend() { return reverse_iterator(begin()); }
rend()506 const_reverse_iterator rend() const {
507 return const_reverse_iterator(begin());
508 }
509
size()510 size_type size() const { return size_type(end() - begin()); }
max_size()511 size_type max_size() const { return size_type(-1); }
capacity()512 size_type capacity() const {
513 return size_type(const_iterator(_M_end_of_storage, 0) - begin());
514 }
empty()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())
_Base(__a)524 : _Base(__a) {}
525
526 __BVECTOR(size_type __n, bool __value,
527 const allocator_type& __a = allocator_type())
_Base(__a)528 : _Base(__a)
529 {
530 _M_initialize(__n);
531 fill(_M_start._M_p, _M_end_of_storage, __value ? ~0 : 0);
532 }
533
__BVECTOR(size_type __n)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
__BVECTOR(const __BVECTOR & __x)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())
_Base(__a)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>
_M_initialize_dispatch(_Integer __n,_Integer __x,__true_type)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>
_M_initialize_dispatch(_InputIterator __first,_InputIterator __last,__false_type)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())
_Base(__a)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())
_Base(__a)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
~__BVECTOR()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
assign(size_t __n,bool __x)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>
assign(_InputIterator __first,_InputIterator __last)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>
_M_assign_dispatch(_Integer __n,_Integer __val,__true_type)627 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
628 { assign((size_t) __n, (bool) __val); }
629
630 template <class _InputIter>
_M_assign_dispatch(_InputIter __first,_InputIter __last,__false_type)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>
_M_assign_aux(_InputIterator __first,_InputIterator __last,input_iterator_tag)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>
_M_assign_aux(_ForwardIterator __first,_ForwardIterator __last,forward_iterator_tag)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
reserve(size_type __n)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
front()673 reference front() { return *begin(); }
front()674 const_reference front() const { return *begin(); }
back()675 reference back() { return *(end() - 1); }
back()676 const_reference back() const { return *(end() - 1); }
push_back(bool __x)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 }
swap(__BVECTOR & __x)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>
insert(iterator __position,_InputIterator __first,_InputIterator __last)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>
_M_insert_dispatch(iterator __pos,_Integer __n,_Integer __x,__true_type)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>
_M_insert_dispatch(iterator __pos,_InputIterator __first,_InputIterator __last,__false_type)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 */
insert(iterator __position,const_iterator __first,const_iterator __last)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
insert(iterator __position,const bool * __first,const bool * __last)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
insert(iterator __position,size_type __n,bool __x)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
pop_back()782 void pop_back() { --_M_finish; }
erase(iterator __position)783 iterator erase(iterator __position) {
784 if (__position + 1 != end())
785 copy(__position + 1, end(), __position);
786 --_M_finish;
787 return __position;
788 }
erase(iterator __first,iterator __last)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 }
clear()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