OSDN Git Service

2003-11-11 Doug Gregor <gregod@cs.rpi.edu>
authorbkoz <bkoz@138bc75d-0d04-0410-961f-82ee72b054a4>
Tue, 11 Nov 2003 20:09:16 +0000 (20:09 +0000)
committerbkoz <bkoz@138bc75d-0d04-0410-961f-82ee72b054a4>
Tue, 11 Nov 2003 20:09:16 +0000 (20:09 +0000)
* docs/html/debug.html: Document libstdc++ debug mode.
* docs/html/debug_mode.html: Document libstdc++ debug mode design.
* docs/html/test.html: Document how to test under debug mode.
* docs/html/17_intro/howto.html: Document debug-mode macros.
* include/Makefile.am: Install debug-mode headers.
* src/Makefile.am: Include debug.cc.
* include/bits/basic_string.tcc:
  (basic_string::_S_construct): Fix NULL pointer check.
  (__is_null_pointer): New.
  Add precondition annotations.
* include/bits/stream_iterator.h (istream_iterator,
ostream_iterator): Added precondition annotations.
* include/bits/streambuf_iterator.h (istreambuf_iterator): Ditto.
* include/bits/stl_queue.h (queue, priority_queue): Ditto.
* include/bits/stl_stack.h (stack): Ditto.
* include/bits/basic_string.h (basic_string): Ditto.
* include/bits/basic_string.tcc (basic_string): Ditto.
* include/std/std_memory.h (auto_ptr): Ditto.
* include/std/std_valarray.h (valarray): Ditto.
* include/bits/stl_algo.h: Added algorithm precondition
annotations.
* include/bits/stl_algobase.h: Added algorithm precondition
annotations.
* include/bits/stl_numeric.h: Ditto.
* include/ext/algorithm: Added algorithm precondition
annotations.
(__is_heap): Moved away from here.
* include/bits/stl_heap.h: Added algorithm precondition
annotations.
(__is_heap): Moved to the top of this file.
(__is_heap): Added iterator range overloads.
* testsuite/20_util/auto_ptr_neg.cc: Fix line numbers to match up
with changes in std_memory.h.
* testsuite/23_containers/list/operators/4.cc: Don't verify
performance guarantees when in debug mode.
* testsuite/23_containers/bitset/invalidation/1.cc: New.
* testsuite/23_containers/deque/invalidation/1.cc: New.
* testsuite/23_containers/deque/invalidation/2.cc: New.
* testsuite/23_containers/deque/invalidation/3.cc: New.
* testsuite/23_containers/deque/invalidation/4.cc: New.
* testsuite/23_containers/list/invalidation/1.cc: New.
* testsuite/23_containers/list/invalidation/2.cc: New.
* testsuite/23_containers/list/invalidation/3.cc: New.
* testsuite/23_containers/list/invalidation/4.cc: New.
* testsuite/23_containers/map/invalidation/1.cc: New.
* testsuite/23_containers/map/invalidation/2.cc: New.
* testsuite/23_containers/multimap/invalidation/1.cc: New.
* testsuite/23_containers/multimap/invalidation/2.cc: New.
* testsuite/23_containers/multiset/invalidation/1.cc: New.
* testsuite/23_containers/multiset/invalidation/2.cc: New.
* testsuite/23_containers/set/invalidation/1.cc: New.
* testsuite/23_containers/set/invalidation/2.cc: New.
* testsuite/23_containers/vector/invalidation/1.cc: New.
* testsuite/23_containers/vector/invalidation/2.cc: New.
* testsuite/23_containers/vector/invalidation/3.cc: New.
* testsuite/23_containers/vector/invalidation/4.cc: New.
* testsuite/25_algorithms/heap.cc: Don't verify
performance guarantees when in debug mode.
* include/debug/bitset: New.
* include/debug/debug.h: New.
* include/debug/deque: New.
* include/debug/formatter.h: New.
* include/debug/hash_map: New.
* include/debug/hash_map.h: New.
* include/debug/hash_multimap.h: New.
* include/debug/hash_set: New.
* include/debug/hash_set.h: New.
* include/debug/hash_multiset.h: New.
* include/debug/list: New.
* include/debug/map: New.
* include/debug/map.h: New.
* include/debug/multimap.h: New.
* include/debug/multiset.h: New.
* include/debug/safe_base.h: New.
* include/debug/safe_iterator.h: New.
* include/debug/safe_iterator.tcc: New.
* include/debug/safe_sequence.h: New.
* include/debug/set: New.
* include/debug/set.h: New.
* include/debug/string: New.
* include/debug/vector: New.
* src/debug.cc: New.
* config/linker-map.gnu: Add debug mode symbols.

2003-11-11  Benjamin Kosnik  <bkoz@redhat.com>

* src/string-inst.cc: Tweak namespaces.
* src/misc-inst.cc: Same.
* docs/html/debug.html: Edits.
* config/link-map.gnu: Remove cruft.

* include/bits/c++config: Add in namespace associations.
* include/std/std_bitset.h: Adjust namespace to __gnu_norm,
comment tweaks.
* include/bits/deque.tcc: Same.
* include/bits/list.tcc: Same.
* include/bits/stl_bvector.h: Same.
* include/bits/stl_deque.h: Same.
* include/bits/stl_list.h: Same.
* include/bits/stl_map.h: Same.
* include/bits/stl_multimap.h: Same.
* include/bits/stl_multiset.h: Same.
* include/bits/stl_set.h: Same.
* include/bits/stl_vector.h: Same.
* include/bits/vector.tcc: Same.

* include/std/std_algorithm.h: Remove markup comments.
* include/std/std_functional.h: Same.
* include/std/std_iterator.h: Same.
* include/std/std_numeric.h: Same.
* include/std/std_utility.h: Same.
* include/bits/stl_queue.h: Formatting tweaks.
* include/bits/stl_stack.h: Same.
* include/std/std_deque.h: Include debugging version in debug mode.
* include/std/std_list.h: Same.
* include/std/std_map.h: Same.
* include/std/std_set.h: Same.
* include/std/std_vector.h: Same.
* include/std/std_queue.h: Use deque, vector.
* include/std/std_stack.h: Same.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@73459 138bc75d-0d04-0410-961f-82ee72b054a4

98 files changed:
libstdc++-v3/ChangeLog
libstdc++-v3/config/linker-map.gnu
libstdc++-v3/docs/html/17_intro/howto.html
libstdc++-v3/docs/html/debug.html
libstdc++-v3/docs/html/debug_mode.html [new file with mode: 0644]
libstdc++-v3/docs/html/test.html
libstdc++-v3/include/Makefile.am
libstdc++-v3/include/Makefile.in
libstdc++-v3/include/bits/basic_string.h
libstdc++-v3/include/bits/basic_string.tcc
libstdc++-v3/include/bits/c++config
libstdc++-v3/include/bits/deque.tcc
libstdc++-v3/include/bits/list.tcc
libstdc++-v3/include/bits/stl_algo.h
libstdc++-v3/include/bits/stl_algobase.h
libstdc++-v3/include/bits/stl_bvector.h
libstdc++-v3/include/bits/stl_deque.h
libstdc++-v3/include/bits/stl_heap.h
libstdc++-v3/include/bits/stl_list.h
libstdc++-v3/include/bits/stl_map.h
libstdc++-v3/include/bits/stl_multimap.h
libstdc++-v3/include/bits/stl_multiset.h
libstdc++-v3/include/bits/stl_numeric.h
libstdc++-v3/include/bits/stl_queue.h
libstdc++-v3/include/bits/stl_set.h
libstdc++-v3/include/bits/stl_stack.h
libstdc++-v3/include/bits/stl_vector.h
libstdc++-v3/include/bits/stream_iterator.h
libstdc++-v3/include/bits/streambuf_iterator.h
libstdc++-v3/include/bits/vector.tcc
libstdc++-v3/include/debug/bitset [new file with mode: 0644]
libstdc++-v3/include/debug/debug.h [new file with mode: 0644]
libstdc++-v3/include/debug/deque [new file with mode: 0644]
libstdc++-v3/include/debug/formatter.h [new file with mode: 0644]
libstdc++-v3/include/debug/hash_map [new file with mode: 0644]
libstdc++-v3/include/debug/hash_map.h [new file with mode: 0644]
libstdc++-v3/include/debug/hash_multimap.h [new file with mode: 0644]
libstdc++-v3/include/debug/hash_multiset.h [new file with mode: 0644]
libstdc++-v3/include/debug/hash_set [new file with mode: 0644]
libstdc++-v3/include/debug/hash_set.h [new file with mode: 0644]
libstdc++-v3/include/debug/list [new file with mode: 0644]
libstdc++-v3/include/debug/map [new file with mode: 0644]
libstdc++-v3/include/debug/map.h [new file with mode: 0644]
libstdc++-v3/include/debug/multimap.h [new file with mode: 0644]
libstdc++-v3/include/debug/multiset.h [new file with mode: 0644]
libstdc++-v3/include/debug/safe_base.h [new file with mode: 0644]
libstdc++-v3/include/debug/safe_iterator.h [new file with mode: 0644]
libstdc++-v3/include/debug/safe_iterator.tcc [new file with mode: 0644]
libstdc++-v3/include/debug/safe_sequence.h [new file with mode: 0644]
libstdc++-v3/include/debug/set [new file with mode: 0644]
libstdc++-v3/include/debug/set.h [new file with mode: 0644]
libstdc++-v3/include/debug/string [new file with mode: 0644]
libstdc++-v3/include/debug/vector [new file with mode: 0644]
libstdc++-v3/include/ext/algorithm
libstdc++-v3/include/std/std_algorithm.h
libstdc++-v3/include/std/std_bitset.h
libstdc++-v3/include/std/std_deque.h
libstdc++-v3/include/std/std_functional.h
libstdc++-v3/include/std/std_iterator.h
libstdc++-v3/include/std/std_list.h
libstdc++-v3/include/std/std_map.h
libstdc++-v3/include/std/std_memory.h
libstdc++-v3/include/std/std_numeric.h
libstdc++-v3/include/std/std_queue.h
libstdc++-v3/include/std/std_set.h
libstdc++-v3/include/std/std_stack.h
libstdc++-v3/include/std/std_utility.h
libstdc++-v3/include/std/std_valarray.h
libstdc++-v3/include/std/std_vector.h
libstdc++-v3/src/Makefile.am
libstdc++-v3/src/Makefile.in
libstdc++-v3/src/debug.cc [new file with mode: 0644]
libstdc++-v3/src/misc-inst.cc
libstdc++-v3/src/string-inst.cc
libstdc++-v3/testsuite/20_util/auto_ptr_neg.cc
libstdc++-v3/testsuite/23_containers/bitset/invalidation/1.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/deque/invalidation/1.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/deque/invalidation/2.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/deque/invalidation/3.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/deque/invalidation/4.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/list/invalidation/1.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/list/invalidation/2.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/list/invalidation/3.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/list/invalidation/4.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/list/operators/4.cc
libstdc++-v3/testsuite/23_containers/map/invalidation/1.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/map/invalidation/2.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/multimap/invalidation/1.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/multimap/invalidation/2.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/multiset/invalidation/1.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/multiset/invalidation/2.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/set/invalidation/1.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/set/invalidation/2.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/vector/invalidation/1.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/vector/invalidation/2.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/vector/invalidation/3.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/vector/invalidation/4.cc [new file with mode: 0644]
libstdc++-v3/testsuite/25_algorithms/heap.cc

