diff options
Diffstat (limited to 'libstdc++/stl/deque.h')
| -rw-r--r-- | libstdc++/stl/deque.h | 1452 |
1 files changed, 1452 insertions, 0 deletions
diff --git a/libstdc++/stl/deque.h b/libstdc++/stl/deque.h new file mode 100644 index 00000000000..6685abffe7c --- /dev/null +++ b/libstdc++/stl/deque.h @@ -0,0 +1,1452 @@ +/* + * + * Copyright (c) 1994 + * Hewlett-Packard Company + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Hewlett-Packard Company makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + * + * + * Copyright (c) 1997 + * Silicon Graphics Computer Systems, Inc. + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Silicon Graphics makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + */ + +#ifndef __SGI_STL_DEQUE_H +#define __SGI_STL_DEQUE_H + +/* Class invariants: + * For any nonsingular iterator i: + * i.node is the address of an element in the map array. The + * contents of i.node is a pointer to the beginning of a node. + * i.first == *(i.node) + * i.last == i.first + node_size + * i.cur is a pointer in the range [i.first, i.last). NOTE: + * the implication of this is that i.cur is always a dereferenceable + * pointer, even if i is a past-the-end iterator. + * Start and Finish are always nonsingular iterators. NOTE: this means + * that an empty deque must have one node, and that a deque + * with N elements, where N is the buffer size, must have two nodes. + * For every node other than start.node and finish.node, every element + * in the node is an initialized object. If start.node == finish.node, + * then [start.cur, finish.cur) are initialized objects, and + * the elements outside that range are uninitialized storage. Otherwise, + * [start.cur, start.last) and [finish.first, finish.cur) are initialized + * objects, and [start.first, start.cur) and [finish.cur, finish.last) + * are uninitialized storage. + * [map, map + map_size) is a valid, non-empty range. + * [start.node, finish.node] is a valid range contained within + * [map, map + map_size). + * A pointer in the range [map, map + map_size) points to an allocated + * node if and only if the pointer is in the range [start.node, finish.node]. + */ + + +/* + * In previous versions of deque, node_size was fixed by the + * implementation. In this version, however, users can select + * the node size. Deque has three template parameters; the third, + * a number of type size_t, is the number of elements per node. + * If the third template parameter is 0 (which is the default), + * then deque will use a default node size. + * + * The only reason for using an alternate node size is if your application + * requires a different performance tradeoff than the default. If, + * for example, your program contains many deques each of which contains + * only a few elements, then you might want to save memory (possibly + * by sacrificing some speed) by using smaller nodes. + * + * Unfortunately, some compilers have trouble with non-type template + * parameters; stl_config.h defines __STL_NON_TYPE_TMPL_PARAM_BUG if + * that is the case. If your compiler is one of them, then you will + * not be able to use alternate node sizes; you will have to use the + * default value. + */ + +#include <stddef.h> +#include <algobase.h> +#include <alloc.h> + +// Note: this function is simply a kludge to work around several compilers' +// bugs in handling constant expressions. +inline size_t __deque_buf_size(size_t n, size_t sz) +{ + return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1)); +} + +#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG +template <class T, class Ref, size_t BufSiz> +struct __deque_iterator { + typedef __deque_iterator<T, T&, BufSiz> iterator; + typedef __deque_iterator<T, const T&, BufSiz> const_iterator; + static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); } +#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ +template <class T, class Ref> +struct __deque_iterator { + typedef __deque_iterator<T, T&> iterator; + typedef __deque_iterator<T, const T&> const_iterator; + static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); } +#endif + + typedef random_access_iterator_tag iterator_category; + typedef T value_type; + typedef value_type* pointer; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef pointer* map_pointer; + + typedef __deque_iterator self; + + pointer cur; + pointer first; + pointer last; + map_pointer node; + + __deque_iterator(pointer x, map_pointer y) + : cur(x), first(*y), last(*y + buffer_size()), node(y) {} + __deque_iterator() : cur(0), first(0), last(0), node(0) {} + __deque_iterator(const iterator& x) + : cur(x.cur), first(x.first), last(x.last), node(x.node) {} + + Ref operator*() const { return *cur; } + + difference_type operator-(const self& x) const { + return buffer_size() * (node - x.node - 1) + + (cur - first) + (x.last - x.cur); + } + + self& operator++() { + ++cur; + if (cur == last) { + set_node(node + 1); + cur = first; + } + return *this; + } + self operator++(int) { + self tmp = *this; + ++*this; + return tmp; + } + + self& operator--() { + if (cur == first) { + set_node(node - 1); + cur = last; + } + --cur; + return *this; + } + self operator--(int) { + self tmp = *this; + --*this; + return tmp; + } + + self& operator+=(difference_type n) { + difference_type offset = n + (cur - first); + if (offset >= 0 && offset < buffer_size()) + cur += n; + else { + difference_type node_offset = + offset > 0 ? offset / buffer_size() + : -difference_type((-offset - 1) / buffer_size()) - 1; + set_node(node + node_offset); + cur = first + (offset - node_offset * buffer_size()); + } + return *this; + } + + self operator+(difference_type n) const { + self tmp = *this; + return tmp += n; + } + + self& operator-=(difference_type n) { return *this += -n; } + + self operator-(difference_type n) const { + self tmp = *this; + return tmp -= n; + } + + Ref operator[](difference_type n) const { return *(*this + n); } + + bool operator==(const self& x) const { return cur == x.cur; } + bool operator!=(const self& x) const { return !(*this == x); } + bool operator<(const self& x) const { + return (node == x.node) ? (cur < x.cur) : (node < x.node); + } + + void set_node(map_pointer new_node) { + node = new_node; + first = *new_node; + last = first + buffer_size(); + } +}; + +#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG + +template <class T, class Ref, size_t BufSiz> +inline random_access_iterator_tag +iterator_category(const __deque_iterator<T, Ref, BufSiz>&) { + return random_access_iterator_tag(); +} + +template <class T, class Ref, size_t BufSiz> +inline T* value_type(const __deque_iterator<T, Ref, BufSiz>&) { return 0; } + +template <class T, class Ref, size_t BufSiz> +inline ptrdiff_t* distance_type(const __deque_iterator<T, Ref, BufSiz>&) { + return 0; +} + +#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ + +template <class T, class Ref> +inline random_access_iterator_tag +iterator_category(const __deque_iterator<T, Ref>&) { + return random_access_iterator_tag(); +} + +template <class T, class Ref> +inline T* value_type(const __deque_iterator<T, Ref>&) { return 0; } + +template <class T, class Ref> +inline ptrdiff_t* distance_type(const __deque_iterator<T, Ref>&) { + return 0; +} + +#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ + + +// See __deque_buf_size(). The only reason that the default value is 0 +// is as a workaround for bugs in the way that some compilers handle +// constant expressions. +template <class T, class Alloc = alloc, size_t BufSiz = 0> +class deque { +public: // Basic types + typedef T value_type; + typedef value_type* pointer; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + +public: // Iterators +#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG + typedef __deque_iterator<value_type, reference, BufSiz> iterator; + typedef __deque_iterator<value_type, const_reference, BufSiz> const_iterator; +#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ + typedef __deque_iterator<value_type, reference> iterator; + typedef __deque_iterator<value_type, const_reference> const_iterator; +#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ + typedef reverse_iterator<const_iterator, value_type, const_reference, + difference_type> + const_reverse_iterator; + typedef reverse_iterator<iterator, value_type, reference, difference_type> + reverse_iterator; + +protected: // Internal typedefs + typedef pointer* map_pointer; + typedef simple_alloc<value_type, Alloc> data_allocator; + typedef simple_alloc<pointer, Alloc> map_allocator; + + static size_type buffer_size() { + return __deque_buf_size(BufSiz, sizeof(value_type)); + } + static size_type initial_map_size() { return 8; } + +protected: // Data members + iterator start; + iterator finish; + + map_pointer map; + size_type map_size; + +public: // Basic accessors + iterator begin() { return start; } + iterator end() { return finish; } + const_iterator begin() const { return start; } + const_iterator end() const { return finish; } + + reverse_iterator rbegin() { return reverse_iterator(finish); } + reverse_iterator rend() { return reverse_iterator(start); } + const_reverse_iterator rbegin() const { + return const_reverse_iterator(finish); + } + const_reverse_iterator rend() const { + return const_reverse_iterator(start); + } + + reference operator[](size_type n) { return start[n]; } + const_reference operator[](size_type n) const { return start[n]; } + + reference front() { return *start; } + reference back() { + iterator tmp = finish; + --tmp; + return *tmp; + } + const_reference front() const { return *start; } + const_reference back() const { + const_iterator tmp = finish; + --tmp; + return *tmp; + } + + size_type size() const { return finish - start;; } + size_type max_size() const { return size_type(-1); } + bool empty() const { return finish == start; } + +public: // Constructor, destructor. + deque() + : start(), finish(), map(0), map_size(0) + { + create_map_and_nodes(0); + } + + deque(const deque& x) + : start(), finish(), map(0), map_size(0) + { + create_map_and_nodes(x.size()); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + uninitialized_copy(x.begin(), x.end(), start); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_map_and_nodes(); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } + + deque(size_type n, const value_type& value) + : start(), finish(), map(0), map_size(0) { + fill_initialize(n, value); + } + + deque(int n, const value_type& value) + : start(), finish(), map(0), map_size(0) { + fill_initialize(n, value); + } + + deque(long n, const value_type& value) + : start(), finish(), map(0), map_size(0) { + fill_initialize(n, value); + } + + explicit deque(size_type n) + : start(), finish(), map(0), map_size(0) { + fill_initialize(n, value_type()); + } + +#ifdef __STL_MEMBER_TEMPLATES + + template <class InputIterator> + deque(InputIterator first, InputIterator last) + : start(), finish(), map(0), map_size(0) + { + range_initialize(first, last, iterator_category(first)); + } + +#else /* __STL_MEMBER_TEMPLATES */ + + deque(const value_type* first, const value_type* last) + : start(), finish(), map(0), map_size(0) + { + create_map_and_nodes(last - first); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + uninitialized_copy(first, last, start); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_map_and_nodes(); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } + + deque(const_iterator first, const_iterator last) + : start(), finish(), map(0), map_size(0) + { + create_map_and_nodes(last - first); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + uninitialized_copy(first, last, start); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_map_and_nodes(); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } + +#endif /* __STL_MEMBER_TEMPLATES */ + + ~deque() { + destroy(start, finish); + destroy_map_and_nodes(); + } + + deque& operator= (const deque& x) { + const size_type len = size(); + if (&x != this) { + if (len >= x.size()) + erase(copy(x.begin(), x.end(), start), finish); + else { + const_iterator mid = x.begin() + len; + copy(x.begin(), mid, start); + insert(finish, mid, x.end()); + } + } + return *this; + } + + void swap(deque& x) { + ::swap(start, x.start); + ::swap(finish, x.finish); + ::swap(map, x.map); + ::swap(map_size, x.map_size); + } + +public: // push_* and pop_* + + void push_back(const value_type& t) { + if (finish.cur != finish.last - 1) { + construct(finish.cur, t); + ++finish.cur; + } + else + push_back_aux(t); + } + + void push_front(const value_type& t) { + if (start.cur != start.first) { + construct(start.cur - 1, t); + --start.cur; + } + else + push_front_aux(t); + } + + void pop_back() { + if (finish.cur != finish.first) { + --finish.cur; + destroy(finish.cur); + } + else + pop_back_aux(); + } + + void pop_front() { + if (start.cur != start.last - 1) { + destroy(start.cur); + ++start.cur; + } + else + pop_front_aux(); + } + +public: // Insert + + iterator insert(iterator position, const value_type& x) { + if (position.cur == start.cur) { + push_front(x); + return start; + } + else if (position.cur == finish.cur) { + push_back(x); + iterator tmp = finish; + --tmp; + return tmp; + } + else { + return insert_aux(position, x); + } + } + + iterator insert(iterator position) { return insert(position, value_type()); } + + void insert(iterator pos, size_type n, const value_type& x); + + void insert(iterator pos, int n, const value_type& x) { + insert(pos, (size_type) n, x); + } + void insert(iterator pos, long n, const value_type& x) { + insert(pos, (size_type) n, x); + } + +#ifdef __STL_MEMBER_TEMPLATES + + template <class InputIterator> + void insert(iterator pos, InputIterator first, InputIterator last) { + insert(pos, first, last, iterator_category(first)); + } + +#else /* __STL_MEMBER_TEMPLATES */ + + void insert(iterator pos, const value_type* first, const value_type* last); + void insert(iterator pos, const_iterator first, const_iterator last); + +#endif /* __STL_MEMBER_TEMPLATES */ + + void resize(size_type new_size, const value_type& x) { + const size_type len = size(); + if (new_size < len) + erase(start + new_size, finish); + else + insert(finish, new_size - len, x); + } + + void resize(size_type new_size) { resize(new_size, value_type()); } + +public: // Erase + void erase(iterator pos) { + iterator next = pos; + ++next; + if (pos - start < size() / 2) { + copy_backward(start, pos, next); + pop_front(); + } + else { + copy(next, finish, pos); + pop_back(); + } + } + + void erase(iterator first, iterator last); + void clear(); + +protected: // Internal construction/destruction + + void create_map_and_nodes(size_type num_elements); + void destroy_map_and_nodes(); + void fill_initialize(size_type n, const value_type& value); + +#ifdef __STL_MEMBER_TEMPLATES + + template <class InputIterator> + void range_initialize(InputIterator first, InputIterator last, + input_iterator_tag); + + template <class ForwardIterator> + void range_initialize(ForwardIterator first, ForwardIterator last, + forward_iterator_tag); + + template <class BidirectionalIterator> + void range_initialize(BidirectionalIterator first, + BidirectionalIterator last, + bidirectional_iterator_tag) { + range_initialize(first, last, forward_iterator_tag()); + } + + template <class RandomAccessIterator> + void range_initialize(RandomAccessIterator first, RandomAccessIterator last, + random_access_iterator_tag) { + range_initialize(first, last, forward_iterator_tag()); + } + +#endif /* __STL_MEMBER_TEMPLATES */ + +protected: // Internal push_* and pop_* + + void push_back_aux(const value_type& t); + void push_front_aux(const value_type& t); + void pop_back_aux(); + void pop_front_aux(); + +protected: // Internal insert functions + +#ifdef __STL_MEMBER_TEMPLATES + + template <class InputIterator> + void insert(iterator pos, InputIterator first, InputIterator last, + input_iterator_tag); + + template <class ForwardIterator> + void insert(iterator pos, ForwardIterator first, ForwardIterator last, + forward_iterator_tag); + + template <class BidirectionalIterator> + void insert(iterator pos, + BidirectionalIterator first, BidirectionalIterator last, + bidirectional_iterator_tag) { + insert(pos, first, last, forward_iterator_tag()); + } + + template <class RandomAccessIterator> + void insert(iterator pos, + RandomAccessIterator first, RandomAccessIterator last, + random_access_iterator_tag) { + insert(pos, first, last, forward_iterator_tag()); + } +#endif /* __STL_MEMBER_TEMPLATES */ + + iterator insert_aux(iterator pos, const value_type& x); + void insert_aux(iterator pos, size_type n, const value_type& x); + +#ifdef __STL_MEMBER_TEMPLATES + + template <class ForwardIterator> + void insert_aux(iterator pos, ForwardIterator first, ForwardIterator last, + size_type n); + +#else /* __STL_MEMBER_TEMPLATES */ + + void insert_aux(iterator pos, + const value_type* first, const value_type* last, + size_type n); + + void insert_aux(iterator pos, const_iterator first, const_iterator last, + size_type n); + +#endif /* __STL_MEMBER_TEMPLATES */ + + iterator reserve_elements_at_front(size_type n) { + size_type vacancies = start.cur - start.first; + if (n > vacancies) + new_elements_at_front(n - vacancies); + return start - n; + } + + iterator reserve_elements_at_back(size_type n) { + size_type vacancies = (finish.last - finish.cur) - 1; + if (n > vacancies) + new_elements_at_back(n - vacancies); + return finish + n; + } + + void new_elements_at_front(size_type new_elements); + void new_elements_at_back(size_type new_elements); + + void destroy_nodes_at_front(iterator before_start); + void destroy_nodes_at_back(iterator after_finish); + +protected: // Allocation of map and nodes + + // Makes sure the map has space for new nodes. Does not actually + // add the nodes. Can invalidate map pointers. (And consequently, + // deque iterators.) + + void reserve_map_at_back (size_type nodes_to_add = 1) { + if (nodes_to_add + 1 > map_size - (finish.node - map)) + reallocate_map(nodes_to_add, false); + } + + void reserve_map_at_front (size_type nodes_to_add = 1) { + if (nodes_to_add > start.node - map) + reallocate_map(nodes_to_add, true); + } + + void reallocate_map(size_type nodes_to_add, bool add_at_front); + + pointer allocate_node() { return data_allocator::allocate(buffer_size()); } + void deallocate_node(pointer n) { + data_allocator::deallocate(n, buffer_size()); + } + +#ifdef __STL_NON_TYPE_TMPL_PARAM_BUG +public: + bool operator==(const deque<T, Alloc, 0>& x) const { + return size() == x.size() && equal(begin(), end(), x.begin()); + } + bool operator!=(const deque<T, Alloc, 0>& x) const { + return size() != x.size() || !equal(begin(), end(), x.begin()); + } + bool operator<(const deque<T, Alloc, 0>& x) const { + return lexicographical_compare(begin(), end(), x.begin(), x.end()); + } +#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ +}; + +// Non-inline member functions + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::insert(iterator pos, + size_type n, const value_type& x) { + if (pos.cur == start.cur) { + iterator new_start = reserve_elements_at_front(n); + uninitialized_fill(new_start, start, x); + start = new_start; + } + else if (pos.cur == finish.cur) { + iterator new_finish = reserve_elements_at_back(n); + uninitialized_fill(finish, new_finish, x); + finish = new_finish; + } + else + insert_aux(pos, n, x); +} + +#ifndef __STL_MEMBER_TEMPLATES + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::insert(iterator pos, + const value_type* first, + const value_type* last) { + size_type n = last - first; + if (pos.cur == start.cur) { + iterator new_start = reserve_elements_at_front(n); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif + uninitialized_copy(first, last, new_start); + start = new_start; +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_front(new_start); + throw; + } +# endif + } + else if (pos.cur == finish.cur) { + iterator new_finish = reserve_elements_at_back(n); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif + uninitialized_copy(first, last, finish); + finish = new_finish; +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_back(new_finish); + throw; + } +# endif + } + else + insert_aux(pos, first, last, n); +} + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::insert(iterator pos, + const_iterator first, + const_iterator last) +{ + size_type n = last - first; + if (pos.cur == start.cur) { + iterator new_start = reserve_elements_at_front(n); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif + uninitialized_copy(first, last, new_start); + start = new_start; +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_front(new_start); + throw; + } +# endif + } + else if (pos.cur == finish.cur) { + iterator new_finish = reserve_elements_at_back(n); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif + uninitialized_copy(first, last, finish); + finish = new_finish; +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_back(new_finish); + throw; + } +# endif + } + else + insert_aux(pos, first, last, n); +} + +#endif /* __STL_MEMBER_TEMPLATES */ + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::erase(iterator first, iterator last) { + if (first == start && last == finish) + clear(); + else { + difference_type n = last - first; + difference_type elems_before = first - start; + if (elems_before < (size() - n) / 2) { + copy_backward(start, first, last); + iterator new_start = start + n; + destroy(start, new_start); + for (map_pointer cur = start.node; cur < new_start.node; ++cur) + data_allocator::deallocate(*cur, buffer_size()); + start = new_start; + } + else { + copy(last, finish, first); + iterator new_finish = finish - n; + destroy(new_finish, finish); + for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur) + data_allocator::deallocate(*cur, buffer_size()); + finish = new_finish; + } + } +} + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::clear() { + for (map_pointer node = start.node + 1; node < finish.node; ++node) { + destroy(*node, *node + buffer_size()); + data_allocator::deallocate(*node, buffer_size()); + } + + if (start.node != finish.node) { + destroy(start.cur, start.last); + destroy(finish.first, finish.cur); + data_allocator::deallocate(finish.first, buffer_size()); + } + else + destroy(start.cur, finish.cur); + + finish = start; +} + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) { + size_type num_nodes = num_elements / buffer_size() + 1; + + map_size = max(initial_map_size(), num_nodes + 2); + map = map_allocator::allocate(map_size); + + map_pointer nstart = map + (map_size - num_nodes) / 2; + map_pointer nfinish = nstart + num_nodes - 1; + + map_pointer cur; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + for (cur = nstart; cur <= nfinish; ++cur) + *cur = allocate_node(); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + for (map_pointer n = nstart; n < cur; ++n) + deallocate_node(*n); + map_allocator::deallocate(map, map_size); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + + start.set_node(nstart); + finish.set_node(nfinish); + start.cur = start.first; + finish.cur = finish.first + num_elements % buffer_size(); +} + +// This is only used as a cleanup function in catch clauses. +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::destroy_map_and_nodes() { + for (map_pointer cur = start.node; cur <= finish.node; ++cur) + deallocate_node(*cur); + map_allocator::deallocate(map, map_size); +} + + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::fill_initialize(size_type n, + const value_type& value) { + create_map_and_nodes(n); + map_pointer cur; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + for (cur = start.node; cur < finish.node; ++cur) + uninitialized_fill(*cur, *cur + buffer_size(), value); + uninitialized_fill(finish.first, finish.cur, value); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + for (map_pointer n = start.node; n < cur; ++n) + destroy(*cur, *cur + buffer_size()); + destroy_map_and_nodes(); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ +} + +#ifdef __STL_MEMBER_TEMPLATES + +template <class T, class Alloc, size_t BufSize> +template <class InputIterator> +void deque<T, Alloc, BufSize>::range_initialize(InputIterator first, + InputIterator last, + input_iterator_tag) { + create_map_and_nodes(0); + for ( ; first != last; ++first) + push_back(*first); +} + +template <class T, class Alloc, size_t BufSize> +template <class ForwardIterator> +void deque<T, Alloc, BufSize>::range_initialize(ForwardIterator first, + ForwardIterator last, + forward_iterator_tag) { + size_type n = 0; + distance(first, last, n); + create_map_and_nodes(n); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + uninitialized_copy(first, last, start); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_map_and_nodes(); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ +} + +#endif /* __STL_MEMBER_TEMPLATES */ + +// Called only if finish.cur == finish.last - 1. +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) { + value_type t_copy = t; + reserve_map_at_back(); + *(finish.node + 1) = allocate_node(); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + construct(finish.cur, t_copy); + finish.set_node(finish.node + 1); + finish.cur = finish.first; +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + deallocate_node(*(finish.node + 1)); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ +} + +// Called only if start.cur == start.first. +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) { + value_type t_copy = t; + reserve_map_at_front(); + *(start.node - 1) = allocate_node(); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + start.set_node(start.node - 1); + start.cur = start.last - 1; + construct(start.cur, t_copy); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + start.set_node(start.node + 1); + start.cur = start.first; + deallocate_node(*(start.node - 1)); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ +} + +// Called only if finish.cur == finish.first. +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>:: pop_back_aux() { + deallocate_node(finish.first); + finish.set_node(finish.node - 1); + finish.cur = finish.last - 1; + destroy(finish.cur); +} + +// Called only if start.cur == start.last - 1. Note that if the deque +// has at least one element (a necessary precondition for this member +// function), and if start.cur == start.last, then the deque must have +// at least two nodes. +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::pop_front_aux() { + destroy(start.cur); + deallocate_node(start.first); + start.set_node(start.node + 1); + start.cur = start.first; +} + +#ifdef __STL_MEMBER_TEMPLATES + +template <class T, class Alloc, size_t BufSize> +template <class InputIterator> +void deque<T, Alloc, BufSize>::insert(iterator pos, + InputIterator first, InputIterator last, + input_iterator_tag) { + copy(first, last, inserter(*this, pos)); +} + +template <class T, class Alloc, size_t BufSize> +template <class ForwardIterator> +void deque<T, Alloc, BufSize>::insert(iterator pos, + ForwardIterator first, + ForwardIterator last, + forward_iterator_tag) { + size_type n = 0; + distance(first, last, n); + if (pos.cur == start.cur) { + iterator new_start = reserve_elements_at_front(n); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif + uninitialized_copy(first, last, new_start); + start = new_start; +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_front(new_start); + throw; + } +# endif + } + else if (pos.cur == finish.cur) { + iterator new_finish = reserve_elements_at_back(n); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif + uninitialized_copy(first, last, finish); + finish = new_finish; +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_back(new_finish); + throw; + } +# endif + } + else + insert_aux(pos, first, last, n); +} + +#endif /* __STL_MEMBER_TEMPLATES */ + +template <class T, class Alloc, size_t BufSize> +deque<T, Alloc, BufSize>::iterator +deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x) { + difference_type index = pos - start; + value_type x_copy = x; + if (index < size() / 2) { + push_front(front()); + iterator front1 = start; + ++front1; + iterator front2 = front1; + ++front2; + pos = start + index; + iterator pos1 = pos; + ++pos1; + copy(front2, pos1, front1); + } + else { + push_back(back()); + iterator back1 = finish; + --back1; + iterator back2 = back1; + --back2; + pos = start + index; + copy_backward(pos, back2, back1); + } + *pos = x_copy; + return pos; +} + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::insert_aux(iterator pos, + size_type n, const value_type& x) { + const difference_type elems_before = pos - start; + size_type length = size(); + value_type x_copy = x; + if (elems_before < length / 2) { + iterator new_start = reserve_elements_at_front(n); + iterator old_start = start; + pos = start + elems_before; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + if (elems_before >= n) { + iterator start_n = start + n; + uninitialized_copy(start, start_n, new_start); + start = new_start; + copy(start_n, pos, old_start); + fill(pos - n, pos, x_copy); + } + else { + __uninitialized_copy_fill(start, pos, new_start, start, x_copy); + start = new_start; + fill(old_start, pos, x_copy); + } +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_front(new_start); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } + else { + iterator new_finish = reserve_elements_at_back(n); + iterator old_finish = finish; + const difference_type elems_after = length - elems_before; + pos = finish - elems_after; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + if (elems_after > n) { + iterator finish_n = finish - n; + uninitialized_copy(finish_n, finish, finish); + finish = new_finish; + copy_backward(pos, finish_n, old_finish); + fill(pos, pos + n, x_copy); + } + else { + __uninitialized_fill_copy(finish, pos + n, x_copy, pos, finish); + finish = new_finish; + fill(pos, old_finish, x_copy); + } +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_back(new_finish); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } +} + +#ifdef __STL_MEMBER_TEMPLATES + +template <class T, class Alloc, size_t BufSize> +template <class ForwardIterator> +void deque<T, Alloc, BufSize>::insert_aux(iterator pos, + ForwardIterator first, + ForwardIterator last, + size_type n) +{ + const difference_type elems_before = pos - start; + size_type length = size(); + if (elems_before < length / 2) { + iterator new_start = reserve_elements_at_front(n); + iterator old_start = start; + pos = start + elems_before; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + if (elems_before >= n) { + iterator start_n = start + n; + uninitialized_copy(start, start_n, new_start); + start = new_start; + copy(start_n, pos, old_start); + copy(first, last, pos - n); + } + else { + ForwardIterator mid = first; + advance(mid, n - elems_before); + __uninitialized_copy_copy(start, pos, first, mid, new_start); + start = new_start; + copy(mid, last, old_start); + } +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_front(new_start); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } + else { + iterator new_finish = reserve_elements_at_back(n); + iterator old_finish = finish; + const difference_type elems_after = length - elems_before; + pos = finish - elems_after; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + if (elems_after > n) { + iterator finish_n = finish - n; + uninitialized_copy(finish_n, finish, finish); + finish = new_finish; + copy_backward(pos, finish_n, old_finish); + copy(first, last, pos); + } + else { + ForwardIterator mid = first; + advance(mid, elems_after); + __uninitialized_copy_copy(mid, last, pos, finish, finish); + finish = new_finish; + copy(first, mid, pos); + } +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_back(new_finish); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } +} + +#else /* __STL_MEMBER_TEMPLATES */ + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::insert_aux(iterator pos, + const value_type* first, + const value_type* last, + size_type n) +{ + const difference_type elems_before = pos - start; + size_type length = size(); + if (elems_before < length / 2) { + iterator new_start = reserve_elements_at_front(n); + iterator old_start = start; + pos = start + elems_before; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + if (elems_before >= n) { + iterator start_n = start + n; + uninitialized_copy(start, start_n, new_start); + start = new_start; + copy(start_n, pos, old_start); + copy(first, last, pos - n); + } + else { + const value_type* mid = first + (n - elems_before); + __uninitialized_copy_copy(start, pos, first, mid, new_start); + start = new_start; + copy(mid, last, old_start); + } +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_front(new_start); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } + else { + iterator new_finish = reserve_elements_at_back(n); + iterator old_finish = finish; + const difference_type elems_after = length - elems_before; + pos = finish - elems_after; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + if (elems_after > n) { + iterator finish_n = finish - n; + uninitialized_copy(finish_n, finish, finish); + finish = new_finish; + copy_backward(pos, finish_n, old_finish); + copy(first, last, pos); + } + else { + const value_type* mid = first + elems_after; + __uninitialized_copy_copy(mid, last, pos, finish, finish); + finish = new_finish; + copy(first, mid, pos); + } +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_back(new_finish); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } +} + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::insert_aux(iterator pos, + const_iterator first, + const_iterator last, + size_type n) +{ + const difference_type elems_before = pos - start; + size_type length = size(); + if (elems_before < length / 2) { + iterator new_start = reserve_elements_at_front(n); + iterator old_start = start; + pos = start + elems_before; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + if (elems_before >= n) { + iterator start_n = start + n; + uninitialized_copy(start, start_n, new_start); + start = new_start; + copy(start_n, pos, old_start); + copy(first, last, pos - n); + } + else { + const_iterator mid = first + (n - elems_before); + __uninitialized_copy_copy(start, pos, first, mid, new_start); + start = new_start; + copy(mid, last, old_start); + } +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_front(new_start); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } + else { + iterator new_finish = reserve_elements_at_back(n); + iterator old_finish = finish; + const difference_type elems_after = length - elems_before; + pos = finish - elems_after; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + if (elems_after > n) { + iterator finish_n = finish - n; + uninitialized_copy(finish_n, finish, finish); + finish = new_finish; + copy_backward(pos, finish_n, old_finish); + copy(first, last, pos); + } + else { + const_iterator mid = first + elems_after; + __uninitialized_copy_copy(mid, last, pos, finish, finish); + finish = new_finish; + copy(first, mid, pos); + } +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy_nodes_at_back(new_finish); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } +} + +#endif /* __STL_MEMBER_TEMPLATES */ + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::new_elements_at_front(size_type new_elements) { + size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size(); + reserve_map_at_front(new_nodes); + size_type i; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + for (i = 1; i <= new_nodes; ++i) + *(start.node - i) = allocate_node(); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + for (size_type j = 1; j < i; ++j) + deallocate_node(*(start.node - j)); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ +} + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::new_elements_at_back(size_type new_elements) { + size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size(); + reserve_map_at_back(new_nodes); + size_type i; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + for (i = 1; i <= new_nodes; ++i) + *(finish.node + i) = allocate_node(); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + for (size_type j = 1; j < i; ++j) + deallocate_node(*(finish.node + j)); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ +} + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::destroy_nodes_at_front(iterator before_start) { + for (map_pointer n = before_start.node; n < start.node; ++n) + deallocate_node(*n); +} + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::destroy_nodes_at_back(iterator after_finish) { + for (map_pointer n = after_finish.node; n > finish.node; --n) + deallocate_node(*n); +} + +template <class T, class Alloc, size_t BufSize> +void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add, + bool add_at_front) { + size_type old_num_nodes = finish.node - start.node + 1; + size_type new_num_nodes = old_num_nodes + nodes_to_add; + + map_pointer new_nstart; + if (map_size > 2 * new_num_nodes) { + new_nstart = map + (map_size - new_num_nodes) / 2 + + (add_at_front ? nodes_to_add : 0); + if (new_nstart < start.node) + copy(start.node, finish.node + 1, new_nstart); + else + copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes); + } + else { + size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2; + + map_pointer new_map = map_allocator::allocate(new_map_size); + new_nstart = new_map + (new_map_size - new_num_nodes) / 2 + + (add_at_front ? nodes_to_add : 0); + copy(start.node, finish.node + 1, new_nstart); + map_allocator::deallocate(map, map_size); + + map = new_map; + map_size = new_map_size; + } + + start.set_node(new_nstart); + finish.set_node(new_nstart + old_num_nodes - 1); +} + + +// Nonmember functions. + +#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG + +template <class T, class Alloc, size_t BufSiz> +bool operator==(const deque<T, Alloc, BufSiz>& x, + const deque<T, Alloc, BufSiz>& y) { + return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); +} + +template <class T, class Alloc, size_t BufSiz> +bool operator<(const deque<T, Alloc, BufSiz>& x, + const deque<T, Alloc, BufSiz>& y) { + return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); +} + +#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ + + +#endif /* __SGI_STL_DEQUE_H */ + |