diff options
Diffstat (limited to 'libstdc++-v3')
| -rw-r--r-- | libstdc++-v3/ChangeLog | 15 | ||||
| -rw-r--r-- | libstdc++-v3/include/Makefile.am | 5 | ||||
| -rw-r--r-- | libstdc++-v3/include/Makefile.in | 265 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/deque.tcc | 784 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/list.tcc | 374 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/stl_deque.h | 741 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/stl_list.h | 318 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/stl_vector.h | 377 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/vector.tcc | 439 | ||||
| -rw-r--r-- | libstdc++-v3/include/ext/stl_hashtable.h | 7 | ||||
| -rw-r--r-- | libstdc++-v3/include/std/std_deque.h | 7 | ||||
| -rw-r--r-- | libstdc++-v3/include/std/std_list.h | 7 | ||||
| -rw-r--r-- | libstdc++-v3/include/std/std_vector.h | 7 |
13 files changed, 1997 insertions, 1349 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index d00fa2f9fb1..a60aec61646 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,18 @@ +2002-06-12 Phil Edwards <pme@gcc.gnu.org> + + * include/Makefile.am: Add new files. + * include/Makefile.in: Regenerate. + + * include/bits/stl_deque.h, include/bits/stl_list.h, + include/bits/stl_vector.h: Clean up, reformat. Move definitions... + * include/bits/deque.tcc, include/bits/list.tcc, + include/bits/vector.tcc: ...to here. New files. + + * include/ext/stl_hashtable.h: Inclide correct full headers. + * include/std/std_deque.h: Include .tcc files for now. + * include/std/std_list.h: Likewise. + * include/std/std_vector.h: Likewise. + 2002-06-12 Daniel Jacobowitz <drow@mvista.com> * Makefile.am: Add FLAGS_TO_PASS. diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 8101941c766..9994b31020c 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -43,6 +43,7 @@ bits_headers = \ ${bits_srcdir}/codecvt.h \ ${bits_srcdir}/concept_check.h \ ${bits_srcdir}/cpp_type_traits.h \ + ${bits_srcdir}/deque.tcc \ ${bits_srcdir}/fpos.h \ ${bits_srcdir}/fstream.tcc \ ${bits_srcdir}/functexcept.h \ @@ -52,6 +53,7 @@ bits_headers = \ ${bits_srcdir}/indirect_array.h \ ${bits_srcdir}/ios_base.h \ ${bits_srcdir}/istream.tcc \ + ${bits_srcdir}/list.tcc \ ${bits_srcdir}/locale_facets.h \ ${bits_srcdir}/locale_facets.tcc \ ${bits_srcdir}/localefwd.h \ @@ -96,7 +98,8 @@ bits_headers = \ ${bits_srcdir}/type_traits.h \ ${bits_srcdir}/valarray_array.h \ ${bits_srcdir}/valarray_array.tcc \ - ${bits_srcdir}/valarray_meta.h + ${bits_srcdir}/valarray_meta.h \ + ${bits_srcdir}/vector.tcc backward_srcdir = ${glibcpp_srcdir}/include/backward backward_builddir = ./backward diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index 7e7a802b077..11b8a0624cd 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -1,6 +1,6 @@ -# Makefile.in generated automatically by automake 1.4-p5 from Makefile.am +# Makefile.in generated automatically by automake 1.4 from Makefile.am -# Copyright (C) 1994, 1995-8, 1999, 2001 Free Software Foundation, Inc. +# Copyright (C) 1994, 1995-8, 1999 Free Software Foundation, Inc. # This Makefile.in is free software; the Free Software Foundation # gives unlimited permission to copy and/or distribute it, # with or without modifications, as long as this notice is preserved. @@ -141,51 +141,282 @@ glibcpp_builddir = @glibcpp_builddir@ bits_srcdir = ${glibcpp_srcdir}/include/bits bits_builddir = ./bits -bits_headers = ${bits_srcdir}/basic_ios.h ${bits_srcdir}/basic_ios.tcc ${bits_srcdir}/basic_string.h ${bits_srcdir}/basic_string.tcc ${bits_srcdir}/boost_concept_check.h ${bits_srcdir}/char_traits.h ${bits_srcdir}/codecvt.h ${bits_srcdir}/concept_check.h ${bits_srcdir}/cpp_type_traits.h ${bits_srcdir}/fpos.h ${bits_srcdir}/fstream.tcc ${bits_srcdir}/functexcept.h ${bits_srcdir}/generic_shadow.h ${bits_srcdir}/gslice.h ${bits_srcdir}/gslice_array.h ${bits_srcdir}/indirect_array.h ${bits_srcdir}/ios_base.h ${bits_srcdir}/istream.tcc ${bits_srcdir}/locale_facets.h ${bits_srcdir}/locale_facets.tcc ${bits_srcdir}/localefwd.h ${bits_srcdir}/mask_array.h ${bits_srcdir}/ostream.tcc ${bits_srcdir}/pthread_allocimpl.h ${bits_srcdir}/stream_iterator.h ${bits_srcdir}/streambuf_iterator.h ${bits_srcdir}/slice.h ${bits_srcdir}/slice_array.h ${bits_srcdir}/sstream.tcc ${bits_srcdir}/stl_algo.h ${bits_srcdir}/stl_algobase.h ${bits_srcdir}/stl_alloc.h ${bits_srcdir}/stl_bvector.h ${bits_srcdir}/stl_construct.h ${bits_srcdir}/stl_deque.h ${bits_srcdir}/stl_function.h ${bits_srcdir}/stl_heap.h ${bits_srcdir}/stl_iterator.h ${bits_srcdir}/stl_iterator_base_funcs.h ${bits_srcdir}/stl_iterator_base_types.h ${bits_srcdir}/stl_list.h ${bits_srcdir}/stl_map.h ${bits_srcdir}/stl_multimap.h ${bits_srcdir}/stl_multiset.h ${bits_srcdir}/stl_numeric.h ${bits_srcdir}/stl_pair.h ${bits_srcdir}/stl_pthread_alloc.h ${bits_srcdir}/stl_queue.h ${bits_srcdir}/stl_raw_storage_iter.h ${bits_srcdir}/stl_relops.h ${bits_srcdir}/stl_set.h ${bits_srcdir}/stl_stack.h ${bits_srcdir}/stl_tempbuf.h ${bits_srcdir}/stl_threads.h ${bits_srcdir}/stl_tree.h ${bits_srcdir}/stl_uninitialized.h ${bits_srcdir}/stl_vector.h ${bits_srcdir}/streambuf.tcc ${bits_srcdir}/stringfwd.h ${bits_srcdir}/type_traits.h ${bits_srcdir}/valarray_array.h ${bits_srcdir}/valarray_array.tcc ${bits_srcdir}/valarray_meta.h +bits_headers = \ + ${bits_srcdir}/basic_ios.h \ + ${bits_srcdir}/basic_ios.tcc \ + ${bits_srcdir}/basic_string.h \ + ${bits_srcdir}/basic_string.tcc \ + ${bits_srcdir}/boost_concept_check.h \ + ${bits_srcdir}/char_traits.h \ + ${bits_srcdir}/codecvt.h \ + ${bits_srcdir}/concept_check.h \ + ${bits_srcdir}/cpp_type_traits.h \ + ${bits_srcdir}/deque.tcc \ + ${bits_srcdir}/fpos.h \ + ${bits_srcdir}/fstream.tcc \ + ${bits_srcdir}/functexcept.h \ + ${bits_srcdir}/generic_shadow.h \ + ${bits_srcdir}/gslice.h \ + ${bits_srcdir}/gslice_array.h \ + ${bits_srcdir}/indirect_array.h \ + ${bits_srcdir}/ios_base.h \ + ${bits_srcdir}/istream.tcc \ + ${bits_srcdir}/list.tcc \ + ${bits_srcdir}/locale_facets.h \ + ${bits_srcdir}/locale_facets.tcc \ + ${bits_srcdir}/localefwd.h \ + ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/ostream.tcc \ + ${bits_srcdir}/pthread_allocimpl.h \ + ${bits_srcdir}/stream_iterator.h \ + ${bits_srcdir}/streambuf_iterator.h \ + ${bits_srcdir}/slice.h \ + ${bits_srcdir}/slice_array.h \ + ${bits_srcdir}/sstream.tcc \ + ${bits_srcdir}/stl_algo.h \ + ${bits_srcdir}/stl_algobase.h \ + ${bits_srcdir}/stl_alloc.h \ + ${bits_srcdir}/stl_bvector.h \ + ${bits_srcdir}/stl_construct.h \ + ${bits_srcdir}/stl_deque.h \ + ${bits_srcdir}/stl_function.h \ + ${bits_srcdir}/stl_heap.h \ + ${bits_srcdir}/stl_iterator.h \ + ${bits_srcdir}/stl_iterator_base_funcs.h \ + ${bits_srcdir}/stl_iterator_base_types.h \ + ${bits_srcdir}/stl_list.h \ + ${bits_srcdir}/stl_map.h \ + ${bits_srcdir}/stl_multimap.h \ + ${bits_srcdir}/stl_multiset.h \ + ${bits_srcdir}/stl_numeric.h \ + ${bits_srcdir}/stl_pair.h \ + ${bits_srcdir}/stl_pthread_alloc.h \ + ${bits_srcdir}/stl_queue.h \ + ${bits_srcdir}/stl_raw_storage_iter.h \ + ${bits_srcdir}/stl_relops.h \ + ${bits_srcdir}/stl_set.h \ + ${bits_srcdir}/stl_stack.h \ + ${bits_srcdir}/stl_tempbuf.h \ + ${bits_srcdir}/stl_threads.h \ + ${bits_srcdir}/stl_tree.h \ + ${bits_srcdir}/stl_uninitialized.h \ + ${bits_srcdir}/stl_vector.h \ + ${bits_srcdir}/streambuf.tcc \ + ${bits_srcdir}/stringfwd.h \ + ${bits_srcdir}/type_traits.h \ + ${bits_srcdir}/valarray_array.h \ + ${bits_srcdir}/valarray_array.tcc \ + ${bits_srcdir}/valarray_meta.h \ + ${bits_srcdir}/vector.tcc backward_srcdir = ${glibcpp_srcdir}/include/backward backward_builddir = ./backward -backward_headers = ${backward_srcdir}/complex.h ${backward_srcdir}/iomanip.h ${backward_srcdir}/istream.h ${backward_srcdir}/ostream.h ${backward_srcdir}/stream.h ${backward_srcdir}/streambuf.h ${backward_srcdir}/algo.h ${backward_srcdir}/algobase.h ${backward_srcdir}/alloc.h ${backward_srcdir}/bvector.h ${backward_srcdir}/defalloc.h ${backward_srcdir}/deque.h ${backward_srcdir}/function.h ${backward_srcdir}/hash_map.h ${backward_srcdir}/hash_set.h ${backward_srcdir}/hashtable.h ${backward_srcdir}/heap.h ${backward_srcdir}/iostream.h ${backward_srcdir}/iterator.h ${backward_srcdir}/list.h ${backward_srcdir}/map.h ${backward_srcdir}/multimap.h ${backward_srcdir}/new.h ${backward_srcdir}/multiset.h ${backward_srcdir}/pair.h ${backward_srcdir}/queue.h ${backward_srcdir}/rope.h ${backward_srcdir}/set.h ${backward_srcdir}/slist.h ${backward_srcdir}/stack.h ${backward_srcdir}/tempbuf.h ${backward_srcdir}/tree.h ${backward_srcdir}/vector.h ${backward_srcdir}/fstream.h ${backward_srcdir}/strstream.h ${backward_srcdir}/strstream ${backward_srcdir}/backward_warning.h +backward_headers = \ + ${backward_srcdir}/complex.h \ + ${backward_srcdir}/iomanip.h \ + ${backward_srcdir}/istream.h \ + ${backward_srcdir}/ostream.h \ + ${backward_srcdir}/stream.h \ + ${backward_srcdir}/streambuf.h \ + ${backward_srcdir}/algo.h \ + ${backward_srcdir}/algobase.h \ + ${backward_srcdir}/alloc.h \ + ${backward_srcdir}/bvector.h \ + ${backward_srcdir}/defalloc.h \ + ${backward_srcdir}/deque.h \ + ${backward_srcdir}/function.h \ + ${backward_srcdir}/hash_map.h \ + ${backward_srcdir}/hash_set.h \ + ${backward_srcdir}/hashtable.h \ + ${backward_srcdir}/heap.h \ + ${backward_srcdir}/iostream.h \ + ${backward_srcdir}/iterator.h \ + ${backward_srcdir}/list.h \ + ${backward_srcdir}/map.h \ + ${backward_srcdir}/multimap.h \ + ${backward_srcdir}/new.h \ + ${backward_srcdir}/multiset.h \ + ${backward_srcdir}/pair.h \ + ${backward_srcdir}/queue.h \ + ${backward_srcdir}/rope.h \ + ${backward_srcdir}/set.h \ + ${backward_srcdir}/slist.h \ + ${backward_srcdir}/stack.h \ + ${backward_srcdir}/tempbuf.h \ + ${backward_srcdir}/tree.h \ + ${backward_srcdir}/vector.h \ + ${backward_srcdir}/fstream.h \ + ${backward_srcdir}/strstream.h \ + ${backward_srcdir}/strstream \ + ${backward_srcdir}/backward_warning.h ext_srcdir = ${glibcpp_srcdir}/include/ext ext_builddir = ./ext -ext_headers = ${ext_srcdir}/algorithm ${ext_srcdir}/enc_filebuf.h ${ext_srcdir}/stdio_filebuf.h ${ext_srcdir}/functional ${ext_srcdir}/hash_map ${ext_srcdir}/hash_set ${ext_srcdir}/iterator ${ext_srcdir}/memory ${ext_srcdir}/numeric ${ext_srcdir}/rb_tree ${ext_srcdir}/rope ${ext_srcdir}/ropeimpl.h ${ext_srcdir}/slist ${ext_srcdir}/stl_hash_fun.h ${ext_srcdir}/stl_hashtable.h ${ext_srcdir}/stl_rope.h +ext_headers = \ + ${ext_srcdir}/algorithm \ + ${ext_srcdir}/enc_filebuf.h \ + ${ext_srcdir}/stdio_filebuf.h \ + ${ext_srcdir}/functional \ + ${ext_srcdir}/hash_map \ + ${ext_srcdir}/hash_set \ + ${ext_srcdir}/iterator \ + ${ext_srcdir}/memory \ + ${ext_srcdir}/numeric \ + ${ext_srcdir}/rb_tree \ + ${ext_srcdir}/rope \ + ${ext_srcdir}/ropeimpl.h \ + ${ext_srcdir}/slist \ + ${ext_srcdir}/stl_hash_fun.h \ + ${ext_srcdir}/stl_hashtable.h \ + ${ext_srcdir}/stl_rope.h # This is the common subset of files that all three "C" header models use. c_base_srcdir = @C_INCLUDE_DIR@ c_base_builddir = . -c_base_headers = ${c_base_srcdir}/std_cassert.h ${c_base_srcdir}/std_cctype.h ${c_base_srcdir}/std_cerrno.h ${c_base_srcdir}/std_cfloat.h ${c_base_srcdir}/std_ciso646.h ${c_base_srcdir}/std_climits.h ${c_base_srcdir}/std_clocale.h ${c_base_srcdir}/std_cmath.h ${c_base_srcdir}/std_csetjmp.h ${c_base_srcdir}/std_csignal.h ${c_base_srcdir}/std_cstdarg.h ${c_base_srcdir}/std_cstddef.h ${c_base_srcdir}/std_cstdio.h ${c_base_srcdir}/std_cstdlib.h ${c_base_srcdir}/std_cstring.h ${c_base_srcdir}/std_ctime.h ${c_base_srcdir}/std_cwchar.h ${c_base_srcdir}/std_cwctype.h - -c_base_headers_rename = cassert cctype cerrno cfloat ciso646 climits clocale cmath csetjmp csignal cstdarg cstddef cstdio cstdlib cstring ctime cwchar cwctype - -@GLIBCPP_C_HEADERS_C_STD_TRUE@c_base_headers_extra = ${c_base_srcdir}/cmath.tcc +c_base_headers = \ + ${c_base_srcdir}/std_cassert.h \ + ${c_base_srcdir}/std_cctype.h \ + ${c_base_srcdir}/std_cerrno.h \ + ${c_base_srcdir}/std_cfloat.h \ + ${c_base_srcdir}/std_ciso646.h \ + ${c_base_srcdir}/std_climits.h \ + ${c_base_srcdir}/std_clocale.h \ + ${c_base_srcdir}/std_cmath.h \ + ${c_base_srcdir}/std_csetjmp.h \ + ${c_base_srcdir}/std_csignal.h \ + ${c_base_srcdir}/std_cstdarg.h \ + ${c_base_srcdir}/std_cstddef.h \ + ${c_base_srcdir}/std_cstdio.h \ + ${c_base_srcdir}/std_cstdlib.h \ + ${c_base_srcdir}/std_cstring.h \ + ${c_base_srcdir}/std_ctime.h \ + ${c_base_srcdir}/std_cwchar.h \ + ${c_base_srcdir}/std_cwctype.h + +c_base_headers_rename = \ + cassert \ + cctype \ + cerrno \ + cfloat \ + ciso646 \ + climits \ + clocale \ + cmath \ + csetjmp \ + csignal \ + cstdarg \ + cstddef \ + cstdio \ + cstdlib \ + cstring \ + ctime \ + cwchar \ + cwctype + +@GLIBCPP_C_HEADERS_C_STD_TRUE@c_base_headers_extra = @GLIBCPP_C_HEADERS_C_STD_TRUE@\ +@GLIBCPP_C_HEADERS_C_STD_TRUE@ ${c_base_srcdir}/cmath.tcc @GLIBCPP_C_HEADERS_C_STD_FALSE@c_base_headers_extra = std_srcdir = ${glibcpp_srcdir}/include/std std_builddir = . -std_headers = ${std_srcdir}/std_algorithm.h ${std_srcdir}/std_bitset.h ${std_srcdir}/std_complex.h ${std_srcdir}/std_deque.h ${std_srcdir}/std_fstream.h ${std_srcdir}/std_functional.h ${std_srcdir}/std_iomanip.h ${std_srcdir}/std_ios.h ${std_srcdir}/std_iosfwd.h ${std_srcdir}/std_iostream.h ${std_srcdir}/std_istream.h ${std_srcdir}/std_iterator.h ${std_srcdir}/std_limits.h ${std_srcdir}/std_list.h ${std_srcdir}/std_locale.h ${std_srcdir}/std_map.h ${std_srcdir}/std_memory.h ${std_srcdir}/std_numeric.h ${std_srcdir}/std_ostream.h ${std_srcdir}/std_queue.h ${std_srcdir}/std_set.h ${std_srcdir}/std_sstream.h ${std_srcdir}/std_stack.h ${std_srcdir}/std_stdexcept.h ${std_srcdir}/std_streambuf.h ${std_srcdir}/std_string.h ${std_srcdir}/std_utility.h ${std_srcdir}/std_valarray.h ${std_srcdir}/std_vector.h +std_headers = \ + ${std_srcdir}/std_algorithm.h \ + ${std_srcdir}/std_bitset.h \ + ${std_srcdir}/std_complex.h \ + ${std_srcdir}/std_deque.h \ + ${std_srcdir}/std_fstream.h \ + ${std_srcdir}/std_functional.h \ + ${std_srcdir}/std_iomanip.h \ + ${std_srcdir}/std_ios.h \ + ${std_srcdir}/std_iosfwd.h \ + ${std_srcdir}/std_iostream.h \ + ${std_srcdir}/std_istream.h \ + ${std_srcdir}/std_iterator.h \ + ${std_srcdir}/std_limits.h \ + ${std_srcdir}/std_list.h \ + ${std_srcdir}/std_locale.h \ + ${std_srcdir}/std_map.h \ + ${std_srcdir}/std_memory.h \ + ${std_srcdir}/std_numeric.h \ + ${std_srcdir}/std_ostream.h \ + ${std_srcdir}/std_queue.h \ + ${std_srcdir}/std_set.h \ + ${std_srcdir}/std_sstream.h \ + ${std_srcdir}/std_stack.h \ + ${std_srcdir}/std_stdexcept.h \ + ${std_srcdir}/std_streambuf.h \ + ${std_srcdir}/std_string.h \ + ${std_srcdir}/std_utility.h \ + ${std_srcdir}/std_valarray.h \ + ${std_srcdir}/std_vector.h # Renamed at build time. -std_headers_rename = algorithm bitset complex deque fstream functional iomanip ios iosfwd iostream istream iterator limits list locale map memory numeric ostream queue set sstream stack stdexcept streambuf string utility valarray vector +std_headers_rename = \ + algorithm \ + bitset \ + complex \ + deque \ + fstream \ + functional \ + iomanip \ + ios \ + iosfwd \ + iostream \ + istream \ + iterator \ + limits \ + list \ + locale \ + map \ + memory \ + numeric \ + ostream \ + queue \ + set \ + sstream \ + stack \ + stdexcept \ + streambuf \ + string \ + utility \ + valarray \ + vector target_srcdir = ${glibcpp_srcdir}/@OS_INC_SRCDIR@ target_builddir = ./${target_alias}/bits -target_headers = ${target_srcdir}/ctype_base.h ${target_srcdir}/ctype_inline.h ${target_srcdir}/ctype_noninline.h ${target_srcdir}/os_defines.h ${glibcpp_srcdir}/@ATOMICITY_INC_SRCDIR@/atomicity.h ${glibcpp_srcdir}/@CPU_LIMITS_INC_SRCDIR@/cpu_limits.h +target_headers = \ + ${target_srcdir}/ctype_base.h \ + ${target_srcdir}/ctype_inline.h \ + ${target_srcdir}/ctype_noninline.h \ + ${target_srcdir}/os_defines.h \ + ${glibcpp_srcdir}/@ATOMICITY_INC_SRCDIR@/atomicity.h \ + ${glibcpp_srcdir}/@CPU_LIMITS_INC_SRCDIR@/cpu_limits.h # These extra_target_headers files are all built with ad hoc naming rules. -extra_target_headers = ${target_builddir}/basic_file.h ${target_builddir}/c++config.h ${target_builddir}/c++io.h ${target_builddir}/c++locale.h ${target_builddir}/messages_members.h ${target_builddir}/codecvt_specializations.h +extra_target_headers = \ + ${target_builddir}/basic_file.h \ + ${target_builddir}/c++config.h \ + ${target_builddir}/c++io.h \ + ${target_builddir}/c++locale.h \ + ${target_builddir}/messages_members.h \ + ${target_builddir}/codecvt_specializations.h -thread_target_headers = ${target_builddir}/gthr.h ${target_builddir}/gthr-single.h ${target_builddir}/gthr-posix.h ${target_builddir}/gthr-default.h +thread_target_headers = \ + ${target_builddir}/gthr.h \ + ${target_builddir}/gthr-single.h \ + ${target_builddir}/gthr-posix.h \ + ${target_builddir}/gthr-default.h # List of all timestamp files. By keeping only one copy of this list, both # CLEANFILES and all-local are kept up-to-date. -allstamps = stamp-std stamp-bits stamp-c_base stamp-backward stamp-ext ${target_builddir}/stamp-target +allstamps = stamp-std stamp-bits stamp-c_base stamp-backward stamp-ext \ + ${target_builddir}/stamp-target # Target includes for threads @@ -208,7 +439,7 @@ DIST_COMMON = Makefile.am Makefile.in DISTFILES = $(DIST_COMMON) $(SOURCES) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST) -TAR = tar +TAR = gtar GZIP_ENV = --best all: all-redirect .SUFFIXES: diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc new file mode 100644 index 00000000000..37cc0155838 --- /dev/null +++ b/libstdc++-v3/include/bits/deque.tcc @@ -0,0 +1,784 @@ +// Deque implementation (out of line) -*- C++ -*- + +// Copyright (C) 2001, 2002 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +/* + * + * 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. + */ + +/** @file deque.tcc + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +#ifndef __GLIBCPP_INTERNAL_DEQUE_TCC +#define __GLIBCPP_INTERNAL_DEQUE_TCC + +// Since this entire file is within namespace std, there's no reason to +// waste two spaces along the left column. Thus the leading indentation is +// slightly violated from here on. +namespace std +{ + +template <typename _Tp, typename _Alloc> + deque<_Tp,_Alloc>& + deque<_Tp,_Alloc>:: + operator=(const deque& __x) + { + const size_type __len = size(); + if (&__x != this) + { + if (__len >= __x.size()) + erase(copy(__x.begin(), __x.end(), _M_start), _M_finish); + else + { + const_iterator __mid = __x.begin() + difference_type(__len); + copy(__x.begin(), __mid, _M_start); + insert(_M_finish, __mid, __x.end()); + } + } + return *this; + } + +template <typename _Tp, typename _Alloc> + typename deque<_Tp,_Alloc>::iterator + deque<_Tp,_Alloc>:: + insert(iterator position, const value_type& __x) + { + if (position._M_cur == _M_start._M_cur) + { + push_front(__x); + return _M_start; + } + else if (position._M_cur == _M_finish._M_cur) + { + push_back(__x); + iterator __tmp = _M_finish; + --__tmp; + return __tmp; + } + else + return _M_insert_aux(position, __x); + } + +template <typename _Tp, typename _Alloc> + typename deque<_Tp,_Alloc>::iterator + deque<_Tp,_Alloc>:: + erase(iterator __position) + { + iterator __next = __position; + ++__next; + size_type __index = __position - _M_start; + if (__index < (size() >> 1)) + { + copy_backward(_M_start, __position, __next); + pop_front(); + } + else + { + copy(__next, _M_finish, __position); + pop_back(); + } + return _M_start + __index; + } + +template <typename _Tp, typename _Alloc> + typename deque<_Tp,_Alloc>::iterator + deque<_Tp,_Alloc>:: + erase(iterator __first, iterator __last) + { + if (__first == _M_start && __last == _M_finish) + { + clear(); + return _M_finish; + } + else + { + difference_type __n = __last - __first; + difference_type __elems_before = __first - _M_start; + if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) + { + copy_backward(_M_start, __first, __last); + iterator __new_start = _M_start + __n; + _Destroy(_M_start, __new_start); + _M_destroy_nodes(_M_start._M_node, __new_start._M_node); + _M_start = __new_start; + } + else + { + copy(__last, _M_finish, __first); + iterator __new_finish = _M_finish - __n; + _Destroy(__new_finish, _M_finish); + _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1); + _M_finish = __new_finish; + } + return _M_start + __elems_before; + } + } + +template <typename _Tp, typename _Alloc> + void + deque<_Tp,_Alloc>:: + clear() + { + for (_Map_pointer __node = _M_start._M_node + 1; + __node < _M_finish._M_node; + ++__node) + { + _Destroy(*__node, *__node + _S_buffer_size()); + _M_deallocate_node(*__node); + } + + if (_M_start._M_node != _M_finish._M_node) + { + _Destroy(_M_start._M_cur, _M_start._M_last); + _Destroy(_M_finish._M_first, _M_finish._M_cur); + _M_deallocate_node(_M_finish._M_first); + } + else + _Destroy(_M_start._M_cur, _M_finish._M_cur); + + _M_finish = _M_start; + } + +template <typename _Tp, class _Alloc> + template <typename _InputIter> + void + deque<_Tp,_Alloc> + ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag) + { + iterator __cur = begin(); + for ( ; __first != __last && __cur != end(); ++__cur, ++__first) + *__cur = *__first; + if (__first == __last) + erase(__cur, end()); + else + insert(end(), __first, __last); + } + +template <typename _Tp, typename _Alloc> + void + deque<_Tp,_Alloc>:: + _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) + { + if (__pos._M_cur == _M_start._M_cur) + { + iterator __new_start = _M_reserve_elements_at_front(__n); + try + { + uninitialized_fill(__new_start, _M_start, __x); + _M_start = __new_start; + } + catch(...) + { + _M_destroy_nodes(__new_start._M_node, _M_start._M_node); + __throw_exception_again; + } + } + else if (__pos._M_cur == _M_finish._M_cur) + { + iterator __new_finish = _M_reserve_elements_at_back(__n); + try + { + uninitialized_fill(_M_finish, __new_finish, __x); + _M_finish = __new_finish; + } + catch(...) + { + _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); + __throw_exception_again; + } + } + else + _M_insert_aux(__pos, __n, __x); + } + +template <typename _Tp, typename _Alloc> + void + deque<_Tp,_Alloc>:: + _M_fill_initialize(const value_type& __value) + { + _Map_pointer __cur; + try + { + for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur) + uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value); + uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value); + } + catch(...) + { + _Destroy(_M_start, iterator(*__cur, __cur)); + __throw_exception_again; + } + } + +template <typename _Tp, typename _Alloc> + template <typename _InputIterator> + void + deque<_Tp,_Alloc>:: + _M_range_initialize(_InputIterator __first, _InputIterator __last, + input_iterator_tag) + { + _M_initialize_map(0); + try + { + for ( ; __first != __last; ++__first) + push_back(*__first); + } + catch(...) + { + clear(); + __throw_exception_again; + } + } + +template <typename _Tp, typename _Alloc> + template <typename _ForwardIterator> + void + deque<_Tp,_Alloc>:: + _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, + forward_iterator_tag) + { + size_type __n = distance(__first, __last); + _M_initialize_map(__n); + + _Map_pointer __cur_node; + try + { + for (__cur_node = _M_start._M_node; + __cur_node < _M_finish._M_node; + ++__cur_node) + { + _ForwardIterator __mid = __first; + advance(__mid, _S_buffer_size()); + uninitialized_copy(__first, __mid, *__cur_node); + __first = __mid; + } + uninitialized_copy(__first, __last, _M_finish._M_first); + } + catch(...) + { + _Destroy(_M_start, iterator(*__cur_node, __cur_node)); + __throw_exception_again; + } + } + +// Called only if _M_finish._M_cur == _M_finish._M_last - 1. +template <typename _Tp, typename _Alloc> + void + deque<_Tp,_Alloc>:: + _M_push_back_aux(const value_type& __t) + { + value_type __t_copy = __t; + _M_reserve_map_at_back(); + *(_M_finish._M_node + 1) = _M_allocate_node(); + try + { + _Construct(_M_finish._M_cur, __t_copy); + _M_finish._M_set_node(_M_finish._M_node + 1); + _M_finish._M_cur = _M_finish._M_first; + } + catch(...) + { + _M_deallocate_node(*(_M_finish._M_node + 1)); + __throw_exception_again; + } + } + +#ifdef _GLIBCPP_DEPRECATED +// Called only if _M_finish._M_cur == _M_finish._M_last - 1. +template <typename _Tp, typename _Alloc> + void + deque<_Tp,_Alloc>:: + _M_push_back_aux() + { + _M_reserve_map_at_back(); + *(_M_finish._M_node + 1) = _M_allocate_node(); + try + { + _Construct(_M_finish._M_cur); + _M_finish._M_set_node(_M_finish._M_node + 1); + _M_finish._M_cur = _M_finish._M_first; + } + catch(...) + { + _M_deallocate_node(*(_M_finish._M_node + 1)); + __throw_exception_again; + } + } +#endif + +// Called only if _M_start._M_cur == _M_start._M_first. +template <typename _Tp, typename _Alloc> + void + deque<_Tp,_Alloc>:: + _M_push_front_aux(const value_type& __t) + { + value_type __t_copy = __t; + _M_reserve_map_at_front(); + *(_M_start._M_node - 1) = _M_allocate_node(); + try + { + _M_start._M_set_node(_M_start._M_node - 1); + _M_start._M_cur = _M_start._M_last - 1; + _Construct(_M_start._M_cur, __t_copy); + } + catch(...) + { + ++_M_start; + _M_deallocate_node(*(_M_start._M_node - 1)); + __throw_exception_again; + } + } + +#ifdef _GLIBCPP_DEPRECATED +// Called only if _M_start._M_cur == _M_start._M_first. +template <typename _Tp, typename _Alloc> + void + deque<_Tp,_Alloc>:: + _M_push_front_aux() + { + _M_reserve_map_at_front(); + *(_M_start._M_node - 1) = _M_allocate_node(); + try + { + _M_start._M_set_node(_M_start._M_node - 1); + _M_start._M_cur = _M_start._M_last - 1; + _Construct(_M_start._M_cur); + } + catch(...) + { + ++_M_start; + _M_deallocate_node(*(_M_start._M_node - 1)); + __throw_exception_again; + } + } +#endif + +// Called only if _M_finish._M_cur == _M_finish._M_first. +template <typename _Tp, typename _Alloc> + void deque<_Tp,_Alloc>:: + _M_pop_back_aux() + { + _M_deallocate_node(_M_finish._M_first); + _M_finish._M_set_node(_M_finish._M_node - 1); + _M_finish._M_cur = _M_finish._M_last - 1; + _Destroy(_M_finish._M_cur); + } + +// Called only if _M_start._M_cur == _M_start._M_last - 1. Note that +// if the deque has at least one element (a precondition for this member +// function), and if _M_start._M_cur == _M_start._M_last, then the deque +// must have at least two nodes. +template <typename _Tp, typename _Alloc> + void deque<_Tp,_Alloc>:: + _M_pop_front_aux() + { + _Destroy(_M_start._M_cur); + _M_deallocate_node(_M_start._M_first); + _M_start._M_set_node(_M_start._M_node + 1); + _M_start._M_cur = _M_start._M_first; + } + +template <typename _Tp, typename _Alloc> + template <typename _InputIterator> + void + deque<_Tp,_Alloc>:: + _M_range_insert_aux(iterator __pos, + _InputIterator __first, _InputIterator __last, + input_iterator_tag) + { + copy(__first, __last, inserter(*this, __pos)); + } + +template <typename _Tp, typename _Alloc> + template <typename _ForwardIterator> + void + deque<_Tp,_Alloc>:: + _M_range_insert_aux(iterator __pos, + _ForwardIterator __first, _ForwardIterator __last, + forward_iterator_tag) + { + size_type __n = distance(__first, __last); + if (__pos._M_cur == _M_start._M_cur) + { + iterator __new_start = _M_reserve_elements_at_front(__n); + try + { + uninitialized_copy(__first, __last, __new_start); + _M_start = __new_start; + } + catch(...) + { + _M_destroy_nodes(__new_start._M_node, _M_start._M_node); + __throw_exception_again; + } + } + else if (__pos._M_cur == _M_finish._M_cur) + { + iterator __new_finish = _M_reserve_elements_at_back(__n); + try + { + uninitialized_copy(__first, __last, _M_finish); + _M_finish = __new_finish; + } + catch(...) + { + _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); + __throw_exception_again; + } + } + else + _M_insert_aux(__pos, __first, __last, __n); + } + +template <typename _Tp, typename _Alloc> + typename deque<_Tp, _Alloc>::iterator + deque<_Tp,_Alloc>:: + _M_insert_aux(iterator __pos, const value_type& __x) + { + difference_type __index = __pos - _M_start; + value_type __x_copy = __x; // XXX copy + if (static_cast<size_type>(__index) < size() / 2) + { + push_front(front()); + iterator __front1 = _M_start; + ++__front1; + iterator __front2 = __front1; + ++__front2; + __pos = _M_start + __index; + iterator __pos1 = __pos; + ++__pos1; + copy(__front2, __pos1, __front1); + } + else + { + push_back(back()); + iterator __back1 = _M_finish; + --__back1; + iterator __back2 = __back1; + --__back2; + __pos = _M_start + __index; + copy_backward(__pos, __back2, __back1); + } + *__pos = __x_copy; + return __pos; + } + +#ifdef _GLIBCPP_DEPRECATED +// Nothing seems to actually use this. According to the pattern followed by +// the rest of the SGI code, it would be called by the deprecated insert(pos) +// function, but that has been replaced. We'll take our time removing this +// anyhow; mark for 3.3. -pme +template <typename _Tp, typename _Alloc> + typename deque<_Tp,_Alloc>::iterator + deque<_Tp,_Alloc>:: + _M_insert_aux(iterator __pos) + { + difference_type __index = __pos - _M_start; + if (static_cast<size_type>(__index) < size() / 2) + { + push_front(front()); + iterator __front1 = _M_start; + ++__front1; + iterator __front2 = __front1; + ++__front2; + __pos = _M_start + __index; + iterator __pos1 = __pos; + ++__pos1; + copy(__front2, __pos1, __front1); + } + else + { + push_back(back()); + iterator __back1 = _M_finish; + --__back1; + iterator __back2 = __back1; + --__back2; + __pos = _M_start + __index; + copy_backward(__pos, __back2, __back1); + } + *__pos = value_type(); + return __pos; + } +#endif + +template <typename _Tp, typename _Alloc> + void + deque<_Tp,_Alloc>:: + _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) + { + const difference_type __elems_before = __pos - _M_start; + size_type __length = this->size(); + value_type __x_copy = __x; + if (__elems_before < difference_type(__length / 2)) + { + iterator __new_start = _M_reserve_elements_at_front(__n); + iterator __old_start = _M_start; + __pos = _M_start + __elems_before; + try + { + if (__elems_before >= difference_type(__n)) + { + iterator __start_n = _M_start + difference_type(__n); + uninitialized_copy(_M_start, __start_n, __new_start); + _M_start = __new_start; + copy(__start_n, __pos, __old_start); + fill(__pos - difference_type(__n), __pos, __x_copy); + } + else + { + __uninitialized_copy_fill(_M_start, __pos, __new_start, + _M_start, __x_copy); + _M_start = __new_start; + fill(__old_start, __pos, __x_copy); + } + } + catch(...) + { + _M_destroy_nodes(__new_start._M_node, _M_start._M_node); + __throw_exception_again; + } + } + else + { + iterator __new_finish = _M_reserve_elements_at_back(__n); + iterator __old_finish = _M_finish; + const difference_type __elems_after = + difference_type(__length) - __elems_before; + __pos = _M_finish - __elems_after; + try + { + if (__elems_after > difference_type(__n)) + { + iterator __finish_n = _M_finish - difference_type(__n); + uninitialized_copy(__finish_n, _M_finish, _M_finish); + _M_finish = __new_finish; + copy_backward(__pos, __finish_n, __old_finish); + fill(__pos, __pos + difference_type(__n), __x_copy); + } + else + { + __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n), + __x_copy, __pos, _M_finish); + _M_finish = __new_finish; + fill(__pos, __old_finish, __x_copy); + } + } + catch(...) + { + _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); + __throw_exception_again; + } + } + } + +template <typename _Tp, typename _Alloc> + template <typename _ForwardIterator> + void + deque<_Tp,_Alloc>:: + _M_insert_aux(iterator __pos, + _ForwardIterator __first, _ForwardIterator __last, + size_type __n) + { + const difference_type __elemsbefore = __pos - _M_start; + size_type __length = size(); + if (static_cast<size_type>(__elemsbefore) < __length / 2) + { + iterator __new_start = _M_reserve_elements_at_front(__n); + iterator __old_start = _M_start; + __pos = _M_start + __elemsbefore; + try + { + if (__elemsbefore >= difference_type(__n)) + { + iterator __start_n = _M_start + difference_type(__n); + uninitialized_copy(_M_start, __start_n, __new_start); + _M_start = __new_start; + copy(__start_n, __pos, __old_start); + copy(__first, __last, __pos - difference_type(__n)); + } + else + { + _ForwardIterator __mid = __first; + advance(__mid, difference_type(__n) - __elemsbefore); + __uninitialized_copy_copy(_M_start, __pos, __first, __mid, + __new_start); + _M_start = __new_start; + copy(__mid, __last, __old_start); + } + } + catch(...) + { + _M_destroy_nodes(__new_start._M_node, _M_start._M_node); + __throw_exception_again; + } + } + else + { + iterator __new_finish = _M_reserve_elements_at_back(__n); + iterator __old_finish = _M_finish; + const difference_type __elemsafter = + difference_type(__length) - __elemsbefore; + __pos = _M_finish - __elemsafter; + try + { + if (__elemsafter > difference_type(__n)) + { + iterator __finish_n = _M_finish - difference_type(__n); + uninitialized_copy(__finish_n, _M_finish, _M_finish); + _M_finish = __new_finish; + copy_backward(__pos, __finish_n, __old_finish); + copy(__first, __last, __pos); + } + else + { + _ForwardIterator __mid = __first; + advance(__mid, __elemsafter); + __uninitialized_copy_copy(__mid, __last, __pos, + _M_finish, _M_finish); + _M_finish = __new_finish; + copy(__first, __mid, __pos); + } + } + catch(...) + { + _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); + __throw_exception_again; + } + } + } + +template <typename _Tp, typename _Alloc> + void + deque<_Tp,_Alloc>:: + _M_new_elements_at_front(size_type __new_elems) + { + size_type __new_nodes + = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); + _M_reserve_map_at_front(__new_nodes); + size_type __i; + try + { + for (__i = 1; __i <= __new_nodes; ++__i) + *(_M_start._M_node - __i) = _M_allocate_node(); + } + catch(...) + { + for (size_type __j = 1; __j < __i; ++__j) + _M_deallocate_node(*(_M_start._M_node - __j)); + __throw_exception_again; + } + } + +template <typename _Tp, typename _Alloc> + void + deque<_Tp,_Alloc>:: + _M_new_elements_at_back(size_type __new_elems) + { + size_type __new_nodes + = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); + _M_reserve_map_at_back(__new_nodes); + size_type __i; + try + { + for (__i = 1; __i <= __new_nodes; ++__i) + *(_M_finish._M_node + __i) = _M_allocate_node(); + } + catch(...) + { + for (size_type __j = 1; __j < __i; ++__j) + _M_deallocate_node(*(_M_finish._M_node + __j)); + __throw_exception_again; + } + } + +template <typename _Tp, typename _Alloc> + void + deque<_Tp,_Alloc>:: + _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) + { + size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1; + size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; + + _Map_pointer __new_nstart; + if (_M_map_size > 2 * __new_num_nodes) + { + __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 + + (__add_at_front ? __nodes_to_add : 0); + if (__new_nstart < _M_start._M_node) + copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); + else + copy_backward(_M_start._M_node, _M_finish._M_node + 1, + __new_nstart + __old_num_nodes); + } + else + { + size_type __new_map_size = + _M_map_size + max(_M_map_size, __nodes_to_add) + 2; + + _Map_pointer __new_map = _M_allocate_map(__new_map_size); + __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 + + (__add_at_front ? __nodes_to_add : 0); + copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); + _M_deallocate_map(_M_map, _M_map_size); + + _M_map = __new_map; + _M_map_size = __new_map_size; + } + + _M_start._M_set_node(__new_nstart); + _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); + } + +} // namespace std + +#endif /* __GLIBCPP_INTERNAL_DEQUE_TCC */ + diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc new file mode 100644 index 00000000000..7fbfa9dd375 --- /dev/null +++ b/libstdc++-v3/include/bits/list.tcc @@ -0,0 +1,374 @@ +// List implementation (out of line) -*- C++ -*- + +// Copyright (C) 2001, 2002 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +/* + * + * 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) 1996,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. + */ + +/** @file list.tcc + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +#ifndef __GLIBCPP_INTERNAL_LIST_TCC +#define __GLIBCPP_INTERNAL_LIST_TCC + +// Since this entire file is within namespace std, there's no reason to +// waste two spaces along the left column. Thus the leading indentation is +// slightly violated from here on. +namespace std +{ + +template<typename _Tp, typename _Alloc> + void + _List_base<_Tp,_Alloc>:: + __clear() + { + typedef _List_node<_Tp> _Node; + _Node* __cur = static_cast<_Node*>(_M_node->_M_next); + while (__cur != _M_node) + { + _Node* __tmp = __cur; + __cur = static_cast<_Node*>(__cur->_M_next); + _Destroy(&__tmp->_M_data); + _M_put_node(__tmp); + } + _M_node->_M_next = _M_node; + _M_node->_M_prev = _M_node; + } + +template<typename _Tp, typename _Alloc> + typename list<_Tp,_Alloc>::iterator + list<_Tp,_Alloc>:: + insert(iterator __position, const value_type& __x) + { + _Node* __tmp = _M_create_node(__x); + __tmp->_M_next = __position._M_node; + __tmp->_M_prev = __position._M_node->_M_prev; + __position._M_node->_M_prev->_M_next = __tmp; + __position._M_node->_M_prev = __tmp; + return __tmp; + } + +template<typename _Tp, typename _Alloc> + typename list<_Tp,_Alloc>::iterator + list<_Tp,_Alloc>:: + erase(iterator __position) + { + _List_node_base* __next_node = __position._M_node->_M_next; + _List_node_base* __prev_node = __position._M_node->_M_prev; + _Node* __n = static_cast<_Node*>(__position._M_node); + __prev_node->_M_next = __next_node; + __next_node->_M_prev = __prev_node; + _Destroy(&__n->_M_data); + _M_put_node(__n); + return iterator(static_cast<_Node*>(__next_node)); + } + +template<typename _Tp, typename _Alloc> + void + list<_Tp,_Alloc>:: + resize(size_type __new_size, const value_type& __x) + { + iterator __i = begin(); + size_type __len = 0; + for ( ; __i != end() && __len < __new_size; ++__i, ++__len) + ; + if (__len == __new_size) + erase(__i, end()); + else // __i == end() + insert(end(), __new_size - __len, __x); + } + +template<typename _Tp, typename _Alloc> + list<_Tp,_Alloc>& + list<_Tp,_Alloc>:: + operator=(const list& __x) + { + if (this != &__x) + { + iterator __first1 = begin(); + iterator __last1 = end(); + const_iterator __first2 = __x.begin(); + const_iterator __last2 = __x.end(); + while (__first1 != __last1 && __first2 != __last2) + *__first1++ = *__first2++; + if (__first2 == __last2) + erase(__first1, __last1); + else + insert(__last1, __first2, __last2); + } + return *this; + } + +template<typename _Tp, typename _Alloc> + void + list<_Tp,_Alloc>:: + _M_fill_assign(size_type __n, const value_type& __val) + { + iterator __i = begin(); + for ( ; __i != end() && __n > 0; ++__i, --__n) + *__i = __val; + if (__n > 0) + insert(end(), __n, __val); + else + erase(__i, end()); + } + +template<typename _Tp, typename _Alloc> + template <typename _InputIter> + void + list<_Tp,_Alloc>:: + _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type) + { + iterator __first1 = begin(); + iterator __last1 = end(); + for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + *__first1 = *__first2; + if (__first2 == __last2) + erase(__first1, __last1); + else + insert(__last1, __first2, __last2); + } + +template<typename _Tp, typename _Alloc> + void + list<_Tp,_Alloc>:: + remove(const value_type& __value) + { + iterator __first = begin(); + iterator __last = end(); + while (__first != __last) + { + iterator __next = __first; + ++__next; + if (*__first == __value) + erase(__first); + __first = __next; + } + } + +template<typename _Tp, typename _Alloc> + void + list<_Tp,_Alloc>:: + unique() + { + iterator __first = begin(); + iterator __last = end(); + if (__first == __last) return; + iterator __next = __first; + while (++__next != __last) + { + if (*__first == *__next) + erase(__next); + else + __first = __next; + __next = __first; + } + } + +template<typename _Tp, typename _Alloc> + void + list<_Tp,_Alloc>:: + merge(list& __x) + { + iterator __first1 = begin(); + iterator __last1 = end(); + iterator __first2 = __x.begin(); + iterator __last2 = __x.end(); + while (__first1 != __last1 && __first2 != __last2) + if (*__first2 < *__first1) + { + iterator __next = __first2; + _M_transfer(__first1, __first2, ++__next); + __first2 = __next; + } + else + ++__first1; + if (__first2 != __last2) + _M_transfer(__last1, __first2, __last2); + } + +// FIXME put this somewhere else +inline void +__List_base_reverse(_List_node_base* __p) +{ + _List_node_base* __tmp = __p; + do { + std::swap(__tmp->_M_next, __tmp->_M_prev); + __tmp = __tmp->_M_prev; // Old next node is now prev. + } while (__tmp != __p); +} + +template<typename _Tp, typename _Alloc> + void + list<_Tp,_Alloc>:: + sort() + { + // Do nothing if the list has length 0 or 1. + if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) + { + list __carry; + list __counter[64]; + int __fill = 0; + while (!empty()) + { + __carry.splice(__carry.begin(), *this, begin()); + int __i = 0; + while(__i < __fill && !__counter[__i].empty()) + { + __counter[__i].merge(__carry); + __carry.swap(__counter[__i++]); + } + __carry.swap(__counter[__i]); + if (__i == __fill) ++__fill; + } + + for (int __i = 1; __i < __fill; ++__i) + __counter[__i].merge(__counter[__i-1]); + swap(__counter[__fill-1]); + } + } + +template<typename _Tp, typename _Alloc> + template <typename _Predicate> + void + list<_Tp,_Alloc>:: + remove_if(_Predicate __pred) + { + iterator __first = begin(); + iterator __last = end(); + while (__first != __last) + { + iterator __next = __first; + ++__next; + if (__pred(*__first)) erase(__first); + __first = __next; + } + } + +template<typename _Tp, typename _Alloc> + template <typename _BinaryPredicate> + void + list<_Tp,_Alloc>:: + unique(_BinaryPredicate __binary_pred) + { + iterator __first = begin(); + iterator __last = end(); + if (__first == __last) return; + iterator __next = __first; + while (++__next != __last) + { + if (__binary_pred(*__first, *__next)) + erase(__next); + else + __first = __next; + __next = __first; + } + } + +template<typename _Tp, typename _Alloc> + template <typename _StrictWeakOrdering> + void + list<_Tp,_Alloc>:: + merge(list& __x, _StrictWeakOrdering __comp) + { + iterator __first1 = begin(); + iterator __last1 = end(); + iterator __first2 = __x.begin(); + iterator __last2 = __x.end(); + while (__first1 != __last1 && __first2 != __last2) + if (__comp(*__first2, *__first1)) + { + iterator __next = __first2; + _M_transfer(__first1, __first2, ++__next); + __first2 = __next; + } + else + ++__first1; + if (__first2 != __last2) _M_transfer(__last1, __first2, __last2); + } + +template<typename _Tp, typename _Alloc> + template <typename _StrictWeakOrdering> + void + list<_Tp,_Alloc>:: + sort(_StrictWeakOrdering __comp) + { + // Do nothing if the list has length 0 or 1. + if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) + { + list __carry; + list __counter[64]; + int __fill = 0; + while (!empty()) + { + __carry.splice(__carry.begin(), *this, begin()); + int __i = 0; + while(__i < __fill && !__counter[__i].empty()) + { + __counter[__i].merge(__carry, __comp); + __carry.swap(__counter[__i++]); + } + __carry.swap(__counter[__i]); + if (__i == __fill) ++__fill; + } + + for (int __i = 1; __i < __fill; ++__i) + __counter[__i].merge(__counter[__i-1], __comp); + swap(__counter[__fill-1]); + } + } + +} // namespace std + +#endif /* __GLIBCPP_INTERNAL_LIST_TCC */ + diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h index 7e0c9f9fb4d..1eedc6a1abf 100644 --- a/libstdc++-v3/include/bits/stl_deque.h +++ b/libstdc++-v3/include/bits/stl_deque.h @@ -100,7 +100,7 @@ __deque_buf_size(size_t __size) * All the functions are op overloads except for _M_set_node. * @endif */ -template <class _Tp, class _Ref, class _Ptr> +template <typename _Tp, typename _Ref, typename _Ptr> struct _Deque_iterator { typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; @@ -214,7 +214,7 @@ template <class _Tp, class _Ref, class _Ptr> // Note: we also provide overloads whose operands are of the same type in // order to avoid ambiguous overload resolution when std::rel_ops operators // are in scope (for additional details, see libstdc++/3628) -template <class _Tp, class _Ref, class _Ptr> +template <typename _Tp, typename _Ref, typename _Ptr> inline bool operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) @@ -222,7 +222,8 @@ operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, return __x._M_cur == __y._M_cur; } -template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> +template <typename _Tp, typename _RefL, typename _PtrL, + typename _RefR, typename _PtrR> inline bool operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) @@ -230,7 +231,7 @@ operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, return __x._M_cur == __y._M_cur; } -template <class _Tp, class _Ref, class _Ptr> +template <typename _Tp, typename _Ref, typename _Ptr> inline bool operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) @@ -238,7 +239,8 @@ operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, return !(__x == __y); } -template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> +template <typename _Tp, typename _RefL, typename _PtrL, + typename _RefR, typename _PtrR> inline bool operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) @@ -246,7 +248,7 @@ operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, return !(__x == __y); } -template <class _Tp, class _Ref, class _Ptr> +template <typename _Tp, typename _Ref, typename _Ptr> inline bool operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) @@ -255,7 +257,8 @@ operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node); } -template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> +template <typename _Tp, typename _RefL, typename _PtrL, + typename _RefR, typename _PtrR> inline bool operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) @@ -264,7 +267,7 @@ operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node); } -template <class _Tp, class _Ref, class _Ptr> +template <typename _Tp, typename _Ref, typename _Ptr> inline bool operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) @@ -272,7 +275,8 @@ operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, return __y < __x; } -template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> +template <typename _Tp, typename _RefL, typename _PtrL, + typename _RefR, typename _PtrR> inline bool operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) @@ -280,7 +284,7 @@ operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, return __y < __x; } -template <class _Tp, class _Ref, class _Ptr> +template <typename _Tp, typename _Ref, typename _Ptr> inline bool operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) @@ -288,7 +292,8 @@ operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, return !(__y < __x); } -template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> +template <typename _Tp, typename _RefL, typename _PtrL, + typename _RefR, typename _PtrR> inline bool operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) @@ -296,7 +301,7 @@ operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, return !(__y < __x); } -template <class _Tp, class _Ref, class _Ptr> +template <typename _Tp, typename _Ref, typename _Ptr> inline bool operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) @@ -304,7 +309,8 @@ operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, return !(__x < __y); } -template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> +template <typename _Tp, typename _RefL, typename _PtrL, + typename _RefR, typename _PtrR> inline bool operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) @@ -312,7 +318,7 @@ operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, return !(__x < __y); } -template <class _Tp, class _Ref, class _Ptr> +template <typename _Tp, typename _Ref, typename _Ptr> inline _Deque_iterator<_Tp, _Ref, _Ptr> operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x) { @@ -332,7 +338,7 @@ operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x) * instanceless allocators. * @endif */ -template <class _Tp, class _Alloc, bool __is_static> +template <typename _Tp, typename _Alloc, bool __is_static> class _Deque_alloc_base { public: @@ -375,7 +381,7 @@ protected: }; /// @if maint Specialization for instanceless allocators. @endif -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> class _Deque_alloc_base<_Tp, _Alloc, true> { public: @@ -425,7 +431,7 @@ protected: * (Deque handles that itself.) Only/All memory management is performed here. * @endif */ -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> class _Deque_base : public _Deque_alloc_base<_Tp,_Alloc, _Alloc_traits<_Tp, _Alloc>::_S_instanceless> @@ -456,7 +462,7 @@ protected: }; -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> _Deque_base<_Tp,_Alloc>::~_Deque_base() { if (_M_map) @@ -475,7 +481,7 @@ _Deque_base<_Tp,_Alloc>::~_Deque_base() * The initial underlying memory layout is a bit complicated... * @endif */ -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) { @@ -509,7 +515,7 @@ _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) __num_elements % __deque_buf_size(sizeof(_Tp)); } -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish) { _Tp** __cur; @@ -525,7 +531,7 @@ void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish) } } -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> void _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) { @@ -616,7 +622,7 @@ _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) * use other standard algorithms as well. * @endif */ -template <class _Tp, class _Alloc = allocator<_Tp> > +template <typename _Tp, typename _Alloc = allocator<_Tp> > class deque : protected _Deque_base<_Tp, _Alloc> { // concept requirements @@ -720,7 +726,7 @@ public: * input iterators are used, then this will do at most 2N calls to the * copy constructor, and logN memory reallocations. */ - template<class _InputIterator> + template<typename _InputIterator> deque(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) @@ -745,20 +751,7 @@ public: * allocator object is not copied. */ deque& - operator=(const deque& __x) // FIXME move to tcc - { - const size_type __len = size(); - if (&__x != this) { - if (__len >= __x.size()) - erase(copy(__x.begin(), __x.end(), _M_start), _M_finish); - else { - const_iterator __mid = __x.begin() + difference_type(__len); - copy(__x.begin(), __mid, _M_start); - insert(_M_finish, __mid, __x.end()); - } - } - return *this; - } + operator=(const deque& __x); /** * @brief Assigns a given value to a %deque. @@ -785,7 +778,7 @@ public: * resulting %deque's size is the same as the number of elements assigned. * Old data may be lost. */ - template<class _InputIterator> + template<typename _InputIterator> void assign(_InputIterator __first, _InputIterator __last) { @@ -1138,22 +1131,7 @@ public: * location. */ iterator - insert(iterator position, const value_type& __x) - { - if (position._M_cur == _M_start._M_cur) { - push_front(__x); - return _M_start; - } - else if (position._M_cur == _M_finish._M_cur) { - push_back(__x); - iterator __tmp = _M_finish; - --__tmp; - return __tmp; - } - else { - return _M_insert_aux(position, __x); - } - } + insert(iterator position, const value_type& __x); #ifdef _GLIBCPP_DEPRECATED /** @@ -1197,7 +1175,7 @@ public: * into the %deque before the location specified by @a pos. This is * known as "range insert." */ - template<class _InputIterator> + template<typename _InputIterator> void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { @@ -1220,21 +1198,7 @@ public: * the pointer is the user's responsibilty. */ iterator - erase(iterator __position) - { - iterator __next = __position; - ++__next; - size_type __index = __position - _M_start; - if (__index < (size() >> 1)) { - copy_backward(_M_start, __position, __next); - pop_front(); - } - else { - copy(__next, _M_finish, __position); - pop_back(); - } - return _M_start + __index; - } + erase(iterator __position); /** * @brief Remove a range of elements. @@ -1284,7 +1248,7 @@ protected: // Internal constructor functions follow. // called by the range constructor to implement [23.1.1]/9 - template<class _Integer> + template<typename _Integer> void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { @@ -1293,7 +1257,7 @@ protected: } // called by the range constructor to implement [23.1.1]/9 - template<class _InputIter> + template<typename _InputIter> void _M_initialize_dispatch(_InputIter __first, _InputIter __last, __false_type) { @@ -1303,16 +1267,29 @@ protected: } // called by the second initialize_dispatch above - template <class _InputIterator> + /** @{ + * @if maint + * @brief Fills the deque with whatever is in [first,last). + * @param first An input iterator. + * @param last An input iterator. + * @return Nothing. + * + * If the iterators are actually forward iterators (or better), then the + * memory layout can be done all at once. Else we move forward using + * push_back on each value from the iterator. + * @endif + */ + template <typename _InputIterator> void _M_range_initialize(_InputIterator __first, _InputIterator __last, input_iterator_tag); // called by the second initialize_dispatch above - template <class _ForwardIterator> + template <typename _ForwardIterator> void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag); + /** @} */ /** * @if maint @@ -1334,7 +1311,7 @@ protected: // assignment work for the range versions. // called by the range assign to implement [23.1.1]/9 - template<class _Integer> + template<typename _Integer> void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) { @@ -1343,7 +1320,7 @@ protected: } // called by the range assign to implement [23.1.1]/9 - template<class _InputIter> + template<typename _InputIter> void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type) { @@ -1353,13 +1330,13 @@ protected: } // called by the second assign_dispatch above - template <class _InputIterator> + template <typename _InputIterator> void _M_assign_aux(_InputIterator __first, _InputIterator __last, input_iterator_tag); // called by the second assign_dispatch above - template <class _ForwardIterator> + template <typename _ForwardIterator> void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag) @@ -1413,7 +1390,7 @@ protected: // insertion work when all shortcuts fail. // called by the range insert to implement [23.1.1]/9 - template<class _Integer> + template<typename _Integer> void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type) { @@ -1422,7 +1399,7 @@ protected: } // called by the range insert to implement [23.1.1]/9 - template<class _InputIterator> + template<typename _InputIterator> void _M_insert_dispatch(iterator __pos, _InputIterator __first, _InputIterator __last, @@ -1434,13 +1411,13 @@ protected: } // called by the second insert_dispatch above - template <class _InputIterator> + template <typename _InputIterator> void _M_range_insert_aux(iterator __pos, _InputIterator __first, _InputIterator __last, input_iterator_tag); // called by the second insert_dispatch above - template <class _ForwardIterator> + template <typename _ForwardIterator> void _M_range_insert_aux(iterator __pos, _ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag); @@ -1460,7 +1437,7 @@ protected: _M_insert_aux(iterator __pos, size_type __n, const value_type& __x); // called by range_insert_aux for forward iterators - template <class _ForwardIterator> + template <typename _ForwardIterator> void _M_insert_aux(iterator __pos, _ForwardIterator __first, _ForwardIterator __last, @@ -1531,590 +1508,6 @@ protected: }; -template <class _Tp, class _Alloc> -template <class _InputIter> -void deque<_Tp, _Alloc> - ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag) -{ - iterator __cur = begin(); - for ( ; __first != __last && __cur != end(); ++__cur, ++__first) - *__cur = *__first; - if (__first == __last) - erase(__cur, end()); - else - insert(end(), __first, __last); -} - -template <class _Tp, class _Alloc> -void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos, - size_type __n, const value_type& __x) -{ - if (__pos._M_cur == _M_start._M_cur) - { - iterator __new_start = _M_reserve_elements_at_front(__n); - try { - uninitialized_fill(__new_start, _M_start, __x); - _M_start = __new_start; - } - catch(...) - { - _M_destroy_nodes(__new_start._M_node, _M_start._M_node); - __throw_exception_again; - } - } - else if (__pos._M_cur == _M_finish._M_cur) - { - iterator __new_finish = _M_reserve_elements_at_back(__n); - try { - uninitialized_fill(_M_finish, __new_finish, __x); - _M_finish = __new_finish; - } - catch(...) - { - _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); - __throw_exception_again; - } - } - else - _M_insert_aux(__pos, __n, __x); -} - -template <class _Tp, class _Alloc> -typename deque<_Tp,_Alloc>::iterator -deque<_Tp,_Alloc>::erase(iterator __first, iterator __last) -{ - if (__first == _M_start && __last == _M_finish) { - clear(); - return _M_finish; - } - else { - difference_type __n = __last - __first; - difference_type __elems_before = __first - _M_start; - if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) { - copy_backward(_M_start, __first, __last); - iterator __new_start = _M_start + __n; - _Destroy(_M_start, __new_start); - _M_destroy_nodes(_M_start._M_node, __new_start._M_node); - _M_start = __new_start; - } - else { - copy(__last, _M_finish, __first); - iterator __new_finish = _M_finish - __n; - _Destroy(__new_finish, _M_finish); - _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1); - _M_finish = __new_finish; - } - return _M_start + __elems_before; - } -} - -template <class _Tp, class _Alloc> -void deque<_Tp,_Alloc>::clear() -{ - for (_Map_pointer __node = _M_start._M_node + 1; - __node < _M_finish._M_node; - ++__node) { - _Destroy(*__node, *__node + _S_buffer_size()); - _M_deallocate_node(*__node); - } - - if (_M_start._M_node != _M_finish._M_node) { - _Destroy(_M_start._M_cur, _M_start._M_last); - _Destroy(_M_finish._M_first, _M_finish._M_cur); - _M_deallocate_node(_M_finish._M_first); - } - else - _Destroy(_M_start._M_cur, _M_finish._M_cur); - - _M_finish = _M_start; -} - -template <class _Tp, class _Alloc> -void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value) -{ - _Map_pointer __cur; - try { - for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur) - uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value); - uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value); - } - catch(...) - { - _Destroy(_M_start, iterator(*__cur, __cur)); - __throw_exception_again; - } -} - -/** @{ - * @if maint - * @brief Fills the deque with whatever is in [first,last). - * @param first An input iterator. - * @param last An input iterator. - * @return Nothing. - * - * If the iterators are actually forward iterators (or better), then the - * memory layout can be done all at once. Else we move forward using - * push_back on each value from the iterator. - * @endif -*/ -template <class _Tp, class _Alloc> template <class _InputIterator> -void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first, - _InputIterator __last, - input_iterator_tag) -{ - _M_initialize_map(0); - try { - for ( ; __first != __last; ++__first) - push_back(*__first); - } - catch(...) - { - clear(); - __throw_exception_again; - } -} - -template <class _Tp, class _Alloc> template <class _ForwardIterator> -void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first, - _ForwardIterator __last, - forward_iterator_tag) -{ - size_type __n = distance(__first, __last); - _M_initialize_map(__n); - - _Map_pointer __cur_node; - try { - for (__cur_node = _M_start._M_node; - __cur_node < _M_finish._M_node; - ++__cur_node) { - _ForwardIterator __mid = __first; - advance(__mid, _S_buffer_size()); - uninitialized_copy(__first, __mid, *__cur_node); - __first = __mid; - } - uninitialized_copy(__first, __last, _M_finish._M_first); - } - catch(...) - { - _Destroy(_M_start, iterator(*__cur_node, __cur_node)); - __throw_exception_again; - } -} -/** @} */ - -// Called only if _M_finish._M_cur == _M_finish._M_last - 1. -template <class _Tp, class _Alloc> -void -deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t) -{ - value_type __t_copy = __t; - _M_reserve_map_at_back(); - *(_M_finish._M_node + 1) = _M_allocate_node(); - try { - _Construct(_M_finish._M_cur, __t_copy); - _M_finish._M_set_node(_M_finish._M_node + 1); - _M_finish._M_cur = _M_finish._M_first; - } - catch(...) - { - _M_deallocate_node(*(_M_finish._M_node + 1)); - __throw_exception_again; - } -} - -#ifdef _GLIBCPP_DEPRECATED -// Called only if _M_finish._M_cur == _M_finish._M_last - 1. -template <class _Tp, class _Alloc> -void -deque<_Tp,_Alloc>::_M_push_back_aux() -{ - _M_reserve_map_at_back(); - *(_M_finish._M_node + 1) = _M_allocate_node(); - try { - _Construct(_M_finish._M_cur); - _M_finish._M_set_node(_M_finish._M_node + 1); - _M_finish._M_cur = _M_finish._M_first; - } - catch(...) - { - _M_deallocate_node(*(_M_finish._M_node + 1)); - __throw_exception_again; - } -} -#endif - -// Called only if _M_start._M_cur == _M_start._M_first. -template <class _Tp, class _Alloc> -void -deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t) -{ - value_type __t_copy = __t; - _M_reserve_map_at_front(); - *(_M_start._M_node - 1) = _M_allocate_node(); - try { - _M_start._M_set_node(_M_start._M_node - 1); - _M_start._M_cur = _M_start._M_last - 1; - _Construct(_M_start._M_cur, __t_copy); - } - catch(...) - { - ++_M_start; - _M_deallocate_node(*(_M_start._M_node - 1)); - __throw_exception_again; - } -} - -#ifdef _GLIBCPP_DEPRECATED -// Called only if _M_start._M_cur == _M_start._M_first. -template <class _Tp, class _Alloc> -void -deque<_Tp,_Alloc>::_M_push_front_aux() -{ - _M_reserve_map_at_front(); - *(_M_start._M_node - 1) = _M_allocate_node(); - try { - _M_start._M_set_node(_M_start._M_node - 1); - _M_start._M_cur = _M_start._M_last - 1; - _Construct(_M_start._M_cur); - } - catch(...) - { - ++_M_start; - _M_deallocate_node(*(_M_start._M_node - 1)); - __throw_exception_again; - } -} -#endif - -// Called only if _M_finish._M_cur == _M_finish._M_first. -template <class _Tp, class _Alloc> -void deque<_Tp,_Alloc>::_M_pop_back_aux() -{ - _M_deallocate_node(_M_finish._M_first); - _M_finish._M_set_node(_M_finish._M_node - 1); - _M_finish._M_cur = _M_finish._M_last - 1; - _Destroy(_M_finish._M_cur); -} - -// Called only if _M_start._M_cur == _M_start._M_last - 1. Note that -// if the deque has at least one element (a precondition for this member -// function), and if _M_start._M_cur == _M_start._M_last, then the deque -// must have at least two nodes. -template <class _Tp, class _Alloc> -void deque<_Tp,_Alloc>::_M_pop_front_aux() -{ - _Destroy(_M_start._M_cur); - _M_deallocate_node(_M_start._M_first); - _M_start._M_set_node(_M_start._M_node + 1); - _M_start._M_cur = _M_start._M_first; -} - -template <class _Tp, class _Alloc> template <class _InputIterator> -void deque<_Tp,_Alloc>::_M_range_insert_aux(iterator __pos, - _InputIterator __first, _InputIterator __last, - input_iterator_tag) -{ - copy(__first, __last, inserter(*this, __pos)); -} - -template <class _Tp, class _Alloc> template <class _ForwardIterator> -void -deque<_Tp,_Alloc>::_M_range_insert_aux(iterator __pos, - _ForwardIterator __first, _ForwardIterator __last, - forward_iterator_tag) { - size_type __n = distance(__first, __last); - if (__pos._M_cur == _M_start._M_cur) { - iterator __new_start = _M_reserve_elements_at_front(__n); - try { - uninitialized_copy(__first, __last, __new_start); - _M_start = __new_start; - } - catch(...) - { - _M_destroy_nodes(__new_start._M_node, _M_start._M_node); - __throw_exception_again; - } - } - else if (__pos._M_cur == _M_finish._M_cur) { - iterator __new_finish = _M_reserve_elements_at_back(__n); - try { - uninitialized_copy(__first, __last, _M_finish); - _M_finish = __new_finish; - } - catch(...) - { - _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); - __throw_exception_again; - } - } - else - _M_insert_aux(__pos, __first, __last, __n); -} - -template <class _Tp, class _Alloc> -typename deque<_Tp, _Alloc>::iterator -deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x) -{ - difference_type __index = __pos - _M_start; - value_type __x_copy = __x; // XXX copy - if (static_cast<size_type>(__index) < size() / 2) { - push_front(front()); - iterator __front1 = _M_start; - ++__front1; - iterator __front2 = __front1; - ++__front2; - __pos = _M_start + __index; - iterator __pos1 = __pos; - ++__pos1; - copy(__front2, __pos1, __front1); - } - else { - push_back(back()); - iterator __back1 = _M_finish; - --__back1; - iterator __back2 = __back1; - --__back2; - __pos = _M_start + __index; - copy_backward(__pos, __back2, __back1); - } - *__pos = __x_copy; - return __pos; -} - -#ifdef _GLIBCPP_DEPRECATED -// Nothing seems to actually use this. According to the pattern followed by -// the rest of the SGI code, it would be called by the deprecated insert(pos) -// function, but that has been replaced. We'll take our time removing this -// anyhow; mark for 3.3. -pme -template <class _Tp, class _Alloc> -typename deque<_Tp,_Alloc>::iterator -deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos) -{ - difference_type __index = __pos - _M_start; - if (static_cast<size_type>(__index) < size() / 2) { - push_front(front()); - iterator __front1 = _M_start; - ++__front1; - iterator __front2 = __front1; - ++__front2; - __pos = _M_start + __index; - iterator __pos1 = __pos; - ++__pos1; - copy(__front2, __pos1, __front1); - } - else { - push_back(back()); - iterator __back1 = _M_finish; - --__back1; - iterator __back2 = __back1; - --__back2; - __pos = _M_start + __index; - copy_backward(__pos, __back2, __back1); - } - *__pos = value_type(); - return __pos; -} -#endif - -template <class _Tp, class _Alloc> -void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, - size_type __n, - const value_type& __x) -{ - const difference_type __elems_before = __pos - _M_start; - size_type __length = this->size(); - value_type __x_copy = __x; - if (__elems_before < difference_type(__length / 2)) { - iterator __new_start = _M_reserve_elements_at_front(__n); - iterator __old_start = _M_start; - __pos = _M_start + __elems_before; - try { - if (__elems_before >= difference_type(__n)) { - iterator __start_n = _M_start + difference_type(__n); - uninitialized_copy(_M_start, __start_n, __new_start); - _M_start = __new_start; - copy(__start_n, __pos, __old_start); - fill(__pos - difference_type(__n), __pos, __x_copy); - } - else { - __uninitialized_copy_fill(_M_start, __pos, __new_start, - _M_start, __x_copy); - _M_start = __new_start; - fill(__old_start, __pos, __x_copy); - } - } - catch(...) - { - _M_destroy_nodes(__new_start._M_node, _M_start._M_node); - __throw_exception_again; - } - } - else { - iterator __new_finish = _M_reserve_elements_at_back(__n); - iterator __old_finish = _M_finish; - const difference_type __elems_after = - difference_type(__length) - __elems_before; - __pos = _M_finish - __elems_after; - try { - if (__elems_after > difference_type(__n)) { - iterator __finish_n = _M_finish - difference_type(__n); - uninitialized_copy(__finish_n, _M_finish, _M_finish); - _M_finish = __new_finish; - copy_backward(__pos, __finish_n, __old_finish); - fill(__pos, __pos + difference_type(__n), __x_copy); - } - else { - __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n), - __x_copy, __pos, _M_finish); - _M_finish = __new_finish; - fill(__pos, __old_finish, __x_copy); - } - } - catch(...) - { - _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); - __throw_exception_again; - } - } -} - -template <class _Tp, class _Alloc> template <class _ForwardIterator> -void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, - _ForwardIterator __first, - _ForwardIterator __last, - size_type __n) -{ - const difference_type __elemsbefore = __pos - _M_start; - size_type __length = size(); - if (static_cast<size_type>(__elemsbefore) < __length / 2) { - iterator __new_start = _M_reserve_elements_at_front(__n); - iterator __old_start = _M_start; - __pos = _M_start + __elemsbefore; - try { - if (__elemsbefore >= difference_type(__n)) { - iterator __start_n = _M_start + difference_type(__n); - uninitialized_copy(_M_start, __start_n, __new_start); - _M_start = __new_start; - copy(__start_n, __pos, __old_start); - copy(__first, __last, __pos - difference_type(__n)); - } - else { - _ForwardIterator __mid = __first; - advance(__mid, difference_type(__n) - __elemsbefore); - __uninitialized_copy_copy(_M_start, __pos, __first, __mid, - __new_start); - _M_start = __new_start; - copy(__mid, __last, __old_start); - } - } - catch(...) - { - _M_destroy_nodes(__new_start._M_node, _M_start._M_node); - __throw_exception_again; - } - } - else { - iterator __new_finish = _M_reserve_elements_at_back(__n); - iterator __old_finish = _M_finish; - const difference_type __elemsafter = - difference_type(__length) - __elemsbefore; - __pos = _M_finish - __elemsafter; - try { - if (__elemsafter > difference_type(__n)) { - iterator __finish_n = _M_finish - difference_type(__n); - uninitialized_copy(__finish_n, _M_finish, _M_finish); - _M_finish = __new_finish; - copy_backward(__pos, __finish_n, __old_finish); - copy(__first, __last, __pos); - } - else { - _ForwardIterator __mid = __first; - advance(__mid, __elemsafter); - __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish); - _M_finish = __new_finish; - copy(__first, __mid, __pos); - } - } - catch(...) - { - _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); - __throw_exception_again; - } - } -} - -template <class _Tp, class _Alloc> -void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) -{ - size_type __new_nodes - = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); - _M_reserve_map_at_front(__new_nodes); - size_type __i; - try { - for (__i = 1; __i <= __new_nodes; ++__i) - *(_M_start._M_node - __i) = _M_allocate_node(); - } - catch(...) { - for (size_type __j = 1; __j < __i; ++__j) - _M_deallocate_node(*(_M_start._M_node - __j)); - __throw_exception_again; - } -} - -template <class _Tp, class _Alloc> -void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) -{ - size_type __new_nodes - = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); - _M_reserve_map_at_back(__new_nodes); - size_type __i; - try { - for (__i = 1; __i <= __new_nodes; ++__i) - *(_M_finish._M_node + __i) = _M_allocate_node(); - } - catch(...) { - for (size_type __j = 1; __j < __i; ++__j) - _M_deallocate_node(*(_M_finish._M_node + __j)); - __throw_exception_again; - } -} - -template <class _Tp, class _Alloc> -void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add, - bool __add_at_front) -{ - size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1; - size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; - - _Map_pointer __new_nstart; - if (_M_map_size > 2 * __new_num_nodes) { - __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 - + (__add_at_front ? __nodes_to_add : 0); - if (__new_nstart < _M_start._M_node) - copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); - else - copy_backward(_M_start._M_node, _M_finish._M_node + 1, - __new_nstart + __old_num_nodes); - } - else { - size_type __new_map_size = - _M_map_size + max(_M_map_size, __nodes_to_add) + 2; - - _Map_pointer __new_map = _M_allocate_map(__new_map_size); - __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 - + (__add_at_front ? __nodes_to_add : 0); - copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); - _M_deallocate_map(_M_map, _M_map_size); - - _M_map = __new_map; - _M_map_size = __new_map_size; - } - - _M_start._M_set_node(__new_nstart); - _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); -} - - /** * @brief Deque equality comparison. * @param x A %deque. @@ -2125,7 +1518,7 @@ void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add, * deques. Deques are considered equivalent if their sizes are equal, * and if corresponding elements compare equal. */ -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator==(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y) { @@ -2144,7 +1537,7 @@ inline bool operator==(const deque<_Tp, _Alloc>& __x, * * See std::lexographical_compare() for how the determination is made. */ -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator<(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y) { @@ -2153,35 +1546,35 @@ inline bool operator<(const deque<_Tp, _Alloc>& __x, } /// Based on operator== -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator!=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y) { return !(__x == __y); } /// Based on operator< -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y) { return __y < __x; } /// Based on operator< -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator<=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y) { return !(__y < __x); } /// Based on operator< -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator>=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y) { return !(__x < __y); } /// See std::deque::swap(). -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) { __x.swap(__y); diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index 26f7ff35982..75931cb0934 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -796,15 +796,7 @@ public: * time, and does not invalidate iterators and references. */ iterator - insert(iterator __position, const value_type& __x) - { - _Node* __tmp = _M_create_node(__x); - __tmp->_M_next = __position._M_node; - __tmp->_M_prev = __position._M_node->_M_prev; - __position._M_node->_M_prev->_M_next = __tmp; - __position._M_node->_M_prev = __tmp; - return __tmp; - } + insert(iterator __position, const value_type& __x); #ifdef _GLIBCPP_DEPRECATED /** @@ -880,17 +872,7 @@ public: * the pointer is the user's responsibilty. */ iterator - erase(iterator __position) - { - _List_node_base* __next_node = __position._M_node->_M_next; - _List_node_base* __prev_node = __position._M_node->_M_prev; - _Node* __n = static_cast<_Node*>(__position._M_node); - __prev_node->_M_next = __next_node; - __next_node->_M_prev = __prev_node; - _Destroy(&__n->_M_data); - _M_put_node(__n); - return iterator(static_cast<_Node*>(__next_node)); - } + erase(iterator __position); /** * @brief Remove a range of elements. @@ -911,7 +893,12 @@ public: * way. Managing the pointer is the user's responsibilty. */ iterator - erase(iterator __first, iterator __last); + erase(iterator __first, iterator __last) + { + while (__first != __last) + erase(__first++); + return __last; + } /** * @brief Swaps data with another %list. @@ -1010,7 +997,7 @@ public: * @doctodo */ void - reverse(); + reverse() { __List_base_reverse(this->_M_node); } /** * @doctodo @@ -1064,12 +1051,20 @@ protected: void _M_insert_dispatch(iterator __pos, _InputIterator __first, _InputIterator __last, - __false_type); + __false_type) + { + for ( ; __first != __last; ++__first) + insert(__pos, *__first); + } // Called by insert(p,n,x), and the range insert when it turns out to be // the same thing. void - _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); + _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) + { + for ( ; __n > 0; --__n) + insert(__pos, __x); + } // Moves the elements from [first,last) before position. @@ -1168,281 +1163,6 @@ template<typename _Tp, typename _Alloc> swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) { __x.swap(__y); } - -template<typename _Tp, typename _Alloc> - void _List_base<_Tp,_Alloc>:: - __clear() - { - _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next); - while (__cur != _M_node) { - _List_node<_Tp>* __tmp = __cur; - __cur = static_cast<_List_node<_Tp>*>(__cur->_M_next); - _Destroy(&__tmp->_M_data); - _M_put_node(__tmp); - } - _M_node->_M_next = _M_node; - _M_node->_M_prev = _M_node; - } - -template<typename _Tp, typename _Alloc> - template <typename _InputIter> - void list<_Tp, _Alloc>:: - _M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last, - __false_type) - { - for ( ; __first != __last; ++__first) - insert(__position, *__first); - - } - -template<typename _Tp, typename _Alloc> - void list<_Tp, _Alloc>:: - _M_fill_insert(iterator __position, size_type __n, const _Tp& __x) - { - for ( ; __n > 0; --__n) - insert(__position, __x); - } - -template<typename _Tp, typename _Alloc> - typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>:: - erase(iterator __first, iterator __last) - { - while (__first != __last) - erase(__first++); - return __last; - } - -template<typename _Tp, typename _Alloc> - void list<_Tp, _Alloc>:: - resize(size_type __new_size, const _Tp& __x) - { - iterator __i = begin(); - size_type __len = 0; - for ( ; __i != end() && __len < __new_size; ++__i, ++__len) - ; - if (__len == __new_size) - erase(__i, end()); - else // __i == end() - insert(end(), __new_size - __len, __x); - } - -template<typename _Tp, typename _Alloc> - list<_Tp, _Alloc>& list<_Tp, _Alloc>:: - operator=(const list<_Tp, _Alloc>& __x) - { - if (this != &__x) { - iterator __first1 = begin(); - iterator __last1 = end(); - const_iterator __first2 = __x.begin(); - const_iterator __last2 = __x.end(); - while (__first1 != __last1 && __first2 != __last2) - *__first1++ = *__first2++; - if (__first2 == __last2) - erase(__first1, __last1); - else - insert(__last1, __first2, __last2); - } - return *this; - } - -template<typename _Tp, typename _Alloc> - void list<_Tp, _Alloc>:: - _M_fill_assign(size_type __n, const _Tp& __val) { - iterator __i = begin(); - for ( ; __i != end() && __n > 0; ++__i, --__n) - *__i = __val; - if (__n > 0) - insert(end(), __n, __val); - else - erase(__i, end()); - } - -template<typename _Tp, typename _Alloc> - template <typename _InputIter> - void list<_Tp, _Alloc>:: - _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type) - { - iterator __first1 = begin(); - iterator __last1 = end(); - for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) - *__first1 = *__first2; - if (__first2 == __last2) - erase(__first1, __last1); - else - insert(__last1, __first2, __last2); - } - -template<typename _Tp, typename _Alloc> - void list<_Tp, _Alloc>:: - remove(const _Tp& __value) - { - iterator __first = begin(); - iterator __last = end(); - while (__first != __last) { - iterator __next = __first; - ++__next; - if (*__first == __value) erase(__first); - __first = __next; - } - } - -template<typename _Tp, typename _Alloc> - void list<_Tp, _Alloc>:: - unique() - { - iterator __first = begin(); - iterator __last = end(); - if (__first == __last) return; - iterator __next = __first; - while (++__next != __last) { - if (*__first == *__next) - erase(__next); - else - __first = __next; - __next = __first; - } - } - -template<typename _Tp, typename _Alloc> - void list<_Tp, _Alloc>:: - merge(list<_Tp, _Alloc>& __x) - { - iterator __first1 = begin(); - iterator __last1 = end(); - iterator __first2 = __x.begin(); - iterator __last2 = __x.end(); - while (__first1 != __last1 && __first2 != __last2) - if (*__first2 < *__first1) { - iterator __next = __first2; - _M_transfer(__first1, __first2, ++__next); - __first2 = __next; - } - else - ++__first1; - if (__first2 != __last2) _M_transfer(__last1, __first2, __last2); - } - -inline void -__List_base_reverse(_List_node_base* __p) -{ - _List_node_base* __tmp = __p; - do { - std::swap(__tmp->_M_next, __tmp->_M_prev); - __tmp = __tmp->_M_prev; // Old next node is now prev. - } while (__tmp != __p); -} - -template<typename _Tp, typename _Alloc> -inline void list<_Tp, _Alloc>:: -reverse() -{ __List_base_reverse(this->_M_node); } - -template<typename _Tp, typename _Alloc> - void list<_Tp, _Alloc>:: - sort() - { - // Do nothing if the list has length 0 or 1. - if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { - list<_Tp, _Alloc> __carry; - list<_Tp, _Alloc> __counter[64]; - int __fill = 0; - while (!empty()) { - __carry.splice(__carry.begin(), *this, begin()); - int __i = 0; - while(__i < __fill && !__counter[__i].empty()) { - __counter[__i].merge(__carry); - __carry.swap(__counter[__i++]); - } - __carry.swap(__counter[__i]); - if (__i == __fill) ++__fill; - } - - for (int __i = 1; __i < __fill; ++__i) - __counter[__i].merge(__counter[__i-1]); - swap(__counter[__fill-1]); - } - } - -template<typename _Tp, typename _Alloc> - template <typename _Predicate> - void list<_Tp, _Alloc>:: - remove_if(_Predicate __pred) - { - iterator __first = begin(); - iterator __last = end(); - while (__first != __last) { - iterator __next = __first; - ++__next; - if (__pred(*__first)) erase(__first); - __first = __next; - } - } - -template<typename _Tp, typename _Alloc> - template <typename _BinaryPredicate> - void list<_Tp, _Alloc>:: - unique(_BinaryPredicate __binary_pred) - { - iterator __first = begin(); - iterator __last = end(); - if (__first == __last) return; - iterator __next = __first; - while (++__next != __last) { - if (__binary_pred(*__first, *__next)) - erase(__next); - else - __first = __next; - __next = __first; - } - } - -template<typename _Tp, typename _Alloc> - template <typename _StrictWeakOrdering> - void list<_Tp, _Alloc>:: - merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp) - { - iterator __first1 = begin(); - iterator __last1 = end(); - iterator __first2 = __x.begin(); - iterator __last2 = __x.end(); - while (__first1 != __last1 && __first2 != __last2) - if (__comp(*__first2, *__first1)) { - iterator __next = __first2; - _M_transfer(__first1, __first2, ++__next); - __first2 = __next; - } - else - ++__first1; - if (__first2 != __last2) _M_transfer(__last1, __first2, __last2); - } - -template<typename _Tp, typename _Alloc> - template <typename _StrictWeakOrdering> - void list<_Tp, _Alloc>:: - sort(_StrictWeakOrdering __comp) - { - // Do nothing if the list has length 0 or 1. - if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { - list<_Tp, _Alloc> __carry; - list<_Tp, _Alloc> __counter[64]; - int __fill = 0; - while (!empty()) { - __carry.splice(__carry.begin(), *this, begin()); - int __i = 0; - while(__i < __fill && !__counter[__i].empty()) { - __counter[__i].merge(__carry, __comp); - __carry.swap(__counter[__i++]); - } - __carry.swap(__counter[__i]); - if (__i == __fill) ++__fill; - } - - for (int __i = 1; __i < __fill; ++__i) - __counter[__i].merge(__counter[__i-1], __comp); - swap(__counter[__fill-1]); - } - } - } // namespace std #endif /* __GLIBCPP_INTERNAL_LIST_H */ diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h index c9c24337420..a948d5f8f87 100644 --- a/libstdc++-v3/include/bits/stl_vector.h +++ b/libstdc++-v3/include/bits/stl_vector.h @@ -77,7 +77,7 @@ namespace std * See bits/stl_deque.h's _Deque_alloc_base for an explanation. * @endif */ -template <class _Tp, class _Allocator, bool _IsStatic> +template <typename _Tp, typename _Allocator, bool _IsStatic> class _Vector_alloc_base { public: @@ -106,7 +106,7 @@ protected: }; /// @if maint Specialization for instanceless allocators. @endif -template <class _Tp, class _Allocator> +template <typename _Tp, typename _Allocator> class _Vector_alloc_base<_Tp, _Allocator, true> { public: @@ -140,7 +140,7 @@ protected: * See bits/stl_deque.h's _Deque_base for an explanation. * @endif */ -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> struct _Vector_base : public _Vector_alloc_base<_Tp, _Alloc, _Alloc_traits<_Tp, _Alloc>::_S_instanceless> @@ -183,7 +183,7 @@ public: * and saves the user from worrying about memory and size allocation. * Subscripting ( @c [] ) access is also provided as with C-style arrays. */ -template <class _Tp, class _Alloc = allocator<_Tp> > +template <typename _Tp, typename _Alloc = allocator<_Tp> > class vector : protected _Vector_base<_Tp, _Alloc> { // concept requirements @@ -280,7 +280,7 @@ public: * input iterators are used, then this will do at most 2N calls to the * copy constructor, and logN memory reallocations. */ - template <class _InputIterator> + template <typename _InputIterator> vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) @@ -333,7 +333,7 @@ public: * resulting %vector's size is the same as the number of elements assigned. * Old data may be lost. */ - template<class _InputIterator> + template<typename _InputIterator> void assign(_InputIterator __first, _InputIterator __last) { @@ -475,19 +475,7 @@ public: * reallocation of memory and copying of %vector data. */ void - reserve(size_type __n) // FIXME should be out of class - { - if (capacity() < __n) - { - const size_type __old_size = size(); - pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish); - _Destroy(_M_start, _M_finish); - _M_deallocate(_M_start, _M_end_of_storage - _M_start); - _M_start = __tmp; - _M_finish = __tmp + __old_size; - _M_end_of_storage = _M_start + __n; - } - } + reserve(size_type __n); // element access /** @@ -593,7 +581,8 @@ public: void push_back(const value_type& __x) { - if (_M_finish != _M_end_of_storage) { + if (_M_finish != _M_end_of_storage) + { _Construct(_M_finish, __x); ++_M_finish; } @@ -628,18 +617,7 @@ public: * it is frequently used the user should consider using std::list. */ iterator - insert(iterator __position, const value_type& __x) - { - size_type __n = __position - begin(); - if (_M_finish != _M_end_of_storage && __position == end()) - { - _Construct(_M_finish, __x); - ++_M_finish; - } - else - _M_insert_aux(__position, __x); - return begin() + __n; - } + insert(iterator __position, const value_type& __x); #ifdef _GLIBCPP_DEPRECATED /** @@ -690,7 +668,7 @@ public: * Note that this kind of operation could be expensive for a %vector and if * it is frequently used the user should consider using std::list. */ - template<class _InputIterator> + template<typename _InputIterator> void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { @@ -714,14 +692,7 @@ public: * the pointer is the user's responsibilty. */ iterator - erase(iterator __position) - { - if (__position + 1 != end()) - copy(__position + 1, end(), __position); - --_M_finish; - _Destroy(_M_finish); - return __position; - } + erase(iterator __position); /** * @brief Remove a range of elements. @@ -740,13 +711,7 @@ public: * way. Managing the pointer is the user's responsibilty. */ iterator - erase(iterator __first, iterator __last) - { - iterator __i(copy(__last, end(), __first)); - _Destroy(__i, end()); - _M_finish = _M_finish - (__last - __first); - return __first; - } + erase(iterator __first, iterator __last); /** * @brief Swaps data with another %vector. @@ -781,7 +746,7 @@ protected: * obtain @a n bytes of memory, and then copies [first,last) into it. * @endif */ - template <class _ForwardIterator> + template <typename _ForwardIterator> pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last) @@ -803,7 +768,7 @@ protected: // Internal constructor functions follow. // called by the range constructor to implement [23.1.1]/9 - template<class _Integer> + template<typename _Integer> void _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) { @@ -813,7 +778,7 @@ protected: } // called by the range constructor to implement [23.1.1]/9 - template<class _InputIter> + template<typename _InputIter> void _M_initialize_dispatch(_InputIter __first, _InputIter __last, __false_type) { @@ -823,7 +788,7 @@ protected: } // called by the second initialize_dispatch above - template <class _InputIterator> + template <typename _InputIterator> void _M_range_initialize(_InputIterator __first, _InputIterator __last, input_iterator_tag) @@ -833,7 +798,7 @@ protected: } // called by the second initialize_dispatch above - template <class _ForwardIterator> + template <typename _ForwardIterator> void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag) { @@ -848,7 +813,7 @@ protected: // assignment work for the range versions. // called by the range assign to implement [23.1.1]/9 - template<class _Integer> + template<typename _Integer> void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) { @@ -857,7 +822,7 @@ protected: } // called by the range assign to implement [23.1.1]/9 - template<class _InputIter> + template<typename _InputIter> void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type) { @@ -867,13 +832,13 @@ protected: } // called by the second assign_dispatch above - template <class _InputIterator> + template <typename _InputIterator> void _M_assign_aux(_InputIterator __first, _InputIterator __last, input_iterator_tag); // called by the second assign_dispatch above - template <class _ForwardIterator> + template <typename _ForwardIterator> void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag); @@ -887,7 +852,7 @@ protected: // Internal insert functions follow. // called by the range insert to implement [23.1.1]/9 - template<class _Integer> + template<typename _Integer> void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, __true_type) @@ -897,7 +862,7 @@ protected: } // called by the range insert to implement [23.1.1]/9 - template<class _InputIterator> + template<typename _InputIterator> void _M_insert_dispatch(iterator __pos, _InputIterator __first, _InputIterator __last, __false_type) @@ -908,14 +873,14 @@ protected: } // called by the second insert_dispatch above - template <class _InputIterator> + template <typename _InputIterator> void _M_range_insert(iterator __pos, _InputIterator __first, _InputIterator __last, input_iterator_tag); // called by the second insert_dispatch above - template <class _ForwardIterator> + template <typename _ForwardIterator> void _M_range_insert(iterator __pos, _ForwardIterator __first, _ForwardIterator __last, @@ -947,7 +912,7 @@ protected: * vectors. Vectors are considered equivalent if their sizes are equal, * and if corresponding elements compare equal. */ -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { @@ -966,7 +931,7 @@ template <class _Tp, class _Alloc> * * See std::lexographical_compare() for how the determination is made. */ -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { @@ -975,316 +940,40 @@ template <class _Tp, class _Alloc> } /// Based on operator== -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { return !(__x == __y); } /// Based on operator< -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { return __y < __x; } /// Based on operator< -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { return !(__y < __x); } /// Based on operator< -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline bool operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { return !(__x < __y); } /// See std::vector::swap(). -template <class _Tp, class _Alloc> +template <typename _Tp, typename _Alloc> inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) { __x.swap(__y); } - -template <class _Tp, class _Alloc> -vector<_Tp,_Alloc>& -vector<_Tp,_Alloc>::operator=(const vector<_Tp,_Alloc>& __x) -{ - if (&__x != this) { - const size_type __xlen = __x.size(); - if (__xlen > capacity()) { - pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end()); - _Destroy(_M_start, _M_finish); - _M_deallocate(_M_start, _M_end_of_storage - _M_start); - _M_start = __tmp; - _M_end_of_storage = _M_start + __xlen; - } - else if (size() >= __xlen) { - iterator __i(copy(__x.begin(), __x.end(), begin())); - _Destroy(__i, end()); - } - else { - copy(__x.begin(), __x.begin() + size(), _M_start); - uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish); - } - _M_finish = _M_start + __xlen; - } - return *this; -} - -template <class _Tp, class _Alloc> -void -vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type& __val) -{ - if (__n > capacity()) { - vector __tmp(__n, __val, get_allocator()); - __tmp.swap(*this); - } - else if (__n > size()) { - fill(begin(), end(), __val); - _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val); - } - else - erase(fill_n(begin(), __n, __val), end()); -} - -template <class _Tp, class _Alloc> template <class _InputIter> -void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last, - input_iterator_tag) { - iterator __cur(begin()); - for ( ; __first != __last && __cur != end(); ++__cur, ++__first) - *__cur = *__first; - if (__first == __last) - erase(__cur, end()); - else - insert(end(), __first, __last); -} - -template <class _Tp, class _Alloc> template <class _ForwardIter> -void -vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last, - forward_iterator_tag) { - size_type __len = distance(__first, __last); - - if (__len > capacity()) { - pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); - _Destroy(_M_start, _M_finish); - _M_deallocate(_M_start, _M_end_of_storage - _M_start); - _M_start = __tmp; - _M_end_of_storage = _M_finish = _M_start + __len; - } - else if (size() >= __len) { - iterator __new_finish(copy(__first, __last, _M_start)); - _Destroy(__new_finish, end()); - _M_finish = __new_finish.base(); - } - else { - _ForwardIter __mid = __first; - advance(__mid, size()); - copy(__first, __mid, _M_start); - _M_finish = uninitialized_copy(__mid, __last, _M_finish); - } -} - -template <class _Tp, class _Alloc> -void -vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x) -{ - if (_M_finish != _M_end_of_storage) { - _Construct(_M_finish, *(_M_finish - 1)); - ++_M_finish; - _Tp __x_copy = __x; - copy_backward(__position, iterator(_M_finish - 2), iterator(_M_finish- 1)); - *__position = __x_copy; - } - else { - const size_type __old_size = size(); - const size_type __len = __old_size != 0 ? 2 * __old_size : 1; - iterator __new_start(_M_allocate(__len)); - iterator __new_finish(__new_start); - try { - __new_finish = uninitialized_copy(iterator(_M_start), __position, - __new_start); - _Construct(__new_finish.base(), __x); - ++__new_finish; - __new_finish = uninitialized_copy(__position, iterator(_M_finish), - __new_finish); - } - catch(...) - { - _Destroy(__new_start,__new_finish); - _M_deallocate(__new_start.base(),__len); - __throw_exception_again; - } - _Destroy(begin(), end()); - _M_deallocate(_M_start, _M_end_of_storage - _M_start); - _M_start = __new_start.base(); - _M_finish = __new_finish.base(); - _M_end_of_storage = __new_start.base() + __len; - } -} - -#ifdef _GLIBCPP_DEPRECATED -template <class _Tp, class _Alloc> -void -vector<_Tp, _Alloc>::_M_insert_aux(iterator __position) -{ - if (_M_finish != _M_end_of_storage) { - _Construct(_M_finish, *(_M_finish - 1)); - ++_M_finish; - copy_backward(__position, iterator(_M_finish - 2), - iterator(_M_finish - 1)); - *__position = _Tp(); - } - else { - const size_type __old_size = size(); - const size_type __len = __old_size != 0 ? 2 * __old_size : 1; - pointer __new_start = _M_allocate(__len); - pointer __new_finish = __new_start; - try { - __new_finish = uninitialized_copy(iterator(_M_start), __position, - __new_start); - _Construct(__new_finish); - ++__new_finish; - __new_finish = uninitialized_copy(__position, iterator(_M_finish), - __new_finish); - } - catch(...) - { - _Destroy(__new_start,__new_finish); - _M_deallocate(__new_start,__len); - __throw_exception_again; - } - _Destroy(begin(), end()); - _M_deallocate(_M_start, _M_end_of_storage - _M_start); - _M_start = __new_start; - _M_finish = __new_finish; - _M_end_of_storage = __new_start + __len; - } -} -#endif - -template <class _Tp, class _Alloc> -void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n, - const _Tp& __x) -{ - if (__n != 0) { - if (size_type(_M_end_of_storage - _M_finish) >= __n) { - _Tp __x_copy = __x; - const size_type __elems_after = end() - __position; - iterator __old_finish(_M_finish); - if (__elems_after > __n) { - uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); - _M_finish += __n; - copy_backward(__position, __old_finish - __n, __old_finish); - fill(__position, __position + __n, __x_copy); - } - else { - uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy); - _M_finish += __n - __elems_after; - uninitialized_copy(__position, __old_finish, _M_finish); - _M_finish += __elems_after; - fill(__position, __old_finish, __x_copy); - } - } - else { - const size_type __old_size = size(); - const size_type __len = __old_size + max(__old_size, __n); - iterator __new_start(_M_allocate(__len)); - iterator __new_finish(__new_start); - try { - __new_finish = uninitialized_copy(begin(), __position, __new_start); - __new_finish = uninitialized_fill_n(__new_finish, __n, __x); - __new_finish - = uninitialized_copy(__position, end(), __new_finish); - } - catch(...) - { - _Destroy(__new_start,__new_finish); - _M_deallocate(__new_start.base(),__len); - __throw_exception_again; - } - _Destroy(_M_start, _M_finish); - _M_deallocate(_M_start, _M_end_of_storage - _M_start); - _M_start = __new_start.base(); - _M_finish = __new_finish.base(); - _M_end_of_storage = __new_start.base() + __len; - } - } -} - -template <class _Tp, class _Alloc> template <class _InputIterator> -void -vector<_Tp, _Alloc>::_M_range_insert(iterator __pos, - _InputIterator __first, - _InputIterator __last, - input_iterator_tag) -{ - for ( ; __first != __last; ++__first) { - __pos = insert(__pos, *__first); - ++__pos; - } -} - -template <class _Tp, class _Alloc> template <class _ForwardIterator> -void -vector<_Tp, _Alloc>::_M_range_insert(iterator __position, - _ForwardIterator __first, - _ForwardIterator __last, - forward_iterator_tag) -{ - if (__first != __last) { - size_type __n = distance(__first, __last); - if (size_type(_M_end_of_storage - _M_finish) >= __n) { - const size_type __elems_after = end() - __position; - iterator __old_finish(_M_finish); - if (__elems_after > __n) { - uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); - _M_finish += __n; - copy_backward(__position, __old_finish - __n, __old_finish); - copy(__first, __last, __position); - } - else { - _ForwardIterator __mid = __first; - advance(__mid, __elems_after); - uninitialized_copy(__mid, __last, _M_finish); - _M_finish += __n - __elems_after; - uninitialized_copy(__position, __old_finish, _M_finish); - _M_finish += __elems_after; - copy(__first, __mid, __position); - } - } - else { - const size_type __old_size = size(); - const size_type __len = __old_size + max(__old_size, __n); - iterator __new_start(_M_allocate(__len)); - iterator __new_finish(__new_start); - try { - __new_finish = uninitialized_copy(iterator(_M_start), - __position, __new_start); - __new_finish = uninitialized_copy(__first, __last, __new_finish); - __new_finish - = uninitialized_copy(__position, iterator(_M_finish), __new_finish); - } - catch(...) - { - _Destroy(__new_start,__new_finish); - _M_deallocate(__new_start.base(), __len); - __throw_exception_again; - } - _Destroy(_M_start, _M_finish); - _M_deallocate(_M_start, _M_end_of_storage - _M_start); - _M_start = __new_start.base(); - _M_finish = __new_finish.base(); - _M_end_of_storage = __new_start.base() + __len; - } - } -} - } // namespace std #endif /* __GLIBCPP_INTERNAL_VECTOR_H */ diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc new file mode 100644 index 00000000000..d63742f9498 --- /dev/null +++ b/libstdc++-v3/include/bits/vector.tcc @@ -0,0 +1,439 @@ +// Vector implementation (out of line) -*- C++ -*- + +// Copyright (C) 2001, 2002 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +/* + * + * 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) 1996 + * 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. + */ + +/** @file vector.tcc + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +#ifndef __GLIBCPP_INTERNAL_VECTOR_TCC +#define __GLIBCPP_INTERNAL_VECTOR_TCC + +// Since this entire file is within namespace std, there's no reason to +// waste two spaces along the left column. Thus the leading indentation is +// slightly violated from here on. +namespace std +{ + +template <typename _Tp, typename _Alloc> + void + vector<_Tp,_Alloc>:: + reserve(size_type __n) + { + if (capacity() < __n) + { + const size_type __old_size = size(); + pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish); + _Destroy(_M_start, _M_finish); + _M_deallocate(_M_start, _M_end_of_storage - _M_start); + _M_start = __tmp; + _M_finish = __tmp + __old_size; + _M_end_of_storage = _M_start + __n; + } + } + +template <typename _Tp, typename _Alloc> + typename vector<_Tp,_Alloc>::iterator + vector<_Tp,_Alloc>:: + insert(iterator __position, const value_type& __x) + { + size_type __n = __position - begin(); + if (_M_finish != _M_end_of_storage && __position == end()) + { + _Construct(_M_finish, __x); + ++_M_finish; + } + else + _M_insert_aux(__position, __x); + return begin() + __n; + } + +template <typename _Tp, typename _Alloc> + typename vector<_Tp,_Alloc>::iterator + vector<_Tp,_Alloc>:: + erase(iterator __position) + { + if (__position + 1 != end()) + copy(__position + 1, end(), __position); + --_M_finish; + _Destroy(_M_finish); + return __position; + } + +template <typename _Tp, typename _Alloc> + typename vector<_Tp,_Alloc>::iterator + vector<_Tp,_Alloc>:: + erase(iterator __first, iterator __last) + { + iterator __i(copy(__last, end(), __first)); + _Destroy(__i, end()); + _M_finish = _M_finish - (__last - __first); + return __first; + } + +template <typename _Tp, typename _Alloc> + vector<_Tp,_Alloc>& + vector<_Tp,_Alloc>:: + operator=(const vector<_Tp,_Alloc>& __x) + { + if (&__x != this) + { + const size_type __xlen = __x.size(); + if (__xlen > capacity()) + { + pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end()); + _Destroy(_M_start, _M_finish); + _M_deallocate(_M_start, _M_end_of_storage - _M_start); + _M_start = __tmp; + _M_end_of_storage = _M_start + __xlen; + } + else if (size() >= __xlen) + { + iterator __i(copy(__x.begin(), __x.end(), begin())); + _Destroy(__i, end()); + } + else + { + copy(__x.begin(), __x.begin() + size(), _M_start); + uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish); + } + _M_finish = _M_start + __xlen; + } + return *this; + } + +template <typename _Tp, typename _Alloc> + void + vector<_Tp,_Alloc>:: + _M_fill_assign(size_t __n, const value_type& __val) + { + if (__n > capacity()) + { + vector __tmp(__n, __val, get_allocator()); + __tmp.swap(*this); + } + else if (__n > size()) + { + fill(begin(), end(), __val); + _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val); + } + else + erase(fill_n(begin(), __n, __val), end()); + } + +template <typename _Tp, typename _Alloc> template <typename _InputIter> + void + vector<_Tp,_Alloc>:: + _M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag) + { + iterator __cur(begin()); + for ( ; __first != __last && __cur != end(); ++__cur, ++__first) + *__cur = *__first; + if (__first == __last) + erase(__cur, end()); + else + insert(end(), __first, __last); + } + +template <typename _Tp, typename _Alloc> template <typename _ForwardIter> + void + vector<_Tp,_Alloc>:: + _M_assign_aux(_ForwardIter __first, _ForwardIter __last, forward_iterator_tag) + { + size_type __len = distance(__first, __last); + + if (__len > capacity()) + { + pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); + _Destroy(_M_start, _M_finish); + _M_deallocate(_M_start, _M_end_of_storage - _M_start); + _M_start = __tmp; + _M_end_of_storage = _M_finish = _M_start + __len; + } + else if (size() >= __len) + { + iterator __new_finish(copy(__first, __last, _M_start)); + _Destroy(__new_finish, end()); + _M_finish = __new_finish.base(); + } + else + { + _ForwardIter __mid = __first; + advance(__mid, size()); + copy(__first, __mid, _M_start); + _M_finish = uninitialized_copy(__mid, __last, _M_finish); + } + } + +template <typename _Tp, typename _Alloc> + void + vector<_Tp,_Alloc>:: + _M_insert_aux(iterator __position, const _Tp& __x) + { + if (_M_finish != _M_end_of_storage) + { + _Construct(_M_finish, *(_M_finish - 1)); + ++_M_finish; + _Tp __x_copy = __x; + copy_backward(__position, iterator(_M_finish-2), iterator(_M_finish-1)); + *__position = __x_copy; + } + else + { + const size_type __old_size = size(); + const size_type __len = __old_size != 0 ? 2 * __old_size : 1; + iterator __new_start(_M_allocate(__len)); + iterator __new_finish(__new_start); + try + { + __new_finish = uninitialized_copy(iterator(_M_start), __position, + __new_start); + _Construct(__new_finish.base(), __x); + ++__new_finish; + __new_finish = uninitialized_copy(__position, iterator(_M_finish), + __new_finish); + } + catch(...) + { + _Destroy(__new_start,__new_finish); + _M_deallocate(__new_start.base(),__len); + __throw_exception_again; + } + _Destroy(begin(), end()); + _M_deallocate(_M_start, _M_end_of_storage - _M_start); + _M_start = __new_start.base(); + _M_finish = __new_finish.base(); + _M_end_of_storage = __new_start.base() + __len; + } + } + +#ifdef _GLIBCPP_DEPRECATED +template <typename _Tp, typename _Alloc> + void + vector<_Tp,_Alloc>:: + _M_insert_aux(iterator __position) + { + if (_M_finish != _M_end_of_storage) + { + _Construct(_M_finish, *(_M_finish - 1)); + ++_M_finish; + copy_backward(__position, iterator(_M_finish - 2), + iterator(_M_finish - 1)); + *__position = value_type(); + } + else + { + const size_type __old_size = size(); + const size_type __len = __old_size != 0 ? 2 * __old_size : 1; + pointer __new_start = _M_allocate(__len); + pointer __new_finish = __new_start; + try + { + __new_finish = uninitialized_copy(iterator(_M_start), __position, + __new_start); + _Construct(__new_finish); + ++__new_finish; + __new_finish = uninitialized_copy(__position, iterator(_M_finish), + __new_finish); + } + catch(...) + { + _Destroy(__new_start,__new_finish); + _M_deallocate(__new_start,__len); + __throw_exception_again; + } + _Destroy(begin(), end()); + _M_deallocate(_M_start, _M_end_of_storage - _M_start); + _M_start = __new_start; + _M_finish = __new_finish; + _M_end_of_storage = __new_start + __len; + } + } +#endif + +template <typename _Tp, typename _Alloc> + void + vector<_Tp,_Alloc>:: + _M_fill_insert(iterator __position, size_type __n, const value_type& __x) + { + if (__n != 0) + { + if (size_type(_M_end_of_storage - _M_finish) >= __n) { + value_type __x_copy = __x; + const size_type __elems_after = end() - __position; + iterator __old_finish(_M_finish); + if (__elems_after > __n) + { + uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); + _M_finish += __n; + copy_backward(__position, __old_finish - __n, __old_finish); + fill(__position, __position + __n, __x_copy); + } + else + { + uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy); + _M_finish += __n - __elems_after; + uninitialized_copy(__position, __old_finish, _M_finish); + _M_finish += __elems_after; + fill(__position, __old_finish, __x_copy); + } + } + else + { + const size_type __old_size = size(); + const size_type __len = __old_size + max(__old_size, __n); + iterator __new_start(_M_allocate(__len)); + iterator __new_finish(__new_start); + try + { + __new_finish = uninitialized_copy(begin(), __position, __new_start); + __new_finish = uninitialized_fill_n(__new_finish, __n, __x); + __new_finish + = uninitialized_copy(__position, end(), __new_finish); + } + catch(...) + { + _Destroy(__new_start,__new_finish); + _M_deallocate(__new_start.base(),__len); + __throw_exception_again; + } + _Destroy(_M_start, _M_finish); + _M_deallocate(_M_start, _M_end_of_storage - _M_start); + _M_start = __new_start.base(); + _M_finish = __new_finish.base(); + _M_end_of_storage = __new_start.base() + __len; + } + } + } + +template <typename _Tp, typename _Alloc> template <typename _InputIterator> + void + vector<_Tp,_Alloc>:: + _M_range_insert(iterator __pos, + _InputIterator __first, _InputIterator __last, + input_iterator_tag) + { + for ( ; __first != __last; ++__first) + { + __pos = insert(__pos, *__first); + ++__pos; + } + } + +template <typename _Tp, typename _Alloc> template <typename _ForwardIterator> + void + vector<_Tp,_Alloc>:: + _M_range_insert(iterator __position, + _ForwardIterator __first, _ForwardIterator __last, + forward_iterator_tag) + { + if (__first != __last) + { + size_type __n = distance(__first, __last); + if (size_type(_M_end_of_storage - _M_finish) >= __n) + { + const size_type __elems_after = end() - __position; + iterator __old_finish(_M_finish); + if (__elems_after > __n) + { + uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); + _M_finish += __n; + copy_backward(__position, __old_finish - __n, __old_finish); + copy(__first, __last, __position); + } + else + { + _ForwardIterator __mid = __first; + advance(__mid, __elems_after); + uninitialized_copy(__mid, __last, _M_finish); + _M_finish += __n - __elems_after; + uninitialized_copy(__position, __old_finish, _M_finish); + _M_finish += __elems_after; + copy(__first, __mid, __position); + } + } + else + { + const size_type __old_size = size(); + const size_type __len = __old_size + max(__old_size, __n); + iterator __new_start(_M_allocate(__len)); + iterator __new_finish(__new_start); + try + { + __new_finish = uninitialized_copy(iterator(_M_start), + __position, __new_start); + __new_finish = uninitialized_copy(__first, __last, __new_finish); + __new_finish = uninitialized_copy(__position, iterator(_M_finish), + __new_finish); + } + catch(...) + { + _Destroy(__new_start,__new_finish); + _M_deallocate(__new_start.base(), __len); + __throw_exception_again; + } + _Destroy(_M_start, _M_finish); + _M_deallocate(_M_start, _M_end_of_storage - _M_start); + _M_start = __new_start.base(); + _M_finish = __new_finish.base(); + _M_end_of_storage = __new_start.base() + __len; + } + } + } + +} // namespace std + +#endif /* __GLIBCPP_INTERNAL_VECTOR_TCC */ + diff --git a/libstdc++-v3/include/ext/stl_hashtable.h b/libstdc++-v3/include/ext/stl_hashtable.h index 5ee49d815f7..c4fab34c474 100644 --- a/libstdc++-v3/include/ext/stl_hashtable.h +++ b/libstdc++-v3/include/ext/stl_hashtable.h @@ -65,13 +65,10 @@ // Hashtable class, used to implement the hashed associative containers // hash_set, hash_map, hash_multiset, and hash_multimap. -#include <bits/stl_algobase.h> -#include <bits/stl_alloc.h> -#include <bits/stl_construct.h> +#include <vector> +#include <iterator> #include <bits/stl_algo.h> -#include <bits/stl_uninitialized.h> #include <bits/stl_function.h> -#include <bits/stl_vector.h> #include <ext/stl_hash_fun.h> namespace __gnu_cxx diff --git a/libstdc++-v3/include/std/std_deque.h b/libstdc++-v3/include/std/std_deque.h index 0fca0d1a3d4..921c25fa493 100644 --- a/libstdc++-v3/include/std/std_deque.h +++ b/libstdc++-v3/include/std/std_deque.h @@ -70,8 +70,9 @@ #include <bits/stl_uninitialized.h> #include <bits/stl_deque.h> +#ifdef _GLIBCPP_NO_TEMPLATE_EXPORT +# include <bits/deque.tcc> +#endif + #endif /* _CPP_DEQUE */ -// Local Variables: -// mode:C++ -// End: diff --git a/libstdc++-v3/include/std/std_list.h b/libstdc++-v3/include/std/std_list.h index f32553be1f4..84523ad8e4f 100644 --- a/libstdc++-v3/include/std/std_list.h +++ b/libstdc++-v3/include/std/std_list.h @@ -70,8 +70,9 @@ #include <bits/stl_uninitialized.h> #include <bits/stl_list.h> +#ifdef _GLIBCPP_NO_TEMPLATE_EXPORT +# include <bits/list.tcc> +#endif + #endif /* _CPP_LIST */ -// Local Variables: -// mode:C++ -// End: diff --git a/libstdc++-v3/include/std/std_vector.h b/libstdc++-v3/include/std/std_vector.h index 4120aa9e3be..5738ef7ade8 100644 --- a/libstdc++-v3/include/std/std_vector.h +++ b/libstdc++-v3/include/std/std_vector.h @@ -71,8 +71,9 @@ #include <bits/stl_vector.h> #include <bits/stl_bvector.h> +#ifdef _GLIBCPP_NO_TEMPLATE_EXPORT +# include <bits/vector.tcc> +#endif + #endif /* _CPP_VECTOR */ -// Local Variables: -// mode:C++ -// End: |