index 5255ff4..1df66ab 100644 (file)
@@ -1,3 +1,126 @@
+2003-11-11  Doug Gregor  <gregod@cs.rpi.edu>
+
+       * docs/html/debug.html: Document libstdc++ debug mode.
+       * docs/html/debug_mode.html: Document libstdc++ debug mode design.
+       * docs/html/test.html: Document how to test under debug mode.
+       * docs/html/17_intro/howto.html: Document debug-mode macros.
+       * include/Makefile.am: Install debug-mode headers.
+       * src/Makefile.am: Include debug.cc.
+       * include/bits/basic_string.tcc: 
+         (basic_string::_S_construct): Fix NULL pointer check.
+         (__is_null_pointer): New.
+         Add precondition annotations.
+       * include/bits/stream_iterator.h (istream_iterator,
+       ostream_iterator): Added precondition annotations.
+       * include/bits/streambuf_iterator.h (istreambuf_iterator): Ditto.
+       * include/bits/stl_queue.h (queue, priority_queue): Ditto.
+       * include/bits/stl_stack.h (stack): Ditto.
+       * include/bits/basic_string.h (basic_string): Ditto.
+       * include/bits/basic_string.tcc (basic_string): Ditto.
+       * include/std/std_memory.h (auto_ptr): Ditto.
+       * include/std/std_valarray.h (valarray): Ditto.
+       * include/bits/stl_algo.h: Added algorithm precondition
+       annotations.
+       * include/bits/stl_algobase.h: Added algorithm precondition
+       annotations.
+       * include/bits/stl_numeric.h: Ditto.
+       * include/ext/algorithm: Added algorithm precondition
+       annotations. 
+       (__is_heap): Moved away from here.
+       * include/bits/stl_heap.h: Added algorithm precondition
+       annotations. 
+       (__is_heap): Moved to the top of this file.
+       (__is_heap): Added iterator range overloads.
+       * testsuite/20_util/auto_ptr_neg.cc: Fix line numbers to match up
+       with changes in std_memory.h.
+       * testsuite/23_containers/list/operators/4.cc: Don't verify
+       performance guarantees when in debug mode.
+       * testsuite/23_containers/bitset/invalidation/1.cc: New.
+       * testsuite/23_containers/deque/invalidation/1.cc: New.
+       * testsuite/23_containers/deque/invalidation/2.cc: New.
+       * testsuite/23_containers/deque/invalidation/3.cc: New.
+       * testsuite/23_containers/deque/invalidation/4.cc: New.
+       * testsuite/23_containers/list/invalidation/1.cc: New.
+       * testsuite/23_containers/list/invalidation/2.cc: New.
+       * testsuite/23_containers/list/invalidation/3.cc: New.
+       * testsuite/23_containers/list/invalidation/4.cc: New.
+       * testsuite/23_containers/map/invalidation/1.cc: New.
+       * testsuite/23_containers/map/invalidation/2.cc: New.
+       * testsuite/23_containers/multimap/invalidation/1.cc: New.
+       * testsuite/23_containers/multimap/invalidation/2.cc: New.
+       * testsuite/23_containers/multiset/invalidation/1.cc: New.
+       * testsuite/23_containers/multiset/invalidation/2.cc: New.
+       * testsuite/23_containers/set/invalidation/1.cc: New.
+       * testsuite/23_containers/set/invalidation/2.cc: New.
+       * testsuite/23_containers/vector/invalidation/1.cc: New.
+       * testsuite/23_containers/vector/invalidation/2.cc: New.
+       * testsuite/23_containers/vector/invalidation/3.cc: New.
+       * testsuite/23_containers/vector/invalidation/4.cc: New.
+       * testsuite/25_algorithms/heap.cc: Don't verify
+       performance guarantees when in debug mode.
+       * include/debug/bitset: New.
+       * include/debug/debug.h: New.
+       * include/debug/deque: New.
+       * include/debug/formatter.h: New.
+       * include/debug/hash_map: New.
+       * include/debug/hash_map.h: New.        
+       * include/debug/hash_multimap.h: New.
+       * include/debug/hash_set: New.
+       * include/debug/hash_set.h: New.
+       * include/debug/hash_multiset.h: New.   
+       * include/debug/list: New.
+       * include/debug/map: New.
+       * include/debug/map.h: New.
+       * include/debug/multimap.h: New.
+       * include/debug/multiset.h: New.        
+       * include/debug/safe_base.h: New.
+       * include/debug/safe_iterator.h: New.
+       * include/debug/safe_iterator.tcc: New.
+       * include/debug/safe_sequence.h: New.
+       * include/debug/set: New.
+       * include/debug/set.h: New.     
+       * include/debug/string: New.
+       * include/debug/vector: New.
+       * src/debug.cc: New.
+       * config/linker-map.gnu: Add debug mode symbols.
+       
+2003-11-11  Benjamin Kosnik  <bkoz@redhat.com>
+
+       * src/string-inst.cc: Tweak namespaces.
+       * src/misc-inst.cc: Same.
+       * docs/html/debug.html: Edits.
+       * config/link-map.gnu: Remove cruft.
+
+       * include/bits/c++config: Add in namespace associations.
+       * include/std/std_bitset.h: Adjust namespace to __gnu_norm,
+       comment tweaks.
+       * include/bits/deque.tcc: Same.
+       * include/bits/list.tcc: Same.
+       * include/bits/stl_bvector.h: Same.
+       * include/bits/stl_deque.h: Same.
+       * include/bits/stl_list.h: Same.
+       * include/bits/stl_map.h: Same.
+       * include/bits/stl_multimap.h: Same.
+       * include/bits/stl_multiset.h: Same.
+       * include/bits/stl_set.h: Same.
+       * include/bits/stl_vector.h: Same.
+       * include/bits/vector.tcc: Same.
+
+       * include/std/std_algorithm.h: Remove markup comments.
+       * include/std/std_functional.h: Same.
+       * include/std/std_iterator.h: Same.
+       * include/std/std_numeric.h: Same.
+       * include/std/std_utility.h: Same.
+       * include/bits/stl_queue.h: Formatting tweaks.
+       * include/bits/stl_stack.h: Same.
+       * include/std/std_deque.h: Include debugging version in debug mode.
+       * include/std/std_list.h: Same.
+       * include/std/std_map.h: Same.
+       * include/std/std_set.h: Same.
+       * include/std/std_vector.h: Same.       
+       * include/std/std_queue.h: Use deque, vector.
+       * include/std/std_stack.h: Same.
+
 2003-11-09  Paolo Carlini  <pcarlini@suse.de>
 
        * include/bits/locale_facets.tcc (_M_insert_int,
index adbd390..671e421 100644 (file)
@@ -57,7 +57,11 @@ GLIBCXX_3.4 {
       std::__num_base::_S_atoms_out;
       std::__moneypunct_cache*;
       std::__numpunct_cache*;
-      std::__timepunct_cache*
+      std::__timepunct_cache*;
+      __gnu_norm::*;
+      __gnu_debug::_Safe_iterator_base*;
+      __gnu_debug::_Safe_sequence_base*;
+      __gnu_debug::_Error_formatter*
     };
 
     # Names not in an 'extern' block are mangled names.
@@ -88,7 +92,7 @@ GLIBCXX_3.4 {
     # std::locale::facet destructors
     _ZNSt6locale5facetD*;
         
-    # std::locale::_Impl constructors, destrutors
+    # std::locale::_Impl constructors, destructors
     _ZNSt6locale5_ImplC*;
     _ZNSt6locale5_ImplD*;
 
@@ -104,9 +108,6 @@ GLIBCXX_3.4 {
     _ZSt21_Rb_tree_rotate_rightPSt18_Rb_tree_node_baseRS0_;
     _ZSt28_Rb_tree_rebalance_for_erasePSt18_Rb_tree_node_baseRS_;
 
-    # std::__ctype_abstract_base*
-    _ZNSt21__ctype_abstract_base*;
-
     # std::__codecvt_abstract_base*
     _ZNStSt23__codecvt_abstract_base*;
 
index d1fc584..29d0db7 100644 (file)
         violations of the requirements of the standard.  This is described
         in more detail <a href="../19_diagnostics/howto.html#3">here</a>.
     </dd>
+    <dt><code>_GLIBCXX_DEBUG</code></dt>
+    <dd>Undefined by default. Configurable. When defined, compiles
+    user code using the <a href="../debug.html#safe">libstdc++ debug
+    mode</a>.
+    </dd>
+    <dt><code>_GLIBCXX_DEBUG_PEDANTIC</code></dt>
+    <dd>Undefined by default. Configurable. When defined while
+    compiling with the <a href="../debug.html#safe">libstdc++ debug
+    mode</a>, makes the debug mode extremely picky by making the use
+    of libstdc++ extensions and libstdc++-specific behavior into
+    errors.
+    </dd>
     <!--
     <dt><code></code></dt>
     <dd>
index dcd035c..be4a861 100644 (file)
@@ -29,9 +29,8 @@
 <!-- ####################################################### -->
 <hr />
 <p>There are numerous things that can be done to improve the ease with
-   which C++ binaries are debugged when using the GNU C++
-   tool chain. Here are some things to keep in mind when debugging C++
-   code with GNU tools.
+   which C++ binaries are debugged when using the GNU 
+   tool chain. Here are some of them.
 </p>
 
 <h3 class="left"><a name="gplusplus">Compiler flags determine debug info</a></h3>
    be varied to change debugging characteristics. For instance,
    turning off all optimization via the <code>-g -O0</code> flag will
    disable inlining, so that stepping through all functions, including
-   inlined constructors and destructors, is possible. Or, the debug
-   format that the compiler and debugger use to communicate
+   inlined constructors and destructors, is possible. In addition,
+   <code>-fno-eliminate-unused-debug-types<code> can be used when
+   additional debug information, such as nested class info, is desired.
+</p>
+
+<p>Or, the debug format that the compiler and debugger use to communicate
    information about source constructs can be changed via <code>
    -gdwarf-2 </code> or <code> -gstabs </code> flags: some debugging
    formats permit more expressive type and scope information to be
-   shown in gdb.
-   The default debug information for a particular platform can be
-   identified via the value set by the PREFERRED_DEBUGGING_TYPE macro
-   in the gcc sources.
+   shown in gdb.  The default debug information for a particular
+   platform can be identified via the value set by the
+   PREFERRED_DEBUGGING_TYPE macro in the gcc sources.
 </p>
 
 <p>Many other options are available: please see
    in Using the GNU Compiler Collection (GCC) for a complete list.
 </p>
 
-
 <h3 class="left"><a name="lib">Using special flags to make a debug binary</a></h3>
-<p>There are two ways to build libstdc++ with debug flags. The first
-   is to run make from the toplevel in a freshly-configured tree with
-   specialized debug <code>CXXFLAGS</code>, as in
-</p>
-<pre>
-     make CXXFLAGS='-g3 -O0' all
-</pre>
-
-<p>This quick and dirty approach is often sufficient for quick
-   debugging tasks, but the lack of state can be confusing in the long
-   term.
-</p>
-<p>A second approach is to use the configuration flags 
-</p>
+<p>If you would like debug symbols in libstdc++, there are two ways to
+  build libstdc++ with debug flags. The first is to run make from the
+  toplevel in a freshly-configured tree with
 <pre>
-     --enable-debug
+     --enable-libstdcxx-debug
 </pre>
 <p>and perhaps</p>
 <pre>
-     --enable-debug-flags='...'
+     --enable-libstdcxx-debug-flags='...'
 </pre>
 <p>to create a separate debug build. Both the normal build and the
    debug build will persist, without having to specify
    options</a> document.
 </p>
 
+<p>A second approach is to use the configuration flags 
+</p>
+<pre>
+     make CXXFLAGS='-g3 -O0' all
+</pre>
+
+<p>This quick and dirty approach is often sufficient for quick
+  debugging tasks, when you cannot or don't want to recompile your
+  application to use the <a href="#safe">debug mode</a>.</p>
+
+<h3 class="left"><a name="safe">The libstdc++ debug mode</a></h3>
+<p>By default, libstdc++ is built with efficiency in mind, and
+  therefore performs little or no error checking that is not required
+  by the C++ standard. This means that programs that incorrectly use
+  the C++ standard library will exhibit behavior that is not portable
+  and may not even be predictable, because they tread into 
+  implementation-specific or undefined behavior. To detect some of
+  these errors before they can become problematic, libstdc++ offers a
+  debug mode that provides additional checking of library facilities,
+  and will report errors in the use of libstdc++ as soon as they can
+  be detected by emitting a description of the problem to standard
+  error and aborting the program. </p>
+
+<p>The libstdc++ debug mode performs checking for many areas of the C++
+  standard, but the focus is on checking interactions among standard
+  iterators, containers, and algorithms, including:</p>
+
+  <ul>
+    <li><em>Safe iterators</em>: Iterators keep track of the
+    container whose elements they reference, so errors such as
+    incrementing a past-the-end iterator or dereferencing an iterator
+    that points to a container that has been destructed are diagnosed
+    immediately.</li>
+    
+    <li><em>Algorithm preconditions</em>: Algorithms attempt to
+    validate their input parameters to detect errors as early as
+    possible. For instance, the <code>set_intersection</code>
+    algorithm requires that its iterator
+    parameters <code>first1</code> and <code>last1</code> form a valid
+    iterator range, and that the sequence
+    [<code>first1</code>, <code>last1</code>) is sorted according to
+    the same predicate that was passed
+    to <code>set_intersection</code>; the libstdc++ debug mode will
+    detect an error if the sequence is not sorted or was sorted by a
+    different predicate.</li>
+  </ul>
+
+<h4 class="left">Using the libstdc++ debug mode</h4>
+<p>To use the libstdc++ debug mode, compile your application with the
+  compiler flag <code>-D_GLIBCXX_DEBUG</code>. Note that this flag
+  changes the sizes and behavior of standard class templates such
+  as <code>std::vector</code>, and therefore you can only link code
+  compiled with debug mode and code compiled without debug mode if no
+  instantiation of a container is passed between the two translation
+  units.</p>
+
+<p>For information about the design of the libstdc++ debug mode,
+  please see the <a href="debug_mode.html">libstdc++ debug mode design
+  document</a>.</p>
+
+<h4 class="left">Using the debugging containers without debug
+  mode</h4>
+<p>When it is not feasible to recompile your entire application, or
+  only specific containers need checking, debugging containers are
+  available as GNU extensions. These debugging containers are
+  functionally equivalent to the standard drop-in containers used in
+  debug mode, but they are available in a separate namespace as GNU
+  extensions and may be used in programs compiled with either release
+  mode or with debug mode. However, unlike the containers in namespace
+  <code>std</code>, these containers may not be specialized. The
+  following table provides the names and headers of the debugging
+  containers:
+
+<table title="Debugging containers" border="1">
+  <tr>
+    <th>Container</th>
+    <th>Header</th>
+    <th>Debug container</th>
+    <th>Debug header</th>
+  </tr>
+  <tr>
+    <td>std::bitset</td>
+    <td>&lt;bitset&gt;</td>
+    <td>__gnu_debug::bitset</td>
+    <td>&lt;debug/bitset&gt;</td>
+  </tr>
+  <tr>
+    <td>std::deque</td>
+    <td>&lt;deque&gt;</td>
+    <td>__gnu_debug::deque</td>
+    <td>&lt;debug/deque&gt;</td>
+  </tr>
+  <tr>
+    <td>std::list</td>
+    <td>&lt;list&gt;</td>
+    <td>__gnu_debug::list</td>
+    <td>&lt;debug/list&gt;</td>
+  </tr>
+  <tr>
+    <td>std::map</td>
+    <td>&lt;map&gt;</td>
+    <td>__gnu_debug::map</td>
+    <td>&lt;debug/map&gt;</td>
+  </tr>
+  <tr>
+    <td>std::multimap</td>
+    <td>&lt;map&gt;</td>
+    <td>__gnu_debug::multimap</td>
+    <td>&lt;debug/map&gt;</td>
+  </tr>
+  <tr>
+    <td>std::multiset</td>
+    <td>&lt;set&gt;</td>
+    <td>__gnu_debug::multiset</td>
+    <td>&lt;debug/set&gt;</td>
+  </tr>
+  <tr>
+    <td>std::set</td>
+    <td>&lt;set&gt;</td>
+    <td>__gnu_debug::set</td>
+    <td>&lt;debug/set&gt;</td>
+  </tr>
+  <tr>
+    <td>std::string</td>
+    <td>&lt;string&gt;</td>
+    <td>__gnu_debug::string</td>
+    <td>&lt;debug/string&gt;</td>
+  </tr>
+  <tr>
+    <td>std::wstring</td>
+    <td>&lt;string&gt;</td>
+    <td>__gnu_debug::wstring</td>
+    <td>&lt;debug/string&gt;</td>
+  </tr>
+  <tr>
+    <td>std::basic_string</td>
+    <td>&lt;string&gt;</td>
+    <td>__gnu_debug::basic_string</td>
+    <td>&lt;debug/string&gt;</td>
+  </tr>
+  <tr>
+    <td>std::vector</td>
+    <td>&lt;vector&gt;</td>
+    <td>__gnu_debug::vector</td>
+    <td>&lt;debug/vector&gt;</td>
+  </tr>
+  <tr>
+    <td>__gnu_cxx::hash_map</td>
+    <td>&lt;ext/hash_map&gt;</td>
+    <td>__gnu_debug::hash_map</td>
+    <td>&lt;debug/hash_map&gt;</td>
+  </tr>
+  <tr>
+    <td>__gnu_cxx::hash_multimap</td>
+    <td>&lt;ext/hash_map&gt;</td>
+    <td>__gnu_debug::hash_multimap</td>
+    <td>&lt;debug/hash_map&gt;</td>
+  </tr>
+  <tr>
+    <td>__gnu_cxx::hash_set</td>
+    <td>&lt;ext/hash_set&gt;</td>
+    <td>__gnu_debug::hash_set</td>
+    <td>&lt;debug/hash_set&gt;</td>
+  </tr>
+  <tr>
+    <td>__gnu_cxx::hash_multiset</td>
+    <td>&lt;ext/hash_set&gt;</td>
+    <td>__gnu_debug::hash_multiset</td>
+    <td>&lt;debug/hash_set&gt;</td>
+  </tr>
+</table>
+
+<h4 class="left">Debug mode semantics</h4>
+<p>A program that does not use the C++ standard library incorrectly
+  will maintain the same semantics under debug mode as it had with
+  the normal (release) library. All functional and exception-handling
+  guarantees made by the normal library also hold for the debug mode
+  library, with one exception: performance guarantees made by the
+  normal library may not hold in the debug mode library. For
+  instance, erasing an element in a <code>std::list</code> is a
+  constant-time operation in normal library, but in debug mode it is
+  linear in the number of iterators that reference that particular
+  list. So while your (correct) program won't change its results, it 
+  is likely to execute more slowly.</p>
+
+<p>libstdc++ includes many extensions to the C++ standard library. In
+  some cases the extensions are obvious, such as the hashed
+  associative containers, whereas other extensions give predictable
+  results to behavior that would otherwise be undefined, such as
+  throwing an exception when a <code>std::basic_string</code> is
+  constructed from a NULL character pointer. This latter category also
+  includes implementation-defined and unspecified semantics, such as
+  the growth rate of a vector. Use of these extensions is not
+  considered incorrect, so code that relies on them will not be
+  rejected by debug mode. However, use of these extensions may affect
+  the portability of code to other implementations of the C++ standard
+  library, and is therefore somewhat hazardous. For this reason, the
+  libstdc++ debug mode offers a "pedantic" mode (similar to
+  GCC's <code>-pedantic</code> compiler flag) that attempts to emulate
+  the semantics guaranteed by the C++ standard. In pedantic mode, for
+  instance, constructing a <code>std::basic_string</code> with a NULL
+  character pointer would result in an exception under normal mode or
+  non-pedantic debug mode (this is a libstdc++ extension), whereas
+  under pedantic debug mode libstdc++ would signal an error. To enable
+  the pedantic debug mode, compile your program with
+  both <code>-D_GLIBCXX_DEBUG</code>
+  and <code>-D_GLIBCXX_DEBUG_PEDANTIC</code> .</p>
+
+<p>The following library components provide extra debugging
+  capabilities in debug mode:</p>
+<ul>
+  <li><code>std::bitset</code></li>
+  <li><code>std::deque</code></li>
+  <li><code>__gnu_cxx::hash_map</code></li>
+  <li><code>__gnu_cxx::hash_multimap</code></li>
+  <li><code>__gnu_cxx::hash_multiset</code></li>
+  <li><code>__gnu_cxx::hash_set</code></li>
+  <li><code>std::list</code></li>
+  <li><code>std::map</code></li>
+  <li><code>std::multimap</code></li>
+  <li><code>std::multiset</code></li>
+  <li><code>std::set</code></li>
+  <li><code>std::vector</code></li>
+</ul>
+
 
 <h3 class="left"><a name="mem">Tips for memory leak hunting</a></h3>
 
    that can be used to provide detailed memory allocation information
    about C++ code. An exhaustive list of tools is not going to be
    attempted, but includes <code>mtrace</code>, <code>valgrind</code>,
-   <code>mudflap</code>, and <code>purify</code>. Also highly
-   recommended are <code>libcwd</code> and some other one that I
-   forget right now.
+   <code>mudflap</code>, and the non-free commercial product
+   <code>purify</code>. In addition, <code>libcwd</code> has a
+   replacement for the global new and delete operators that can track
+   memory allocation and deallocation and provide useful memory
+   statistics.
 </p>
 
 <p>Regardless of the memory debugging tool being used, there is one
 
 <p>In a nutshell, the default allocator used by <code>
    std::allocator</code> is a high-performance pool allocator, and can
-   give the mistaken impression that memory is being leaked, when in
-   reality the memory is still being used by the library and is reclaimed
-   after program termination.
+   give the mistaken impression that in a suspect executable, memory
+   is being leaked, when in reality the memory "leak" is a pool being
+   used by the library's allocator and is reclaimed after program
+   termination.
 </p>
 
 <p>For valgrind, there are some specific items to keep in mind. First
    versions should work at least as well. Second of all, use a
    completely unoptimized build to avoid confusing valgrind. Third,
    use GLIBCXX_FORCE_NEW to keep extraneous pool allocation noise from
-   cluttering debug information. 
+   cluttering debug information.
 </p>
 
 <p>Fourth, it may be necessary to force deallocation in other
diff --git a/libstdc++-v3/docs/html/debug_mode.html b/libstdc++-v3/docs/html/debug_mode.html
new file mode 100644 (file)
index 0000000..6ec7c4b
--- /dev/null
@@ -0,0 +1,547 @@
+<?xml version="1.0" encoding="ISO-8859-1"?>
+<!DOCTYPE html
+          PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
+          "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
+<head>
+   <meta name="AUTHOR" content="dgregor@apple.com (Doug Gregor)" />
+   <meta name="KEYWORDS" content="libstdc++, libstdc++-v3, GCC, g++, debug" />
+   <meta name="DESCRIPTION" content="Design of the libstdc++ debug mode." />
+   <meta name="GENERATOR" content="vi and eight fingers" />
+   <title>Design of the libstdc++ debug mode</title>
+<link rel="StyleSheet" href="lib3styles.css" />
+</head>
+<body>
+
+<h1 class="centered"><a name="top">Design of the libstdc++ debug mode</a></h1>
+
+<p class="fineprint"><em>
+   The latest version of this document is always available at
+   <a href="http://gcc.gnu.org/onlinedocs/libstdc++/debug_mode.html">
+   http://gcc.gnu.org/onlinedocs/libstdc++/debug_mode.html</a>.
+</em></p>
+
+<p><em>
+   To the <a href="http://gcc.gnu.org/libstdc++/">libstdc++-v3 homepage</a>.
+</em></p>
+
+
+<!-- ####################################################### -->
+
+<hr />
+<h1>Debug mode design</h1>
+<p> The libstdc++ debug mode replaces unsafe (but efficient) standard
+  containers and iterators with semantically equivalent safe standard
+  containers and iterators to aid in debugging user programs. The
+  following goals directed the design of the libstdc++ debug mode:</p>
+
+  <ul>
+
+    <li><b>Correctness</b>: the libstdc++ debug mode must not change
+    the semantics of the standard library for all cases specified in
+    the ANSI/ISO C++ standard. The essence of this constraint is that
+    any valid C++ program should behave in the same manner regardless
+    of whether it is compiled with debug mode or release mode. In
+    particular, entities that are defined in namespace std in release
+    mode should remain defined in namespace std in debug mode, so that
+    legal specializations of namespace std entities will remain
+    valid. A program that is not valid C++ (e.g., invokes undefined
+    behavior) is not required to behave similarly, although the debug
+    mode will abort with a diagnostic when it detects undefined
+    behavior.</li>
+
+    <li><b>Performance</b>: the additional of the libstdc++ debug mode
+    must not affect the performance of the library when it is compiled
+    in release mode. Performance of the libstdc++ debug mode is
+    secondary (and, in fact, will be worse than the release
+    mode).</li>
+
+    <li><b>Usability</b>: the libstdc++ debug mode should be easy to
+    use. It should be easily incorporated into the user's development
+    environment (e.g., by requiring only a single new compiler switch)
+    and should produce reasonable diagnostics when it detects a
+    problem with the user program. Usability also involves detection
+    of errors when using the debug mode incorrectly, e.g., by linking
+    a release-compiled object against a debug-compiled object if in
+    fact the resulting program will not run correctly.</li>
+
+    <li><b>Minimize recompilation</b>: While it is expected that
+    users recompile at least part of their program to use debug
+    mode, the amount of recompilation affects the
+    detect-compile-debug turnaround time. This indirectly affects the
+    usefulness of the debug mode, because debugging some applications
+    may require rebuilding a large amount of code, which may not be
+    feasible when the suspect code may be very localized. There are
+    several levels of conformance to this requirement, each with its
+    own usability and implementation characteristics. In general, the
+    higher-numbered conformance levels are more usable (i.e., require
+    less recompilation) but are more complicated to implement than
+    the lower-numbered conformance levels. 
+      <ol>
+       <li><b>Full recompilation</b>: The user must recompile his or
+       her entire application and all C++ libraries it depends on,
+       including the C++ standard library that ships with the
+       compiler. This must be done even if only a small part of the
+       program can use debugging features.</li>
+
+       <li><b>Full user recompilation</b>: The user must recompile
+       his or her entire application and all C++ libraries it depends
+       on, but not the C++ standard library itself. This must be done
+       even if only a small part of the program can use debugging
+       features. This can be achieved given a full recompilation
+       system by compiling two versions of the standard library when
+       the compiler is installed and linking against the appropriate
+       one, e.g., a multilibs approach.</li>
+
+       <li><b>Partial recompilation</b>: The user must recompile the
+       parts of his or her application and the C++ libraries it
+       depends on that will use the debugging facilities
+       directly. This means that any code that uses the debuggable
+       standard containers would need to be recompiled, but code
+       that does not use them (but may, for instance, use IOStreams)
+       would not have to be recompiled.</li>
+
+       <li><b>Per-use recompilation</b>: The user must recompile the
+       parts of his or her application and the C++ libraries it
+       depends on where debugging should occur, and any other code
+       that interacts with those containers. This means that a set of
+       translation units that accesses a particular standard
+       container instance may either be compiled in release mode (no
+       checking) or debug mode (full checking), but must all be
+       compiled in the same way; a translation unit that does not see
+       that standard container instance need not be recompiled. This
+       also means that a translation unit <em>A</em> that contains a
+       particular instantiation
+       (say, <code>std::vector&lt;int&gt;</code>) compiled in release
+       mode can be linked against a translation unit <em>B</em> that
+       contains the same instantiation compiled in debug mode (a
+       feature not present with partial recompilation). While this
+       behavior is technically a violation of the One Definition
+       Rule, this ability tends to be very important in
+       practice. The libstdc++ debug mode supports this level of
+       recompilation. </li>
+
+       <li><b>Per-unit recompilation</b>: The user must only
+       recompile the translation units where checking should occur,
+       regardless of where debuggable standard containers are
+       used. This has also been dubbed "<code>-g</code> mode",
+       because the <code>-g</code> compiler switch works in this way,
+       emitting debugging information at a per--translation-unit
+       granularity. We believe that this level of recompilation is in
+       fact not possible if we intend to supply safe iterators, leave
+       the program semantics unchanged, and not regress in
+       performance under release mode because we cannot associate
+       extra information with an iterator (to form a safe iterator)
+       without either reserving that space in release mode
+       (performance regression) or allocating extra memory associated
+       with each iterator with <code>new</code> (changes the program
+       semantics).</li>
+      </ol>
+    </li>
+  </ul>
+
+<h2><a name="other">Other implementations</a></h2>
+<p> There are several existing implementations of debug modes for C++
+  standard library implementations, although none of them directly
+  supports debugging for programs using libstdc++. The existing
+  implementations include:</p>
+<ul>
+  <li><a
+  href="http://www.mathcs.sjsu.edu/faculty/horstman/safestl.html">SafeSTL</a>:
+  SafeSTL was the original debugging version of the Standard Template
+  Library (STL), implemented by Cay S. Horstmann on top of the
+  Hewlett-Packard STL. Though it inspired much work in this area, it
+  has not been kept up-to-date for use with modern compilers or C++
+  standard library implementations.</li>
+
+  <li><a href="http://www.stlport.org/">STLport</a>: STLport is a free
+  implementation of the C++ standard library derived from the <a
+  href="http://www.sgi.com/tech/stl/">SGI implementation</a>, and
+  ported to many other platforms. It includes a debug mode that uses a
+  wrapper model (that in some way inspired the libstdc++ debug mode
+  design), although at the time of this writing the debug mode is
+  somewhat incomplete and meets only the "Full user recompilation" (2)
+  recompilation guarantee by requiring the user to link against a
+  different library in debug mode vs. release mode.</li>
+
+  <li><a href="http://www.metrowerks.com/mw/default.htm">Metrowerks
+  CodeWarrior</a>: The C++ standard library that ships with Metrowerks
+  CodeWarrior includes a debug mode. It is a full debug-mode
+  implementation (including debugging for CodeWarrior extensions) and
+  is easy to use, although it meets only the "Full recompilation" (1)
+  recompilation guarantee.</li>
+</ul>
+
+<h2><a name="design">Debug mode design methodology</a></h2>
+<p>This section provides an overall view of the design of the
+  libstdc++ debug mode and details the relationship between design
+  decisions and the stated design goals.</p>
+
+<h3><a name="wrappers">The wrapper model</a></h3>
+<p>The libstdc++ debug mode uses a wrapper model where the debugging
+  versions of library components (e.g., iterators and containers) form
+  a layer on top of the release versions of the library
+  components. The debugging components first verify that the operation
+  is correct (aborting with a diagnostic if an error is found) and
+  will then forward to the underlying release-mode container that will
+  perform the actual work. This design decision ensures that we cannot
+  regress release-mode performance (because the release-mode
+  containers are left untouched) and partially enables <a
+  href="#mixing">mixing debug and release code</a> at link time,
+  although that will not be discussed at this time.</p>
+
+<p>Two types of wrappers are used in the implementation of the debug
+  mode: container wrappers and iterator wrappers. The two types of
+  wrappers interact to maintain relationships between iterators and
+  their associated containers, which are necessary to detect certain
+  types of standard library usage errors such as dereferencing
+  past-the-end iterators or inserting into a container using an
+  iterator from a different container.</p>
+
+<h4><a name="safe_iterator">Safe iterators</a></h4>
+<p>Iterator wrappers provide a debugging layer over any iterator that
+  is attached to a particular container, and will manage the
+  information detailing the iterator's state (singular,
+  dereferenceable, etc.) and tracking the container to which the
+  iterator is attached. Because iterators have a well-defined, common
+  interface the iterator wrapper is implemented with the iterator
+  adaptor class template <code>__gnu_debug::_Safe_iterator</code>,
+  which takes two template parameters:</p>
+
+<ul>
+  <li><code>Iterator</code>: The underlying iterator type, which must
+    be either the <code>iterator</code> or <code>const_iterator</code>
+    typedef from the sequence type this iterator can reference.</li>
+  
+  <li><code>Sequence</code>: The type of sequence that this iterator
+  references. This sequence must be a safe sequence (discussed below)
+  whose <code>iterator</code> or <code>const_iterator</code> typedef
+  is the type of the safe iterator.</li>
+</ul>
+
+<h4><a name="safe_sequence">Safe sequences (containers)</a></h4>
+<p>Container wrappers provide a debugging layer over a particular
+  container type. Because containers vary greatly in the member
+  functions they support and the semantics of those member functions
+  (especially in the area of iterator invalidation), container
+  wrappers are tailored to the container they reference, e.g., the
+  debugging version of <code>std::list</code> duplicates the entire
+  interface of <code>std::list</code>, adding additional semantic
+  checks and then forwarding operations to the
+  real <code>std::list</code> (a public base class of the debugging
+  version) as appropriate. However, all safe containers inherit from
+  the class template <code>__gnu_debug::_Safe_sequence</code>,
+  instantiated with the type of the safe container itself (an instance
+  of the curiously recurring template pattern).</p>
+
+<p>The iterators of a container wrapper will be 
+  <a href="#safe_iterator">safe iterators</a> that reference sequences
+  of this type and wrap the iterators provided by the release-mode
+  base class. The debugging container will use only the safe
+  iterators within its own interface (therefore requiring the user to
+  use safe iterators, although this does not change correct user
+  code) and will communicate with the release-mode base class with
+  only the underlying, unsafe, release-mode iterators that the base
+  class exports.</p>
+
+<p> The debugging version of <code>std::list</code> will have the
+  following basic structure:</p>
+
+<pre>
+template&lt;typename _Tp, typename _Allocator = std::allocator&lt;_Tp&gt;
+  class debug-list :
+    public release-list&lt;_Tp, _Allocator&gt;,
+    public __gnu_debug::_Safe_sequence&lt;debug-list&lt;_Tp, _Allocator&gt; &gt;
+  {
+    typedef release-list&lt;_Tp, _Allocator&gt; _Base;
+    typedef debug-list&lt;_Tp, _Allocator&gt;   _Self;
+
+  public:
+    typedef __gnu_debug::_Safe_iterator&lt;typename _Base::iterator, _Self&gt;       iterator;
+    typedef __gnu_debug::_Safe_iterator&lt;typename _Base::const_iterator, _Self&gt; const_iterator;
+
+    // duplicate std::list interface with debugging semantics
+  };
+</pre>
+
+<h3><a name="precondition">Precondition checking</a></h3>
+<p>The debug mode operates primarily by checking the preconditions of
+  all standard library operations that it supports. Preconditions that
+  are always checked (regardless of whether or not we are in debug
+  mode) are checked via the <code>__check_xxx</code> macros defined
+  and documented in the source
+  file <code>include/debug/debug.h</code>. Preconditions that may or
+  may not be checked, depending on the debug-mode
+  macro <code>_GLIBCXX_DEBUG</code>, are checked via
+  the <code>__requires_xxx</code> macros defined and documented in the
+  same source file. Preconditions are validated using any additional
+  information available at run-time, e.g., the containers that are
+  associated with a particular iterator, the position of the iterator
+  within those containers, the distance between two iterators that may
+  form a valid range, etc. In the absence of suitable information,
+  e.g., an input iterator that is not a safe iterator, these
+  precondition checks will silently succeed.</p>
+
+<p>The majority of precondition checks use the aforementioned macros,
+  which have the secondary benefit of having prewritten debug
+  messages that use information about the current status of the
+  objects involved (e.g., whether an iterator is singular or what
+  sequence it is attached to) along with some static information
+  (e.g., the names of the function parameters corresponding to the
+  objects involved). When not using these macros, the debug mode uses
+  either the debug-mode assertion
+  macro <code>_GLIBCXX_DEBUG_ASSERT</code> , its pedantic
+  cousin <code>_GLIBCXX_DEBUG_PEDASSERT</code>, or the assertion
+  check macro that supports more advance formulation of error
+  messages, <code>_GLIBCXX_DEBUG_VERIFY</code>. These macros are
+  documented more thoroughly in the debug mode source code.</p>
+
+<h3><a name="coexistence">Release- and debug-mode coexistence</a></h3>
+<p>The libstdc++ debug mode is the first debug mode we know of that
+  is able to provide the "Per-use recompilation" (4) guarantee, that
+  allows release-compiled and debug-compiled code to be linked and
+  executed together without causing unpredictable behavior. This
+  guarantee minimizes the recompilation that users are required to
+  perform, shortening the detect-compile-debug bughunting cycle
+  and making the debug mode easier to incorporate into development
+  environments by minimizing dependencies.</p>
+
+<p>Achieving link- and run-time coexistence is not a trivial
+  implementation task. To achieve this goal we required a small
+  extension to the GNU C++ compiler (described in the section on
+  <a href="#mixing">link- and run-time coexistence</a>) and complex
+  organization of debug- and release-modes. The end result is that we
+  have achieved per-use recompilation but have had to give up some
+  checking of the <code>std::basic_string</code> class template
+  (namely, safe iterators).
+
+<h4><a name="compile_coexistence">Compile-time coexistence of release- and
+    debug-mode components</a></h4>
+<p>Both the release-mode components and the debug-mode
+  components need to exist within a single translation unit so that
+  the debug versions can wrap the release versions. However, only one
+  of these components should be user-visible at any particular
+  time with the standard name, e.g., <code>std::list</code>. In
+  release mode, we define only the release-mode version of the
+  component with its standard name and do not include the debugging
+  component at all (except, perhaps, in <code>__gnu_debug</code>, if
+  requested via the separate debugging headers). This method leaves the
+  behavior of release mode completely unchanged from its behavior
+  prior to the introduction of the libstdc++ debug mode.</p>
+
+<p>In debug mode we include the release-mode container into its
+  natural namespace but perform renaming to an implementation-defined
+  name using preprocessor macros. Thus the
+  release-mode <code>std::list</code> will be renamed
+  to <code>std::_Release_list</code> during debug mode, and we will
+  automatically include the debugging version with the
+  name <code>std::list</code> for users to reference. This method
+  allows the debug- and release-mode versions of the same component to
+  coexist at compile-time without causing an unreasonable maintenance
+  burden.</p>
+
+<h4><a name="mixing">Link- and run-time coexistence of release- and
+    debug-mode components</a></h4>
+<p>There is a problem with the simple compile-time coexistence
+  mechanism: if a user compiles some modules with release mode and
+  some modules with debug mode, the debuggable components will differ
+  in different translation units, violating the C++ One Definition
+  Rule (ODR). This violation will likely be detected at link time,
+  because the sizes of debug-mode containers will differ from the
+  sizes of release-mode containers, although in some cases (such as
+  dynamic linking) the error may be detected much later (or not at
+  all!).</p>
+
+<p>Unfortunately, it is not possible to avoid violating the ODR with
+  most debug mode designs (see the section on <a
+  href="#coexistence_alt">alternatives for coexistence</a>), so the
+  philosophy of the libstdc++ debug mode is to acknowledge that there
+  is an unavoidable ODR violation in this case but to ensure that the
+  ODR violation does not affect execution. To accomplish this, the
+  libstdc++ debug mode uses the aforementioned preprocessor renaming
+  scheme but includes an additional renaming scheme that happens at
+  compile-time that essentially reverses the preprocessor
+  renaming <em>from the linker's point of view</em>. Thus, in debug
+  mode, the release-mode <code>list</code> container is
+  named <code>std::_Release_list</code> but will be mangled with the
+  name <code>std::list</code> (as it was in release mode). Similarly,
+  the debug-mode <code>list</code> is named <code>std::list</code>
+  (in debug mode) but will be mangled
+  as <code>std::_Debug_list</code>. Thus the
+  release-mode <code>list</code> always compiles down to code that
+  uses the name <code>std::list</code>, and the
+  debug-mode <code>list</code> always compiles down to code that uses
+  the name <code>std::_Debug_list</code>, independent of the use of
+  debug mode. This has several positive effects:</p>
+
+<ul>
+  <li>No linking conflicts between debug/release objects: because the
+  names of the debug- and release-mode containers are different in the
+  compiled object files, there are no link-time conflicts between the
+  two.</li>
+
+  <li>Release-mode code is shared: the release-mode code can be shared
+  within a program, even with it is compiled partly in release-mode
+  and partly in debug-mode, because the release-mode code is unchanged
+  in name and function. This can decrease the size of mixed
+  debug/release binaries.</li>
+
+  <li>Able to catch <em>most</em> invalid debug/release combinations:
+  because the names of debug- and release-mode containers are
+  different in the compiled object files, if a debug/release
+  interaction cannot occur (e.g., because a container a translation
+  unit compiled in debug mode is passed to a routine in a translation
+  unit compiled in release mode) the result will be an undefined
+  symbol at link time. The undefined symbol occurs because the mangled
+  name of the definition will contain the release-mode container type
+  and the mangled name of the reference will contain the debug-mode
+  container type. However, we cannot detect these collisions if the
+  only use of the container is in the return type, because the return
+  type is not part of the mangled name of a function.</li>
+</ul>
+
+<p>The new <code>link_name</code> class attribute facilities
+  renaming. It may be attached to any class type (or any class
+  template) to override the name of the class used for name
+  mangling. For instance, a class named <code>bar</code> would
+  generally mangle as <code>3bar</code>; if the class has
+  a <code>link_name</code> attribute that specifies the string
+  "wibble", then it would mangle as <code>6wibble</code>.</p>
+
+<p>Note that although we have hidden the ODR violation, it still
+  exists. For this reason we cannot easily provide safe iterators for
+  the <code>std::basic_string</code> class template, as it is present
+  throughout the C++ standard library. For instance, locale facets
+  define typedefs that include <code>basic_string</code>: in a mixed
+  debug/release program, should that typedef be based on the
+  debug-mode <code>basic_string</code> or the
+  release-mode <code>basic_string</code>? While the answer could be
+  "both", and the difference hidden via renaming a la the
+  debug/release containers, we must note two things about locale
+  facets:</p>
+
+<ol>
+  <li>They exist as shared state: one can create a facet in one
+  translation unit and access the facet via the same type name in a
+  different translation unit. This means that we cannot have two
+  different versions of locale facets, because the types would not be
+  the same across debug/release-mode translation unit barriers.</li>
+
+  <li>They have virtual functions returning strings: these functions
+  mangle in the same way regardless of the mangling of their return
+  types (see above), and their precise signatures can be relied upon
+  by users because they may be overridden in derived classes.
+</ol>
+
+<p>With the design of libstdc++ debug mode, we cannot effectively hide
+  the differences between debug and release-mode strings from the
+  user. Failure to hide the differences may result in unpredictable
+  behavior, and for this reason we have opted to only
+  perform <code>basic_string</code> changes that do not require ABI
+  changes. The effect on users is expected to be minimal, as there are
+  simple alternatives (e.g., <code>__gnu_debug::basic_string</code>),
+  and the usability benefit we gain from the ability to mix debug- and
+  release-compiled translation units is enormous.</p>
+
+<h4><a name="coexistence_alt">Alternatives for Coexistence</a></h4>
+<p>The coexistence scheme was chosen over many alternatives,
+  including language-only solutions and solutions that also required
+  extensions to the C++ front end. The following is a partial list of
+  solutions, with justifications for our rejection of each.</p>
+
+<ul>
+  <li><em>Completely separate debug/release libraries</em>: This is by
+  far the simplest implementation option, where we do not allow any
+  coexistence of debug- and release-compiled translation units in a
+  program. This solution has an extreme negative affect on usability,
+  because it is quite likely that some libraries an application
+  depends on cannot be recompiled easily. This would not meet
+  our <b>usability</b> or <b>minimize recompilation</b> criteria
+  well.</li>
+
+  <li><em>Add a <code>Debug</code> boolean template parameter</em>:
+  Partial specialization could be used to select the debug
+  implementation when <code>Debug == true</code>, and the state
+  of <code>_GLIBCXX_DEBUG</code> could decide whether the
+  default <code>Debug</code> argument is <code>true</code>
+  or <code>false</code>. This option would break conformance with the
+  C++ standard in both debug <em>and</em> release modes. This would
+  not meet our <b>correctness</b> criteria. </li>
+
+  <li><em>Packaging a debug flag in the allocators</em>: We could
+    reuse the <code>Allocator</code> template parameter of containers
+    by adding a sentinel wrapper <code>debug&lt;&gt;</code> that
+    signals the user's intention to use debugging, and pick up
+    the <code>debug&lr;&gt;</code> allocator wrapper in a partial
+    specialization. However, this has two drawbacks: first, there is a
+    conformance issue because the default allocator would not be the
+    standard-specified <code>std::allocator&lt;T&gt;</code>. Secondly
+    (and more importantly), users that specify allocators instead of
+    implicitly using the default allocator would not get debugging
+    containers. Thus this solution fails the <b>correctness</b>
+    criteria.</li>
+
+  <li><em>Define debug containers in another namespace, and employ
+      a <code>using</code> declaration (or directive)</em>: This is an
+      enticing option, because it would eliminate the need for
+      the <code>link_name</code> extension by aliasing the
+      templates. However, there is no true template aliasing mechanism
+      is C++, because both <code>using</code> directives and using
+      declarations disallow specialization. This method fails
+      the <b>correctness</b> criteria.</li>
+
+  <li><em>Extension: allow template aliasing/renaming</em>: This is
+    the runner-up to the <code>link_name</code> solution, eliminated
+    only because it requires more extensive compiler changes
+    than <code>link_name</code>. In this model, we would define the
+    debug containers in a different namespace
+    (e.g., <code>__gnu_debug</code>) and then import them (e.g., with
+    an extended <code>using</code> declaration that aliases templates,
+    such as that of <a
+    href="http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1449.pdf">template
+    aliases</a> proposal). This solution is workable, and in fact
+    would be desirable in the long run, but requires a sizeable change
+    to the C++ compiler front-end that is not within the scope of
+    this project.</li>
+
+  <li><em>Extension: allow reopening on namespaces</em>: This would
+    allow the debug mode to effectively alias the
+    namespace <code>std</code> to an internal namespace, such
+    as <code>__gnu_std_debug</code>, so that it is completely
+    separate from the release-mode <code>std</code> namespace. While
+    this will solve some renaming problems and ensure that
+    debug- and release-compiled code cannot be mixed unsafely, it ensures that
+    debug- and release-compiled code cannot be mixed at all. For
+    instance, the program would have two <code>std::cout</code>
+    objects! This solution would fails the <b>minimize
+    recompilation</b> requirement, because we would only be able to
+    support option (1) or (2).</li>
+  </li>
+</ul>
+
+<p>Other options may exist for implementing the debug mode, many of
+  which have probably been considered and others that may still be
+  lurking. This list may be expanded over time to include other
+  options that we could have implemented, but in all cases the full
+  ramifications of the approach (as measured against the design goals
+  for a libstdc++ debug mode) should be considered first. The DejaGNU
+  testsuite includes some testcases that check for known problems with
+  some solutions (e.g., the <code>using</code> declaration solution
+  that breaks user specialization), and additional testcases will be
+  added as we are able to identify other typical problem cases. These
+  test cases will serve as a benchmark by which we can compare debug
+  mode implementations.</p>
+
+<!-- ####################################################### -->
+
+<hr />
+<p class="fineprint"><em>
+See <a href="17_intro/license.html">license.html</a> for copying conditions.
+Comments and suggestions are welcome, and may be sent to
+<a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.
+</em></p>
+
+
+</body>
+</html>
index 07d585f..6fb2c3a 100644 (file)
@@ -34,6 +34,7 @@
    <li><a href="#util">Utilities: abicheck and libv3test</a></li>
    <li><a href="#new">How to write a new test case</a></li>
    <li><a href="#check">Options for running the tests</a></li>
+   <li><a href="#debug">Running debug-mode tests</a></li>
    <li><a href="#future">Future</a></li>
    <li><a href="#internals">DejaGNU internals</a></li>
 </ul>
@@ -544,6 +545,19 @@ make check-target-libstdc++-v3 RUNTESTFLAGS="--target_board=arm-sim"
       for which files to examine.
    </p>
 
+<hr/>
+<h2><a name="debug">Running debug-mode tests</a></h2>
+<p>To run the libstdc++ test suite under the <a
+  href="debug.html#safe">debug mode</a>,
+  edit <code>libstdc++/scripts/testsuite_flags</code> to add the
+  compile-time flag <code>-D_GLIBCXX_DEBUG</code> to the result
+  printed by the <code>--build-cxx</code> option. Additionally, add
+  the <code>-D_GLIBCXX_DEBUG_PEDANTIC</code> flag to turn on pedantic
+  checking. The libstdc++ test suite should produce precisely the same
+  results under debug mode that it does under release mode: any
+  deviation indicates an error in either the library or the test
+  suite.</p>
+
 <hr />
 <h2><a name="future">Future</a></h2>
 
index 862b0a3..3af38b3 100644 (file)
@@ -224,7 +224,6 @@ ext_headers = \
        ${ext_srcdir}/hash_fun.h \
        ${ext_srcdir}/hashtable.h
 
-
 # This is the common subset of files that all three "C" header models use.
 c_base_srcdir = $(C_INCLUDE_DIR)
 c_base_builddir = .
@@ -290,6 +289,34 @@ c_compatibility_headers = \
        ${c_compatibility_srcdir}/wchar.h \
        ${c_compatibility_srcdir}/wctype.h
 
+# Debug mode headers
+debug_srcdir = ${glibcxx_srcdir}/include/debug
+debug_builddir = ./debug
+debug_headers = \
+       ${debug_srcdir}/bitset \
+       ${debug_srcdir}/debug.h \
+       ${debug_srcdir}/deque \
+       ${debug_srcdir}/formatter.h \
+       ${debug_srcdir}/hash_map \
+       ${debug_srcdir}/hash_map.h \
+       ${debug_srcdir}/hash_multimap.h \
+       ${debug_srcdir}/hash_multiset.h \
+       ${debug_srcdir}/hash_set \
+       ${debug_srcdir}/hash_set.h \
+       ${debug_srcdir}/list \
+       ${debug_srcdir}/map \
+       ${debug_srcdir}/map.h \
+       ${debug_srcdir}/multimap.h \
+       ${debug_srcdir}/multiset.h \
+       ${debug_srcdir}/safe_base.h \
+       ${debug_srcdir}/safe_iterator.h \
+       ${debug_srcdir}/safe_iterator.tcc \
+       ${debug_srcdir}/safe_sequence.h \
+       ${debug_srcdir}/set \
+       ${debug_srcdir}/set.h \
+       ${debug_srcdir}/string \
+       ${debug_srcdir}/vector
+
 # Some of the different "C" header models need extra files.
 # Some "C" header schemes require the "C" compatibility headers.
 # For --enable-cheaders=c_std
@@ -350,7 +377,7 @@ endif
 # CLEANFILES and all-local are kept up-to-date.
 allstamped = \
        stamp-std stamp-bits stamp-c_base stamp-c_compatibility \
-       stamp-backward stamp-ext stamp-host
+       stamp-backward stamp-ext stamp-debug stamp-host
 
 # List of all files that are created by explicit building, editing, or
 # catenation.
@@ -429,6 +456,15 @@ stamp-ext: ${ext_headers}
        fi ;\
        $(STAMP) stamp-ext
 
+stamp-debug: ${debug_headers}
+       @if [ ! -d "${debug_builddir}" ]; then \
+         mkdir -p ${debug_builddir} ;\
+       fi ;\
+       if [ ! -f stamp-debug ]; then \
+         (cd ${debug_builddir} && @LN_S@ $? . || true) ;\
+       fi ;\
+       $(STAMP) stamp-debug
+
 stamp-${host_alias}:
        @if [ ! -d ${host_builddir} ]; then \
          mkdir -p ${host_builddir} ;\
@@ -556,6 +592,9 @@ install-headers:
        $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${std_builddir}
        for file in ${std_headers_rename}; do \
          $(INSTALL_DATA) ${std_builddir}/$${file} $(DESTDIR)${gxx_include_dir}/${std_builddir}; done
+       $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${debug_builddir}
+       for file in ${debug_headers}; do \
+         $(INSTALL_DATA) $${file} $(DESTDIR)${gxx_include_dir}/${debug_builddir}; done
        $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${host_builddir}
        for file in ${host_headers} ${host_headers_extra} \
         ${thread_host_headers}; do \
index 1db9bfc..cf40dcf 100644 (file)
@@ -491,11 +491,40 @@ c_compatibility_headers = \
        ${c_compatibility_srcdir}/wctype.h
 
 
+# Debug mode headers
+debug_srcdir = ${glibcxx_srcdir}/include/debug
+debug_builddir = ./debug
+debug_headers = \
+       ${debug_srcdir}/bitset \
+       ${debug_srcdir}/debug.h \
+       ${debug_srcdir}/deque \
+       ${debug_srcdir}/formatter.h \
+       ${debug_srcdir}/hash_map \
+       ${debug_srcdir}/hash_map.h \
+       ${debug_srcdir}/hash_multimap.h \
+       ${debug_srcdir}/hash_multiset.h \
+       ${debug_srcdir}/hash_set \
+       ${debug_srcdir}/hash_set.h \
+       ${debug_srcdir}/list \
+       ${debug_srcdir}/map \
+       ${debug_srcdir}/map.h \
+       ${debug_srcdir}/multimap.h \
+       ${debug_srcdir}/multiset.h \
+       ${debug_srcdir}/safe_base.h \
+       ${debug_srcdir}/safe_iterator.h \
+       ${debug_srcdir}/safe_iterator.tcc \
+       ${debug_srcdir}/safe_sequence.h \
+       ${debug_srcdir}/set \
+       ${debug_srcdir}/set.h \
+       ${debug_srcdir}/string \
+       ${debug_srcdir}/vector
+
+@GLIBCXX_C_HEADERS_C_STD_FALSE@c_base_headers_extra = 
+
 # Some of the different "C" header models need extra files.
 # Some "C" header schemes require the "C" compatibility headers.
 # For --enable-cheaders=c_std
 @GLIBCXX_C_HEADERS_C_STD_TRUE@c_base_headers_extra = ${c_base_srcdir}/cmath.tcc
-@GLIBCXX_C_HEADERS_C_STD_FALSE@c_base_headers_extra = 
 @GLIBCXX_C_HEADERS_COMPATIBILITY_FALSE@c_compatibility_headers_extra = 
 
 @GLIBCXX_C_HEADERS_COMPATIBILITY_TRUE@c_compatibility_headers_extra = ${c_compatibility_headers}
@@ -546,7 +575,7 @@ PCHFLAGS = -Winvalid-pch -Wno-deprecated -x c++-header $(CXXFLAGS)
 # CLEANFILES and all-local are kept up-to-date.
 allstamped = \
        stamp-std stamp-bits stamp-c_base stamp-c_compatibility \
-       stamp-backward stamp-ext stamp-host
+       stamp-backward stamp-ext stamp-debug stamp-host
 
 
 # List of all files that are created by explicit building, editing, or
@@ -783,6 +812,15 @@ stamp-ext: ${ext_headers}
        fi ;\
        $(STAMP) stamp-ext
 
+stamp-debug: ${debug_headers}
+       @if [ ! -d "${debug_builddir}" ]; then \
+         mkdir -p ${debug_builddir} ;\
+       fi ;\
+       if [ ! -f stamp-debug ]; then \
+         (cd ${debug_builddir} && @LN_S@ $? . || true) ;\
+       fi ;\
+       $(STAMP) stamp-debug
+
 stamp-${host_alias}:
        @if [ ! -d ${host_builddir} ]; then \
          mkdir -p ${host_builddir} ;\
@@ -904,6 +942,9 @@ install-headers:
        $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${std_builddir}
        for file in ${std_headers_rename}; do \
          $(INSTALL_DATA) ${std_builddir}/$${file} $(DESTDIR)${gxx_include_dir}/${std_builddir}; done
+       $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${debug_builddir}
+       for file in ${debug_headers}; do \
+         $(INSTALL_DATA) $${file} $(DESTDIR)${gxx_include_dir}/${debug_builddir}; done
        $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${host_builddir}
        for file in ${host_headers} ${host_headers_extra} \
         ${thread_host_headers}; do \
index 44df752..7b1ba5c 100644 (file)
@@ -43,6 +43,7 @@
 #pragma GCC system_header
 
 #include <bits/atomicity.h>
+#include <debug/debug.h>
 
 namespace std
 {
@@ -608,7 +609,10 @@ namespace std
        */
       const_reference
       operator[] (size_type __pos) const
-      { return _M_data()[__pos]; }
+      { 
+       _GLIBCXX_DEBUG_ASSERT(__pos <= size());
+       return _M_data()[__pos]; 
+      }
 
       /**
        *  @brief  Subscript access to the data contained in the %string.
@@ -623,6 +627,7 @@ namespace std
       reference
       operator[](size_type __pos)
       {
+       _GLIBCXX_DEBUG_ASSERT(__pos < size());
        _M_leak();
        return _M_data()[__pos];
       }
@@ -729,7 +734,10 @@ namespace std
        */
       basic_string&
       append(const _CharT* __s)
-      { return this->append(__s, traits_type::length(__s)); }
+      { 
+       __glibcxx_requires_string(__s);
+       return this->append(__s, traits_type::length(__s)); 
+      }
 
       /**
        *  @brief  Append multiple characters.
@@ -810,7 +818,10 @@ namespace std
        */
       basic_string&
       assign(const _CharT* __s)
-      { return this->assign(__s, traits_type::length(__s)); }
+      { 
+       __glibcxx_requires_string(__s);
+       return this->assign(__s, traits_type::length(__s)); 
+      }
 
       /**
        *  @brief  Set value to multiple characters.
@@ -942,7 +953,10 @@ namespace std
       */
       basic_string&
       insert(size_type __pos, const _CharT* __s)
-      { return this->insert(__pos, __s, traits_type::length(__s)); }
+      { 
+       __glibcxx_requires_string(__s);
+       return this->insert(__pos, __s, traits_type::length(__s)); 
+      }
 
       /**
        *  @brief  Insert multiple characters.
@@ -983,6 +997,7 @@ namespace std
       iterator
       insert(iterator __p, _CharT __c)
       {
+       _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
        const size_type __pos = __p - _M_ibegin();
        this->insert(_M_check(__pos), size_type(1), __c);
        _M_rep()->_M_set_leaked();
@@ -1043,6 +1058,8 @@ namespace std
       iterator
       erase(iterator __position)
       {
+       _GLIBCXX_DEBUG_PEDASSERT(__position >= _M_ibegin() 
+                                && __position < _M_iend());
        const size_type __i = __position - _M_ibegin();
         this->replace(__position, __position + 1, _M_data(), _M_data());
        _M_rep()->_M_set_leaked();
@@ -1064,6 +1081,8 @@ namespace std
       iterator
       erase(iterator __first, iterator __last)
       {
+       _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
+                                && __last <= _M_iend());
         const size_type __i = __first - _M_ibegin();
        this->replace(__first, __last, _M_data(), _M_data());
        _M_rep()->_M_set_leaked();
@@ -1150,7 +1169,10 @@ namespace std
       */
       basic_string&
       replace(size_type __pos, size_type __n1, const _CharT* __s)
-      { return this->replace(__pos, __n1, __s, traits_type::length(__s)); }
+      { 
+       __glibcxx_requires_string(__s);
+       return this->replace(__pos, __n1, __s, traits_type::length(__s)); 
+      }
 
       /**
        *  @brief  Replace characters with multiple characters.
@@ -1187,7 +1209,11 @@ namespace std
       */
       basic_string&
       replace(iterator __i1, iterator __i2, const basic_string& __str)
-      { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
+      { 
+       _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
+                                && __i2 <= _M_iend());
+       return this->replace(__i1, __i2, __str._M_data(), __str.size()); 
+      }
 
       /**
        *  @brief  Replace range of characters with C substring.
@@ -1205,7 +1231,7 @@ namespace std
       */
       basic_string&
       replace(iterator __i1, iterator __i2,
-                           const _CharT* __s, size_type __n)
+             const _CharT* __s, size_type __n)
       { return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n); }
 
       /**
@@ -1223,7 +1249,12 @@ namespace std
       */
       basic_string&
       replace(iterator __i1, iterator __i2, const _CharT* __s)
-      { return this->replace(__i1, __i2, __s, traits_type::length(__s)); }
+      { 
+       _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
+                                && __i2 <= _M_iend());
+       __glibcxx_requires_string(__s);
+       return this->replace(__i1, __i2, __s, traits_type::length(__s)); 
+      }
 
       /**
        *  @brief  Replace range of characters with multiple characters
@@ -1241,7 +1272,11 @@ namespace std
       */
       basic_string&
       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
-      { return _M_replace_aux(__i1, __i2, __n, __c); }
+      { 
+       _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
+                                && __i2 <= _M_iend());
+       return _M_replace_aux(__i1, __i2, __n, __c); 
+      }
 
       /**
        *  @brief  Replace range of characters with range.
@@ -1261,30 +1296,55 @@ namespace std
         basic_string&
         replace(iterator __i1, iterator __i2,
                _InputIterator __k1, _InputIterator __k2)
-        { typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
-         return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral()); }
+        { 
+         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
+                                  && __i2 <= _M_iend());
+         __glibcxx_requires_valid_range(__k1, __k2);
+         typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
+         return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral()); 
+       }
 
       // Specializations for the common case of pointer and iterator:
       // useful to avoid the overhead of temporary buffering in _M_replace.
       basic_string&
-      replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
-        { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
-                              __k1, __k2 - __k1); }
+        replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
+        { 
+         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
+                                  && __i2 <= _M_iend());
+         __glibcxx_requires_valid_range(__k1, __k2);
+         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
+                              __k1, __k2 - __k1); 
+       }
 
       basic_string&
-      replace(iterator __i1, iterator __i2, const _CharT* __k1, const _CharT* __k2)
-        { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
-                              __k1, __k2 - __k1); }
+        replace(iterator __i1, iterator __i2, 
+               const _CharT* __k1, const _CharT* __k2)
+        { 
+         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
+                                  && __i2 <= _M_iend());
+         __glibcxx_requires_valid_range(__k1, __k2);
+         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
+                              __k1, __k2 - __k1); 
+       }
 
       basic_string&
-      replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
-        { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
+        replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
+        { 
+         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
+                                  && __i2 <= _M_iend());
+         __glibcxx_requires_valid_range(__k1, __k2);
+         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
                               __k1.base(), __k2 - __k1);
        }
 
       basic_string&
-      replace(iterator __i1, iterator __i2, const_iterator __k1, const_iterator __k2)
-        { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
+        replace(iterator __i1, iterator __i2, 
+               const_iterator __k1, const_iterator __k2)
+        { 
+         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
+                                  && __i2 <= _M_iend());
+         __glibcxx_requires_valid_range(__k1, __k2);
+         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
                               __k1.base(), __k2 - __k1);
        }
 
@@ -1459,7 +1519,10 @@ namespace std
       */
       size_type
       find(const _CharT* __s, size_type __pos = 0) const
