// -*- C++ -*- /*************************************************************************** * * - definition of the C++ Standard Library list class template * * $Id$ * *************************************************************************** * * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed * with this work for additional information regarding copyright * ownership. The ASF licenses this file to you under the Apache * License, Version 2.0 (the "License"); you may not use this file * except in compliance with the License. You may obtain a copy of * the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or * implied. See the License for the specific language governing * permissions and limitations under the License. * * Copyright 1994-2005 Rogue Wave Software. * *************************************************************************** * * 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. * **************************************************************************/ #ifndef _RWSTD_LIST_INCLUDED #define _RWSTD_LIST_INCLUDED #include #include #include #include #include #include _RWSTD_NAMESPACE (std) { template struct __rw_list_node { __rw_list_node* _C_next; // pointer to next node __rw_list_node* _C_prev; // pointer to previous node _TypeT _C_data; // client data }; template class __rw_list_iter : public iterator { typedef iterator _C_iter_base; public: typedef _TYPENAME _C_iter_base::value_type value_type; typedef _TYPENAME _C_iter_base::difference_type difference_type; typedef _TYPENAME _C_iter_base::pointer pointer; typedef _TYPENAME _C_iter_base::reference reference; // const_pointer and const_reference must be explicity typedef'ed to // const value_type* and const value_type& since we don't know if // _Pointer and _Reference are const types (they aren't if this isn't // a const iterator) typedef const value_type* const_pointer; typedef const value_type& const_reference; typedef bidirectional_iterator_tag iterator_category; typedef __rw_list_iter _C_mutable_iter; typedef __rw_list_node* _C_link_type; __rw_list_iter () { } __rw_list_iter (const _C_link_type& __rhs) : _C_node (__rhs) { } // no copy ctor other than the one below defined; will use // a compiler generated one if __rw_list_iter != _C_mutable_iter __rw_list_iter (const _C_mutable_iter &__rhs) : _C_node (__rhs._C_node) { } __rw_list_iter& operator++ () { _C_node = (_C_link_type)((*_C_node)._C_next); return *this; } __rw_list_iter& operator-- () { _C_node = (_C_link_type)((*_C_node)._C_prev); return *this; } __rw_list_iter operator++ (int) { __rw_list_iter __tmp = *this; return ++*this, __tmp; } __rw_list_iter operator-- (int) { __rw_list_iter __tmp = *this; return --*this, __tmp; } reference operator* () const { return (*_C_node)._C_data; } _RWSTD_OPERATOR_ARROW (pointer operator-> () const); difference_type operator- (const __rw_list_iter&) const { return 0; } bool operator== (const __rw_list_iter& __iter) const { return _C_node == __iter._C_node; } bool operator!= (const __rw_list_iter& __iter) const { return !(*this == __iter); } // private: _C_link_type _C_node; }; #undef _ITER_NODE #define _ITER_NODE(it) (_ITER_BASE (it)._C_node) template inline bool operator== (const __rw_list_iter<_TypeT, _DiffT, _Ptr1, _Ref1> &__x, const __rw_list_iter<_TypeT, _DiffT, _Ptr2, _Ref2> &__y) { return __x._C_node == __y._C_node; } template inline bool operator!= (const __rw_list_iter<_TypeT, _DiffT, _Ptr1, _Ref1> &__x, const __rw_list_iter<_TypeT, _DiffT, _Ptr2, _Ref2> &__y) { return !(__x == __y); } _EXPORT template > class list : private _Allocator { public: typedef _TypeT value_type; typedef _Allocator allocator_type; typedef _TYPENAME allocator_type::reference reference; typedef _TYPENAME allocator_type::const_reference const_reference; typedef _TYPENAME allocator_type::size_type size_type; typedef _TYPENAME allocator_type::difference_type difference_type; typedef _TYPENAME allocator_type::pointer pointer; typedef _TYPENAME allocator_type::const_pointer const_pointer; typedef __rw_list_node _C_list_node; typedef _C_list_node* _C_link_type; typedef _RWSTD_REBIND (allocator_type, _C_list_node) _C_node_alloc_type; typedef _RWSTD_ALLOC_TYPE (allocator_type, value_type) _C_value_alloc_type; typedef __rw_list_iter _C_list_iter; typedef __rw_list_iter _C_list_citer; #ifndef _RWSTD_NO_DEBUG_ITER typedef _RW::__rw_debug_iter iterator; typedef _RW::__rw_debug_iter const_iterator; iterator _C_make_iter (const _C_link_type &__node) { return iterator (*this, _C_list_iter (__node)); } const_iterator _C_make_iter (const _C_link_type &__node) const { return const_iterator (*this, _C_list_citer (__node)); } #else // if defined (_RWSTD_NO_DEBUG_ITER) typedef _C_list_iter iterator; typedef _C_list_citer const_iterator; iterator _C_make_iter (const _C_link_type &__node) { return iterator (__node); } const_iterator _C_make_iter (const _C_link_type &__node) const { return const_iterator (__node); } #endif // _RWSTD_NO_DEBUG_ITER #if !defined (_RWSTD_NO_CLASS_PARTIAL_SPEC) typedef _STD::reverse_iterator const_reverse_iterator; typedef _STD::reverse_iterator reverse_iterator; #else // if defined (_RWSTD_NO_CLASS_PARTIAL_SPEC) typedef std::reverse_iterator const_reverse_iterator; typedef std::reverse_iterator reverse_iterator; #endif // _RWSTD_NO_CLASS_PARTIAL_SPEC protected: #ifndef _RWSTD_NO_LIST_NODE_BUFFER // Node buffer data structure struct _C_nodebuf { typedef _RWSTD_REBIND (allocator_type, _C_nodebuf) _C_alloc_type; typedef _TYPENAME _C_alloc_type::pointer _C_pointer; _C_pointer _C_next_buf; size_type _C_bufsize; _C_link_type _C_buffer; }; typedef _TYPENAME _C_nodebuf::_C_alloc_type _C_buf_alloc_type; typedef _TYPENAME _C_nodebuf::_C_pointer _C_buf_pointer; void _C_add_buffer (bool); void _C_free_buffers (); _C_buf_pointer _C_buflist; _C_link_type _C_free_list; #endif // _RWSTD_USE_LIST_NODE_BUFFER _C_link_type _C_next_avail; _C_link_type _C_last; _C_link_type _C_node; size_type _C_length; // Macros used later in node buffer management #if !defined (_RWSTD_NO_LIST_NODE_BUFFER) # define _RWSTD_NODE_BUFFER_INIT(blist,flist) \ _C_buflist (blist), _C_free_list (flist), # define _RWSTD_NODE_LIST_FREE() \ _C_free_buffers () # define _RWSTD_NODE_LIST_SWAP(other) \ _STD::swap (_C_buflist, other._C_buflist); \ _STD::swap (_C_free_list, other._C_free_list) # define _RWSTD_LIST_INSERT_RANGE(b,e,v) \ _TRY { \ insert (b, e, v); \ } _CATCH (...) { \ _RWSTD_NODE_LIST_FREE(); \ _RETHROW; \ } typedef void __dummy_t _C_link_type _C_get_node (bool __empty_list = false) { if (_C_free_list) { _C_link_type __tmp = _C_free_list; _C_free_list = _C_free_list->_C_next; return __tmp; } if (_C_next_avail == _C_last) _C_add_buffer (__empty_list); return _C_next_avail++; } void _C_put_node (_C_link_type __link) { __link->_C_next = _C_free_list; _C_free_list = __link; } #else // defined (_RWSTD_NO_LIST_NODE_BUFFER) # define _RWSTD_NODE_BUFFER_INIT(ignore0,ignore1) # define _RWSTD_NODE_LIST_FREE() # define _RWSTD_NODE_LIST_SWAP(ignore) # define _RWSTD_LIST_INSERT_RANGE(b,e,v) \ insert (b,e,v) _C_link_type _C_get_node (bool = false) { return _C_node_alloc_type (*this).allocate (1, (void*)_C_last); } void _C_put_node (_C_link_type __link) { _C_node_alloc_type (*this).deallocate (__link, 1); } #endif // _RWSTD_NO_LIST_NODE_BUFFER # define _RWSTD_LIST_SAFE_INSERT_RANGE(__it, __first, __last) \ _RWSTD_ASSERT_RANGE (begin (), __it); \ _RWSTD_ASSERT_RANGE (__first, __last); \ \ if (!(__first == __last)) { \ iterator __start = __it; \ \ _TRY { \ __start = insert (__it, *__first); \ \ while (!(++__first == __last)) \ insert (__it, *__first); \ } _CATCH (...) { \ erase (__start, __it); \ _RETHROW; \ } \ } typedef void __dummy_t // here and only here is _C_node initialized void _C_init (bool __empty_list = false) { _C_node = _C_get_node (__empty_list); (*_C_node)._C_next = _C_node; (*_C_node)._C_prev = _C_node; } void _C_init (size_type __n, const value_type& __val) { _C_init(); _RWSTD_LIST_INSERT_RANGE (begin (), __n, __val); } public: _EXPLICIT list (const allocator_type& __alloc = allocator_type ()) : allocator_type (__alloc), _RWSTD_NODE_BUFFER_INIT(0,0) _C_next_avail (0), _C_last (0), _C_node (0), _C_length (0) { _C_init (true); } _EXPLICIT list (size_type __n, const_reference __x = value_type (), const allocator_type &__alloc = allocator_type ()) : allocator_type (__alloc), _RWSTD_NODE_BUFFER_INIT(0,0) _C_next_avail (0), _C_last (0), _C_node (0), _C_length (0) { _C_init (__n, __x); } template void _C_init (_InputIterator __first, _InputIterator __last, void*) { _RWSTD_ASSERT_RANGE (__first, __last); _C_init(); _RWSTD_LIST_INSERT_RANGE (begin (), __first, __last); } template void _C_init (_InputIterator __first, _InputIterator __last, int) { _RWSTD_ASSERT_RANGE (__first, __last); _C_init (__first, __last); } template list (_InputIterator __first, _InputIterator __last, const allocator_type& __alloc = allocator_type ()) : allocator_type (__alloc), _RWSTD_NODE_BUFFER_INIT(0,0) _C_next_avail (0), _C_last (0), _C_node (0), _C_length (0) { _RWSTD_ASSERT_RANGE (__first, __last); _C_init (__first, __last, _RWSTD_DISPATCH (_InputIterator)); } list (const list &__rhs) : allocator_type(__rhs.get_allocator()), _RWSTD_NODE_BUFFER_INIT(0,0) _C_next_avail (0), _C_last (0), _C_node (0), _C_length (0) { _C_init(); _RWSTD_LIST_INSERT_RANGE (begin (), __rhs.begin (), __rhs.end ()); } ~list (); list& operator= (const list&); template void assign (_InputIterator __first, _InputIterator __last) { _RWSTD_ASSERT_RANGE (__first, __last); clear (); _C_insert (begin (), __first, __last, _RWSTD_DISPATCH (_InputIterator)); } void assign (size_type __n, const_reference __val) { clear (); insert (begin (), __n, __val); } allocator_type get_allocator () const { return *this; } iterator begin () { return _C_make_iter ((*_C_node)._C_next); } const_iterator begin () const { return _C_make_iter ((*_C_node)._C_next); } iterator end () { return _C_make_iter (_C_node); } const_iterator end () const { return _C_make_iter (_C_node); } reverse_iterator rbegin () { return reverse_iterator (end ()); } const_reverse_iterator rbegin () const { return const_reverse_iterator (end ()); } reverse_iterator rend () { return reverse_iterator (begin ()); } const_reverse_iterator rend () const { return const_reverse_iterator (begin ()); } bool empty () const { return 0 == size (); } size_type size () const { return _C_length; } size_type max_size () const { return _C_node_alloc_type (*this).max_size (); } void resize (size_type, value_type); void resize (size_type __n) { resize (__n, value_type ()); } reference front () { _RWSTD_ASSERT (!empty ()); return *begin (); } const_reference front () const { _RWSTD_ASSERT (!empty ()); return *begin (); } reference back () { _RWSTD_ASSERT (!empty ()); return *--end (); } const_reference back () const { _RWSTD_ASSERT (!empty ()); return *--end (); } void push_front (const_reference __x) { insert (begin (), __x); _RWSTD_ASSERT (!empty ()); } void push_back (const_reference __x) { insert (end (), __x); _RWSTD_ASSERT (!empty ()); } void pop_front () { _RWSTD_ASSERT (!empty ()); erase (begin ()); } void pop_back () { _RWSTD_ASSERT (!empty ()); erase (--end ()); } iterator insert (iterator __it, const_reference __x); // handles nonintegral types template void _C_insert (const iterator &__it, _InputIterator __first, _InputIterator __last, void*) { _RWSTD_LIST_SAFE_INSERT_RANGE (__it, __first, __last); } // handles integral types template void _C_insert (const iterator &__it, _InputIterator __first, _InputIterator __last, int) { _C_insert (__it, size_type (__first), const_reference (__last)); } template void insert (iterator __it, _InputIterator __first, _InputIterator __last) { _RWSTD_ASSERT_RANGE (begin (), __it); _RWSTD_ASSERT_RANGE (__first, __last); // calling insert on a list specialized on an integral type // may lead to ambiguities if the actual function arguments do not // exactly match those of the non-templatized function (below) // the dispatch mechanism determines whether the arguments // really are iterators or whether they are just integral types // and calls the appropriate implementation function _C_insert (__it, __first, __last, _RWSTD_DISPATCH (_InputIterator)); } void insert (iterator __it, size_type __n, const_reference __val) { _RWSTD_ASSERT_RANGE (begin (), __it); _C_insert (__it, __n, __val); } iterator erase (iterator); iterator erase (iterator, iterator); void swap (list&); void clear () { erase (begin (), end ()); } #if defined (_RWSTD_NO_PART_SPEC_OVERLOAD) friend void swap (list& __lhs, list& __rhs) { __lhs.swap (__rhs); } #endif protected: void _C_transfer (iterator, iterator, iterator, list&); void _C_advance (iterator &__it, difference_type __n, const iterator &__end) { while (__n-- && !(__it == __end)) ++__it; } // uses transfer_node to merge in list by transfering nodes to list void _C_adjacent_merge (iterator, iterator, iterator); #ifndef _RWSTD_NO_MEMBER_TEMPLATES // uses transfer_node to merge in list by transfering nodes to list template void _C_adjacent_merge (iterator, iterator, iterator, _Compare); #else // if defined (_RWSTD_NO_MEMBER_TEMPLATES) void _C_adjacent_merge (iterator, iterator, iterator, bool (*)(const_reference, const_reference)); #endif // _RWSTD_NO_MEMBER_TEMPLATES void _C_insert (iterator __it, size_type __n, const_reference __x) { _RWSTD_ASSERT_RANGE (begin (), __it); if (__n) { iterator __start = __it; _TRY { __start = insert (__it, __x); while (--__n) insert (__it, __x); } _CATCH (...) { erase (__start, __it); _RETHROW; } } } public: // 23.2.2.4, p4 void splice (iterator, list&); // 23.2.2.4, p7 void splice (iterator, list&, iterator); // 23.2.2.4, p11 void splice (iterator, list&, iterator, iterator); void remove (const_reference); void unique (); void merge (list&); void reverse (); void sort (); #ifndef _RWSTD_NO_MEMBER_TEMPLATES template void remove_if (_Predicate); template void unique (_BinaryPredicate); template void merge (list &__x, _Compare); template void sort (_Compare); #else // if defined (_RWSTD_NO_MEMBER_TEMPLATES) void remove_if (bool (*)(const_reference)); void unique (bool (*)(const_reference, const_reference)); void merge (list &__x, bool (*)(const_reference, const_reference)); void sort (bool (*)(const_reference, const_reference)); #endif // _RWSTD_NO_MEMBER_TEMPLATES }; template inline bool operator== (const list<_TypeT, _Allocator>& __x, const list<_TypeT, _Allocator>& __y) { return __x.size () == __y.size () && equal (__x.begin (), __x.end (), __y.begin ()); } template inline bool operator< (const list<_TypeT, _Allocator>& __x, const list<_TypeT, _Allocator>& __y) { return lexicographical_compare (__x.begin (), __x.end (), __y.begin (), __y.end ()); } template inline bool operator!= (const list<_TypeT, _Allocator>& __x, const list<_TypeT, _Allocator>& __y) { return !(__x == __y); } template inline bool operator<= (const list<_TypeT, _Allocator>& __x, const list<_TypeT, _Allocator>& __y) { return !(__y < __x); } template inline bool operator> (const list<_TypeT, _Allocator>& __x, const list<_TypeT, _Allocator>& __y) { return __y < __x; } template inline bool operator>= (const list<_TypeT, _Allocator>& __x, const list<_TypeT, _Allocator>& __y) { return !(__x < __y); } #ifndef _RWSTD_NO_PART_SPEC_OVERLOAD template inline void swap (list<_TypeT, _Allocator>& __x, list<_TypeT, _Allocator>& __y) { __x.swap (__y); } #endif // _RWSTD_NO_PART_SPEC_OVERLOAD template inline _TYPENAME list<_TypeT, _Allocator>::iterator list<_TypeT, _Allocator>::insert (iterator __it, const_reference __x) { _RWSTD_ASSERT_RANGE (begin (), __it); // create temporary allocator for non-conforming compilers // which need to use allocator_interface _C_link_type __tmp = _C_get_node (false); _TRY { _RWSTD_VALUE_ALLOC (_C_value_alloc_type, *this, construct (_RWSTD_VALUE_ALLOC (_C_value_alloc_type, *this, address ((*__tmp)._C_data)), __x)); } _CATCH (...) { _C_put_node (__tmp); _RETHROW; } (*__tmp)._C_next = _ITER_NODE (__it); (*__tmp)._C_prev = (*_ITER_NODE (__it))._C_prev; (*(_C_link_type ((*_ITER_NODE (__it))._C_prev)))._C_next = __tmp; (*_ITER_NODE (__it))._C_prev = __tmp; ++_C_length; return _C_make_iter (__tmp); } template inline _TYPENAME list<_TypeT, _Allocator>::iterator list<_TypeT, _Allocator>::erase (iterator __it) { _RWSTD_ASSERT_RANGE (begin (), __it); if (__it == end ()) return end (); iterator __tmp = _C_make_iter (_C_link_type ((*_ITER_NODE (__it))._C_next)); (*(_C_link_type ((*_ITER_NODE (__it))._C_prev)))._C_next = (*_ITER_NODE (__it))._C_next; (*(_C_link_type ((*_ITER_NODE (__it))._C_next)))._C_prev = (*_ITER_NODE (__it))._C_prev; --_C_length; _RWSTD_VALUE_ALLOC (_C_value_alloc_type, *this, destroy (_RWSTD_VALUE_ALLOC (_C_value_alloc_type, *this, address ((*_ITER_NODE (__it))._C_data)))); _C_put_node (_ITER_NODE (__it)); return __tmp; } template inline void list<_TypeT, _Allocator>::swap (list &__x) { if (get_allocator () == __x.get_allocator ()) { _STD::swap (_C_node, __x._C_node); _STD::swap (_C_length, __x._C_length); _RWSTD_NODE_LIST_SWAP(__x); _STD::swap (_C_next_avail, __x._C_next_avail); _STD::swap (_C_last, __x._C_last); } else { list __tmp (*this); *this = __x; __x = __tmp; } } } // namespace std #ifdef _RWSTD_NO_IMPLICIT_INCLUSION # include #endif #endif //_RWSTD_LIST_INCLUDED