-      { return this->find(__s, __pos, traits_type::length(__s)); }
+      { 
+       __glibcxx_requires_string(__s);
+       return this->find(__s, __pos, traits_type::length(__s)); 
+      }
 
       /**
        *  @brief  Find position of a character.
@@ -1514,7 +1577,10 @@ namespace std
       */
       size_type
       rfind(const _CharT* __s, size_type __pos = npos) const
-      { return this->rfind(__s, __pos, traits_type::length(__s)); }
+      { 
+       __glibcxx_requires_string(__s);
+       return this->rfind(__s, __pos, traits_type::length(__s)); 
+      }
 
       /**
        *  @brief  Find last position of a character.
@@ -1569,7 +1635,10 @@ namespace std
       */
       size_type
       find_first_of(const _CharT* __s, size_type __pos = 0) const
-      { return this->find_first_of(__s, __pos, traits_type::length(__s)); }
+      { 
+       __glibcxx_requires_string(__s);
+       return this->find_first_of(__s, __pos, traits_type::length(__s)); 
+      }
 
       /**
        *  @brief  Find position of a character.
@@ -1627,7 +1696,10 @@ namespace std
       */
       size_type
       find_last_of(const _CharT* __s, size_type __pos = npos) const
-      { return this->find_last_of(__s, __pos, traits_type::length(__s)); }
+      { 
+       __glibcxx_requires_string(__s);
+       return this->find_last_of(__s, __pos, traits_type::length(__s)); 
+      }
 
       /**
        *  @brief  Find last position of a character.
@@ -1686,7 +1758,10 @@ namespace std
       */
       size_type
       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
-      { return this->find_first_not_of(__s, __pos, traits_type::length(__s)); }
+      { 
+       __glibcxx_requires_string(__s);
+       return this->find_first_not_of(__s, __pos, traits_type::length(__s)); 
+      }
 
       /**
        *  @brief  Find position of a different character.
@@ -1742,7 +1817,10 @@ namespace std
       */
       size_type
       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
-      { return this->find_last_not_of(__s, __pos, traits_type::length(__s)); }
+      { 
+       __glibcxx_requires_string(__s);
+       return this->find_last_not_of(__s, __pos, traits_type::length(__s)); 
+      }
 
       /**
        *  @brief  Find last position of a different character.
@@ -2197,7 +2275,6 @@ namespace std
             const basic_string<_CharT, _Traits, _Alloc>& __rhs)
     { return __rhs.compare(__lhs) <= 0; }
 
-
   /**
    *  @brief  Swap contents of two strings.
    *  @param lhs  First string.
index ecd8f71..34a373c 100644 (file)
 
 namespace std
 {
+  template<typename _Type>
+    inline bool
+    __is_null_pointer(_Type* __ptr)
+    { return __ptr == 0; }
+
+  template<typename _Type>
+    inline bool
+    __is_null_pointer(const _Type&)
+    { return false; }
+
   template<typename _CharT, typename _Traits, typename _Alloc>
     const typename basic_string<_CharT, _Traits, _Alloc>::size_type 
     basic_string<_CharT, _Traits, _Alloc>::
@@ -141,8 +151,8 @@ namespace std
        if (__beg == __end && __a == _Alloc())
          return _S_empty_rep()._M_refdata();
 
-       // NB: Not required, but considered best practice.
-       if (__builtin_expect(__beg == _InIterator(), 0))
+       // NB: Not required, but considered best practice. 
+       if (__builtin_expect(__is_null_pointer(__beg), 0))
          __throw_logic_error("basic_string::_S_construct NULL not valid");
 
        const size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
@@ -215,12 +225,14 @@ namespace std
                               __str._M_fold(__pos, __n), __a), __a)
     { }
 
+  // TBD: DPG annotate
   template<typename _CharT, typename _Traits, typename _Alloc>
     basic_string<_CharT, _Traits, _Alloc>::
     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
     { }
 
+  // TBD: DPG annotate
   template<typename _CharT, typename _Traits, typename _Alloc>
     basic_string<_CharT, _Traits, _Alloc>::
     basic_string(const _CharT* __s, const _Alloc& __a)
@@ -233,7 +245,8 @@ namespace std
     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
     : _M_dataplus(_S_construct(__n, __c, __a), __a)
     { }
+
+  // TBD: DPG annotate 
   template<typename _CharT, typename _Traits, typename _Alloc>
     template<typename _InputIterator>
     basic_string<_CharT, _Traits, _Alloc>::
@@ -275,6 +288,7 @@ namespace std
      basic_string<_CharT, _Traits, _Alloc>::
      assign(const _CharT* __s, size_type __n)
      {
+       __glibcxx_requires_string_len(__s, __n);
        if (__n > this->max_size())
         __throw_length_error("basic_string::assign");
        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
@@ -313,6 +327,7 @@ namespace std
      basic_string<_CharT, _Traits, _Alloc>::
      insert(size_type __pos, const _CharT* __s, size_type __n)
      {
+       __glibcxx_requires_string_len(__s, __n);
        const size_type __size = this->size();
        if (__pos > __size)
          __throw_out_of_range("basic_string::insert");
@@ -350,6 +365,7 @@ namespace std
      replace(size_type __pos, size_type __n1, const _CharT* __s,
             size_type __n2)
      {
+       __glibcxx_requires_string_len(__s, __n2);
        const size_type __size = this->size();
        if (__pos > __size)
          __throw_out_of_range("basic_string::replace");
@@ -727,6 +743,7 @@ namespace std
     basic_string<_CharT, _Traits, _Alloc>::
     append(const _CharT* __s, size_type __n)
     {
+      __glibcxx_requires_string_len(__s, __n);
       const size_type __len = __n + this->size();
       if (__len > this->capacity())
        this->reserve(__len);
@@ -749,6 +766,7 @@ namespace std
     operator+(const _CharT* __lhs,
              const basic_string<_CharT, _Traits, _Alloc>& __rhs)
     {
+      __glibcxx_requires_string(__lhs);
       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
       typedef typename __string_type::size_type          __size_type;
       const __size_type __len = _Traits::length(__lhs);
@@ -783,6 +801,8 @@ namespace std
       
       if (__n > this->size() - __pos)
        __n = this->size() - __pos;
+
+      __glibcxx_requires_string_len(__s, __n);
       
       traits_type::copy(__s, _M_data() + __pos, __n);
       // 21.3.5.7 par 3: do not append null.  (good.)
@@ -794,6 +814,8 @@ namespace std
     basic_string<_CharT, _Traits, _Alloc>::
     find(const _CharT* __s, size_type __pos, size_type __n) const
     {
+      __glibcxx_requires_string_len(__s, __n);
+
       const size_type __size = this->size();
       size_t __xpos = __pos;
       const _CharT* __data = _M_data();
@@ -827,6 +849,8 @@ namespace std
     basic_string<_CharT, _Traits, _Alloc>::
     rfind(const _CharT* __s, size_type __pos, size_type __n) const
     {
+      __glibcxx_requires_string_len(__s, __n);
+
       const size_type __size = this->size();
       if (__n <= __size)
        {
@@ -866,6 +890,8 @@ namespace std
     basic_string<_CharT, _Traits, _Alloc>::
     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
     {
+      __glibcxx_requires_string_len(__s, __n);
+
       for (; __n && __pos < this->size(); ++__pos)
        {
          const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
@@ -880,6 +906,8 @@ namespace std
     basic_string<_CharT, _Traits, _Alloc>::
     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
     {
+      __glibcxx_requires_string_len(__s, __n);
+
       size_type __size = this->size();
       if (__size && __n)
        { 
@@ -900,6 +928,8 @@ namespace std
     basic_string<_CharT, _Traits, _Alloc>::
     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
     {
+      __glibcxx_requires_string_len(__s, __n);
+
       size_t __xpos = __pos;
       for (; __xpos < this->size(); ++__xpos)
        if (!traits_type::find(__s, __n, _M_data()[__xpos]))
@@ -924,6 +954,8 @@ namespace std
     basic_string<_CharT, _Traits, _Alloc>::
     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
     {
+      __glibcxx_requires_string_len(__s, __n);
+
       size_type __size = this->size();
       if (__size)
        { 
@@ -1004,6 +1036,8 @@ namespace std
     basic_string<_CharT, _Traits, _Alloc>::
     compare(const _CharT* __s) const
     {
+      __glibcxx_requires_string(__s);
+
       const size_type __size = this->size();
       const size_type __osize = traits_type::length(__s);
       const size_type __len = std::min(__size, __osize);
@@ -1019,6 +1053,8 @@ namespace std
     basic_string <_CharT, _Traits, _Alloc>::
     compare(size_type __pos, size_type __n1, const _CharT* __s) const
     {
+      __glibcxx_requires_string(__s);
+
       const size_type __size = this->size();
       if (__pos > __size)
        __throw_out_of_range("basic_string::compare");
@@ -1038,6 +1074,8 @@ namespace std
     compare(size_type __pos, size_type __n1, const _CharT* __s, 
            size_type __n2) const
     {
+      __glibcxx_requires_string_len(__s, __n2);
+
       const size_type __size = this->size();
       if (__pos > __size)
        __throw_out_of_range("basic_string::compare");
index d6ce9ed..6a0fb79 100644 (file)
 # define _GLIBCXX_EXTERN_TEMPLATE 1
 #endif
 
-// To enable older, ARM-style iostreams and other anachronisms use this.
-//#define _GLIBCXX_DEPRECATED 1
+// To enable debug mode.
+namespace __gnu_norm 
+{ 
+  using namespace std; 
+}
 
-// Use corrected code from the committee library group's issues list.
-//#define _GLIBCXX_RESOLVE_LIB_DEFECTS 1
+namespace __gnu_debug_def { }
+
+namespace __gnu_debug 
+{ 
+  using namespace std; 
+  using namespace __gnu_debug_def __attribute__ ((strong));
+}
+
+namespace std
+{
+#ifdef _GLIBCXX_DEBUG
+  using namespace __gnu_debug_def __attribute__ ((strong));
+#else
+  using namespace __gnu_norm __attribute__ ((strong));
+#endif
+}
 
 // The remainder of the prewritten config is automatic; all the
 // user hooks are listed above.
index dedab6a..9f01eed 100644 (file)
@@ -61,7 +61,7 @@
 #ifndef _DEQUE_TCC
 #define _DEQUE_TCC 1
 
-namespace std
+namespace __gnu_norm
 { 
   template <typename _Tp, typename _Alloc>
     deque<_Tp,_Alloc>&
@@ -707,6 +707,6 @@ namespace std
       this->_M_start._M_set_node(__new_nstart);
       this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
     }
-} // namespace std 
+} // namespace __gnu_norm
   
 #endif
index 9c5a0cd..283b0ac 100644 (file)
@@ -61,7 +61,7 @@
 #ifndef _LIST_TCC
 #define _LIST_TCC 1
 
-namespace std
+namespace __gnu_norm
 {
   template<typename _Tp, typename _Alloc>
     void
@@ -409,6 +409,6 @@ namespace std
         swap(__counter[__fill-1]);
       }
     }
-} // namespace std
+} // namespace __gnu_norm
 
 #endif /* _LIST_TCC */
index 70ef219..7cb54eb 100644 (file)
 
 #include <bits/stl_heap.h>
 #include <bits/stl_tempbuf.h>     // for _Temporary_buffer
+#include <debug/debug.h>
 
 // See concept_check.h for the __glibcxx_*_requires macros.
 
 namespace std
 {
-
   /**
    *  @brief Find the median of three values.
    *  @param  a  A value.
@@ -153,6 +153,7 @@ namespace std
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
       for ( ; __first != __last; ++__first)
        __f(*__first);
       return __f;
@@ -295,6 +296,7 @@ namespace std
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_EqualOpConcept<
                typename iterator_traits<_InputIterator>::value_type, _Tp>)
+      __glibcxx_requires_valid_range(__first, __last);
       return std::find(__first, __last, __val, std::__iterator_category(__first));
     }
 
@@ -315,6 +317,7 @@ namespace std
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
              typename iterator_traits<_InputIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
       return std::find_if(__first, __last, __pred, std::__iterator_category(__first));
     }
 
@@ -334,6 +337,7 @@ namespace std
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_EqualityComparableConcept<
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
       if (__first == __last)
        return __last;
       _ForwardIterator __next = __first;
@@ -365,6 +369,7 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
            typename iterator_traits<_ForwardIterator>::value_type,
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
       if (__first == __last)
        return __last;
       _ForwardIterator __next = __first;
@@ -393,6 +398,7 @@ namespace std
       __glibcxx_function_requires(_EqualityComparableConcept<
            typename iterator_traits<_InputIterator>::value_type >)
       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
+      __glibcxx_requires_valid_range(__first, __last);
       typename iterator_traits<_InputIterator>::difference_type __n = 0;
       for ( ; __first != __last; ++__first)
        if (*__first == __value)
@@ -416,6 +422,7 @@ namespace std
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
            typename iterator_traits<_InputIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
       typename iterator_traits<_InputIterator>::difference_type __n = 0;
       for ( ; __first != __last; ++__first)
        if (__pred(*__first))
@@ -458,7 +465,8 @@ namespace std
       __glibcxx_function_requires(_EqualOpConcept<
            typename iterator_traits<_ForwardIterator1>::value_type,
            typename iterator_traits<_ForwardIterator2>::value_type>)
-
+      __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_valid_range(__first2, __last2);
       // Test for empty ranges
       if (__first1 == __last1 || __first2 == __last2)
        return __first1;
@@ -531,6 +539,8 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
            typename iterator_traits<_ForwardIterator1>::value_type,
            typename iterator_traits<_ForwardIterator2>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_valid_range(__first2, __last2);
 
       // Test for empty ranges
       if (__first1 == __last1 || __first2 == __last2)
@@ -603,6 +613,7 @@ namespace std
       __glibcxx_function_requires(_EqualityComparableConcept<
            typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__count <= 0)
        return __first;
@@ -651,6 +662,7 @@ namespace std
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
            typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__count <= 0)
        return __first;
@@ -708,6 +720,7 @@ namespace std
       __glibcxx_function_requires(_ConvertibleConcept<
            typename iterator_traits<_ForwardIterator2>::value_type,
            typename iterator_traits<_ForwardIterator1>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
 
       for ( ; __first1 != __last1; ++__first1, ++__first2)
        std::iter_swap(__first1, __first2);
@@ -739,6 +752,7 @@ namespace std
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
             // "the type returned by a _UnaryOperation"
             __typeof__(__unary_op(*__first))>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first, ++__result)
        *__result = __unary_op(*__first);
@@ -775,6 +789,7 @@ namespace std
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
             // "the type returned by a _BinaryOperation"
             __typeof__(__binary_op(*__first1,*__first2))>)
+      __glibcxx_requires_valid_range(__first1, __last1);
 
       for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
        *__result = __binary_op(*__first1, *__first2);
@@ -804,6 +819,7 @@ namespace std
            typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first)
        if (*__first == __old_value)
@@ -833,6 +849,7 @@ namespace std
            typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first)
        if (__pred(*__first))
@@ -865,6 +882,7 @@ namespace std
            typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_function_requires(_EqualOpConcept<
            typename iterator_traits<_InputIterator>::value_type, _Tp>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first, ++__result)
        *__result = *__first == __old_value ? __new_value : *__first;
@@ -898,6 +916,7 @@ namespace std
            typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
            typename iterator_traits<_InputIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first, ++__result)
        *__result = __pred(*__first) ? __new_value : *__first;
@@ -923,6 +942,7 @@ namespace std
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_GeneratorConcept<_Generator,
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first)
        *__first = __gen();
@@ -977,6 +997,7 @@ namespace std
            typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_function_requires(_EqualOpConcept<
            typename iterator_traits<_InputIterator>::value_type, _Tp>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first)
        if (!(*__first == __value)) {
@@ -1011,6 +1032,7 @@ namespace std
            typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
            typename iterator_traits<_InputIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first)
        if (!__pred(*__first)) {
@@ -1047,6 +1069,7 @@ namespace std
            typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_function_requires(_EqualOpConcept<
            typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       __first = std::find(__first, __last, __value);
       _ForwardIterator __i = __first;
@@ -1079,6 +1102,7 @@ namespace std
       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       __first = std::find_if(__first, __last, __pred);
       _ForwardIterator __i = __first;
@@ -1207,6 +1231,7 @@ namespace std
            typename iterator_traits<_InputIterator>::value_type>)
       __glibcxx_function_requires(_EqualityComparableConcept<
            typename iterator_traits<_InputIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       typedef typename iterator_traits<_OutputIterator>::iterator_category _IterType;
 
@@ -1239,6 +1264,7 @@ namespace std
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
            typename iterator_traits<_InputIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       typedef typename iterator_traits<_OutputIterator>::iterator_category _IterType;
 
@@ -1266,7 +1292,8 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_EqualityComparableConcept<
-           typename iterator_traits<_ForwardIterator>::value_type>)
+                    typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       // Skip the beginning, if already unique.
       __first = std::adjacent_find(__first, __last);
@@ -1306,6 +1333,7 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
                typename iterator_traits<_ForwardIterator>::value_type,
                typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       // Skip the beginning, if already unique.
       __first = std::adjacent_find(__first, __last, __binary_pred);
@@ -1371,7 +1399,8 @@ namespace std
     {
       // concept requirements
       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
-               _BidirectionalIterator>)
+                   _BidirectionalIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
       std::__reverse(__first, __last, std::__iterator_category(__first));
     }
 
@@ -1399,6 +1428,7 @@ namespace std
       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
                typename iterator_traits<_BidirectionalIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       while (__first != __last) {
        --__last;
@@ -1583,6 +1613,8 @@ namespace std
     {
       // concept requirements
       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
+      __glibcxx_requires_valid_range(__first, __middle);
+      __glibcxx_requires_valid_range(__middle, __last);
 
       typedef typename iterator_traits<_ForwardIterator>::iterator_category _IterType;
       std::__rotate(__first, __middle, __last, _IterType());
@@ -1614,6 +1646,8 @@ namespace std
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
                typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __middle);
+      __glibcxx_requires_valid_range(__middle, __last);
 
       return std::copy(__first, __middle, copy(__middle, __last, __result));
     }
@@ -1657,6 +1691,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last) return;
       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
@@ -1684,6 +1719,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last) return;
       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
@@ -1773,6 +1809,7 @@ namespace std
       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       return std::__partition(__first, __last, __pred, std::__iterator_category(__first));
     }
@@ -1873,6 +1910,7 @@ namespace std
       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last)
        return __first;
@@ -2139,6 +2177,8 @@ namespace std
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_requires_valid_range(__first, __middle);
+      __glibcxx_requires_valid_range(__middle, __last);
 
       std::make_heap(__first, __middle);
       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
@@ -2179,6 +2219,8 @@ namespace std
            _RandomAccessIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
                                                          _ValueType, _ValueType>)
+      __glibcxx_requires_valid_range(__first, __middle);
+      __glibcxx_requires_valid_range(__middle, __last);
 
       std::make_heap(__first, __middle, __comp);
       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
@@ -2219,6 +2261,8 @@ namespace std
       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
       __glibcxx_function_requires(_LessThanComparableConcept<_InputValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_valid_range(__result_first, __result_last);
 
       if (__result_first == __result_last) return __result_last;
       _RandomAccessIterator __result_real_last = __result_first;
@@ -2275,6 +2319,8 @@ namespace std
       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
                                  _OutputValueType, _OutputValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_valid_range(__result_first, __result_last);
 
       if (__result_first == __result_last) return __result_last;
       _RandomAccessIterator __result_real_last = __result_first;
@@ -2375,6 +2421,7 @@ namespace std
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first != __last) {
        std::__introsort_loop(__first, __last, __lg(__last - __first) * 2);
@@ -2406,6 +2453,7 @@ namespace std
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first != __last) {
        std::__introsort_loop(__first, __last, __lg(__last - __first) * 2, __comp);
@@ -2438,6 +2486,7 @@ namespace std
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
+      __glibcxx_requires_partitioned(__first, __last, __val);
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -2483,6 +2532,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
+      __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -2525,6 +2575,7 @@ namespace std
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
+      __glibcxx_requires_partitioned(__first, __last, __val);
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -2570,6 +2621,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
+      __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -2755,6 +2807,8 @@ namespace std
            typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_InputIterator1>::value_type>)
+      __glibcxx_requires_sorted(__first1, __last1);
+      __glibcxx_requires_sorted(__first2, __last2);
 
       while (__first1 != __last1 && __first2 != __last2) {
        if (*__first2 < *__first1) {
@@ -2808,6 +2862,8 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_InputIterator1>::value_type,
            typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
+      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
 
       while (__first1 != __last1 && __first2 != __last2) {
        if (__comp(*__first2, *__first1)) {
@@ -3170,6 +3226,8 @@ namespace std
       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
            _BidirectionalIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_requires_sorted(__first, __middle);
+      __glibcxx_requires_sorted(__middle, __last);
 
       if (__first == __middle || __middle == __last)
        return;
@@ -3223,6 +3281,8 @@ namespace std
            _BidirectionalIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            _ValueType, _ValueType>)
+      __glibcxx_requires_sorted_pred(__first, __middle, __comp);
+      __glibcxx_requires_sorted_pred(__middle, __last, __comp);
 
       if (__first == __middle || __middle == __last)
        return;
@@ -3309,6 +3369,7 @@ namespace std
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       _Temporary_buffer<_RandomAccessIterator, _ValueType> buf(__first, __last);
       if (buf.begin() == 0)
@@ -3346,6 +3407,7 @@ namespace std
            _RandomAccessIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
                                                          _ValueType, _ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       _Temporary_buffer<_RandomAccessIterator, _ValueType> buf(__first, __last);
       if (buf.begin() == 0)
@@ -3381,6 +3443,8 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_requires_valid_range(__first, __nth);
+      __glibcxx_requires_valid_range(__nth, __last);
 
       while (__last - __first > 3) {
        _RandomAccessIterator __cut =
@@ -3425,6 +3489,8 @@ namespace std
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
                                  _ValueType, _ValueType>)
+      __glibcxx_requires_valid_range(__first, __nth);
+      __glibcxx_requires_valid_range(__nth, __last);
 
       while (__last - __first > 3) {
        _RandomAccessIterator __cut =
@@ -3469,6 +3535,7 @@ namespace std
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
+      __glibcxx_requires_partitioned(__first, __last, __val);
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -3524,6 +3591,7 @@ namespace std
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
+      __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
 
       _DistanceType __len = std::distance(__first, __last);
       _DistanceType __half;
@@ -3572,6 +3640,7 @@ namespace std
       __glibcxx_function_requires(_SameTypeConcept<_Tp,
                typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
+      __glibcxx_requires_partitioned(__first, __last, __val);
 
       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
       return __i != __last && !(__val < *__i);
@@ -3603,6 +3672,7 @@ namespace std
                typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
                typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
 
       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
       return __i != __last && !__comp(__val, *__i);
@@ -3642,6 +3712,8 @@ namespace std
            typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_InputIterator1>::value_type>)
+      __glibcxx_requires_sorted(__first1, __last1);
+      __glibcxx_requires_sorted(__first2, __last2);
 
       while (__first1 != __last1 && __first2 != __last2)
        if (*__first2 < *__first1)
@@ -3687,6 +3759,8 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_InputIterator1>::value_type,
            typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
+      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
        if (__comp(*__first2, *__first1))
@@ -3732,6 +3806,8 @@ namespace std
            typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_InputIterator1>::value_type>)
+      __glibcxx_requires_sorted(__first1, __last1);
+      __glibcxx_requires_sorted(__first2, __last2);
 
       while (__first1 != __last1 && __first2 != __last2) {
        if (*__first1 < *__first2) {
@@ -3788,6 +3864,8 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_InputIterator1>::value_type,
            typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
+      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
 
       while (__first1 != __last1 && __first2 != __last2) {
        if (__comp(*__first1, *__first2)) {
@@ -3840,6 +3918,8 @@ namespace std
            typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_InputIterator1>::value_type>)
+      __glibcxx_requires_sorted(__first1, __last1);
+      __glibcxx_requires_sorted(__first2, __last2);
 
       while (__first1 != __last1 && __first2 != __last2)
        if (*__first1 < *__first2)
@@ -3892,6 +3972,8 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_InputIterator1>::value_type,
            typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
+      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
        if (__comp(*__first1, *__first2))
@@ -3941,6 +4023,8 @@ namespace std
            typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_InputIterator1>::value_type>)
+      __glibcxx_requires_sorted(__first1, __last1);
+      __glibcxx_requires_sorted(__first2, __last2);
 
       while (__first1 != __last1 && __first2 != __last2)
        if (*__first1 < *__first2) {
@@ -3996,6 +4080,8 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_InputIterator1>::value_type,
            typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
+      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
        if (__comp(*__first1, *__first2)) {
@@ -4044,6 +4130,8 @@ namespace std
            typename iterator_traits<_InputIterator2>::value_type>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_InputIterator1>::value_type>)
+      __glibcxx_requires_sorted(__first1, __last1);
+      __glibcxx_requires_sorted(__first2, __last2);
 
       while (__first1 != __last1 && __first2 != __last2)
        if (*__first1 < *__first2) {
@@ -4101,6 +4189,8 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_InputIterator1>::value_type,
            typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
+      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
        if (__comp(*__first1, *__first2)) {
@@ -4137,6 +4227,7 @@ namespace std
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last) return __first;
       _ForwardIterator __result = __first;
@@ -4164,6 +4255,7 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_ForwardIterator>::value_type,
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last) return __first;
       _ForwardIterator __result = __first;
@@ -4186,6 +4278,7 @@ namespace std
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last) return __first;
       _ForwardIterator __result = __first;
@@ -4213,6 +4306,7 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_ForwardIterator>::value_type,
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last) return __first;
       _ForwardIterator __result = __first;
@@ -4244,6 +4338,7 @@ namespace std
       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_BidirectionalIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last)
        return false;
@@ -4296,6 +4391,7 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_BidirectionalIterator>::value_type,
            typename iterator_traits<_BidirectionalIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last)
        return false;
@@ -4344,6 +4440,7 @@ namespace std
       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_BidirectionalIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last)
        return false;
@@ -4396,6 +4493,7 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_BidirectionalIterator>::value_type,
            typename iterator_traits<_BidirectionalIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last)
        return false;
@@ -4451,6 +4549,8 @@ namespace std
       __glibcxx_function_requires(_EqualOpConcept<
            typename iterator_traits<_InputIterator>::value_type,
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_valid_range(__first2, __last2);
 
       for ( ; __first1 != __last1; ++__first1)
        for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
@@ -4489,6 +4589,8 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
            typename iterator_traits<_InputIterator>::value_type,
            typename iterator_traits<_ForwardIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_valid_range(__first2, __last2);
 
       for ( ; __first1 != __last1; ++__first1)
        for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
@@ -4649,6 +4751,8 @@ namespace std
       __glibcxx_function_requires(_EqualOpConcept<
            typename iterator_traits<_ForwardIterator1>::value_type,
            typename iterator_traits<_ForwardIterator2>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_valid_range(__first2, __last2);
 
       return std::__find_end(__first1, __last1, __first2, __last2,
                             std::__iterator_category(__first1),
@@ -4694,6 +4798,8 @@ namespace std
       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
            typename iterator_traits<_ForwardIterator1>::value_type,
            typename iterator_traits<_ForwardIterator2>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_valid_range(__first2, __last2);
 
       return std::__find_end(__first1, __last1, __first2, __last2,
                             std::__iterator_category(__first1),
index 73b1359..3e1a7c6 100644 (file)
@@ -74,6 +74,7 @@
 #include <bits/stl_iterator_base_funcs.h>
 #include <bits/stl_iterator.h>
 #include <bits/concept_check.h>
+#include <debug/debug.h>
 
 namespace std
 {
@@ -333,6 +334,7 @@ namespace std
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
            typename iterator_traits<_InputIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
        typedef typename _Is_normal_iterator<_InputIterator>::_Normal __Normal;
        return std::__copy_ni1(__first, __last, __result, __Normal());
@@ -471,6 +473,7 @@ namespace std
       __glibcxx_function_requires(_ConvertibleConcept<
            typename iterator_traits<_BI1>::value_type,
            typename iterator_traits<_BI2>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal;
       return std::__copy_backward_input_normal_iterator(__first, __last, __result,
@@ -495,6 +498,7 @@ namespace std
     {
       // concept requirements
       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first)
        *__first = __value;
@@ -527,6 +531,7 @@ namespace std
   inline void
   fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c)
   {
+    __glibcxx_requires_valid_range(__first, __last);
     unsigned char __tmp = __c;
     std::memset(__first, __tmp, __last - __first);
   }
@@ -534,6 +539,7 @@ namespace std
   inline void
   fill(signed char* __first, signed char* __last, const signed char& __c)
   {
+    __glibcxx_requires_valid_range(__first, __last);
     signed char __tmp = __c;
     std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
   }
@@ -541,6 +547,7 @@ namespace std
   inline void
   fill(char* __first, char* __last, const char& __c)
   {
+    __glibcxx_requires_valid_range(__first, __last);
     char __tmp = __c;
     std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
   }
@@ -594,6 +601,7 @@ namespace std
            typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_function_requires(_EqualityComparableConcept<
            typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
 
       while (__first1 != __last1 && *__first1 == *__first2)
         {
@@ -625,6 +633,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
+      __glibcxx_requires_valid_range(__first1, __last1);
 
       while (__first1 != __last1 && __binary_pred(*__first1, *__first2))
         {
@@ -655,6 +664,7 @@ namespace std
       __glibcxx_function_requires(_EqualOpConcept<
            typename iterator_traits<_InputIterator1>::value_type,
            typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
 
       for ( ; __first1 != __last1; ++__first1, ++__first2)
        if (!(*__first1 == *__first2))
@@ -684,6 +694,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
+      __glibcxx_requires_valid_range(__first1, __last1);
 
       for ( ; __first1 != __last1; ++__first1, ++__first2)
        if (!__binary_pred(*__first1, *__first2))
@@ -717,6 +728,8 @@ namespace std
            typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_InputIterator2>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_valid_range(__first2, __last2);
 
       for (;__first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) 
        {
@@ -749,6 +762,8 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
+      __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_valid_range(__first2, __last2);
 
       for ( ; __first1 != __last1 && __first2 != __last2
            ; ++__first1, ++__first2) 
@@ -767,6 +782,9 @@ namespace std
                          const unsigned char* __first2, 
                          const unsigned char* __last2)
   {
+    __glibcxx_requires_valid_range(__first1, __last1);
+    __glibcxx_requires_valid_range(__first2, __last2);
+
     const size_t __len1 = __last1 - __first1;
     const size_t __len2 = __last2 - __first2;
     const int __result = std::memcmp(__first1, __first2, std::min(__len1, __len2));
@@ -777,6 +795,9 @@ namespace std
   lexicographical_compare(const char* __first1, const char* __last1,
                          const char* __first2, const char* __last2)
   {
+    __glibcxx_requires_valid_range(__first1, __last1);
+    __glibcxx_requires_valid_range(__first2, __last2);
+
 #if CHAR_MAX == SCHAR_MAX
     return std::lexicographical_compare((const signed char*) __first1,
                                        (const signed char*) __last1,
index 15e0f57..d05f607 100644 (file)
@@ -61,7 +61,7 @@
 #ifndef _BVECTOR_H
 #define _BVECTOR_H 1
 
-namespace std
+namespace __gnu_norm
 { 
   typedef unsigned long _Bit_type;
   enum { _S_word_bit = int(CHAR_BIT * sizeof(_Bit_type)) };
@@ -334,13 +334,12 @@ public:
   ~_Bvector_base() { _Base::_M_deallocate(); }
 };
 
-} // namespace std
+} // namespace __gnu_norm
 
 // Declare a partial specialization of vector<T, Alloc>.
 #include <bits/stl_vector.h>
-namespace std
+namespace __gnu_norm
 {
-
 template <typename _Alloc> 
   class vector<bool, _Alloc> : public _Bvector_base<_Alloc> 
   {
@@ -723,13 +722,8 @@ template <typename _Alloc>
     void clear() { erase(begin(), end()); }
   };
 
-// This typedef is non-standard.  It is provided for backward compatibility.
-typedef vector<bool, __alloc> bit_vector;
-
-} // namespace std 
+  // This typedef is non-standard.  It is provided for backward compatibility.
+  typedef vector<bool, __alloc> bit_vector;
+} // namespace __gnu_norm
 
 #endif /* _BVECTOR_H */
-
-// Local Variables:
-// mode:C++
-// End:
index b573343..2498bb6 100644 (file)
@@ -65,7 +65,7 @@
 #include <bits/stl_iterator_base_types.h>
 #include <bits/stl_iterator_base_funcs.h>
 
-namespace std
+namespace __gnu_norm
 { 
   /**
    *  @if maint
@@ -96,7 +96,7 @@ namespace std
    *  All the functions are op overloads except for _M_set_node.
    *  @endif
   */
-  template <typename _Tp, typename _Ref, typename _Ptr>
+  template<typename _Tp, typename _Ref, typename _Ptr>
     struct _Deque_iterator
   {
     typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
@@ -205,7 +205,7 @@ namespace std
   // 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 <typename _Tp, typename _Ref, typename _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)
@@ -213,7 +213,7 @@ namespace std
     return __x._M_cur == __y._M_cur;
   }
   
-  template <typename _Tp, typename _RefL, typename _PtrL,
+  template<typename _Tp, typename _RefL, typename _PtrL,
                           typename _RefR, typename _PtrR>
   inline bool
   operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
@@ -222,7 +222,7 @@ namespace std
     return __x._M_cur == __y._M_cur;
   }
   
-  template <typename _Tp, typename _Ref, typename _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)
@@ -230,7 +230,7 @@ namespace std
     return !(__x == __y);
   }
   
-  template <typename _Tp, typename _RefL, typename _PtrL,
+  template<typename _Tp, typename _RefL, typename _PtrL,
                           typename _RefR, typename _PtrR>
   inline bool
   operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
@@ -239,7 +239,7 @@ namespace std
     return !(__x == __y);
   }
   
-  template <typename _Tp, typename _Ref, typename _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)
@@ -248,7 +248,7 @@ namespace std
       (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
   }
   
-  template <typename _Tp, typename _RefL, typename _PtrL,
+  template<typename _Tp, typename _RefL, typename _PtrL,
                           typename _RefR, typename _PtrR>
   inline bool
   operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
@@ -258,7 +258,7 @@ namespace std
       (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
   }
   
-  template <typename _Tp, typename _Ref, typename _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)
@@ -266,7 +266,7 @@ namespace std
     return __y < __x;
   }
   
-  template <typename _Tp, typename _RefL, typename _PtrL,
+  template<typename _Tp, typename _RefL, typename _PtrL,
                           typename _RefR, typename _PtrR>
   inline bool
   operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
@@ -275,7 +275,7 @@ namespace std
     return __y < __x;
   }
   
-  template <typename _Tp, typename _Ref, typename _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)
@@ -283,7 +283,7 @@ namespace std
     return !(__y < __x);
   }
   
-  template <typename _Tp, typename _RefL, typename _PtrL,
+  template<typename _Tp, typename _RefL, typename _PtrL,
                           typename _RefR, typename _PtrR>
   inline bool
   operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
@@ -292,7 +292,7 @@ namespace std
     return !(__y < __x);
   }
   
-  template <typename _Tp, typename _Ref, typename _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)
@@ -300,7 +300,7 @@ namespace std
     return !(__x < __y);
   }
   
-  template <typename _Tp, typename _RefL, typename _PtrL,
+  template<typename _Tp, typename _RefL, typename _PtrL,
                           typename _RefR, typename _PtrR>
   inline bool
   operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
@@ -313,7 +313,7 @@ namespace std
   // According to the resolution of DR179 not only the various comparison
   // operators but also operator- must accept mixed iterator/const_iterator
   // parameters.
-  template <typename _Tp, typename _RefL, typename _PtrL,
+  template<typename _Tp, typename _RefL, typename _PtrL,
                           typename _RefR, typename _PtrR>
   inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
   operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
@@ -325,7 +325,7 @@ namespace std
       (__y._M_last - __y._M_cur);
   }
   
-  template <typename _Tp, typename _Ref, typename _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)
   {
@@ -345,7 +345,7 @@ namespace std
    *  instanceless allocators.
    *  @endif
   */
-  template <typename _Tp, typename _Alloc, bool __is_static>
+  template<typename _Tp, typename _Alloc, bool __is_static>
     class _Deque_alloc_base
   {
   public:
@@ -388,7 +388,7 @@ namespace std
   };
   
   /// @if maint Specialization for instanceless allocators.  @endif
-  template <typename _Tp, typename _Alloc>
+  template<typename _Tp, typename _Alloc>
     class _Deque_alloc_base<_Tp, _Alloc, true>
   {
   public:
@@ -439,7 +439,7 @@ namespace std
    *  here.
    *  @endif
   */
-  template <typename _Tp, typename _Alloc>
+  template<typename _Tp, typename _Alloc>
     class _Deque_base
     : public _Deque_alloc_base<_Tp,_Alloc,
                                 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
@@ -470,7 +470,7 @@ namespace std
   };
   
   
-  template <typename _Tp, typename _Alloc>
+  template<typename _Tp, typename _Alloc>
   _Deque_base<_Tp,_Alloc>::~_Deque_base()
   {
     if (this->_M_map)
@@ -490,7 +490,7 @@ namespace std
    *  The initial underlying memory layout is a bit complicated...
    *  @endif
   */
-  template <typename _Tp, typename _Alloc>
+  template<typename _Tp, typename _Alloc>
   void
   _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
   {
@@ -525,7 +525,7 @@ namespace std
                        __num_elements % __deque_buf_size(sizeof(_Tp));
   }
   
-  template <typename _Tp, typename _Alloc>
+  template<typename _Tp, typename _Alloc>
   void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
   {
     _Tp** __cur;
@@ -541,7 +541,7 @@ namespace std
       }
   }
   
-  template <typename _Tp, typename _Alloc>
+  template<typename _Tp, typename _Alloc>
   void
   _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
   {
@@ -634,7 +634,7 @@ namespace std
    *  and we can use other standard algorithms as well.
    *  @endif
   */
-  template <typename _Tp, typename _Alloc = allocator<_Tp> >
+  template<typename _Tp, typename _Alloc = allocator<_Tp> >
     class deque : protected _Deque_base<_Tp, _Alloc>
   {
     // concept requirements
@@ -1227,13 +1227,13 @@ namespace std
      *  push_back on each value from the iterator.
      *  @endif
     */
-    template <typename _InputIterator>
+    template<typename _InputIterator>
       void
       _M_range_initialize(_InputIterator __first, _InputIterator __last,
                           input_iterator_tag);
   
     // called by the second initialize_dispatch above
-    template <typename _ForwardIterator>
+    template<typename _ForwardIterator>
       void
       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
                           forward_iterator_tag);
@@ -1278,13 +1278,13 @@ namespace std
       }
   
     // called by the second assign_dispatch above
-    template <typename _InputIterator>
+    template<typename _InputIterator>
       void
       _M_assign_aux(_InputIterator __first, _InputIterator __last,
                     input_iterator_tag);
   
     // called by the second assign_dispatch above
-    template <typename _ForwardIterator>
+    template<typename _ForwardIterator>
       void
       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
                     forward_iterator_tag)
@@ -1357,13 +1357,13 @@ namespace std
       }
   
     // called by the second insert_dispatch above
-    template <typename _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 <typename _ForwardIterator>
+    template<typename _ForwardIterator>
       void
       _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
                           _ForwardIterator __last, forward_iterator_tag);
@@ -1383,7 +1383,7 @@ namespace std
     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
   
     // called by range_insert_aux for forward iterators
-    template <typename _ForwardIterator>
+    template<typename _ForwardIterator>
       void
       _M_insert_aux(iterator __pos, 
                     _ForwardIterator __first, _ForwardIterator __last,
@@ -1464,7 +1464,7 @@ namespace std
    *  deques.  Deques are considered equivalent if their sizes are equal,
    *  and if corresponding elements compare equal.
   */
-  template <typename _Tp, typename _Alloc>
+  template<typename _Tp, typename _Alloc>
   inline bool operator==(const deque<_Tp, _Alloc>& __x,
                          const deque<_Tp, _Alloc>& __y)
   {
@@ -1483,7 +1483,7 @@ namespace std
    *
    *  See std::lexicographical_compare() for how the determination is made.
   */
-  template <typename _Tp, typename _Alloc>
+  template<typename _Tp, typename _Alloc>
   inline bool operator<(const deque<_Tp, _Alloc>& __x,
                         const deque<_Tp, _Alloc>& __y)
   {
@@ -1492,39 +1492,39 @@ namespace std
   }
   
   /// Based on operator==
-  template <typename _Tp, typename _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 <typename _Tp, typename _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 <typename _Tp, typename _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 <typename _Tp, typename _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 <typename _Tp, typename _Alloc>
+  template<typename _Tp, typename _Alloc>
   inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
   {
     __x.swap(__y);
   }
-} // namespace std 
+} // namespace __gnu_norm
   
 #endif /* _DEQUE_H */
index 697f2c6..c16cbe0 100644 (file)
 #ifndef _STL_HEAP_H
 #define _STL_HEAP_H 1
 
+#include <debug/debug.h>
+
 namespace std
 {
+  // is_heap, a predicate testing whether or not a range is
+  // a heap.  This function is an extension, not part of the C++
+  // standard.
+  template<typename _RandomAccessIterator, typename _Distance>
+    bool
+    __is_heap(_RandomAccessIterator __first, _Distance __n)
+    {
+      _Distance __parent = 0;
+      for (_Distance __child = 1; __child < __n; ++__child) {
+       if (__first[__parent] < __first[__child]) 
+         return false;
+       if ((__child & 1) == 0)
+         ++__parent;
+      }
+      return true;
+    }
+
+  template<typename _RandomAccessIterator, typename _Distance,
+           typename _StrictWeakOrdering>
+    bool
+    __is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp,
+             _Distance __n)
+    {
+      _Distance __parent = 0;
+      for (_Distance __child = 1; __child < __n; ++__child) {
+       if (__comp(__first[__parent], __first[__child]))
+         return false;
+       if ((__child & 1) == 0)
+         ++__parent;
+      }
+      return true;
+    }
+
+  template<typename _RandomAccessIterator>
+    bool
+    __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+    { return std::__is_heap(__first, std::distance(__first, __last)); }
+
+  template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
+    bool
+    __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+           _StrictWeakOrdering __comp)
+    { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
 
   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
 
@@ -101,6 +146,8 @@ namespace std
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
+      //      __glibcxx_requires_heap(__first, __last - 1);
 
       std::__push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
                       _ValueType(*(__last - 1)));
@@ -145,6 +192,8 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
 
       std::__push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
                       _ValueType(*(__last - 1)), __comp);
@@ -200,6 +249,8 @@ namespace std
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_heap(__first, __last);
 
       std::__pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)));
     }
@@ -256,6 +307,8 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_heap_pred(__first, __last, __comp);
 
       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
       std::__pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp);
@@ -282,6 +335,7 @@ namespace std
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__last - __first < 2) return;
       _DistanceType __len = __last - __first;
@@ -317,7 +371,8 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
-
+      __glibcxx_requires_valid_range(__first, __last);
+      
       if (__last - __first < 2) return;
       _DistanceType __len = __last - __first;
       _DistanceType __parent = (__len - 2)/2;
@@ -347,6 +402,8 @@ namespace std
            _RandomAccessIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<
            typename iterator_traits<_RandomAccessIterator>::value_type>)
+      __glibcxx_requires_valid_range(__first, __last);
+      //      __glibcxx_requires_heap(__first, __last);
 
       while (__last - __first > 1)
        std::pop_heap(__first, __last--);
@@ -370,6 +427,8 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_heap_pred(__first, __last, __comp);
 
       while (__last - __first > 1)
        std::pop_heap(__first, __last--, __comp);
index 4533aee..4524e9e 100644 (file)
@@ -63,7 +63,7 @@
 
 #include <bits/concept_check.h>
 
-namespace std
+namespace __gnu_norm
 {
   // Supporting structures are split into common and templated types; the
   // latter publicly inherits from the former in an effort to reduce code
@@ -89,9 +89,9 @@ namespace std
    *  @if maint
    *  @brief Common part of a list::iterator.
    *
-   *  A simple type to walk a doubly-linked list.  All operations here should
-   *  be self-explanatory after taking any decent introductory data structures
-   *  course.
+   *  A simple type to walk a doubly-linked list.  All operations here
+   *  should be self-explanatory after taking any decent introductory
+   *  data structures course.
    *  @endif
   */
   struct _List_iterator_base
@@ -233,17 +233,20 @@ namespace std
     { _M_node_allocator.deallocate(__p, 1); }
   
     // NOTA BENE
-    // The stored instance is not actually of "allocator_type"'s type.  Instead
-    // we rebind the type to Allocator<List_node<Tp>>, which according to
-    // [20.1.5]/4 should probably be the same.  List_node<Tp> is not the same
-    // size as Tp (it's two pointers larger), and specializations on Tp may go
-    // unused because List_node<Tp> is being bound instead.
+    // The stored instance is not actually of "allocator_type"'s type.
+    // Instead we rebind the type to Allocator<List_node<Tp>>, which
+    // according to [20.1.5]/4 should probably be the same.
+    // List_node<Tp> is not the same size as Tp (it's two pointers
+    // larger), and specializations on Tp may go unused because
+    // List_node<Tp> is being bound instead.
     //
-    // We put this to the test in get_allocator above; if the two types are
-    // actually different, there had better be a conversion between them.
+    // We put this to the test in get_allocator above; if the two
+    // types are actually different, there had better be a conversion
+    // between them.
     //
-    // None of the predefined allocators shipped with the library (as of 3.1)
-    // use this instantiation anyhow; they're all instanceless.
+    // None of the predefined allocators shipped with the library (as
+    // of 3.1) use this instantiation anyhow; they're all
+    // instanceless.
     typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
              _M_node_allocator;
   
@@ -329,36 +332,37 @@ namespace std
    *  <a href="tables.html#68">optional sequence requirements</a> with the
    *  %exception of @c at and @c operator[].
    *
-   *  This is a @e doubly @e linked %list.  Traversal up and down the %list
-   *  requires linear time, but adding and removing elements (or @e nodes) is
-   *  done in constant time, regardless of where the change takes place.
-   *  Unlike std::vector and std::deque, random-access iterators are not
-   *  provided, so subscripting ( @c [] ) access is not allowed.  For algorithms
-   *  which only need sequential access, this lack makes no difference.
+   *  This is a @e doubly @e linked %list.  Traversal up and down the
+   *  %list requires linear time, but adding and removing elements (or
+   *  @e nodes) is done in constant time, regardless of where the
+   *  change takes place.  Unlike std::vector and std::deque,
+   *  random-access iterators are not provided, so subscripting ( @c
+   *  [] ) access is not allowed.  For algorithms which only need
+   *  sequential access, this lack makes no difference.
    *
-   *  Also unlike the other standard containers, std::list provides specialized 
-   *  algorithms %unique to linked lists, such as splicing, sorting, and
-   *  in-place reversal.
+   *  Also unlike the other standard containers, std::list provides
+   *  specialized algorithms %unique to linked lists, such as
+   *  splicing, sorting, and in-place reversal.
    *
    *  @if maint
    *  A couple points on memory allocation for list<Tp>:
    *
-   *  First, we never actually allocate a Tp, we allocate List_node<Tp>'s
-   *  and trust [20.1.5]/4 to DTRT.  This is to ensure that after elements from
-   *  %list<X,Alloc1> are spliced into %list<X,Alloc2>, destroying the memory of
-   *  the second %list is a valid operation, i.e., Alloc1 giveth and Alloc2
-   *  taketh away.
+   *  First, we never actually allocate a Tp, we allocate
+   *  List_node<Tp>'s and trust [20.1.5]/4 to DTRT.  This is to ensure
+   *  that after elements from %list<X,Alloc1> are spliced into
+   *  %list<X,Alloc2>, destroying the memory of the second %list is a
+   *  valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
    *
    *  Second, a %list conceptually represented as
    *  @code
    *    A <---> B <---> C <---> D
    *  @endcode
-   *  is actually circular; a link exists between A and D.  The %list class
-   *  holds (as its only data member) a private list::iterator pointing to
-   *  @e D, not to @e A!  To get to the head of the %list, we start at the tail
-   *  and move forward by one.  When this member iterator's next/previous
-   *  pointers refer to itself, the %list is %empty.
-   *  @endif
+   *  is actually circular; a link exists between A and D.  The %list
+   *  class holds (as its only data member) a private list::iterator
+   *  pointing to @e D, not to @e A!  To get to the head of the %list,
+   *  we start at the tail and move forward by one.  When this member
+   *  iterator's next/previous pointers refer to itself, the %list is
+   *  %empty.  @endif
   */
   template<typename _Tp, typename _Alloc = allocator<_Tp> >
     class list : protected _List_base<_Tp, _Alloc>
@@ -505,18 +509,19 @@ namespace std
       { this->insert(begin(), __first, __last); }
   
     /**
-     *  No explicit dtor needed as the _Base dtor takes care of things.
-     *  The _Base dtor only erases the elements, and note that if the elements
-     *  themselves are pointers, the pointed-to memory is not touched in any
-     *  way.  Managing the pointer is the user's responsibilty.
+     *  No explicit dtor needed as the _Base dtor takes care of
+     *  things.  The _Base dtor only erases the elements, and note
+     *  that if the elements themselves are pointers, the pointed-to
+     *  memory is not touched in any way.  Managing the pointer is the
+     *  user's responsibilty.
     */
   
     /**
      *  @brief  %List assignment operator.
      *  @param  x  A %list of identical element and allocator types.
      * 
-     *  All the elements of @a x are copied, but unlike the copy constructor,
-     *  the allocator object is not copied.
+     *  All the elements of @a x are copied, but unlike the copy
+     *  constructor, the allocator object is not copied.
     */
     list&
     operator=(const list& __x);
@@ -526,13 +531,14 @@ namespace std
      *  @param  n  Number of elements to be assigned.
      *  @param  val  Value to be assigned.
      *
-     *  This function fills a %list with @a n copies of the given value.
-     *  Note that the assignment completely changes the %list and that the
-     *  resulting %list's size is the same as the number of elements assigned.
-     *  Old data may be lost.
+     *  This function fills a %list with @a n copies of the given
+     *  value.  Note that the assignment completely changes the %list
+     *  and that the resulting %list's size is the same as the number
+     *  of elements assigned.  Old data may be lost.
     */
     void
-    assign(size_type __n, const value_type& __val) { _M_fill_assign(__n, __val); }
+    assign(size_type __n, const value_type& __val) 
+    { _M_fill_assign(__n, __val); }
   
     /**
      *  @brief  Assigns a range to a %list.
@@ -568,44 +574,50 @@ namespace std
     begin() { return static_cast<_Node*>(this->_M_node._M_next); }
   
     /**
-     *  Returns a read-only (constant) iterator that points to the first element
-     *  in the %list.  Iteration is done in ordinary element order.
+     *  Returns a read-only (constant) iterator that points to the
+     *  first element in the %list.  Iteration is done in ordinary
+     *  element order.
     */
     const_iterator
     begin() const { return static_cast<_Node*>(this->_M_node._M_next); }
   
     /**
-     *  Returns a read/write iterator that points one past the last element in
-     *  the %list.  Iteration is done in ordinary element order.
+     *  Returns a read/write iterator that points one past the last
+     *  element in the %list.  Iteration is done in ordinary element
+     *  order.
     */
     iterator
     end() { return static_cast<_Node*>(&this->_M_node); }
   
     /**
-     *  Returns a read-only (constant) iterator that points one past the last
-     *  element in the %list.  Iteration is done in ordinary element order.
+     *  Returns a read-only (constant) iterator that points one past
+     *  the last element in the %list.  Iteration is done in ordinary
+     *  element order.
     */
     const_iterator
-    end() const { return const_cast<_Node *>(static_cast<const _Node*>(&this->_M_node)); }
+    end() const 
+    { return const_cast<_Node *>(static_cast<const _Node*>(&this->_M_node)); }
   
     /**
-     *  Returns a read/write reverse iterator that points to the last element in
-     *  the %list.  Iteration is done in reverse element order.
+     *  Returns a read/write reverse iterator that points to the last
+     *  element in the %list.  Iteration is done in reverse element
+     *  order.
     */
     reverse_iterator
     rbegin() { return reverse_iterator(end()); }
   
     /**
-     *  Returns a read-only (constant) reverse iterator that points to the last
-     *  element in the %list.  Iteration is done in reverse element order.
+     *  Returns a read-only (constant) reverse iterator that points to
+     *  the last element in the %list.  Iteration is done in reverse
+     *  element order.
     */
     const_reverse_iterator
     rbegin() const { return const_reverse_iterator(end()); }
   
     /**
-     *  Returns a read/write reverse iterator that points to one before the
-     *  first element in the %list.  Iteration is done in reverse element
-     *  order.
+     *  Returns a read/write reverse iterator that points to one
+     *  before the first element in the %list.  Iteration is done in
+     *  reverse element order.
     */
     reverse_iterator
     rend() { return reverse_iterator(begin()); }
@@ -621,7 +633,8 @@ namespace std
   
     // [23.2.2.2] capacity
     /**
-     *  Returns true if the %list is empty.  (Thus begin() would equal end().)
+     *  Returns true if the %list is empty.  (Thus begin() would equal
+     *  end().)
     */
     bool
     empty() const { return this->_M_node._M_next == &this->_M_node; }
@@ -635,14 +648,14 @@ namespace std
     max_size() const { return size_type(-1); }
   
     /**
-     *  @brief  Resizes the %list to the specified number of elements.
-     *  @param  new_size  Number of elements the %list should contain.
-     *  @param  x  Data with which new elements should be populated.
+     *  @brief Resizes the %list to the specified number of elements.
+     *  @param new_size Number of elements the %list should contain.
+     *  @param x Data with which new elements should be populated.
      *
-     *  This function will %resize the %list to the specified number of
-     *  elements.  If the number is smaller than the %list's current size the
-     *  %list is truncated, otherwise the %list is extended and new elements
-     *  are populated with given data.
+     *  This function will %resize the %list to the specified number
+     *  of elements.  If the number is smaller than the %list's
+     *  current size the %list is truncated, otherwise the %list is
+     *  extended and new elements are populated with given data.
     */
     void
     resize(size_type __new_size, const value_type& __x);
@@ -652,9 +665,9 @@ namespace std
      *  @param  new_size  Number of elements the %list should contain.
      *
      *  This function will resize the %list to the specified number of
-     *  elements.  If the number is smaller than the %list's current size the
-     *  %list is truncated, otherwise the %list is extended and new elements
-     *  are default-constructed.
+     *  elements.  If the number is smaller than the %list's current
+     *  size the %list is truncated, otherwise the %list is extended
+     *  and new elements are default-constructed.
     */
     void
     resize(size_type __new_size) { this->resize(__new_size, value_type()); }
@@ -675,8 +688,8 @@ namespace std
     front() const { return *begin(); }
   
     /**
-     *  Returns a read/write reference to the data at the last element of the
-     *  %list.
+     *  Returns a read/write reference to the data at the last element
+     *  of the %list.
     */
     reference
     back() { return *(--end()); }
@@ -693,10 +706,11 @@ namespace std
      *  @brief  Add data to the front of the %list.
      *  @param  x  Data to be added.
      *
-     *  This is a typical stack operation.  The function creates an element at
-     *  the front of the %list and assigns the given data to it.  Due to the
-     *  nature of a %list this operation can be done in constant time, and
-     *  does not invalidate iterators and references.
+     *  This is a typical stack operation.  The function creates an
+     *  element at the front of the %list and assigns the given data
+     *  to it.  Due to the nature of a %list this operation can be
+     *  done in constant time, and does not invalidate iterators and
+     *  references.
     */
     void
     push_front(const value_type& __x) { this->insert(begin(), __x); }
@@ -704,13 +718,14 @@ namespace std
     /**
      *  @brief  Removes first element.
      *
-     *  This is a typical stack operation.  It shrinks the %list by one.
-     *  Due to the nature of a %list this operation can be done in constant
-     *  time, and only invalidates iterators/references to the element being
-     *  removed.
+     *  This is a typical stack operation.  It shrinks the %list by
+     *  one.  Due to the nature of a %list this operation can be done
+     *  in constant time, and only invalidates iterators/references to
+     *  the element being removed.
      *
-     *  Note that no data is returned, and if the first element's data is
-     *  needed, it should be retrieved before pop_front() is called.
+     *  Note that no data is returned, and if the first element's data
+     *  is needed, it should be retrieved before pop_front() is
+     *  called.
     */
     void
     pop_front() { this->erase(begin()); }
@@ -719,10 +734,11 @@ namespace std
      *  @brief  Add data to the end of the %list.
      *  @param  x  Data to be added.
      *
-     *  This is a typical stack operation.  The function creates an element at
-     *  the end of the %list and assigns the given data to it.  Due to the
-     *  nature of a %list this operation can be done in constant time, and
-     *  does not invalidate iterators and references.
+     *  This is a typical stack operation.  The function creates an
+     *  element at the end of the %list and assigns the given data to
+     *  it.  Due to the nature of a %list this operation can be done
+     *  in constant time, and does not invalidate iterators and
+     *  references.
     */
     void
     push_back(const value_type& __x) { this->insert(end(), __x); }
@@ -730,13 +746,13 @@ namespace std
     /**
      *  @brief  Removes last element.
      *
-     *  This is a typical stack operation.  It shrinks the %list by one.
-     *  Due to the nature of a %list this operation can be done in constant
-     *  time, and only invalidates iterators/references to the element being
-     *  removed.
+     *  This is a typical stack operation.  It shrinks the %list by
+     *  one.  Due to the nature of a %list this operation can be done
+     *  in constant time, and only invalidates iterators/references to
+     *  the element being removed.
      *
-     *  Note that no data is returned, and if the last element's data is
-     *  needed, it should be retrieved before pop_back() is called.
+     *  Note that no data is returned, and if the last element's data
+     *  is needed, it should be retrieved before pop_back() is called.
     */
     void
     pop_back()
@@ -751,10 +767,10 @@ namespace std
      *  @param  x  Data to be inserted.
      *  @return  An iterator that points to the inserted data.
      *
-     *  This function will insert a copy of the given value before the specified
-     *  location.
-     *  Due to the nature of a %list this operation can be done in constant
-     *  time, and does not invalidate iterators and references.
+     *  This function will insert a copy of the given value before the
+     *  specified location.  Due to the nature of a %list this
+     *  operation can be done in constant time, and does not
+     *  invalidate iterators and references.
     */
     iterator
     insert(iterator __position, const value_type& __x);
@@ -765,11 +781,12 @@ namespace std
      *  @param  n  Number of elements to be inserted.
      *  @param  x  Data to be inserted.
      *
-     *  This function will insert a specified number of copies of the given data
-     *  before the location specified by @a position.
+     *  This function will insert a specified number of copies of the
+     *  given data before the location specified by @a position.
      *
-     *  Due to the nature of a %list this operation can be done in constant
-     *  time, and does not invalidate iterators and references.
+     *  Due to the nature of a %list this operation can be done in
+     *  constant time, and does not invalidate iterators and
+     *  references.
     */
     void
     insert(iterator __position, size_type __n, const value_type& __x)
@@ -781,16 +798,17 @@ namespace std
      *  @param  first  An input iterator.
      *  @param  last   An input iterator.
      *
-     *  This function will insert copies of the data in the range
-     *  [@a first,@a last) into the %list before the location specified by @a
-     *  position.
+     *  This function will insert copies of the data in the range [@a
+     *  first,@a last) into the %list before the location specified by
+     *  @a position.
      *
      *  Due to the nature of a %list this operation can be done in constant
      *  time, and does not invalidate iterators and references.
     */
     template<typename _InputIterator>
       void
-      insert(iterator __position, _InputIterator __first, _InputIterator __last)
+      insert(iterator __position, _InputIterator __first, 
+            _InputIterator __last)
       {
         // Check whether it's an integral type.  If so, it's not an iterator.
         typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
@@ -805,13 +823,12 @@ namespace std
      *  This function will erase the element at the given position and thus
      *  shorten the %list by one.
      *
-     *  Due to the nature of a %list this operation can be done in constant
-     *  time, and only invalidates iterators/references to the element being
-     *  removed.
-     *  The user is also cautioned that
-     *  this function only erases the element, and that if the element is itself
-     *  a pointer, the pointed-to memory is not touched in any way.  Managing
-     *  the pointer is the user's responsibilty.
+     *  Due to the nature of a %list this operation can be done in
+     *  constant time, and only invalidates iterators/references to
+     *  the element being removed.  The user is also cautioned that
+     *  this function only erases the element, and that if the element
+     *  is itself a pointer, the pointed-to memory is not touched in
+     *  any way.  Managing the pointer is the user's responsibilty.
     */
     iterator
     erase(iterator __position);
@@ -824,16 +841,16 @@ namespace std
      *  @return  An iterator pointing to the element pointed to by @a last
      *           prior to erasing (or end()).
      *
-     *  This function will erase the elements in the range @a [first,last) and
-     *  shorten the %list accordingly.
+     *  This function will erase the elements in the range @a
+     *  [first,last) and shorten the %list accordingly.
      *
-     *  Due to the nature of a %list this operation can be done in constant
-     *  time, and only invalidates iterators/references to the element being
-     *  removed.
-     *  The user is also cautioned that
-     *  this function only erases the elements, and that if the elements
-     *  themselves are pointers, the pointed-to memory is not touched in any
-     *  way.  Managing the pointer is the user's responsibilty.
+     *  Due to the nature of a %list this operation can be done in
+     *  constant time, and only invalidates iterators/references to
+     *  the element being removed.  The user is also cautioned that
+     *  this function only erases the elements, and that if the
+     *  elements themselves are pointers, the pointed-to memory is not
+     *  touched in any way.  Managing the pointer is the user's
+     *  responsibilty.
     */
     iterator
     erase(iterator __first, iterator __last)
@@ -847,18 +864,19 @@ namespace std
      *  @brief  Swaps data with another %list.
      *  @param  x  A %list of the same element and allocator types.
      *
-     *  This exchanges the elements between two lists in constant time.
-     *  Note that the global std::swap() function is specialized such that
-     *  std::swap(l1,l2) will feed to this function.
+     *  This exchanges the elements between two lists in constant
+     *  time.  Note that the global std::swap() function is
+     *  specialized such that std::swap(l1,l2) will feed to this
+     *  function.
     */
     void
     swap(list& __x);
   
     /**
-     *  Erases all the elements.  Note that this function only erases the
-     *  elements, and that if the elements themselves are pointers, the
-     *  pointed-to memory is not touched in any way.  Managing the pointer is
-     *  the user's responsibilty.
+     *  Erases all the elements.  Note that this function only erases
+     *  the elements, and that if the elements themselves are
+     *  pointers, the pointed-to memory is not touched in any way.
+     *  Managing the pointer is the user's responsibilty.
     */
     void
     clear() { _Base::__clear(); }
@@ -869,8 +887,9 @@ namespace std
      *  @param  position  Iterator referencing the element to insert before.
      *  @param  x  Source list.
      *
-     *  The elements of @a x are inserted in constant time in front of the
-     *  element referenced by @a position.  @a x becomes an empty list.
+     *  The elements of @a x are inserted in constant time in front of
+     *  the element referenced by @a position.  @a x becomes an empty
+     *  list.
     */
     void
     splice(iterator __position, list& __x)
@@ -885,8 +904,8 @@ namespace std
      *  @param  x  Source list.
      *  @param  i  Iterator referencing the element to move.
      *
-     *  Removes the element in list @a x referenced by @a i and inserts it into the
-     *  current list before @a position.
+     *  Removes the element in list @a x referenced by @a i and
+     *  inserts it into the current list before @a position.
     */
     void
     splice(iterator __position, list&, iterator __i)
@@ -904,8 +923,8 @@ namespace std
      *  @param  first  Iterator referencing the start of range in x.
      *  @param  last  Iterator referencing the end of range in x.
      *
-     *  Removes elements in the range [first,last) and inserts them before
-     *  @a position in constant time.
+     *  Removes elements in the range [first,last) and inserts them
+     *  before @a position in constant time.
      *
      *  Undefined if @a position is in [first,last).
    */
@@ -920,11 +939,11 @@ namespace std
      *  @brief  Remove all elements equal to value.
      *  @param  value  The value to remove.
      *
-     *  Removes every element in the list equal to @a value.  Remaining
-     *  elements stay in list order.  Note that this function only erases the
-     *  elements, and that if the elements themselves are pointers, the
-     *  pointed-to memory is not touched in any way.  Managing the pointer is
-     *  the user's responsibilty.
+     *  Removes every element in the list equal to @a value.
+     *  Remaining elements stay in list order.  Note that this
+     *  function only erases the elements, and that if the elements
+     *  themselves are pointers, the pointed-to memory is not touched
+     *  in any way.  Managing the pointer is the user's responsibilty.
     */
     void
     remove(const _Tp& __value);
@@ -933,11 +952,12 @@ namespace std
      *  @brief  Remove all elements satisfying a predicate.
      *  @param  Predicate  Unary predicate function or object.
      *
-     *  Removes every element in the list for which the predicate returns
-     *  true.  Remaining elements stay in list order.  Note that this function
-     *  only erases the elements, and that if the elements themselves are
-     *  pointers, the pointed-to memory is not touched in any way.  Managing
-     *  the pointer is the user's responsibilty.
+     *  Removes every element in the list for which the predicate
+     *  returns true.  Remaining elements stay in list order.  Note
+     *  that this function only erases the elements, and that if the
+     *  elements themselves are pointers, the pointed-to memory is not
+     *  touched in any way.  Managing the pointer is the user's
+     *  responsibilty.
     */
     template<typename _Predicate>
       void
@@ -946,11 +966,12 @@ namespace std
     /**
      *  @brief  Remove consecutive duplicate elements.
      *
-     *  For each consecutive set of elements with the same value, remove all
-     *  but the first one.  Remaining elements stay in list order.  Note that
-     *  this function only erases the elements, and that if the elements
-     *  themselves are pointers, the pointed-to memory is not touched in any
-     *  way.  Managing the pointer is the user's responsibilty.
+     *  For each consecutive set of elements with the same value,
+     *  remove all but the first one.  Remaining elements stay in list
+     *  order.  Note that this function only erases the elements, and
+     *  that if the elements themselves are pointers, the pointed-to
+     *  memory is not touched in any way.  Managing the pointer is the
+     *  user's responsibilty.
     */
     void
     unique();
@@ -960,11 +981,12 @@ namespace std
      *  @param  BinaryPredicate  Binary predicate function or object.
      *
      *  For each consecutive set of elements [first,last) that satisfy
-     *  predicate(first,i) where i is an iterator in [first,last), remove all
-     *  but the first one.  Remaining elements stay in list order.  Note that
-     *  this function only erases the elements, and that if the elements
-     *  themselves are pointers, the pointed-to memory is not touched in any
-     *  way.  Managing the pointer is the user's responsibilty.
+     *  predicate(first,i) where i is an iterator in [first,last),
+     *  remove all but the first one.  Remaining elements stay in list
+     *  order.  Note that this function only erases the elements, and
+     *  that if the elements themselves are pointers, the pointed-to
+     *  memory is not touched in any way.  Managing the pointer is the
+     *  user's responsibilty.
     */
     template<typename _BinaryPredicate>
       void
@@ -975,9 +997,9 @@ namespace std
      *  @param  x  Sorted list to merge.
      *
      *  Assumes that both @a x and this list are sorted according to
-     *  operator<().  Merges elements of @a x into this list in sorted order,
-     *  leaving @a x empty when complete.  Elements in this list precede
-     *  elements in @a x that are equal.
+     *  operator<().  Merges elements of @a x into this list in sorted
+     *  order, leaving @a x empty when complete.  Elements in this
+     *  list precede elements in @a x that are equal.
     */
     void
     merge(list& __x);
@@ -988,9 +1010,10 @@ namespace std
      *  @param  StrictWeakOrdering  Comparison function definining sort order.
      *
      *  Assumes that both @a x and this list are sorted according to
-     *  StrictWeakOrdering.  Merges elements of @a x into this list in sorted
-     *  order, leaving @a x empty when complete.  Elements in this list precede
-     *  elements in @a x that are equivalent according to StrictWeakOrdering().
+     *  StrictWeakOrdering.  Merges elements of @a x into this list in
+     *  sorted order, leaving @a x empty when complete.  Elements in
+     *  this list precede elements in @a x that are equivalent
+     *  according to StrictWeakOrdering().
     */
     template<typename _StrictWeakOrdering>
       void
@@ -1007,8 +1030,8 @@ namespace std
     /**
      *  @brief  Sort the elements.
      *
-     *  Sorts the elements of this list in NlogN time.  Equivalent elements
-     *  remain in list order.
+     *  Sorts the elements of this list in NlogN time.  Equivalent
+     *  elements remain in list order.
     */
     void
     sort();
@@ -1016,8 +1039,8 @@ namespace std
     /**
      *  @brief  Sort the elements according to comparison function.
      *
-     *  Sorts the elements of this list in NlogN time.  Equivalent elements
-     *  remain in list order.
+     *  Sorts the elements of this list in NlogN time.  Equivalent
+     *  elements remain in list order.
     */
     template<typename _StrictWeakOrdering>
       void
@@ -1026,7 +1049,7 @@ namespace std
   protected:
     // Internal assign functions follow.
   
-    // called by the range assign to implement [23.1.1]/9
+    // Called by the range assign to implement [23.1.1]/9
     template<typename _Integer>
       void
       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
@@ -1035,20 +1058,21 @@ namespace std
                        static_cast<value_type>(__val));
       }
   
-    // called by the range assign to implement [23.1.1]/9
+    // Called by the range assign to implement [23.1.1]/9
     template<typename _InputIterator>
       void
-      _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type);
+      _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 
+                        __false_type);
   
-    // Called by assign(n,t), and the range assign when it turns out to be the
-    // same thing.
+    // Called by assign(n,t), and the range assign when it turns out
+    // to be the same thing.
     void
     _M_fill_assign(size_type __n, const value_type& __val);
   
   
     // Internal insert functions follow.
   
-    // called by the range insert to implement [23.1.1]/9
+    // Called by the range insert to implement [23.1.1]/9
     template<typename _Integer>
       void
       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
@@ -1058,7 +1082,7 @@ namespace std
                        static_cast<value_type>(__x));
       }
   
-    // called by the range insert to implement [23.1.1]/9
+    // Called by the range insert to implement [23.1.1]/9
     template<typename _InputIterator>
       void
       _M_insert_dispatch(iterator __pos,
@@ -1069,8 +1093,8 @@ namespace std
           insert(__pos, *__first);
       }
   
-    // Called by insert(p,n,x), and the range insert when it turns out to be
-    // the same thing.
+    // 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)
     {
@@ -1105,9 +1129,9 @@ namespace std
    *  @param  y  A %list of the same type as @a x.
    *  @return  True iff the size and elements of the lists are equal.
    *
-   *  This is an equivalence relation.  It is linear in the size of the
-   *  lists.  Lists are considered equivalent if their sizes are equal,
-   *  and if corresponding elements compare equal.
+   *  This is an equivalence relation.  It is linear in the size of
+   *  the lists.  Lists are considered equivalent if their sizes are
+   *  equal, and if corresponding elements compare equal.
   */
   template<typename _Tp, typename _Alloc>
   inline bool
@@ -1174,6 +1198,6 @@ namespace std
     inline void
     swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
     { __x.swap(__y); }
-} // namespace std
+} // namespace __gnu_norm
 
 #endif /* _LIST_H */
index 7b15dcc..9895cad 100644 (file)
@@ -63,7 +63,7 @@
 
 #include <bits/concept_check.h>
 
-namespace std
+namespace __gnu_norm
 {
   /**
    *  @brief A standard container made up of (key,value) pairs, which can be
@@ -653,6 +653,6 @@ namespace std
     inline void
     swap(map<_Key,_Tp,_Compare,_Alloc>& __x, map<_Key,_Tp,_Compare,_Alloc>& __y)
     { __x.swap(__y); }
-} // namespace std
+} // namespace __gnu_norm
 
 #endif /* _MAP_H */
index ebc7ff9..4d89228 100644 (file)
@@ -63,7 +63,7 @@
 
 #include <bits/concept_check.h>
 
-namespace std
+namespace __gnu_norm
 {
   // Forward declaration of operators < and ==, needed for friend declaration.
   
@@ -632,6 +632,6 @@ namespace std
     swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x,
          multimap<_Key,_Tp,_Compare,_Alloc>& __y)
     { __x.swap(__y); }
-} // namespace std
+} // namespace __gnu_norm
 
 #endif /* _MULTIMAP_H */
index 49d8c4e..d85c910 100644 (file)
@@ -63,7 +63,7 @@
 
 #include <bits/concept_check.h>
 
-namespace std
+namespace __gnu_norm
 {
 
 // Forward declaration of operators < and ==, needed for friend declaration.
@@ -256,6 +256,6 @@ inline void swap(multiset<_Key,_Compare,_Alloc>& __x,
   __x.swap(__y);
 }
 
-} // namespace std
+} // namespace __gnu_norm
 
 #endif /* _MULTISET_H */
index 4aa92ed..7b901a5 100644 (file)
@@ -61,6 +61,8 @@
 #ifndef _STL_NUMERIC_H
 #define _STL_NUMERIC_H 1
 
+#include <debug/debug.h>
+
 namespace std
 {
 
@@ -70,6 +72,7 @@ namespace std
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first)
        __init = __init + *__first;
@@ -83,6 +86,7 @@ namespace std
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first)
        __init = __binary_op(__init, *__first);
@@ -97,6 +101,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
+      __glibcxx_requires_valid_range(__first1, __last1);
 
       for ( ; __first1 != __last1; ++__first1, ++__first2)
        __init = __init + (*__first1 * *__first2);
@@ -114,6 +119,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
+      __glibcxx_requires_valid_range(__first1, __last1);
 
       for ( ; __first1 != __last1; ++__first1, ++__first2)
        __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
@@ -130,6 +136,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last) return __result;
       *__result = *__first;
@@ -151,6 +158,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last) return __result;
       *__result = *__first;
@@ -172,6 +180,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last) return __result;
       *__result = *__first;
@@ -194,6 +203,7 @@ namespace std
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
 
       if (__first == __last) return __result;
       *__result = *__first;
index 0bb41ac..441fc55 100644 (file)
 #define _QUEUE_H 1
 
 #include <bits/concept_check.h>
+#include <debug/debug.h>
 
 namespace std
 {
   // Forward declarations of operators < and ==, needed for friend declaration.
+  template<typename _Tp, typename _Sequence = deque<_Tp> >
+    class queue;
   
-  template <typename _Tp, typename _Sequence = deque<_Tp> >
-  class queue;
-  
-  template <typename _Tp, typename _Seq>
-  inline bool operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
-  
-  template <typename _Tp, typename _Seq>
-  inline bool operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
+  template<typename _Tp, typename _Seq>
+    inline bool 
+    operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
   
+  template<typename _Tp, typename _Seq>
+    inline bool 
+    operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
   
   /**
    *  @brief  A standard container giving FIFO behavior.
@@ -101,111 +102,133 @@ namespace std
    *  which is a typedef for the second Sequence parameter, and @c push and
    *  @c pop, which are standard %queue/FIFO operations.
   */
-  template <typename _Tp, typename _Sequence>
+  template<typename _Tp, typename _Sequence>
     class queue
-  {
-    // concept requirements
-    typedef typename _Sequence::value_type _Sequence_value_type;
-    __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
-    __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
-    __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
-    __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
-  
-    template <typename _Tp1, typename _Seq1>
-    friend bool operator== (const queue<_Tp1, _Seq1>&,
-                            const queue<_Tp1, _Seq1>&);
-    template <typename _Tp1, typename _Seq1>
-    friend bool operator< (const queue<_Tp1, _Seq1>&,
-                           const queue<_Tp1, _Seq1>&);
-  
-  public:
-    typedef typename _Sequence::value_type                value_type;
-    typedef typename _Sequence::reference                 reference;
-    typedef typename _Sequence::const_reference           const_reference;
-    typedef typename _Sequence::size_type                 size_type;
-    typedef          _Sequence                            container_type;
-  
-  protected:
-    /**
-     *  'c' is the underlying container.  Maintainers wondering why this isn't
-     *  uglified as per style guidelines should note that this name is
-     *  specified in the standard, [23.2.3.1].  (Why?  Presumably for the same
-     *  reason that it's protected instead of private:  to allow derivation.
-     *  But none of the other containers allow for derivation.  Odd.)
-    */
-    _Sequence c;
-  
-  public:
-    /**
-     *  @brief  Default constructor creates no elements.
-    */
-    explicit
-    queue(const _Sequence& __c = _Sequence())
-    : c(__c) {}
-  
-    /**
-     *  Returns true if the %queue is empty.
-    */
-    bool
-    empty() const { return c.empty(); }
-  
-    /**  Returns the number of elements in the %queue.  */
-    size_type
-    size() const { return c.size(); }
-  
-    /**
-     *  Returns a read/write reference to the data at the first element of the
-     *  %queue.
-    */
-    reference
-    front() { return c.front(); }
-  
-    /**
-     *  Returns a read-only (constant) reference to the data at the first
-     *  element of the %queue.
-    */
-    const_reference
-    front() const { return c.front(); }
-  
-    /**
-     *  Returns a read/write reference to the data at the last element of the
-     *  %queue.
-    */
-    reference
-    back() { return c.back(); }
-  
-    /**
-     *  Returns a read-only (constant) reference to the data at the last
-     *  element of the %queue.
-    */
-    const_reference
-    back() const { return c.back(); }
-  
-    /**
-     *  @brief  Add data to the end of the %queue.
-     *  @param  x  Data to be added.
-     *
-     *  This is a typical %queue operation.  The function creates an element at
-     *  the end of the %queue and assigns the given data to it.
-     *  The time complexity of the operation depends on the underlying
-     *  sequence.
-    */
-    void
-    push(const value_type& __x) { c.push_back(__x); }
-  
-    /**
-     *  @brief  Removes first element.
-     *
-     *  This is a typical %queue operation.  It shrinks the %queue by one.
-     *  The time complexity of the operation depends on the underlying
-     *  sequence.
-     *
-     *  Note that no data is returned, and if the first element's data is
-     *  needed, it should be retrieved before pop() is called.
-    */
-    void
-    pop() { c.pop_front(); }
-  };
+    {
+      // concept requirements
+      typedef typename _Sequence::value_type _Sequence_value_type;
+      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
+      __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
+      __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
+      __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
+  
+       template<typename _Tp1, typename _Seq1>
+          friend bool 
+          operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
+
+      template<typename _Tp1, typename _Seq1>
+        friend bool 
+        operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
+  
+    public:
+      typedef typename _Sequence::value_type                value_type;
+      typedef typename _Sequence::reference                 reference;
+      typedef typename _Sequence::const_reference           const_reference;
+      typedef typename _Sequence::size_type                 size_type;
+      typedef          _Sequence                            container_type;
+      
+    protected:
+      /**
+       *  'c' is the underlying container.  Maintainers wondering why
+       *  this isn't uglified as per style guidelines should note that
+       *  this name is specified in the standard, [23.2.3.1].  (Why?
+       *  Presumably for the same reason that it's protected instead
+       *  of private: to allow derivation.  But none of the other
+       *  containers allow for derivation.  Odd.)
+       */
+      _Sequence c;
+      
+    public:
+      /**
+       *  @brief  Default constructor creates no elements.
+       */
+      explicit
+      queue(const _Sequence& __c = _Sequence()) : c(__c) {}
+      
+      /**
+       *  Returns true if the %queue is empty.
+       */
+      bool
+      empty() const { return c.empty(); }
+      
+      /**  Returns the number of elements in the %queue.  */
+      size_type
+      size() const { return c.size(); }
+      
+      /**
+       *  Returns a read/write reference to the data at the first
+       *  element of the %queue.
+       */
+      reference
+      front() 
+      { 
+       __glibcxx_requires_nonempty();
+       return c.front(); 
+      }
+      
+      /**
+       *  Returns a read-only (constant) reference to the data at the first
+       *  element of the %queue.
+       */
+      const_reference
+      front() const 
+      { 
+       __glibcxx_requires_nonempty();
+       return c.front(); 
+      }
+      
+      /**
+       *  Returns a read/write reference to the data at the last
+       *  element of the %queue.
+       */
+      reference
+      back() 
+      {
+       __glibcxx_requires_nonempty();
+       return c.back(); 
+      }
+      
+      /**
+       *  Returns a read-only (constant) reference to the data at the last
+       *  element of the %queue.
+       */
+      const_reference
+      back() const 
+      {
+       __glibcxx_requires_nonempty();
+       return c.back(); 
+      }
+      
+      /**
+       *  @brief  Add data to the end of the %queue.
+       *  @param  x  Data to be added.
+       *
+       *  This is a typical %queue operation.  The function creates an
+       *  element at the end of the %queue and assigns the given data
+       *  to it.  The time complexity of the operation depends on the
+       *  underlying sequence.
+       */
+      void
+      push(const value_type& __x) { c.push_back(__x); }
+      
+      /**
+       *  @brief  Removes first element.
+       *
+       *  This is a typical %queue operation.  It shrinks the %queue by one.
+       *  The time complexity of the operation depends on the underlying
+       *  sequence.
+       *
+       *  Note that no data is returned, and if the first element's
+       *  data is needed, it should be retrieved before pop() is
+       *  called.
+       */
+      void
+      pop() 
+      { 
+       __glibcxx_requires_nonempty();
+       c.pop_front(); 
+      }
+    };
   
   
   /**
@@ -219,9 +242,10 @@ namespace std
    *  linear in the size of the sequences, and queues are considered equivalent
    *  if their sequences compare equal.
   */
-  template <typename _Tp, typename _Sequence>
+  template<typename _Tp, typename _Sequence>
     inline bool 
-    operator==(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
+    operator==(const queue<_Tp,_Sequence>& __x, 
+              const queue<_Tp,_Sequence>& __y)
     { return __x.c == __y.c; }
   
   /**
@@ -230,39 +254,43 @@ namespace std
    *  @param  y  A %queue of the same type as @a x.
    *  @return  True iff @a x is lexicographically less than @a y.
    *
-   *  This is an total ordering relation.  Complexity and semantics depend on
-   *  the underlying sequence type, but the expected rules are:  this relation
-   *  is linear in the size of the sequences, the elements must be comparable
-   *  with @c <, and std::lexicographical_compare() is usually used to make the
+   *  This is an total ordering relation.  Complexity and semantics
+   *  depend on the underlying sequence type, but the expected rules
+   *  are: this relation is linear in the size of the sequences, the
+   *  elements must be comparable with @c <, and
+   *  std::lexicographical_compare() is usually used to make the
    *  determination.
   */
-  template <typename _Tp, typename _Sequence>
+  template<typename _Tp, typename _Sequence>
     inline bool
     operator<(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
     { return __x.c < __y.c; }
   
   /// Based on operator==
-  template <typename _Tp, typename _Sequence>
+  template<typename _Tp, typename _Sequence>
     inline bool
-    operator!=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
+    operator!=(const queue<_Tp,_Sequence>& __x, 
+              const queue<_Tp,_Sequence>& __y)
     { return !(__x == __y); }
   
   /// Based on operator<
-  template <typename _Tp, typename _Sequence>
+  template<typename _Tp, typename _Sequence>
     inline bool 
     operator>(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
     { return __y < __x; }
   
   /// Based on operator<
-  template <typename _Tp, typename _Sequence>
+  template<typename _Tp, typename _Sequence>
     inline bool 
-    operator<=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
+    operator<=(const queue<_Tp,_Sequence>& __x, 
+              const queue<_Tp,_Sequence>& __y)
     { return !(__y < __x); }
   
   /// Based on operator<
-  template <typename _Tp, typename _Sequence>
+  template<typename _Tp, typename _Sequence>
     inline bool 
-    operator>=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
+    operator>=(const queue<_Tp,_Sequence>& __x, 
+              const queue<_Tp,_Sequence>& __y)
     { return !(__x < __y); }
   
   
@@ -272,157 +300,169 @@ namespace std
    *  @ingroup Containers
    *  @ingroup Sequences
    *
-   *  This is not a true container, but an @e adaptor.  It holds another
-   *  container, and provides a wrapper interface to that container.  The
-   *  wrapper is what enforces sorting and first-in-first-out %queue behavior.
-   *  Very few of the standard container/sequence interface requirements are
-   *  met (e.g., iterators).
+   *  This is not a true container, but an @e adaptor.  It holds
+   *  another container, and provides a wrapper interface to that
+   *  container.  The wrapper is what enforces sorting and
+   *  first-in-first-out %queue behavior.  Very few of the standard
+   *  container/sequence interface requirements are met (e.g.,
+   *  iterators).
    *
    *  The second template parameter defines the type of the underlying
-   *  sequence/container.  It defaults to std::vector, but it can be any type
-   *  that supports @c front(), @c push_back, @c pop_back, and random-access
-   *  iterators, such as std::deque or an appropriate user-defined type.
+   *  sequence/container.  It defaults to std::vector, but it can be
+   *  any type that supports @c front(), @c push_back, @c pop_back,
+   *  and random-access iterators, such as std::deque or an
+   *  appropriate user-defined type.
    *
-   *  The third template parameter supplies the means of making priority
-   *  comparisons.  It defaults to @c less<value_type> but can be anything
-   *  defining a strict weak ordering.
+   *  The third template parameter supplies the means of making
+   *  priority comparisons.  It defaults to @c less<value_type> but
+   *  can be anything defining a strict weak ordering.
    *
    *  Members not found in "normal" containers are @c container_type,
-   *  which is a typedef for the second Sequence parameter, and @c push,
-   *  @c pop, and @c top, which are standard %queue/FIFO operations.
+   *  which is a typedef for the second Sequence parameter, and @c
+   *  push, @c pop, and @c top, which are standard %queue/FIFO
+   *  operations.
    *
-   *  @note  No equality/comparison operators are provided for %priority_queue.
+   *  @note No equality/comparison operators are provided for
+   *  %priority_queue.
    *
-   *  @note  Sorting of the elements takes place as they are added to, and
-   *         removed from, the %priority_queue using the %priority_queue's
-   *         member functions.  If you access the elements by other means, and
-   *         change their data such that the sorting order would be different,
-   *         the %priority_queue will not re-sort the elements for you.  (How
-   *         could it know to do so?)
+   *  @note Sorting of the elements takes place as they are added to,
+   *  and removed from, the %priority_queue using the
+   *  %priority_queue's member functions.  If you access the elements
+   *  by other means, and change their data such that the sorting
+   *  order would be different, the %priority_queue will not re-sort
+   *  the elements for you.  (How could it know to do so?)
   */
-  template <typename _Tp, typename _Sequence = vector<_Tp>,
+  template<typename _Tp, typename _Sequence = vector<_Tp>,
             typename _Compare  = less<typename _Sequence::value_type> >
     class priority_queue
-  {
-    // concept requirements
-    typedef typename _Sequence::value_type _Sequence_value_type;
-    __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
-    __glibcxx_class_requires(_Sequence, _SequenceConcept)
-    __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
-    __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
-    __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept)
-  
-  public:
-    typedef typename _Sequence::value_type                value_type;
-    typedef typename _Sequence::reference                 reference;
-    typedef typename _Sequence::const_reference           const_reference;
-    typedef typename _Sequence::size_type                 size_type;
-    typedef          _Sequence                            container_type;
-  
-  protected:
-    //  See queue::c for notes on these names.
-    _Sequence  c;
-    _Compare   comp;
-  
-  public:
-    /**
-     *  @brief  Default constructor creates no elements.
-    */
-    explicit
-    priority_queue(const _Compare& __x = _Compare(),
-                   const _Sequence& __s = _Sequence()) 
-    : c(__s), comp(__x) 
-    { std::make_heap(c.begin(), c.end(), comp); }
-  
-    /**
-     *  @brief  Builds a %queue from a range.
-     *  @param  first  An input iterator.
-     *  @param  last  An input iterator.
-     *  @param  x  A comparison functor describing a strict weak ordering.
-     *  @param  s  An initial sequence with which to start.
-     * 
-     *  Begins by copying @a s, inserting a copy of the elements from
-     *  @a [first,last) into the copy of @a s, then ordering the copy
-     *  according to @a x.
-     *
-     *  For more information on function objects, see the documentation on
-     *  @link s20_3_1_base functor base classes@endlink.
-    */
-    template <typename _InputIterator>
-      priority_queue(_InputIterator __first, _InputIterator __last,
-                     const _Compare& __x = _Compare(),
-                     const _Sequence& __s = _Sequence())
-      : c(__s), comp(__x)
-      { 
-        c.insert(c.end(), __first, __last);
-        std::make_heap(c.begin(), c.end(), comp);
-      }
-  
-    /**
-     *  Returns true if the %queue is empty.
-    */
-    bool
-    empty() const { return c.empty(); }
-  
-    /**  Returns the number of elements in the %queue.  */
-    size_type
-    size() const { return c.size(); }
-  
-    /**
-     *  Returns a read-only (constant) reference to the data at the first
-     *  element of the %queue.
-    */
-    const_reference
-    top() const { return c.front(); }
-  
-    /**
-     *  @brief  Add data to the %queue.
-     *  @param  x  Data to be added.
-     *
-     *  This is a typical %queue operation.
-     *  The time complexity of the operation depends on the underlying
-     *  sequence.
-    */
-    void 
-    push(const value_type& __x) 
     {
-      try 
+      // concept requirements
+      typedef typename _Sequence::value_type _Sequence_value_type;
+      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
+      __glibcxx_class_requires(_Sequence, _SequenceConcept)
+      __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
+      __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
+      __glibcxx_class_requires4(_Compare, bool, _Tp,_Tp,_BinaryFunctionConcept)
+  
+       public:
+      typedef typename _Sequence::value_type                value_type;
+      typedef typename _Sequence::reference                 reference;
+      typedef typename _Sequence::const_reference           const_reference;
+      typedef typename _Sequence::size_type                 size_type;
+      typedef          _Sequence                            container_type;
+      
+    protected:
+      //  See queue::c for notes on these names.
+      _Sequence  c;
+      _Compare   comp;
+      
+    public:
+      /**
+       *  @brief  Default constructor creates no elements.
+       */
+      explicit
+      priority_queue(const _Compare& __x = _Compare(), 
+                    const _Sequence& __s = _Sequence()) 
+      : c(__s), comp(__x) 
+      { std::make_heap(c.begin(), c.end(), comp); }
+  
+      /**
+       *  @brief  Builds a %queue from a range.
+       *  @param  first  An input iterator.
+       *  @param  last  An input iterator.
+       *  @param  x  A comparison functor describing a strict weak ordering.
+       *  @param  s  An initial sequence with which to start.
+       * 
+       *  Begins by copying @a s, inserting a copy of the elements
+       *  from @a [first,last) into the copy of @a s, then ordering
+       *  the copy according to @a x.
+       *
+       *  For more information on function objects, see the
+       *  documentation on @link s20_3_1_base functor base
+       *  classes@endlink.
+       */
+      template<typename _InputIterator>
+        priority_queue(_InputIterator __first, _InputIterator __last,
+                      const _Compare& __x = _Compare(),
+                      const _Sequence& __s = _Sequence())
+       : c(__s), comp(__x)
+        { 
+         __glibcxx_requires_valid_range(__first, __last);
+         c.insert(c.end(), __first, __last);
+         std::make_heap(c.begin(), c.end(), comp);
+       }
+      
+      /**
+       *  Returns true if the %queue is empty.
+       */
+      bool
+      empty() const { return c.empty(); }
+      
+      /**  Returns the number of elements in the %queue.  */
+      size_type
+      size() const { return c.size(); }
+      
+      /**
+       *  Returns a read-only (constant) reference to the data at the first
+       *  element of the %queue.
+       */
+      const_reference
+      top() const 
+      {
+       __glibcxx_requires_nonempty();
+       return c.front(); 
+      }
+      
+      /**
+       *  @brief  Add data to the %queue.
+       *  @param  x  Data to be added.
+       *
+       *  This is a typical %queue operation.
+       *  The time complexity of the operation depends on the underlying
+       *  sequence.
+       */
+      void 
+      push(const value_type& __x) 
+      {
+       try 
         {
           c.push_back(__x); 
           std::push_heap(c.begin(), c.end(), comp);
         }
-      catch(...)
+       catch(...)
         {
           c.clear();
           __throw_exception_again; 
         }
-    }
-  
-    /**
-     *  @brief  Removes first element.
-     *
-     *  This is a typical %queue operation.  It shrinks the %queue by one.
-     *  The time complexity of the operation depends on the underlying
-     *  sequence.
-     *
-     *  Note that no data is returned, and if the first element's data is
-     *  needed, it should be retrieved before pop() is called.
-    */
-    void 
-    pop() 
-    {
-      try 
+      }
+      
+      /**
+       *  @brief  Removes first element.
+       *
+       *  This is a typical %queue operation.  It shrinks the %queue
+       *  by one.  The time complexity of the operation depends on the
+       *  underlying sequence.
+       *
+       *  Note that no data is returned, and if the first element's
+       *  data is needed, it should be retrieved before pop() is
+       *  called.
+       */
+      void 
+      pop() 
+      {
+       __glibcxx_requires_nonempty();
+       try 
         {
           std::pop_heap(c.begin(), c.end(), comp);
           c.pop_back();
         }
-      catch(...)
+       catch(...)
         {
           c.clear();
           __throw_exception_again; 
         }
-    }
-  };
+      }
+    };
   
   // No equality/comparison operators are provided for priority_queue.
 } // namespace std
index fa8c6cf..d1494b9 100644 (file)
 
 #include <bits/concept_check.h>
 
-namespace std
+namespace __gnu_norm
 {
-
-// Forward declarations of operators < and ==, needed for friend declaration.
-
-template <class _Key, class _Compare = less<_Key>,
-          class _Alloc = allocator<_Key> >
-class set;
-
-template <class _Key, class _Compare, class _Alloc>
-inline bool operator==(const set<_Key,_Compare,_Alloc>& __x, 
-                       const set<_Key,_Compare,_Alloc>& __y);
-
-template <class _Key, class _Compare, class _Alloc>
-inline bool operator<(const set<_Key,_Compare,_Alloc>& __x, 
-                      const set<_Key,_Compare,_Alloc>& __y);
-
-
-template <class _Key, class _Compare, class _Alloc>
-class set
-{
-  // concept requirements
-  __glibcxx_class_requires(_Key, _SGIAssignableConcept)
-  __glibcxx_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept)
-
-public:
-  // typedefs:
-  typedef _Key     key_type;
-  typedef _Key     value_type;
-  typedef _Compare key_compare;
-  typedef _Compare value_compare;
+  // Forward declarations of operators < and ==, needed for friend declaration.
+  template<class _Key, class _Compare = less<_Key>, 
+          class _Alloc = allocator<_Key> >
+  class set;
+
+  template<class _Key, class _Compare, class _Alloc>
+    inline bool 
+    operator==(const set<_Key,_Compare,_Alloc>& __x, 
+              const set<_Key,_Compare,_Alloc>& __y);
+
+  template<class _Key, class _Compare, class _Alloc>
+    inline bool 
+    operator<(const set<_Key,_Compare,_Alloc>& __x, 
+             const set<_Key,_Compare,_Alloc>& __y);
+
+  template<class _Key, class _Compare, class _Alloc>
+    class set
+    {
+      // concept requirements
+      __glibcxx_class_requires(_Key, _SGIAssignableConcept)
+      __glibcxx_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept)
+       
+       public:
+      // typedefs:
+      typedef _Key     key_type;
+      typedef _Key     value_type;
+      typedef _Compare key_compare;
+      typedef _Compare value_compare;
 private:
   typedef _Rb_tree<key_type, value_type, 
                   _Identity<value_type>, key_compare, _Alloc> _Rep_type;
@@ -118,12 +117,12 @@ public:
                const allocator_type& __a = allocator_type())
     : _M_t(__comp, __a) {}
 
-  template <class _InputIterator>
+  template<class _InputIterator>
   set(_InputIterator __first, _InputIterator __last)
     : _M_t(_Compare(), allocator_type())
     { _M_t.insert_unique(__first, __last); }
 
-  template <class _InputIterator>
+  template<class _InputIterator>
   set(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
       const allocator_type& __a = allocator_type())
     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
@@ -159,7 +158,7 @@ public:
     typedef typename _Rep_type::iterator _Rep_iterator;
     return _M_t.insert_unique((_Rep_iterator&)__position, __x);
   }
-  template <class _InputIterator>
+  template<class _InputIterator>
   void insert(_InputIterator __first, _InputIterator __last) {
     _M_t.insert_unique(__first, __last);
   }
@@ -205,54 +204,54 @@ public:
     return _M_t.equal_range(__x);
   }
 
-  template <class _K1, class _C1, class _A1>
+  template<class _K1, class _C1, class _A1>
   friend bool operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
-  template <class _K1, class _C1, class _A1>
+  template<class _K1, class _C1, class _A1>
   friend bool operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
 };
 
-template <class _Key, class _Compare, class _Alloc>
+template<class _Key, class _Compare, class _Alloc>
 inline bool operator==(const set<_Key,_Compare,_Alloc>& __x, 
                        const set<_Key,_Compare,_Alloc>& __y) {
   return __x._M_t == __y._M_t;
 }
 
-template <class _Key, class _Compare, class _Alloc>
+template<class _Key, class _Compare, class _Alloc>
 inline bool operator<(const set<_Key,_Compare,_Alloc>& __x, 
                       const set<_Key,_Compare,_Alloc>& __y) {
   return __x._M_t < __y._M_t;
 }
 
-template <class _Key, class _Compare, class _Alloc>
+template<class _Key, class _Compare, class _Alloc>
 inline bool operator!=(const set<_Key,_Compare,_Alloc>& __x, 
                        const set<_Key,_Compare,_Alloc>& __y) {
   return !(__x == __y);
 }
 
-template <class _Key, class _Compare, class _Alloc>
+template<class _Key, class _Compare, class _Alloc>
 inline bool operator>(const set<_Key,_Compare,_Alloc>& __x, 
                       const set<_Key,_Compare,_Alloc>& __y) {
   return __y < __x;
 }
 
-template <class _Key, class _Compare, class _Alloc>
+template<class _Key, class _Compare, class _Alloc>
 inline bool operator<=(const set<_Key,_Compare,_Alloc>& __x, 
                        const set<_Key,_Compare,_Alloc>& __y) {
   return !(__y < __x);
 }
 
-template <class _Key, class _Compare, class _Alloc>
+template<class _Key, class _Compare, class _Alloc>
 inline bool operator>=(const set<_Key,_Compare,_Alloc>& __x, 
                        const set<_Key,_Compare,_Alloc>& __y) {
   return !(__x < __y);
 }
 
-template <class _Key, class _Compare, class _Alloc>
+template<class _Key, class _Compare, class _Alloc>
 inline void swap(set<_Key,_Compare,_Alloc>& __x, 
                  set<_Key,_Compare,_Alloc>& __y) {
   __x.swap(__y);
 }
 
-} // namespace std
+} // namespace __gnu_norm
 
 #endif /* _SET_H */
index b9847ce..d72755a 100644 (file)
 #define _STACK_H 1
 
 #include <bits/concept_check.h>
+#include <debug/debug.h>
 
 namespace std
 {
-  // Forward declarations of operators == and <, needed for friend declaration.
+  // Forward declarations of operators == and <, needed for friend
+  // declaration.
+  template<typename _Tp, typename _Sequence = deque<_Tp> >
+    class stack;
   
-  template <typename _Tp, typename _Sequence = deque<_Tp> >
-  class stack;
+  template<typename _Tp, typename _Seq>
+    inline bool 
+    operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y);
   
-  template <typename _Tp, typename _Seq>
-  inline bool operator==(const stack<_Tp,_Seq>& __x,
-                        const stack<_Tp,_Seq>& __y);
-  
-  template <typename _Tp, typename _Seq>
-  inline bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y);
+  template<typename _Tp, typename _Seq>
+    inline bool 
+    operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y);
   
   
   /**
@@ -89,104 +91,120 @@ namespace std
    *  but does not define anything to do with iterators.  Very few of the
    *  other standard container interfaces are defined.
    *
-   *  This is not a true container, but an @e adaptor.  It holds another
-   *  container, and provides a wrapper interface to that container.  The
-   *  wrapper is what enforces strict first-in-last-out %stack behavior.
+   *  This is not a true container, but an @e adaptor.  It holds
+   *  another container, and provides a wrapper interface to that
+   *  container.  The wrapper is what enforces strict
+   *  first-in-last-out %stack behavior.
    *
    *  The second template parameter defines the type of the underlying
-   *  sequence/container.  It defaults to std::deque, but it can be any type
-   *  that supports @c back, @c push_back, and @c pop_front, such as
-   *  std::list, std::vector, or an appropriate user-defined type.
+   *  sequence/container.  It defaults to std::deque, but it can be
+   *  any type that supports @c back, @c push_back, and @c pop_front,
+   *  such as std::list, std::vector, or an appropriate user-defined
+   *  type.
    *
    *  Members not found in "normal" containers are @c container_type,
-   *  which is a typedef for the second Sequence parameter, and @c push,
-   *  @c pop, and @c top, which are standard %stack/FILO operations.
+   *  which is a typedef for the second Sequence parameter, and @c
+   *  push, @c pop, and @c top, which are standard %stack/FILO
+   *  operations.
   */
-  template <typename _Tp, typename _Sequence>
+  template<typename _Tp, typename _Sequence>
     class stack
-  {
-    // concept requirements
-    typedef typename _Sequence::value_type _Sequence_value_type;
-    __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
-    __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
-    __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
-  
-    template <typename _Tp1, typename _Seq1>
-    friend bool operator== (const stack<_Tp1, _Seq1>&,
-                            const stack<_Tp1, _Seq1>&);
-    template <typename _Tp1, typename _Seq1>
-    friend bool operator< (const stack<_Tp1, _Seq1>&,
-                           const stack<_Tp1, _Seq1>&);
-  
-  public:
-    typedef typename _Sequence::value_type                value_type;
-    typedef typename _Sequence::reference                 reference;
-    typedef typename _Sequence::const_reference           const_reference;
-    typedef typename _Sequence::size_type                 size_type;
-    typedef          _Sequence                            container_type;
-  
-  protected:
-    //  See queue::c for notes on this name.
-    _Sequence c;
-  
-  public:
-    // XXX removed old def ctor, added def arg to this one to match 14882
-    /**
-     *  @brief  Default constructor creates no elements.
-    */
-    explicit
-    stack(const _Sequence& __c = _Sequence())
-    : c(__c) {}
+    {
+      // concept requirements
+      typedef typename _Sequence::value_type _Sequence_value_type;
+      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
+      __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
+      __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
   
-    /**
-     *  Returns true if the %stack is empty.
-    */
-    bool
-    empty() const { return c.empty(); }
-  
-    /**  Returns the number of elements in the %stack.  */
-    size_type
-    size() const { return c.size(); }
-  
-    /**
-     *  Returns a read/write reference to the data at the first element of the
-     *  %stack.
-    */
-    reference
-    top() { return c.back(); }
-  
-    /**
-     *  Returns a read-only (constant) reference to the data at the first
-     *  element of the %stack.
-    */
-    const_reference
-    top() const { return c.back(); }
+       template<typename _Tp1, typename _Seq1>
+          friend bool 
+          operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
+
+      template<typename _Tp1, typename _Seq1>
+        friend bool 
+        operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
   
-    /**
-     *  @brief  Add data to the top of the %stack.
-     *  @param  x  Data to be added.
-     *
-     *  This is a typical %stack operation.  The function creates an element at
-     *  the top of the %stack and assigns the given data to it.
-     *  The time complexity of the operation depends on the underlying
-     *  sequence.
-    */
-    void
-    push(const value_type& __x) { c.push_back(__x); }
+    public:
+      typedef typename _Sequence::value_type                value_type;
+      typedef typename _Sequence::reference                 reference;
+      typedef typename _Sequence::const_reference           const_reference;
+      typedef typename _Sequence::size_type                 size_type;
+      typedef          _Sequence                            container_type;
+      
+    protected:
+      //  See queue::c for notes on this name.
+      _Sequence c;
+      
+    public:
+      // XXX removed old def ctor, added def arg to this one to match 14882
+      /**
+       *  @brief  Default constructor creates no elements.
+       */
+      explicit
+      stack(const _Sequence& __c = _Sequence()) : c(__c) {}
+      
+      /**
+       *  Returns true if the %stack is empty.
+       */
+      bool
+      empty() const { return c.empty(); }
+      
+      /**  Returns the number of elements in the %stack.  */
+      size_type
+      size() const { return c.size(); }
+      
+      /**
+       *  Returns a read/write reference to the data at the first
+       *  element of the %stack.
+       */
+      reference
+      top() 
+      { 
+       __glibcxx_requires_nonempty();
+       return c.back(); 
+      }
+      
+      /**
+       *  Returns a read-only (constant) reference to the data at the first
+       *  element of the %stack.
+       */
+      const_reference
+      top() const 
+      {
+       __glibcxx_requires_nonempty();
+       return c.back(); 
+      }
+      
+      /**
+       *  @brief  Add data to the top of the %stack.
+       *  @param  x  Data to be added.
+       *
+       *  This is a typical %stack operation.  The function creates an
+       *  element at the top of the %stack and assigns the given data
+       *  to it.  The time complexity of the operation depends on the
+       *  underlying sequence.
+       */
+      void
+      push(const value_type& __x) { c.push_back(__x); }
   
-    /**
-     *  @brief  Removes first element.
-     *
-     *  This is a typical %stack operation.  It shrinks the %stack by one.
-     *  The time complexity of the operation depends on the underlying
-     *  sequence.
-     *
-     *  Note that no data is returned, and if the first element's data is
-     *  needed, it should be retrieved before pop() is called.
-    */
-    void
-    pop() { c.pop_back(); }
-  };
+      /**
+       *  @brief  Removes first element.
+       *
+       *  This is a typical %stack operation.  It shrinks the %stack
+       *  by one.  The time complexity of the operation depends on the
+       *  underlying sequence.
+       *
+       *  Note that no data is returned, and if the first element's
+       *  data is needed, it should be retrieved before pop() is
+       *  called.
+       */
+      void
+      pop() 
+      {
+       __glibcxx_requires_nonempty();
+       c.pop_back(); 
+      }
+    };
   
   
   /**
@@ -195,12 +213,13 @@ namespace std
    *  @param  y  A %stack of the same type as @a x.
    *  @return  True iff the size and elements of the stacks are equal.
    *
-   *  This is an equivalence relation.  Complexity and semantics depend on the
-   *  underlying sequence type, but the expected rules are:  this relation is
-   *  linear in the size of the sequences, and stacks are considered equivalent
-   *  if their sequences compare equal.
+   *  This is an equivalence relation.  Complexity and semantics
+   *  depend on the underlying sequence type, but the expected rules
+   *  are: this relation is linear in the size of the sequences, and
+   *  stacks are considered equivalent if their sequences compare
+   *  equal.
   */
-  template <typename _Tp, typename _Seq>
+  template<typename _Tp, typename _Seq>
     inline bool
     operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
     { return __x.c == __y.c; }
@@ -211,37 +230,38 @@ namespace std
    *  @param  y  A %stack of the same type as @a x.
    *  @return  True iff @a x is lexicographically less than @a y.
    *
-   *  This is an total ordering relation.  Complexity and semantics depend on
-   *  the underlying sequence type, but the expected rules are:  this relation
-   *  is linear in the size of the sequences, the elements must be comparable
-   *  with @c <, and std::lexicographical_compare() is usually used to make the
+   *  This is an total ordering relation.  Complexity and semantics
+   *  depend on the underlying sequence type, but the expected rules
+   *  are: this relation is linear in the size of the sequences, the
+   *  elements must be comparable with @c <, and
+   *  std::lexicographical_compare() is usually used to make the
    *  determination.
   */
-  template <typename _Tp, typename _Seq>
+  template<typename _Tp, typename _Seq>
     inline bool
     operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
     { return __x.c < __y.c; }
   
   /// Based on operator==
-  template <typename _Tp, typename _Seq>
+  template<typename _Tp, typename _Seq>
     inline bool
     operator!=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
     { return !(__x == __y); }
   
   /// Based on operator<
-  template <typename _Tp, typename _Seq>
+  template<typename _Tp, typename _Seq>
     inline bool
     operator>(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
     { return __y < __x; }
   
   /// Based on operator<
-  template <typename _Tp, typename _Seq>
+  template<typename _Tp, typename _Seq>
     inline bool
     operator<=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
     { return !(__y < __x); }
   
   /// Based on operator<
-  template <typename _Tp, typename _Seq>
+  template<typename _Tp, typename _Seq>
     inline bool
     operator>=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
     { return !(__x < __y); }
index e911697..94d6a4a 100644 (file)
@@ -65,7 +65,7 @@
 #include <bits/functexcept.h>
 #include <bits/concept_check.h>
 
-namespace std
+namespace __gnu_norm
 {
   /// @if maint Primary default version.  @endif
   /**
@@ -966,6 +966,6 @@ namespace std
     inline void
     swap(vector<_Tp,_Alloc>& __x, vector<_Tp,_Alloc>& __y)
     { __x.swap(__y); }
-} // namespace std
+} // namespace __gnu_norm
 
 #endif /* _VECTOR_H */
index dcbf9f0..cc67505 100644 (file)
@@ -37,6 +37,8 @@
 
 #pragma GCC system_header
 
+#include <debug/debug.h>
+
 namespace std
 {
   template<typename _Tp, typename _CharT = char, 
@@ -65,18 +67,33 @@ namespace std
       { }
 
       const _Tp&
-      operator*() const { return _M_value; }
+      operator*() const 
+      { 
+       __glibcxx_requires_cond(_M_ok,
+                               _M_message(__gnu_debug::__msg_deref_istream)
+                               ._M_iterator(*this));
+       return _M_value;
+      }
 
       const _Tp*
       operator->() const { return &(operator*()); }
 
       istream_iterator& 
       operator++() 
-      { _M_read(); return *this; }
+      { 
+       __glibcxx_requires_cond(_M_ok,
+                               _M_message(__gnu_debug::__msg_inc_istream)
+                               ._M_iterator(*this));
+       _M_read(); 
+       return *this; 
+      }
 
       istream_iterator 
       operator++(int)  
       {
+       __glibcxx_requires_cond(_M_ok,
+                               _M_message(__gnu_debug::__msg_inc_istream)
+                               ._M_iterator(*this)); 
        istream_iterator __tmp = *this;
        _M_read();
        return __tmp;
@@ -138,6 +155,9 @@ namespace std
       ostream_iterator& 
       operator=(const _Tp& __value) 
       { 
+       __glibcxx_requires_cond(_M_stream != 0,
+                               _M_message(__gnu_debug::__msg_output_ostream)
+                               ._M_iterator(*this));
        *_M_stream << __value;
        if (_M_string) *_M_stream << _M_string;
        return *this;
index 51d8384..d193de2 100644 (file)
@@ -39,6 +39,7 @@
 #pragma GCC system_header
 
 #include <streambuf>
+#include <debug/debug.h>
 
 // NB: Should specialize copy, find algorithms for streambuf iterators.
 
@@ -82,11 +83,23 @@ namespace std
       // NB: The result of operator*() on an end of stream is undefined.
       char_type 
       operator*() const
-      { return traits_type::to_char_type(_M_get()); }
+      { 
+#ifdef _GLIBCXX_DEBUG_PEDANTIC
+       // Dereferencing a past-the-end istreambuf_iterator is a
+       // libstdc++ extension
+       __glibcxx_requires_cond(!_M_at_eof(),
+                               _M_message(__gnu_debug::__msg_deref_istreambuf)
+                               ._M_iterator(*this)); 
+#endif
+       return traits_type::to_char_type(_M_get()); 
+      }
        
       istreambuf_iterator& 
       operator++()
       { 
+       __glibcxx_requires_cond(!_M_at_eof(),
+                               _M_message(__gnu_debug::__msg_inc_istreambuf)
+                               ._M_iterator(*this)); 
        const int_type __eof = traits_type::eof();
        if (_M_sbuf && traits_type::eq_int_type(_M_sbuf->sbumpc(), __eof))
          _M_sbuf = 0;
@@ -98,6 +111,10 @@ namespace std
       istreambuf_iterator
       operator++(int)
       {
+       __glibcxx_requires_cond(!_M_at_eof(),
+                               _M_message(__gnu_debug::__msg_inc_istreambuf)
+                               ._M_iterator(*this)); 
+
        const int_type __eof = traits_type::eof();
        istreambuf_iterator __old = *this;
        if (_M_sbuf
@@ -116,8 +133,8 @@ namespace std
       equal(const istreambuf_iterator& __b) const
       {
        const int_type __eof = traits_type::eof();
-       bool __thiseof = traits_type::eq_int_type(_M_get(), __eof);
-       bool __beof = traits_type::eq_int_type(__b._M_get(), __eof);
+       bool __thiseof = _M_at_eof();
+       bool __beof = __b._M_at_eof();
        return (__thiseof && __beof || (!__thiseof && !__beof));
       }
 
@@ -137,6 +154,13 @@ namespace std
          }
        return __ret;
       }
+
+      bool 
+      _M_at_eof() const
+      {
+       const int_type __eof = traits_type::eof();
+       return traits_type::eq_int_type(_M_get(), __eof);
+      }
     };
 
   template<typename _CharT, typename _Traits>
index 181b359..6342743 100644 (file)
@@ -61,7 +61,7 @@
 #ifndef _VECTOR_TCC
 #define _VECTOR_TCC 1
 
-namespace std
+namespace __gnu_norm
 {
   template<typename _Tp, typename _Alloc>
     void
@@ -432,7 +432,8 @@ namespace std
             {
               __new_finish = std::uninitialized_copy(iterator(this->_M_start),
                                                     __position, __new_start);
-              __new_finish = std::uninitialized_copy(__first, __last, __new_finish);
+              __new_finish = std::uninitialized_copy(__first, __last, 
+                                                    __new_finish);
               __new_finish = std::uninitialized_copy(__position,
                                                     iterator(this->_M_finish),
                                                     __new_finish);
@@ -452,6 +453,6 @@ namespace std
         }
       }
     }
-} // namespace std
+} // namespace __gnu_norm
 
 #endif /* _VECTOR_TCC */
diff --git a/libstdc++-v3/include/debug/bitset b/libstdc++-v3/include/debug/bitset
new file mode 100644 (file)
index 0000000..3c474cf
--- /dev/null
@@ -0,0 +1,298 @@
+// Debugging bitset implementation -*- C++ -*-
+
+// Copyright (C) 2003
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_BITSET
+#define _GLIBCXX_DEBUG_BITSET
+
+#include <bitset>
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug_def
+{ 
+  template<size_t _Nb> 
+    class bitset
+    : public __gnu_norm::bitset<_Nb>, public __gnu_debug::_Safe_sequence_base
+    {
+      typedef  __gnu_norm::bitset<_Nb>                 _Base;
+      typedef __gnu_debug::_Safe_sequence_base  _Safe_base;
+
+    public:
+      // bit reference:
+      class reference 
+      : private _Base::reference, public __gnu_debug::_Safe_iterator_base
+      {
+       typedef typename _Base::reference _Base_ref;
+
+       friend class bitset;
+       reference();
+       
+       reference(const _Base_ref& __base, bitset* __seq) 
+       : _Base_ref(__base), _Safe_iterator_base(__seq, false)
+       { }
+
+      public:
+       reference(const reference& __x)
+       : _Base_ref(__x), _Safe_iterator_base(__x, false)
+       { }
+
+       reference& 
+       operator=(bool __x)
+       {
+         _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+                             _M_message(::__gnu_debug::__msg_bad_bitset_write)
+                               ._M_iterator(*this));
+         *static_cast<_Base_ref*>(this) = __x;
+         return *this;
+       }
+
+       reference& 
+       operator=(const reference& __x)
+       {
+         _GLIBCXX_DEBUG_VERIFY(! __x._M_singular(),
+                              _M_message(::__gnu_debug::__msg_bad_bitset_read)
+                               ._M_iterator(__x));
+         _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+                             _M_message(::__gnu_debug::__msg_bad_bitset_write)
+                               ._M_iterator(*this));
+         *static_cast<_Base_ref*>(this) = __x;
+         return *this;
+       }
+       
+       bool 
+       operator~() const
+       {
+         _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+                              _M_message(::__gnu_debug::__msg_bad_bitset_read)
+                               ._M_iterator(*this));
+         return ~(*static_cast<const _Base_ref*>(this));
+       }
+       
+       operator bool() const
+       {
+         _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+                             _M_message(::__gnu_debug::__msg_bad_bitset_read)
+                               ._M_iterator(*this));
+         return *static_cast<const _Base_ref*>(this);
+       }
+       
+       reference& 
+       flip()
+       {
+         _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+                             _M_message(::__gnu_debug::__msg_bad_bitset_flip)
+                               ._M_iterator(*this));
+         _Base_ref::flip();
+         return *this;
+       }
+      };
+
+      // 23.3.5.1 constructors:
+      bitset() : _Base() { }
+      
+      bitset(unsigned long __val) : _Base(__val) { }
+      
+      template<typename _CharT, typename _Traits, typename _Allocator>
+        explicit 
+        bitset(const std::basic_string<_CharT,_Traits,_Allocator>& __str,
+              typename std::basic_string<_CharT,_Traits,_Allocator>::size_type
+              __pos = 0,
+              typename std::basic_string<_CharT,_Traits,_Allocator>::size_type
+              __n = (std::basic_string<_CharT,_Traits,_Allocator>::npos))
+       : _Base(__str, __pos, __n) { }
+
+      bitset(const _Base& __x) : _Base(__x), _Safe_base() { }
+
+      // 23.3.5.2 bitset operations:
+      bitset<_Nb>& 
+      operator&=(const bitset<_Nb>& __rhs)
+      {
+       _M_base() &= __rhs;
+       return *this;
+      }
+      
+      bitset<_Nb>& 
+      operator|=(const bitset<_Nb>& __rhs)
+      {
+       _M_base() != __rhs;
+       return *this;
+      }
+      
+      bitset<_Nb>& 
+      operator^=(const bitset<_Nb>& __rhs)
+      {
+       _M_base() ^= __rhs;
+       return *this;
+      }
+      
+      bitset<_Nb>& 
+      operator<<=(size_t __pos)
+      {
+       _M_base() <<= __pos;
+       return *this;
+      }
+      
+      bitset<_Nb>& 
+      operator>>=(size_t __pos)
+      {
+       _M_base() >>= __pos;
+       return *this;
+      }
+      
+      bitset<_Nb>& 
+      set()
+      {
+       _Base::set();
+       return *this;
+      }
+      
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 186. bitset::set() second parameter should be bool 
+      bitset<_Nb>& 
+      set(size_t __pos, bool __val = true)
+      {
+       _Base::set(__pos, __val);
+       return *this;
+      }
+      
+      bitset<_Nb>& 
+      reset()
+      {
+       _Base::reset();
+       return *this;
+      }
+      
+      bitset<_Nb>& 
+      reset(size_t __pos)
+      {
+       _Base::reset(__pos);
+       return *this;
+      }
+      
+      bitset<_Nb> operator~() const { return bitset(~_M_base()); }
+      
+      bitset<_Nb>& 
+      flip()
+      {
+       _Base::flip();
+       return *this;
+      }
+      
+      bitset<_Nb>& 
+      flip(size_t __pos)
+      {
+       _Base::flip(__pos);
+       return *this;
+      }
+      
+      // element access:
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 11. Bitset minor problems 
+      reference 
+      operator[](size_t __pos)
+      { 
+       __glibcxx_check_subscript(__pos);
+       return reference(_M_base()[__pos], this); 
+      }
+      
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 11. Bitset minor problems 
+      bool 
+      operator[](size_t __pos) const 
+      { 
+       __glibcxx_check_subscript(__pos);
+       return _M_base()[__pos]; 
+      }
+      
+      using _Base::to_ulong;
+      
+      template <typename _CharT, typename _Traits, typename _Allocator>
+        std::basic_string<_CharT, _Traits, _Allocator> 
+        to_string() const
+        { return _M_base().template to_string<_CharT, _Traits, _Allocator>(); }
+      
+      using _Base::count;
+      using _Base::size;
+      
+      bool 
+      operator==(const bitset<_Nb>& __rhs) const
+      { return _M_base() == __rhs; }
+
+      bool 
+      operator!=(const bitset<_Nb>& __rhs) const
+      { return _M_base() != __rhs; }
+      
+      using _Base::test;
+      using _Base::any;
+      using _Base::none;
+      
+      bitset<_Nb> 
+      operator<<(size_t __pos) const
+      { return bitset<_Nb>(_M_base() << __pos); }
+      
+      bitset<_Nb> 
+      operator>>(size_t __pos) const
+      { return bitset<_Nb>(_M_base() >> __pos); }
+      
+      _Base&       
+      _M_base() { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+    };
+  template<size_t _Nb>
+    bitset<_Nb> 
+    operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
+    { return bitset<_Nb>(__x) &= __y; }
+  
+  template<size_t _Nb>
+    bitset<_Nb> 
+    operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
+    { return bitset<_Nb>(__x) |= __y; }
+
+  template<size_t _Nb>
+    bitset<_Nb> 
+    operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
+    { return bitset<_Nb>(__x) ^= __y; }
+
+  template<typename _CharT, typename _Traits, size_t _Nb>
+    std::basic_istream<_CharT, _Traits>&
+    operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
+    { return __is >> __x._M_base(); }
+
+  template<typename _CharT, typename _Traits, size_t _Nb>
+    std::basic_ostream<_CharT, _Traits>&
+    operator<<(std::basic_ostream<_CharT, _Traits>& __os, 
+              const bitset<_Nb>& __x)
+    { return __os << __x._M_base(); }
+} // namespace __gnu_debug_def
+
+#endif
diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h
new file mode 100644 (file)
index 0000000..edb19aa
--- /dev/null
@@ -0,0 +1,531 @@
+// Debugging support implementation -*- C++ -*-
+
+// Copyright (C) 2003
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_DEBUG_H
+#define _GLIBCXX_DEBUG_DEBUG_H 1
+
+/**
+ * Macros used by the implementation to verify certain
+ * properties. These macros may only be used directly by the debug
+ * wrappers. Note that these are macros (instead of the more obviously
+ * "correct" choice of making them functions) because we need line and
+ * file information at the call site, to minimize the distance between
+ * the user error and where the error is reported.
+ *
+ */
+#define _GLIBCXX_DEBUG_VERIFY(_Condition,_ErrorMessage)                \
+  do {                                                                 \
+    if (! (_Condition))                                                        \
+      ::__gnu_debug::_Error_formatter::_M_at(__FILE__, __LINE__)       \
+         ._ErrorMessage._M_error();                                    \
+  } while (false)
+
+// Verify that [_First, _Last) forms a valid iterator range.
+#define __glibcxx_check_valid_range(_First,_Last)                      \
+_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__valid_range(_First, _Last),     \
+                     _M_message(::__gnu_debug::__msg_valid_range)      \
+                     ._M_iterator(_First, #_First)                     \
+                     ._M_iterator(_Last, #_Last))
+
+/** Verify that we can insert into *this with the iterator _Position.
+ *  Insertion into a container at a specific position requires that
+ *  the iterator be nonsingular (i.e., either dereferenceable or
+ *  past-the-end) and that it reference the sequence we are inserting
+ *  into. Note that this macro is only valid when the container is a
+ *  _Safe_sequence and the iterator is a _Safe_iterator.
+*/
+#define __glibcxx_check_insert(_Position)                              \
+_GLIBCXX_DEBUG_VERIFY(!_Position._M_singular(),                                \
+                     _M_message(::__gnu_debug::__msg_insert_singular) \
+                     ._M_sequence(*this, "this")                       \
+                     ._M_iterator(_Position, #_Position));             \
+_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this),                  \
+                     _M_message(::__gnu_debug::__msg_insert_different) \
+                     ._M_sequence(*this, "this")                       \
+                     ._M_iterator(_Position, #_Position))
+
+/** Verify that we can insert the values in the iterator range
+ *  [_First, _Last) into *this with the iterator _Position.  Insertion
+ *  into a container at a specific position requires that the iterator
+ *  be nonsingular (i.e., either dereferenceable or past-the-end),
+ *  that it reference the sequence we are inserting into, and that the
+ *  iterator range [_First, Last) is a valid (possibly empty)
+ *  range. Note that this macro is only valid when the container is a
+ *  _Safe_sequence and the iterator is a _Safe_iterator.
+ *
+ *  @tbd We would like to be able to check for noninterference of
+ *  _Position and the range [_First, _Last), but that can't (in
+ *  general) be done.
+*/
+#define __glibcxx_check_insert_range(_Position,_First,_Last)           \
+__glibcxx_check_valid_range(_First,_Last);                             \
+_GLIBCXX_DEBUG_VERIFY(!_Position._M_singular(),                                \
+                     _M_message(::__gnu_debug::__msg_insert_singular) \
+                      ._M_sequence(*this, "this")                      \
+                     ._M_iterator(_Position, #_Position));             \
+_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this),                  \
+                     _M_message(::__gnu_debug::__msg_insert_different) \
+                     ._M_sequence(*this, "this")                       \
+                     ._M_iterator(_Position, #_Position))
+
+/** Verify that we can erase the element referenced by the iterator
+ * _Position. We can erase the element if the _Position iterator is
+ * dereferenceable and references this sequence.
+*/
+#define __glibcxx_check_erase(_Position)                               \
+_GLIBCXX_DEBUG_VERIFY(_Position._M_dereferenceable(),                  \
+                     _M_message(::__gnu_debug::__msg_erase_bad)        \
+                      ._M_sequence(*this, "this")                      \
+                     ._M_iterator(_Position, #_Position));             \
+_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this),                  \
+                     _M_message(::__gnu_debug::__msg_erase_different) \
+                     ._M_sequence(*this, "this")                       \
+                     ._M_iterator(_Position, #_Position))
+
+/** Verify that we can erase the elements in the iterator range
+ *  [_First, _Last). We can erase the elements if [_First, _Last) is a
+ *  valid iterator range within this sequence.
+*/
+#define __glibcxx_check_erase_range(_First,_Last)                      \
+__glibcxx_check_valid_range(_First,_Last);                             \
+_GLIBCXX_DEBUG_VERIFY(_First._M_attached_to(this),                     \
+                     _M_message(::__gnu_debug::__msg_erase_different) \
+                      ._M_sequence(*this, "this")                      \
+                     ._M_iterator(_First, #_First)                     \
+                     ._M_iterator(_Last, #_Last))
+
+// Verify that the subscript _N is less than the container's size.
+#define __glibcxx_check_subscript(_N)                                  \
+_GLIBCXX_DEBUG_VERIFY(_N < this->size(),                               \
+                     _M_message(::__gnu_debug::__msg_subscript_oob) \
+                      ._M_sequence(*this, "this")                      \
+                     ._M_integer(_N, #_N)                              \
+                     ._M_integer(this->size(), "size"))
+
+// Verify that the container is nonempty
+#define __glibcxx_check_nonempty()                                     \
+_GLIBCXX_DEBUG_VERIFY(! this->empty(),                                 \
+                     _M_message(::__gnu_debug::__msg_empty)    \
+                      ._M_sequence(*this, "this"))
+
+// Verify that the < operator for elements in the sequence is a
+// StrictWeakOrdering by checking that it is irreflexive.
+#define __glibcxx_check_strict_weak_ordering(_First,_Last)     \
+_GLIBCXX_DEBUG_ASSERT(_First == _Last || !(*_First < *_First))
+
+// Verify that the predicate is StrictWeakOrdering by checking that it
+// is irreflexive.
+#define __glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred)  \
+_GLIBCXX_DEBUG_ASSERT(_First == _Last || !_Pred(*_First, *_First))
+
+
+// Verify that the iterator range [_First, _Last) is sorted
+#define __glibcxx_check_sorted(_First,_Last)                           \
+__glibcxx_check_valid_range(_First,_Last);                             \
+__glibcxx_check_strict_weak_ordering(_First,_Last);                    \
+_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_sorted(_First, _Last),    \
+                     _M_message(::__gnu_debug::__msg_unsorted) \
+                      ._M_iterator(_First, #_First)                    \
+                     ._M_iterator(_Last, #_Last))
+
+/** Verify that the iterator range [_First, _Last) is sorted by the
+    predicate _Pred. */
+#define __glibcxx_check_sorted_pred(_First,_Last,_Pred)                        \
+__glibcxx_check_valid_range(_First,_Last);                             \
+__glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred);         \
+_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_sorted(_First, _Last, _Pred), \
+                     _M_message(::__gnu_debug::__msg_unsorted_pred) \
+                      ._M_iterator(_First, #_First)                    \
+                     ._M_iterator(_Last, #_Last)                       \
+                     ._M_string(#_Pred))
+
+/** Verify that the iterator range [_First, _Last) is partitioned
+    w.r.t. the value _Value. */
+#define __glibcxx_check_partitioned(_First,_Last,_Value)               \
+__glibcxx_check_valid_range(_First,_Last);                             \
+_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_partitioned(_First, _Last,        \
+                                                        _Value),       \
+                     _M_message(::__gnu_debug::__msg_unpartitioned) \
+                     ._M_iterator(_First, #_First)                     \
+                     ._M_iterator(_Last, #_Last)                       \
+                     ._M_string(#_Value))
+
+/** Verify that the iterator range [_First, _Last) is partitioned
+    w.r.t. the value _Value and predicate _Pred. */
+#define __glibcxx_check_partitioned_pred(_First,_Last,_Value,_Pred)    \
+__glibcxx_check_valid_range(_First,_Last);                             \
+_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_partitioned(_First, _Last,        \
+                                                        _Value, _Pred), \
+                     _M_message(::__gnu_debug::__msg_unpartitioned_pred) \
+                     ._M_iterator(_First, #_First)                     \
+                     ._M_iterator(_Last, #_Last)                       \
+                     ._M_string(#_Pred)                                \
+                      ._M_string(#_Value))
+
+// Verify that the iterator range [_First, _Last) is a heap
+#define __glibcxx_check_heap(_First,_Last)                             \
+__glibcxx_check_valid_range(_First,_Last);                             \
+_GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last),         \
+                     _M_message(::__gnu_debug::__msg_not_heap) \
+                     ._M_iterator(_First, #_First)                     \
+                     ._M_iterator(_Last, #_Last))
+
+/** Verify that the iterator range [_First, _Last) is a heap
+    w.r.t. the predicate _Pred. */
+#define __glibcxx_check_heap_pred(_First,_Last,_Pred)                  \
+__glibcxx_check_valid_range(_First,_Last);                             \
+_GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last, _Pred),          \
+                     _M_message(::__gnu_debug::__msg_not_heap_pred) \
+                      ._M_iterator(_First, #_First)                    \
+                     ._M_iterator(_Last, #_Last)                       \
+                     ._M_string(#_Pred))
+
+#ifdef _GLIBCXX_DEBUG_PEDANTIC
+#  define __glibcxx_check_string(_String) _GLIBCXX_DEBUG_ASSERT(_String != 0)
+#  define __glibcxx_check_string_len(_String,_Len) \
+       _GLIBCXX_DEBUG_ASSERT(_String != 0 || _Len == 0)
+#else
+#  define __glibcxx_check_string(_String)
+#  define __glibcxx_check_string_len(_String,_Len)
+#endif
+
+/** Macros used by the implementation outside of debug wrappers to
+ *  verify certain properties. The __glibcxx_requires_xxx macros are
+ *  merely wrappers around the __glibcxx_check_xxx wrappers when we
+ *  are compiling with debug mode, but disappear when we are in
+ *  release mode so that there is no checking performed in, e.g., the
+ *  standard library algorithms.
+*/
+#ifdef _GLIBCXX_DEBUG
+#  define _GLIBCXX_DEBUG_ASSERT(_Condition) assert(_Condition)
+
+#  ifdef _GLIBXX_DEBUG_PEDANTIC
+#    define _GLIBCXX_DEBUG_PEDASSERT(_Condition) assert(_Condition)
+#  else
+#    define _GLIBCXX_DEBUG_PEDASSERT(_Condition)
+#  endif
+
+#  define __glibcxx_requires_cond(_Cond,_Msg) _GLIBCXX_DEBUG_VERIFY(_Cond,_Msg)
+#  define __glibcxx_requires_valid_range(_First,_Last) \
+     __glibcxx_check_valid_range(_First,_Last)
+#  define __glibcxx_requires_sorted(_First,_Last) \
+     __glibcxx_check_sorted(_First,_Last)
+#  define __glibcxx_requires_sorted_pred(_First,_Last,_Pred) \
+     __glibcxx_check_sorted_pred(_First,_Last,_Pred)
+#  define __glibcxx_requires_partitioned(_First,_Last,_Value)  \
+     __glibcxx_check_partitioned(_First,_Last,_Value)
+#  define __glibcxx_requires_partitioned_pred(_First,_Last,_Value,_Pred) \
+     __glibcxx_check_partitioned_pred(_First,_Last,_Value,_Pred)
+#  define __glibcxx_requires_heap(_First,_Last) \
+     __glibcxx_check_heap(_First,_Last)
+#  define __glibcxx_requires_heap_pred(_First,_Last,_Pred) \
+     __glibcxx_check_heap_pred(_First,_Last,_Pred)
+#  define __glibcxx_requires_nonempty() __glibcxx_check_nonempty()
+#  define __glibcxx_requires_string(_String) __glibcxx_check_string(_String)
+#  define __glibcxx_requires_string_len(_String,_Len)  \
+     __glibcxx_check_string_len(_String,_Len)
+#  define __glibcxx_requires_subscript(_N) __glibcxx_check_subscript(_N)
+#else
+#  define _GLIBCXX_DEBUG_ASSERT(_Condition)
+#  define _GLIBCXX_DEBUG_PEDASSERT(_Condition)
+#  define __glibcxx_requires_cond(_Cond,_Msg)
+#  define __glibcxx_requires_valid_range(_First,_Last)
+#  define __glibcxx_requires_sorted(_First,_Last)
+#  define __glibcxx_requires_sorted_pred(_First,_Last,_Pred)
+#  define __glibcxx_requires_partitioned(_First,_Last,_Value)
+#  define __glibcxx_requires_partitioned_pred(_First,_Last,_Value,_Pred)
+#  define __glibcxx_requires_heap(_First,_Last)
+#  define __glibcxx_requires_heap_pred(_First,_Last,_Pred)
+#  define __glibcxx_requires_nonempty()
+#  define __glibcxx_requires_string(_String)
+#  define __glibcxx_requires_string_len(_String,_Len)
+#  define __glibcxx_requires_subscript(_N)
+#endif 
+
+#include <cassert> // TBD: temporary
+
+#include <stddef.h>                       // for ptrdiff_t
+#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories
+#include <bits/type_traits.h>             // for _Is_integer
+
+namespace __gnu_debug
+{
+  template<typename _Iterator, typename _Sequence> 
+    class _Safe_iterator;
+
+  // An arbitrary iterator pointer is not singular.
+  inline bool 
+  __check_singular_aux(const void*) { return false; }
+
+  // We may have an iterator that derives from _Safe_iterator_base but isn't
+  // a _Safe_iterator.
+  template<typename _Iterator>
+    inline bool
+    __check_singular(_Iterator& __x)
+    { return __gnu_debug::__check_singular_aux(&__x); }
+
+  /** Non-NULL pointers are nonsingular. */
+  template<typename _Tp>
+    inline bool
+    __check_singular(const _Tp* __ptr)
+    { return __ptr == 0; }
+
+  /** Safe iterators know if they are singular. */
+  template<typename _Iterator, typename _Sequence>
+    inline bool
+    __check_singular(const _Safe_iterator<_Iterator, _Sequence>& __x)
+    { return __x._M_singular(); }
+
+  /** Assume that some arbitrary iterator is dereferenceable, because we
+      can't prove that it isn't. */
+  template<typename _Iterator>
+    inline bool
+    __check_dereferenceable(_Iterator&)
+    { return true; }
+
+  /** Non-NULL pointers are dereferenceable. */
+  template<typename _Tp>
+    inline bool
+    __check_dereferenceable(const _Tp* __ptr)
+    { return __ptr; }
+
+  /** Safe iterators know if they are singular. */
+  template<typename _Iterator, typename _Sequence>
+    inline bool
+    __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
+    { return __x._M_dereferenceable(); }
+
+  /** If the distance between two random access iterators is
+   *  nonnegative, assume the range is valid. 
+  */
+  template<typename _RandomAccessIterator>
+    inline bool
+    __valid_range_aux2(const _RandomAccessIterator& __first, 
+                      const _RandomAccessIterator& __last,
+                      std::random_access_iterator_tag)
+    { return __last - __first >= 0; }
+
+  /** Can't test for a valid range with input iterators, because
+   *  iteration may be destructive. So we just assume that the range
+   *  is valid.
+  */
+  template<typename _InputIterator>
+    inline bool
+    __valid_range_aux2(const _InputIterator&, const _InputIterator&,
+                      std::input_iterator_tag)
+    { return true; }
+
+  /** We say that integral types for a valid range, and defer to other
+   *  routines to realize what to do with integral types instead of
+   *  iterators. 
+  */
+  template<typename _Integral>
+    inline bool
+    __valid_range_aux(const _Integral&, const _Integral&, __true_type)
+    { return true; }
+
+  /** We have iterators, so figure out what kind of iterators that are
+   *  to see if we can check the range ahead of time.
+  */
+  template<typename _InputIterator>
+    inline bool
+    __valid_range_aux(const _InputIterator& __first, 
+                     const _InputIterator& __last, __false_type)
+  {
+    typedef typename std::iterator_traits<_InputIterator>::iterator_category
+      _Category;
+    return __gnu_debug::__valid_range_aux2(__first, __last, _Category()); 
+  }
+
+  /** Don't know what these iterators are, or if they are even
+   *  iterators (we may get an integral type for InputIterator), so
+   *  see if they are integral and pass them on to the next phase
+   *  otherwise.
+  */
+  template<typename _InputIterator>
+    inline bool
+    __valid_range(const _InputIterator& __first, const _InputIterator& __last)
+    { 
+      typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
+      return __gnu_debug::__valid_range_aux(__first, __last, _Integral());
+    }
+
+  /** Safe iterators know how to check if they form a valid range. */
+  template<typename _Iterator, typename _Sequence>
+    inline bool 
+    __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
+                 const _Safe_iterator<_Iterator, _Sequence>& __last)
+    { return __first._M_valid_range(__last); }
+
+  /* Checks that [first, last) is a valid range, and then returns
+   * __first. This routine is useful when we can't use a separate
+   * assertion statement because, e.g., we are in a constructor. 
+  */
+  template<typename _InputIterator>
+    inline _InputIterator
+    __check_valid_range(const _InputIterator& __first, 
+                       const _InputIterator& __last)
+    {
+      _GLIBCXX_DEBUG_ASSERT(__gnu_debug::__valid_range(__first, __last));
+      return __first;
+    }
+
+  /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
+  template<typename _CharT, typename _Integer>
+    inline const _CharT*
+    __check_string(const _CharT* __s, const _Integer& __n)
+    {
+#ifdef _GLIBCXX_DEBUG_PEDANTIC
+      _GLIBCXX_DEBUG_ASSERT(__s != 0 || __n == 0);
+#endif
+      return __s;
+    }
+
+  /** Checks that __s is non-NULL and then returns __s. */
+  template<typename _CharT>
+    inline const _CharT*
+    __check_string(const _CharT* __s)
+    {
+#ifdef _GLIBCXX_DEBUG_PEDANTIC
+      _GLIBCXX_DEBUG_ASSERT(__s != 0);
+#endif
+      return __s;
+    }
+
+  // Can't check if an input iterator sequence is sorted, because we
+  // can't step through the sequence.
+  template<typename _InputIterator>
+    inline bool 
+    __check_sorted_aux(const _InputIterator&, const _InputIterator&,
+                       std::input_iterator_tag)
+    { return true; }
+
+  // Can verify if a forward iterator sequence is in fact sorted using
+  // std::__is_sorted
+  template<typename _ForwardIterator>
+    inline bool
+    __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
+                       std::forward_iterator_tag)
+    { 
+      if (__first == __last)
+        return true;
+
+      _ForwardIterator __next = __first;
+      for (++__next; __next != __last; __first = __next, ++__next) {
+        if (*__next < *__first)
+          return false;
+      }
+
+      return true;
+    }
+
+  // Can't check if an input iterator sequence is sorted, because we can't step
+  // through the sequence.
+  template<typename _InputIterator, typename _Predicate>
+    inline bool 
+    __check_sorted_aux(const _InputIterator&, const _InputIterator&,
+                       _Predicate, std::input_iterator_tag)
+    { return true; }
+
+  // Can verify if a forward iterator sequence is in fact sorted using
+  // std::__is_sorted
+  template<typename _ForwardIterator, typename _Predicate>
+    inline bool
+    __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 
+                       _Predicate __pred, std::forward_iterator_tag)
+    { 
+      if (__first == __last)
+        return true;
+
+      _ForwardIterator __next = __first;
+      for (++__next; __next != __last; __first = __next, ++__next) {
+        if (__pred(*__next, *__first))
+          return false;
+      }
+
+      return true;
+    }
+
+  // Determine if a sequence is sorted.
+  template<typename _InputIterator>
+    inline bool
+    __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
+    { 
+      typedef typename std::iterator_traits<_InputIterator>::iterator_category 
+        _Category;
+      return __gnu_debug::__check_sorted_aux(__first, __last, _Category());
+    }
+
+  template<typename _InputIterator, typename _Predicate>
+    inline bool
+    __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
+                   _Predicate __pred)
+    { 
+      typedef typename std::iterator_traits<_InputIterator>::iterator_category 
+        _Category;
+      return __gnu_debug::__check_sorted_aux(__first, __last, __pred,
+                                            _Category());
+    }
+
+  // _GLIBCXX_RESOLVE_LIB_DEFECTS
+  // 270. Binary search requirements overly strict 
+  // Determine if a sequence is partitioned w.r.t. this element.
+  template<typename _ForwardIterator, typename _Tp>
+    inline bool
+    __check_partitioned(_ForwardIterator __first, _ForwardIterator __last,
+                       const _Tp& __value)
+    {
+      while (__first != __last && *__first < __value)
+       ++__first;
+      while (__first != __last && !(*__first < __value))
+       ++__first;
+      return __first == __last;
+    }
+
+  // Determine if a sequence is partitioned w.r.t. this element.
+  template<typename _ForwardIterator, typename _Tp, typename _Pred>
+    inline bool
+    __check_partitioned(_ForwardIterator __first, _ForwardIterator __last,
+                       const _Tp& __value, _Pred __pred)
+    {
+      while (__first != __last && __pred(*__first, __value))
+       ++__first;
+      while (__first != __last && !__pred(*__first, __value))
+       ++__first;
+      return __first == __last;
+    }
+} // namespace __gnu_debug
+
+#ifdef _GLIBCXX_DEBUG
+// We need the error formatter
+#  include <debug/formatter.h>
+#endif
+
+#endif 
diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
new file mode 100644 (file)
index 0000000..b9d68af
--- /dev/null
@@ -0,0 +1,386 @@
+// Debugging deque implementation -*- C++ -*-
+
+// Copyright (C) 2003
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_DEQUE
+#define _GLIBCXX_DEBUG_DEQUE 1
+
+#include <deque>
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug_def
+{
+  template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
+    class deque 
+    : public  __gnu_norm::deque<_Tp, _Allocator>,
+    public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
+    {
+      typedef  __gnu_norm::deque<_Tp, _Allocator> _Base;
+      typedef __gnu_debug::_Safe_sequence<deque> _Safe_base;
+
+    public:
+      typedef typename _Allocator::reference        reference;
+      typedef typename _Allocator::const_reference  const_reference;
+      
+      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque> 
+                                                   iterator;
+      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque>
+                                                    const_iterator;
+      
+      typedef typename _Base::size_type             size_type;
+      typedef typename _Base::difference_type       difference_type;
+      
+      typedef _Tp                                  value_type;
+      typedef _Allocator                           allocator_type;
+      typedef typename _Allocator::pointer          pointer;
+      typedef typename _Allocator::const_pointer    const_pointer;
+      typedef std::reverse_iterator<iterator>       reverse_iterator;
+      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
+      // 23.2.1.1 construct/copy/destroy:
+      explicit deque(const _Allocator& __a = _Allocator())
+      : _Base(__a) { }
+
+      explicit deque(size_type __n, const _Tp& __value = _Tp(),
+                    const _Allocator& __a = _Allocator())
+      : _Base(__n, __value, __a) { }
+
+      template<class _InputIterator>
+        deque(_InputIterator __first, _InputIterator __last,
+             const _Allocator& __a = _Allocator())
+       : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
+        { }
+
+      deque(const deque<_Tp,_Allocator>& __x) : _Base(__x), _Safe_base() { }
+
+      deque(const _Base& __x) : _Base(__x), _Safe_base() { }
+      
+      ~deque() { }
+      
+      deque<_Tp,_Allocator>& 
+      operator=(const deque<_Tp,_Allocator>& __x)
+      {
+       *static_cast<_Base*>(this) = __x;
+       this->_M_invalidate_all();
+       return *this;
+      }
+      
+      template<class _InputIterator>
+        void 
+        assign(_InputIterator __first, _InputIterator __last)
+        {
+         __glibcxx_check_valid_range(__first, __last);
+         _Base::assign(__first, __last);
+         this->_M_invalidate_all();
+       }
+
+      void 
+      assign(size_type __n, const _Tp& __t)
+      {
+       _Base::assign(__n, __t);
+       this->_M_invalidate_all();
+      }
+      
+      using _Base::get_allocator;
+      
+      // iterators:
+      iterator 
+      begin() 
+      { return iterator(_Base::begin(), this); }
+      
+      const_iterator 
+      begin() const 
+      { return const_iterator(_Base::begin(), this); }
+      
+      iterator 
+      end() 
+      { return iterator(_Base::end(), this); }
+      
+      const_iterator 
+      end() const 
+      { return const_iterator(_Base::end(), this); }
+      
+      reverse_iterator 
+      rbegin() 
+      { return reverse_iterator(end()); }
+      
+      const_reverse_iterator 
+      rbegin() const
+      { return const_reverse_iterator(end()); }
+      
+      reverse_iterator 
+      rend() 
+      { return reverse_iterator(begin()); }
+      
+      const_reverse_iterator 
+      rend() const
+      { return const_reverse_iterator(begin()); }
+      
+      // 23.2.1.2 capacity:
+      using _Base::size;
+      using _Base::max_size;
+      
+      void 
+      resize(size_type __sz, _Tp __c = _Tp())
+      {
+       typedef typename _Base::const_iterator _Base_const_iterator;
+       typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
+       
+       bool __invalidate_all = __sz > this->size();
+       if (__sz < this->size())
+         this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
+       
+       _Base::resize(__sz, __c);
+       
+       if (__invalidate_all)
+         this->_M_invalidate_all();
+      }
+      
+      using _Base::empty;
+      
+      // element access:
+      reference 
+      operator[](size_type __n)
+      {
+       __glibcxx_check_subscript(__n);
+       return _M_base()[__n];
+      }
+      
+      const_reference 
+      operator[](size_type __n) const
+      {
+       __glibcxx_check_subscript(__n);
+       return _M_base()[__n];
+      }
+      
+      using _Base::at;
+      
+      reference 
+      front()
+      {
+       __glibcxx_check_nonempty();
+       return _Base::front();
+      }
+      
+      const_reference 
+      front() const
+      {
+       __glibcxx_check_nonempty();
+       return _Base::front();
+      }
+      
+      reference 
+      back()
+      {
+       __glibcxx_check_nonempty();
+       return _Base::back();
+      }
+      
+      const_reference 
+      back() const
+      {
+       __glibcxx_check_nonempty();
+       return _Base::back();
+      }
+      
+      // 23.2.1.3 modifiers:
+      void 
+      push_front(const _Tp& __x)
+      {
+       _Base::push_front(__x);
+       this->_M_invalidate_all();
+      }
+      
+      void 
+      push_back(const _Tp& __x)
+      {
+       _Base::push_back(__x);
+       this->_M_invalidate_all();
+      }
+      
+      iterator 
+      insert(iterator __position, const _Tp& __x)
+      {
+       __glibcxx_check_insert(__position);
+       typename _Base::iterator __res = _Base::insert(__position.base(), __x);
+       this->_M_invalidate_all();
+       return iterator(__res, this);
+      }
+      
+      void 
+      insert(iterator __position, size_type __n, const _Tp& __x)
+      {
+       __glibcxx_check_insert(__position);
+       _Base::insert(__position.base(), __n, __x);
+       this->_M_invalidate_all();
+      }
+      
+      template<class _InputIterator>
+        void 
+        insert(iterator __position, 
+              _InputIterator __first, _InputIterator __last)
+        {
+         __glibcxx_check_insert_range(__position, __first, __last);
+         _Base::insert(__position.base(), __first, __last);
+         this->_M_invalidate_all();
+       }
+      
+      void 
+      pop_front()
+      {
+       __glibcxx_check_nonempty();
+       iterator __victim = begin();
+       __victim._M_invalidate();
+       _Base::pop_front();
+      }
+      
+      void 
+      pop_back()
+      {
+       __glibcxx_check_nonempty();
+       iterator __victim = end();
+       --__victim;
+       __victim._M_invalidate();
+       _Base::pop_back();
+      }
+      
+      iterator 
+      erase(iterator __position)
+      {
+       __glibcxx_check_erase(__position);
+       if (__position == begin() || __position == end()-1)
+         {
+           __position._M_invalidate();
+           return iterator(_Base::erase(__position.base()), this);
+         }
+       else
+         {
+           typename _Base::iterator __res = _Base::erase(__position.base());
+           this->_M_invalidate_all();
+           return iterator(__res, this);
+         }
+      }
+      
+      iterator 
+      erase(iterator __first, iterator __last)
+      {
+       // _GLIBCXX_RESOLVE_LIB_DEFECTS
+       // 151. can't currently clear() empty container
+       __glibcxx_check_erase_range(__first, __last);
+       if (__first == begin() || __last == end()-1)
+         {
+           this->_M_detach_singular();
+           for (iterator __position = __first; __position != __last; )
+             {
+               iterator __victim = __position++;
+               __victim._M_invalidate();
+             }
+           try 
+             { 
+               return iterator(_Base::erase(__first.base(), __last.base()),
+                               this); 
+             }
+           catch (...)
+             {
+               this->_M_revalidate_singular();
+               __throw_exception_again;
+             }
+         }
+       else
+         {
+           typename _Base::iterator __res = _Base::erase(__first.base(), 
+                                                         __last.base());
+           this->_M_invalidate_all();
+           return iterator(__res, this);
+         }
+      }
+      
+      void 
+      swap(deque<_Tp,_Allocator>& __x)
+      {
+       _Base::swap(__x);
+       this->_M_swap(__x);
+      }
+      
+      void 
+      clear()
+      {
+       _Base::clear();
+       this->_M_invalidate_all();
+      }
+      
+      _Base&       
+      _M_base()       { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+    };
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator==(const deque<_Tp, _Alloc>& __lhs, 
+              const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() == __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator!=(const deque<_Tp, _Alloc>& __lhs, 
+              const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() != __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator<(const deque<_Tp, _Alloc>& __lhs, const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() < __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator<=(const deque<_Tp, _Alloc>& __lhs, 
+              const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() <= __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator>=(const deque<_Tp, _Alloc>& __lhs, 
+              const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() >= __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator>(const deque<_Tp, _Alloc>& __lhs, const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() > __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline void
+    swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
+    { __lhs.swap(__rhs); }
+} // namespace __gnu_debug_def
+
+#endif
diff --git a/libstdc++-v3/include/debug/formatter.h b/libstdc++-v3/include/debug/formatter.h
new file mode 100644 (file)
index 0000000..317ce21
--- /dev/null
@@ -0,0 +1,385 @@
+// Debug-mode error formatting implementation -*- C++ -*-
+
+// Copyright (C) 2003
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_FORMATTER_H
+#define _GLIBCXX_DEBUG_FORMATTER_H 1
+
+#include <typeinfo>
+#include <debug/debug.h>
+
+namespace __gnu_debug
+{
+  /** Determine if the two types are the same. */
+  template<typename _Type1, typename _Type2>
+    struct __is_same
+    {
+      static const bool value = false;
+    };
+
+  template<typename _Type>
+    struct __is_same<_Type, _Type>
+    {
+      static const bool value = true;
+    };
+
+  template<bool> struct __truth { };
+
+  class _Safe_sequence_base;
+
+  template<typename _Iterator, typename _Sequence> 
+    class _Safe_iterator;
+
+  template<typename _Sequence> 
+    class _Safe_sequence;
+
+  enum _Debug_msg_id
+  {
+    // General checks
+    __msg_valid_range,
+    __msg_insert_singular,
+    __msg_insert_different,
+    __msg_erase_bad,
+    __msg_erase_different,
+    __msg_subscript_oob,
+    __msg_empty,
+    __msg_unpartitioned,
+    __msg_unpartitioned_pred,
+    __msg_unsorted,
+    __msg_unsorted_pred,
+    __msg_not_heap,
+    __msg_not_heap_pred,
+    // std::bitset checks
+    __msg_bad_bitset_write,
+    __msg_bad_bitset_read,
+    __msg_bad_bitset_flip,
+    // std::list checks
+    __msg_self_splice,
+    __msg_splice_alloc,
+    __msg_splice_bad,
+    __msg_splice_other,
+    __msg_splice_overlap,
+    // iterator checks
+    __msg_init_singular,
+    __msg_init_copy_singular,
+    __msg_init_const_singular,
+    __msg_copy_singular,
+    __msg_bad_deref,
+    __msg_bad_inc,
+    __msg_bad_dec,
+    __msg_iter_subscript_oob,
+    __msg_advance_oob,
+    __msg_retreat_oob,
+    __msg_iter_compare_bad,
+    __msg_compare_different,
+    __msg_iter_order_bad,
+    __msg_order_different,
+    __msg_distance_bad,
+    __msg_distance_different,
+    // istream_iterator
+    __msg_deref_istream,
+    __msg_inc_istream,
+    // ostream_iterator
+    __msg_output_ostream,
+    // istreambuf_iterator
+    __msg_deref_istreambuf,
+    __msg_inc_istreambuf
+  };
+
+  class _Error_formatter
+  {
+    /// Whether an iterator is constant, mutable, or unknown
+    enum _Constness
+    {
+      __unknown_constness,
+      __const_iterator,
+      __mutable_iterator,
+      __last_constness
+    }; 
+
+    // The state of the iterator (fine-grained), if we know it.
+    enum _Iterator_state
+    {
+      __unknown_state,
+      __singular,      // singular, may still be attached to a sequence
+      __begin,         // dereferenceable, and at the beginning
+      __middle,        // dereferenceable, not at the beginning
+      __end,           // past-the-end, may be at beginning if sequence empty
+      __last_state
+    };
+
+    // Tags denoting the type of parameter for construction
+    struct _Is_iterator { };
+    struct _Is_sequence { };
+
+    // A parameter that may be referenced by an error message
+    struct _Parameter
+    {
+      enum 
+      { 
+       __unused_param, 
+       __iterator, 
+       __sequence, 
+       __integer,
+       __string
+      } _M_kind;
+      
+      union
+      {
+       // When _M_kind == __iterator
+       struct 
+       {
+         const char*      _M_name;      
+         const void*      _M_address;   
+         const type_info* _M_type;   
+         _Constness       _M_constness;
+         _Iterator_state  _M_state;
+         const void*      _M_sequence;  
+         const type_info* _M_seq_type;
+       } _M_iterator;
+       
+       // When _M_kind == __sequence
+       struct
+       {
+         const char*      _M_name;
+         const void*      _M_address;
+         const type_info* _M_type;
+       } _M_sequence;
+
+       // When _M_kind == __integer
+       struct
+       {
+         const char* _M_name;
+         long        _M_value;
+       } _M_integer;
+
+       // When _M_kind == __string
+       struct
+       {
+         const char* _M_name;
+         const char* _M_value;
+       } _M_string;
+      } _M_variant;
+
+      _Parameter() : _M_kind(__unused_param) { }
+      
+      _Parameter(long __value, const char* __name) 
+      : _M_kind(__integer)
+      { 
+       _M_variant._M_integer._M_name = __name;
+       _M_variant._M_integer._M_value = __value; 
+      }
+
+      _Parameter(const char* __value, const char* __name)
+      : _M_kind(__string)
+      {
+       _M_variant._M_string._M_name = __name;
+       _M_variant._M_string._M_value = __value; 
+      }
+
+      template<typename _Iterator, typename _Sequence>
+        _Parameter(const _Safe_iterator<_Iterator, _Sequence>& __it,
+                  const char* __name, _Is_iterator)
+       : _M_kind(__iterator)
+        {
+         _M_variant._M_iterator._M_name = __name;
+         _M_variant._M_iterator._M_address = &__it;
+         _M_variant._M_iterator._M_type = &typeid(__it);
+         _M_variant._M_iterator._M_constness = 
+           __is_same<_Safe_iterator<_Iterator, _Sequence>,
+                                typename _Sequence::iterator>::
+             value? __mutable_iterator : __const_iterator;
+         _M_variant._M_iterator._M_sequence = __it._M_get_sequence();
+         _M_variant._M_iterator._M_seq_type = &typeid(_Sequence);
+
+         if (__it._M_singular())
+           _M_variant._M_iterator._M_state = __singular;
+         else
+           {
+             bool __is_begin = __it._M_is_begin();
+             bool __is_end = __it._M_is_end();
+             if (__is_end)
+               _M_variant._M_iterator._M_state = __end;
+             else if (__is_begin)
+               _M_variant._M_iterator._M_state = __begin;
+             else
+               _M_variant._M_iterator._M_state = __middle;
+           }
+       }
+
+      template<typename _Type>
+        _Parameter(const _Type*& __it, const char* __name, _Is_iterator)
+       : _M_kind(__iterator)
+        {
+         _M_variant._M_iterator._M_name = __name;
+         _M_variant._M_iterator._M_address = &__it;
+         _M_variant._M_iterator._M_type = &typeid(__it);
+         _M_variant._M_iterator._M_constness = __mutable_iterator;
+         _M_variant._M_iterator._M_state = __it? __unknown_state : __singular;
+         _M_variant._M_iterator._M_sequence = 0;
+         _M_variant._M_iterator._M_seq_type = 0;
+       }
+
+      template<typename _Type>
+        _Parameter(_Type*& __it, const char* __name, _Is_iterator)
+        : _M_kind(__iterator)
+        {
+         _M_variant._M_iterator._M_name = __name;
+         _M_variant._M_iterator._M_address = &__it;
+         _M_variant._M_iterator._M_type = &typeid(__it);
+         _M_variant._M_iterator._M_constness = __const_iterator;
+         _M_variant._M_iterator._M_state = __it? __unknown_state : __singular;
+         _M_variant._M_iterator._M_sequence = 0;
+         _M_variant._M_iterator._M_seq_type = 0;
+       }
+      
+      template<typename _Iterator>
+        _Parameter(const _Iterator& __it, const char* __name, _Is_iterator)
+       : _M_kind(__iterator)
+        {
+         _M_variant._M_iterator._M_name = __name;
+         _M_variant._M_iterator._M_address = &__it;
+         _M_variant._M_iterator._M_type = &typeid(__it);
+         _M_variant._M_iterator._M_constness = __unknown_constness;
+         _M_variant._M_iterator._M_state = 
+           __gnu_debug::__check_singular(__it)? __singular : __unknown_state;
+         _M_variant._M_iterator._M_sequence = 0;
+         _M_variant._M_iterator._M_seq_type = 0;
+       }
+
+      template<typename _Sequence>
+        _Parameter(const _Safe_sequence<_Sequence>& __seq,
+                  const char* __name, _Is_sequence)
+       : _M_kind(__sequence)
+        {
+         _M_variant._M_sequence._M_name = __name;
+         _M_variant._M_sequence._M_address = 
+           static_cast<const _Sequence*>(&__seq);
+         _M_variant._M_sequence._M_type = &typeid(_Sequence);
+       }
+
+      template<typename _Sequence>
+        _Parameter(const _Sequence& __seq, const char* __name, _Is_sequence)
+       : _M_kind(__sequence)
+        {
+         _M_variant._M_sequence._M_name = __name;
+         _M_variant._M_sequence._M_address = &__seq;
+         _M_variant._M_sequence._M_type = &typeid(_Sequence);
+       }
+      
+      void
+      _M_print_field(const _Error_formatter* __formatter, 
+                    const char* __name) const;
+                                        
+      void
+      _M_print_description(const _Error_formatter* __formatter) const;
+    };
+
+    friend struct _Parameter;
+
+  public:    
+    template<typename _Iterator>
+      const _Error_formatter&
+      _M_iterator(const _Iterator& __it, const char* __name = 0)  const
+      {
+       if (_M_num_parameters < __max_parameters)
+         _M_parameters[_M_num_parameters++] = _Parameter(__it, __name,
+                                                         _Is_iterator());
+       return *this;
+      }
+
+    const _Error_formatter&
+    _M_integer(long __value, const char* __name = 0) const
+    {
+      if (_M_num_parameters < __max_parameters)
+       _M_parameters[_M_num_parameters++] = _Parameter(__value, __name);
+      return *this;
+    }
+
+    const _Error_formatter&
+    _M_string(const char* __value, const char* __name = 0) const
+    {
+      if (_M_num_parameters < __max_parameters)
+       _M_parameters[_M_num_parameters++] = _Parameter(__value, __name);
+      return *this;
+    }
+
+    template<typename _Sequence>
+      const _Error_formatter&
+      _M_sequence(const _Sequence& __seq, const char* __name = 0) const
+      {
+       if (_M_num_parameters < __max_parameters)
+         _M_parameters[_M_num_parameters++] = _Parameter(__seq, __name, 
+                                                         _Is_sequence());
+       return *this;
+      }
+
+    const _Error_formatter&
+    _M_message(const char* __text) const
+    { _M_text = __text; return *this; }
+
+    const _Error_formatter&
+    _M_message(_Debug_msg_id __id) const;
+
+    void 
+    _M_error() const;
+
+  private:
+    _Error_formatter(const char* __file, size_t __line)
+    : _M_file(__file), _M_line(__line), _M_num_parameters(0), _M_text(0),
+      _M_max_length(78), _M_column(1), _M_first_line(true), _M_wordwrap(false)
+    { }
+
+    void 
+    _M_print_word(const char* __word) const;
+
+    void 
+    _M_print_string(const char* __string) const;
+
+    enum { __max_parameters = 9 };
+
+    const char*         _M_file;
+    size_t              _M_line;
+    mutable _Parameter  _M_parameters[__max_parameters];
+    mutable size_t      _M_num_parameters;
+    mutable const char* _M_text;
+    mutable size_t      _M_max_length;
+    enum { _M_indent = 4 } ;
+    mutable size_t      _M_column;
+    mutable bool        _M_first_line;
+    mutable bool        _M_wordwrap;
+
+  public:
+    static _Error_formatter
+    _M_at(const char* __file, size_t __line)
+    { return _Error_formatter(__file, __line); }
+  };
+} // namespace __gnu_debug
+
+#endif 
diff --git a/libstdc++-v3/include/debug/hash_map b/libstdc++-v3/include/debug/hash_map
new file mode 100644 (file)
index 0000000..570a9af
--- /dev/null
@@ -0,0 +1,38 @@
+// Debugging hash_map/hash_multimap implementation -*- C++ -*-
+
+// Copyright (C) 2003
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_HASH_MAP
+#define _GLIBCXX_DEBUG_HASH_MAP 1
+
+#include <hash_map>
+#include <debug/dbg_hash_map.h>
+#include <debug/dbg_hash_multimap.h>
+
+#endif
diff --git a/libstdc++-v3/include/debug/hash_map.h b/libstdc++-v3/include/debug/hash_map.h
new file mode 100644 (file)
index 0000000..5ca102a
--- /dev/null
@@ -0,0 +1,270 @@
+// Debugging hash_map implementation -*- C++ -*-
+
+// Copyright (C) 2003
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_HASH_MAP_H
+#define _GLIBCXX_DEBUG_HASH_MAP_H 1
+
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug_def
+{
+  template<typename _Value, typename _Tp,
+          typename _HashFcn  = __gnu_cxx::hash<_Value>,
+          typename _EqualKey = std::equal_to<_Value>,
+          typename _Alloc = std::allocator<_Value> >
+    class hash_map
+    : public __gnu_cxx::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>,
+      public __gnu_debug::_Safe_sequence<hash_map<_Value, _Tp, _HashFcn,
+                                                _EqualKey, _Alloc> >
+    {
+      typedef __gnu_cxx::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc> 
+                                                       _Base;
+      typedef __gnu_debug::_Safe_sequence<hash_map>    _Safe_base;
+
+    public:
+      typedef typename _Base::key_type        key_type;
+      typedef typename _Base::data_type       data_type;
+      typedef typename _Base::mapped_type     mapped_type;
+      typedef typename _Base::value_type      value_type;
+      typedef typename _Base::hasher          hasher;
+      typedef typename _Base::key_equal       key_equal;
+      typedef typename _Base::size_type       size_type;
+      typedef typename _Base::difference_type difference_type;