Makefile.am: Add alloc_traits.h headers.

2011-06-22  Jonathan Wakely  <jwakely.gcc@gmail.com>

	* include/Makefile.am: Add alloc_traits.h headers.
	* include/Makefile.in: Regenerate.
	* include/std/memory: Include uses_allocator.h explicitly.
	* include/bits/allocator.h (allocator_traits): Move to ...
	* include/bits/alloc_traits.h: New header.
	* include/ext/alloc_traits.h (__alloc_traits): Extension to provide
	a common allocator interface for C++98 and C++0x.
	* include/bits/stl_construct.h: Use __alloc_traits.
	* include/bits/stl_uninitialized.h: Likewise.

From-SVN: r175305

9 files changed, 659 insertions, 411 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index bd75196..0fc0f73 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,15 @@
+2011-06-22  Jonathan Wakely  <jwakely.gcc@gmail.com>
+
+	* include/Makefile.am: Add alloc_traits.h headers.
+	* include/Makefile.in: Regenerate.
+	* include/std/memory: Include uses_allocator.h explicitly.
+	* include/bits/allocator.h (allocator_traits): Move to ...
+	* include/bits/alloc_traits.h: New header.
+	* include/ext/alloc_traits.h (__alloc_traits): Extension to provide
+	a common allocator interface for C++98 and C++0x.
+	* include/bits/stl_construct.h: Use __alloc_traits.
+	* include/bits/stl_uninitialized.h: Likewise.
+
 2011-06-22  Daniel Krugler  <daniel.kruegler@googlemail.com>
 	    Paolo Carlini  <paolo.carlini@oracle.com>
 
diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index 6a21c16..b6a0116 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -79,6 +79,7 @@ bits_srcdir = ${glibcxx_srcdir}/include/bits
 bits_builddir = ./bits
 bits_headers = \
         ${bits_srcdir}/algorithmfwd.h \
+	${bits_srcdir}/alloc_traits.h \
 	${bits_srcdir}/allocator.h \
 	${bits_srcdir}/atomic_base.h \
 	${bits_srcdir}/atomic_0.h \
@@ -493,6 +494,7 @@ ext_srcdir = ${glibcxx_srcdir}/include/ext
 ext_builddir = ./ext
 ext_headers = \
 	${ext_srcdir}/algorithm \
+	${ext_srcdir}/alloc_traits.h \
 	${ext_srcdir}/atomicity.h \
 	${ext_srcdir}/array_allocator.h \
 	${ext_srcdir}/bitmap_allocator.h \
diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
index 5b05ef3..7fdf182 100644
--- a/libstdc++-v3/include/Makefile.in
+++ b/libstdc++-v3/include/Makefile.in
@@ -330,6 +330,7 @@ bits_srcdir = ${glibcxx_srcdir}/include/bits
 bits_builddir = ./bits
 bits_headers = \
         ${bits_srcdir}/algorithmfwd.h \
+	${bits_srcdir}/alloc_traits.h \
 	${bits_srcdir}/allocator.h \
 	${bits_srcdir}/atomic_base.h \
 	${bits_srcdir}/atomic_0.h \
@@ -742,6 +743,7 @@ ext_srcdir = ${glibcxx_srcdir}/include/ext
 ext_builddir = ./ext
 ext_headers = \
 	${ext_srcdir}/algorithm \
+	${ext_srcdir}/alloc_traits.h \
 	${ext_srcdir}/atomicity.h \
 	${ext_srcdir}/array_allocator.h \
 	${ext_srcdir}/bitmap_allocator.h \
diff --git a/libstdc++-v3/include/bits/alloc_traits.h b/libstdc++-v3/include/bits/alloc_traits.h
new file mode 100644
index 0000000..9d2a472
--- /dev/null
+++ b/libstdc++-v3/include/bits/alloc_traits.h
@@ -0,0 +1,499 @@
+// Allocator traits -*- C++ -*-
+
+// Copyright (C) 2011 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 3, 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.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef _ALLOC_TRAITS_H
+#define _ALLOC_TRAITS_H 1
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+
+#include <bits/ptr_traits.h>
+#include <ext/numeric_traits.h>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  template<typename _Alloc, typename _Tp>
+    class __alloctr_rebind_helper
+    {
+      template<typename _Alloc2, typename _Tp2>
+	static constexpr bool
+       	_S_chk(typename _Alloc2::template rebind<_Tp2>::other*)
+	{ return true; }
+
+      template<typename, typename>
+        static constexpr bool
+       	_S_chk(...)
+       	{ return false; }
+
+    public:
+      static const bool __value = _S_chk<_Alloc, _Tp>(nullptr);
+    };
+
+  template<typename _Alloc, typename _Tp,
+           bool = __alloctr_rebind_helper<_Alloc, _Tp>::__value>
+    struct __alloctr_rebind;
+
+  template<typename _Alloc, typename _Tp>
+    struct __alloctr_rebind<_Alloc, _Tp, true>
+    {
+      typedef typename _Alloc::template rebind<_Tp>::other __type;
+    };
+
+  template<template<typename, typename...> class _Alloc, typename _Tp,
+            typename _Up, typename... _Args>
+    struct __alloctr_rebind<_Alloc<_Up, _Args...>, _Tp, false>
+    {
+      typedef _Alloc<_Tp, _Args...> __type;
+    };
+
+  /**
+   * @brief  Uniform interface to all allocator types.
+   * @ingroup allocators
+  */
+  template<typename _Alloc>
+    struct allocator_traits
+    {
+      /// The allocator type
+      typedef _Alloc allocator_type;
+      /// The allocated type
+      typedef typename _Alloc::value_type value_type;
+
+#define _GLIBCXX_ALLOC_TR_NESTED_TYPE(_NTYPE, _ALT) \
+  private: \
+  template<typename _Tp> \
+    static typename _Tp::_NTYPE _S_##_NTYPE##_helper(_Tp*); \
+  static _ALT _S_##_NTYPE##_helper(...); \
+    typedef decltype(_S_##_NTYPE##_helper((_Alloc*)0)) __##_NTYPE; \
+  public:
+
+_GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*)
+
+      /**
+       * @brief   The allocator's pointer type.
+       *
+       * @c Alloc::pointer if that type exists, otherwise @c value_type*
+      */
+      typedef __pointer pointer;
+
+// TODO: Use pointer_traits::rebind alias template.
+
+_GLIBCXX_ALLOC_TR_NESTED_TYPE(const_pointer,
+  typename pointer_traits<pointer>::template __rebind<const value_type>::__type)
+
+      /**
+       * @brief   The allocator's const pointer type.
+       *
+       * @c Alloc::const_pointer if that type exists, otherwise
+       * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
+      */
+      typedef __const_pointer const_pointer;
+
+_GLIBCXX_ALLOC_TR_NESTED_TYPE(void_pointer,
+  typename pointer_traits<pointer>::template __rebind<void>::__type)
+
+      /**
+       * @brief   The allocator's void pointer type.
+       *
+       * @c Alloc::void_pointer if that type exists, otherwise
+       * <tt> pointer_traits<pointer>::rebind<void> </tt>
+      */
+      typedef __void_pointer void_pointer;
+
+_GLIBCXX_ALLOC_TR_NESTED_TYPE(const_void_pointer,
+  typename pointer_traits<pointer>::template __rebind<const void>::__type)
+
+      /**
+       * @brief   The allocator's const void pointer type.
+       *
+       * @c Alloc::const_void_pointer if that type exists, otherwise
+       * <tt> pointer_traits<pointer>::rebind<const void> </tt>
+      */
+      typedef __const_void_pointer const_void_pointer;
+
+_GLIBCXX_ALLOC_TR_NESTED_TYPE(difference_type,
+                              typename pointer_traits<pointer>::difference_type)
+
+      /**
+       * @brief   The allocator's difference type
+       *
+       * @c Alloc::difference_type if that type exists, otherwise
+       * <tt> pointer_traits<pointer>::difference_type </tt>
+      */
+      typedef __difference_type difference_type;
+
+_GLIBCXX_ALLOC_TR_NESTED_TYPE(size_type,
+                              typename make_unsigned<difference_type>::type)
+
+      /**
+       * @brief   The allocator's size type
+       *
+       * @c Alloc::size_type if that type exists, otherwise
+       * <tt> make_unsigned<difference_type>::type </tt>
+      */
+      typedef __size_type size_type;
+
+_GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_copy_assignment,
+                              false_type)
+
+      /**
+       * @brief   How the allocator is propagated on copy assignment
+       *
+       * @c Alloc::propagate_on_container_copy_assignment if that type exists,
+       * otherwise @c false_type
+      */
+      typedef __propagate_on_container_copy_assignment
+       	propagate_on_container_copy_assignment;
+
+_GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_move_assignment,
+                              false_type)
+
+      /**
+       * @brief   How the allocator is propagated on move assignment
+       *
+       * @c Alloc::propagate_on_container_move_assignment if that type exists,
+       * otherwise @c false_type
+      */
+      typedef __propagate_on_container_move_assignment
+       	propagate_on_container_move_assignment;
+
+_GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap,
+                              false_type)
+
+      /**
+       * @brief   How the allocator is propagated on swap
+       *
+       * @c Alloc::propagate_on_container_swap if that type exists,
+       * otherwise @c false_type
+      */
+      typedef __propagate_on_container_swap propagate_on_container_swap;
+
+#undef _GLIBCXX_ALLOC_TR_NESTED_TYPE
+
+      /* TODO: use template alias 
+      template<typename _Tp>
+        using rebind_alloc = __alloctr_rebind<_Alloc, _Tp>::__type;
+      template<typename _Tp>
+        using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
+      */
+      template<typename _Tp>
+        struct __rebind_alloc
+	{
+  	  typedef typename __alloctr_rebind<_Alloc, _Tp>::__type __type;
+       	};
+
+      template<typename _Tp>
+        struct __rebind_traits
+	{
+	  typedef allocator_traits<typename __rebind_alloc<_Tp>::__type> __type;
+	};
+
+    private:
+      template<typename _Alloc2>
+	struct __allocate_helper
+	{
+	  template<typename _Alloc3,
+	    typename = decltype(std::declval<_Alloc3*>()->allocate(
+		  std::declval<size_type>(),
+		  std::declval<const_void_pointer>()))>
+	    static true_type __test(int);
+
+	  template<typename>
+	    static false_type __test(...);
+
+	  typedef decltype(__test<_Alloc>(0)) type;
+	  static const bool value = type::value;
+	};
+
+      template<typename _Alloc2>
+	static typename
+       	enable_if<__allocate_helper<_Alloc2>::value, pointer>::type
+       	_S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint)
+	{ return __a.allocate(__n, __hint); }
+
+      template<typename _Alloc2>
+	static typename
+       	enable_if<!__allocate_helper<_Alloc2>::value, pointer>::type
+       	_S_allocate(_Alloc2& __a, size_type __n, ...)
+	{ return __a.allocate(__n); }
+
+      template<typename _Tp, typename... _Args>
+	struct __construct_helper
+	{
+	  template<typename _Alloc2,
+	    typename = decltype(std::declval<_Alloc2*>()->construct(
+		  std::declval<_Tp*>(), std::declval<_Args>()...))>
+	    static true_type __test(int);
+
+	  template<typename>
+	    static false_type __test(...);
+
+	  typedef decltype(__test<_Alloc>(0)) type;
+	  static const bool value = type::value;
+	};
+
+      template<typename _Tp, typename... _Args>
+	static typename
+       	enable_if<__construct_helper<_Tp, _Args...>::value, void>::type
+       	_S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
+	{ __a.construct(__p, std::forward<_Args>(__args)...); }
+
+      template<typename _Tp, typename... _Args>
+	static typename
+       	enable_if<!__construct_helper<_Tp, _Args...>::value, void>::type
+       	_S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
+	{ ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
+
+      template<typename _Tp>
+	struct __destroy_helper
+	{
+	  template<typename _Alloc2,
+	    typename = decltype(std::declval<_Alloc2*>()->destroy(
+		  std::declval<_Tp*>()))>
+	    static true_type __test(int);
+
+	  template<typename>
+	    static false_type __test(...);
+
+	  typedef decltype(__test<_Alloc>(0)) type;
+	  static const bool value = type::value;
+	};
+
+      template<typename _Tp>
+	static typename enable_if<__destroy_helper<_Tp>::value, void>::type
+       	_S_destroy(_Alloc& __a, _Tp* __p)
+	{ __a.destroy(__p); }
+
+      template<typename _Tp>
+	static typename enable_if<!__destroy_helper<_Tp>::value, void>::type
+       	_S_destroy(_Alloc&, _Tp* __p)
+	{ __p->~_Tp(); }
+
+      template<typename _Alloc2>
+	struct __maxsize_helper
+	{
+	  template<typename _Alloc3,
+	    typename = decltype(std::declval<_Alloc3*>()->max_size())>
+	    static true_type __test(int);
+
+	  template<typename>
+	    static false_type __test(...);
+
+	  typedef decltype(__test<_Alloc2>(0)) type;
+	  static const bool value = type::value;
+	};
+
+      template<typename _Alloc2>
+	static typename
+       	enable_if<__maxsize_helper<_Alloc2>::value, size_type>::type
+       	_S_max_size(_Alloc2& __a)
+	{ return __a.max_size(); }
+
+      template<typename _Alloc2>
+	static typename
+       	enable_if<!__maxsize_helper<_Alloc2>::value, size_type>::type
+	_S_max_size(_Alloc2&)
+	{ return __gnu_cxx::__numeric_traits<size_type>::__max; }
+
+      template<typename _Alloc2>
+	struct __select_helper
+	{
+	  template<typename _Alloc3, typename
+	    = decltype(std::declval<_Alloc3*>()
+		->select_on_container_copy_construction())>
+	    static true_type __test(int);
+
+	  template<typename>
+	    static false_type __test(...);
+
+	  typedef decltype(__test<_Alloc2>(0)) type;
+	  static const bool value = type::value;
+	};
+      template<typename _Alloc2>
+	static typename
+       	enable_if<__select_helper<_Alloc2>::value, _Alloc2>::type
+       	_S_select(_Alloc2& __a)
+	{ return __a.select_on_container_copy_construction(); }
+
+      template<typename _Alloc2>
+	static typename
+       	enable_if<!__select_helper<_Alloc2>::value, _Alloc2>::type
+       	_S_select(_Alloc2& __a)
+	{ return __a; }
+
+    public:
+
+      /**
+       *  @brief  Allocate memory.
+       *  @param  a  An allocator.
+       *  @param  n  The number of objects to allocate space for.
+       *
+       *  Calls @c a.allocate(n)
+      */
+      static pointer
+      allocate(_Alloc& __a, size_type __n)
+      { return __a.allocate(__n); }
+
+      /**
+       *  @brief  Allocate memory.
+       *  @param  a  An allocator.
+       *  @param  n  The number of objects to allocate space for.
+       *  @param  hint Aid to locality.
+       *  @return Memory of suitable size and alignment for @a n objects
+       *          of type @c value_type
+       *
+       *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
+       *  well-formed, otherwise returns @c a.allocate(n)
+      */
+      static pointer
+      allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
+      { return _S_allocate(__a, __n, __hint); }
+
+      /**
+       *  @brief  Deallocate memory.
+       *  @param  a  An allocator.
+       *  @param  p  Pointer to the memory to deallocate.
+       *  @param  n  The number of objects space was allocated for.
+       *
+       *  Calls <tt> a.deallocate(p, n) </tt>
+      */
+      static void deallocate(_Alloc& __a, pointer __p, size_type __n)
+      { __a.deallocate(__p, __n); }
+
+      /**
+       *  @brief  Construct an object of type @a Tp
+       *  @param  a  An allocator.
+       *  @param  p  Pointer to memory of suitable size and alignment for Tp
+       *  @param  args Constructor arguments.
+       *
+       *  Calls <tt> a.construct(p, std::forward<Args>(args)...) </tt>
+       *  if that expression is well-formed, otherwise uses placement-new
+       *  to construct an object of type @a Tp at location @a p from the
+       *  arguments @a args...
+      */
+      template<typename _Tp, typename... _Args>
+	static void construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
+	{ _S_construct(__a, __p, std::forward<_Args>(__args)...); }
+
+      /**
+       *  @brief  Destroy an object of type @a Tp
+       *  @param  a  An allocator.
+       *  @param  p  Pointer to the object to destroy
+       *
+       *  Calls @c a.destroy(p) if that expression is well-formed,
+       *  otherwise calls @c p->~Tp()
+      */
+      template <class _Tp>
+	static void destroy(_Alloc& __a, _Tp* __p)
+	{ _S_destroy(__a, __p); }
+
+      /**
+       *  @brief  The maximum supported allocation size
+       *  @param  a  An allocator.
+       *  @return @c a.max_size() or @c numeric_limits<size_type>::max()
+       *
+       *  Returns @c a.max_size() if that expression is well-formed,
+       *  otherwise returns @c numeric_limits<size_type>::max()
+      */
+      static size_type max_size(const _Alloc& __a)
+      { return _S_max_size(__a); }
+
+      /**
+       *  @brief  Obtain an allocator to use when copying a container.
+       *  @param  rhs  An allocator.
+       *  @return @c rhs.select_on_container_copy_construction() or @a rhs
+       *
+       *  Returns @c rhs.select_on_container_copy_construction() if that
+       *  expression is well-formed, otherwise returns @a rhs
+      */
+      static _Alloc
+      select_on_container_copy_construction(const _Alloc& __rhs)
+      { return _S_select(__rhs); }
+    };
+
+  template<typename _Alloc>
+    inline void
+    __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type)
+    { __one = __two; }
+
+  template<typename _Alloc>
+    inline void
+    __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type)
+    { }
+
+  template<typename _Alloc>
+    inline void __alloc_on_copy(_Alloc& __one, const _Alloc& __two)
+    {
+      typedef allocator_traits<_Alloc> __traits;
+      typedef typename __traits::propagate_on_container_copy_assignment __pocca;
+      __do_alloc_on_copy(__one, __two, __pocca());
+    }
+
+  template<typename _Alloc>
+    inline _Alloc __alloc_on_copy(const _Alloc& __a)
+    {
+      typedef allocator_traits<_Alloc> __traits;
+      return __traits::select_on_container_copy_construction(__a);
+    }
+
+  template<typename _Alloc>
+    inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type)
+    { __one = std::move(__two); }
+
+  template<typename _Alloc>
+    inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type)
+    { }
+
+  template<typename _Alloc>
+    inline void __alloc_on_move(_Alloc& __one, _Alloc& __two)
+    {
+      typedef allocator_traits<_Alloc> __traits;
+      typedef typename __traits::propagate_on_container_move_assignment __pocma;
+      __do_alloc_on_move(__one, __two, __pocma());
+    }
+
+  template<typename _Alloc>
+    inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type)
+    {
+      using std::swap;
+      swap(__one, __two);
+    }
+
+  template<typename _Alloc>
+    inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type)
+    { }
+
+  template<typename _Alloc>
+    inline void __alloc_on_swap(_Alloc& __one, _Alloc& __two)
+    {
+      typedef allocator_traits<_Alloc> __traits;
+      typedef typename __traits::propagate_on_container_swap __pocs;
+      __do_alloc_on_swap(__one, __two, __pocs());
+    }
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
+
+#endif
+#endif
diff --git a/libstdc++-v3/include/bits/allocator.h b/libstdc++-v3/include/bits/allocator.h
index 6801950..76329b3 100644
--- a/libstdc++-v3/include/bits/allocator.h
+++ b/libstdc++-v3/include/bits/allocator.h
@@ -47,12 +47,6 @@
 // Define the base class to std::allocator.
 #include <bits/c++allocator.h>
 
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
-#include <bits/ptr_traits.h>
-#include <bits/uses_allocator.h>
-#include <ext/numeric_traits.h>
-#endif
-
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
@@ -62,6 +56,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    * @ingroup memory
    *
    * Classes encapsulating memory operations.
+   *
+   * @{
    */
 
   template<typename _Tp>
@@ -85,7 +81,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /**
    * @brief  The @a standard allocator, as per [20.4].
-   * @ingroup allocators
    *
    *  See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt04ch11.html
    *  for further details.
@@ -139,6 +134,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
     { return false; }
 
+  /**
+   * @}
+   */
+
   // Inhibit implicit instantiations for required instantiations,
   // which are defined via explicit instantiations elsewhere.
 #if _GLIBCXX_EXTERN_TEMPLATE
@@ -207,404 +206,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       }
     };
 
-  template<typename _Alloc, typename _Tp>
-    class __alloctr_rebind_helper
-    {
-      template<typename _Alloc2, typename _Tp2>
-	static constexpr bool
-       	_S_chk(typename _Alloc2::template rebind<_Tp2>::other*)
-	{ return true; }
-
-      template<typename, typename>
-        static constexpr bool
-       	_S_chk(...)
-       	{ return false; }
-
-    public:
-      static const bool __value = _S_chk<_Alloc, _Tp>(nullptr);
-    };
-
-  template<typename _Alloc, typename _Tp,
-           bool = __alloctr_rebind_helper<_Alloc, _Tp>::__value>
-    struct __alloctr_rebind;
-
-  template<typename _Alloc, typename _Tp>
-    struct __alloctr_rebind<_Alloc, _Tp, true>
-    {
-      typedef typename _Alloc::template rebind<_Tp>::other __type;
-    };
-
-  template<template<typename, typename...> class _Alloc, typename _Tp,
-            typename _Up, typename... _Args>
-    struct __alloctr_rebind<_Alloc<_Up, _Args...>, _Tp, false>
-    {
-      typedef _Alloc<_Tp, _Args...> __type;
-    };
-
-  /**
-   * @brief  Uniform interface to all allocator types.
-   * @ingroup allocators
-  */
-  template<typename _Alloc>
-    struct allocator_traits
-    {
-      /// The allocator type
-      typedef _Alloc allocator_type;
-      /// The allocated type
-      typedef typename _Alloc::value_type value_type;
-
-#define _GLIBCXX_ALLOC_TR_NESTED_TYPE(_NTYPE, _ALT) \
-  private: \
-  template<typename _Tp> \
-    static typename _Tp::_NTYPE _S_##_NTYPE##_helper(_Tp*); \
-  static _ALT _S_##_NTYPE##_helper(...); \
-    typedef decltype(_S_##_NTYPE##_helper((_Alloc*)0)) __##_NTYPE; \
-  public:
-
-_GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*)
-
-      /**
-       * @brief   The allocator's pointer type.
-       *
-       * @c Alloc::pointer if that type exists, otherwise @c value_type*
-      */
-      typedef __pointer pointer;
-
-// TODO: Use pointer_traits::rebind alias template.
-
-_GLIBCXX_ALLOC_TR_NESTED_TYPE(const_pointer,
-  typename pointer_traits<pointer>::template __rebind<const value_type>::__type)
-
-      /**
-       * @brief   The allocator's const pointer type.
-       *
-       * @c Alloc::const_pointer if that type exists, otherwise
-       * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
-      */
-      typedef __const_pointer const_pointer;
-
-_GLIBCXX_ALLOC_TR_NESTED_TYPE(void_pointer,
-  typename pointer_traits<pointer>::template __rebind<void>::__type)
-
-      /**
-       * @brief   The allocator's void pointer type.
-       *
-       * @c Alloc::void_pointer if that type exists, otherwise
-       * <tt> pointer_traits<pointer>::rebind<void> </tt>
-      */
-      typedef __void_pointer void_pointer;
-
-_GLIBCXX_ALLOC_TR_NESTED_TYPE(const_void_pointer,
-  typename pointer_traits<pointer>::template __rebind<const void>::__type)
-
-      /**
-       * @brief   The allocator's const void pointer type.
-       *
-       * @c Alloc::const_void_pointer if that type exists, otherwise
-       * <tt> pointer_traits<pointer>::rebind<const void> </tt>
-      */
-      typedef __const_void_pointer const_void_pointer;
-
-_GLIBCXX_ALLOC_TR_NESTED_TYPE(difference_type,
-                              typename pointer_traits<pointer>::difference_type)
-
-      /**
-       * @brief   The allocator's difference type
-       *
-       * @c Alloc::difference_type if that type exists, otherwise
-       * <tt> pointer_traits<pointer>::difference_type </tt>
-      */
-      typedef __difference_type difference_type;
-
-_GLIBCXX_ALLOC_TR_NESTED_TYPE(size_type,
-                              typename make_unsigned<difference_type>::type)
-
-      /**
-       * @brief   The allocator's size type
-       *
-       * @c Alloc::size_type if that type exists, otherwise
-       * <tt> make_unsigned<difference_type>::type </tt>
-      */
-      typedef __size_type size_type;
-
-_GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_copy_assignment,
-                              false_type)
-
-      /**
-       * @brief   How the allocator is propagated on copy assignment
-       *
-       * @c Alloc::propagate_on_container_copy_assignment if that type exists,
-       * otherwise @c false_type
-      */
-      typedef __propagate_on_container_copy_assignment
-       	propagate_on_container_copy_assignment;
-
-_GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_move_assignment,
-                              false_type)
-
-      /**
-       * @brief   How the allocator is propagated on move assignment
-       *
-       * @c Alloc::propagate_on_container_move_assignment if that type exists,
-       * otherwise @c false_type
-      */
-      typedef __propagate_on_container_move_assignment
-       	propagate_on_container_move_assignment;
-
-_GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap,
-                              false_type)
-
-      /**
-       * @brief   How the allocator is propagated on swap
-       *
-       * @c Alloc::propagate_on_container_swap if that type exists,
-       * otherwise @c false_type
-      */
-      typedef __propagate_on_container_swap propagate_on_container_swap;
-
-#undef _GLIBCXX_ALLOC_TR_NESTED_TYPE
-
-      /* TODO: use template alias 
-      template<typename _Tp>
-        using rebind_alloc = __alloctr_rebind<_Alloc, _Tp>::__type;
-      template<typename _Tp>
-        using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
-      */
-      template<typename _Tp>
-        struct __rebind_alloc
-	{
-  	  typedef typename __alloctr_rebind<_Alloc, _Tp>::__type __type;
-       	};
-
-      template<typename _Tp>
-        struct __rebind_traits
-	{
-	  typedef allocator_traits<typename __rebind_alloc<_Tp>::__type> __type;
-	};
-
-    private:
-      template<typename _Alloc2>
-	struct __allocate_helper
-	{
-	  template<typename _Alloc3,
-	    typename = decltype(std::declval<_Alloc3*>()->allocate(
-		  std::declval<size_type>(),
-		  std::declval<const_void_pointer>()))>
-	    static true_type __test(int);
-
-	  template<typename>
-	    static false_type __test(...);
-
-	  typedef decltype(__test<_Alloc>(0)) type;
-	  static const bool value = type::value;
-	};
-
-      template<typename _Alloc2>
-	static typename
-       	enable_if<__allocate_helper<_Alloc2>::value, pointer>::type
-       	_S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint)
-	{ return __a.allocate(__n, __hint); }
-
-      template<typename _Alloc2>
-	static typename
-       	enable_if<!__allocate_helper<_Alloc2>::value, pointer>::type
-       	_S_allocate(_Alloc2& __a, size_type __n, ...)
-	{ return __a.allocate(__n); }
-
-      template<typename _Tp, typename... _Args>
-	struct __construct_helper
-	{
-	  template<typename _Alloc2,
-	    typename = decltype(std::declval<_Alloc2*>()->construct(
-		  std::declval<_Tp*>(), std::declval<_Args>()...))>
-	    static true_type __test(int);
-
-	  template<typename>
-	    static false_type __test(...);
-
-	  typedef decltype(__test<_Alloc>(0)) type;
-	  static const bool value = type::value;
-	};
-
-      template<typename _Tp, typename... _Args>
-	static typename
-       	enable_if<__construct_helper<_Tp, _Args...>::value, void>::type
-       	_S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
-	{ __a.construct(__p, std::forward<_Args>(__args)...); }
-
-      template<typename _Tp, typename... _Args>
-	static typename
-       	enable_if<!__construct_helper<_Tp, _Args...>::value, void>::type
-       	_S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
-	{ ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
-
-      template<typename _Tp>
-	struct __destroy_helper
-	{
-	  template<typename _Alloc2,
-	    typename = decltype(std::declval<_Alloc2*>()->destroy(
-		  std::declval<_Tp*>()))>
-	    static true_type __test(int);
-
-	  template<typename>
-	    static false_type __test(...);
-
-	  typedef decltype(__test<_Alloc>(0)) type;
-	  static const bool value = type::value;
-	};
-
-      template<typename _Tp>
-	static typename enable_if<__destroy_helper<_Tp>::value, void>::type
-       	_S_destroy(_Alloc& __a, _Tp* __p)
-	{ __a.destroy(__p); }
-
-      template<typename _Tp>
-	static typename enable_if<!__destroy_helper<_Tp>::value, void>::type
-       	_S_destroy(_Alloc&, _Tp* __p)
-	{ __p->~_Tp(); }
-
-      template<typename _Alloc2>
-	struct __maxsize_helper
-	{
-	  template<typename _Alloc3,
-	    typename = decltype(std::declval<_Alloc3*>()->max_size())>
-	    static true_type __test(int);
-
-	  template<typename>
-	    static false_type __test(...);
-
-	  typedef decltype(__test<_Alloc2>(0)) type;
-	  static const bool value = type::value;
-	};
-
-      template<typename _Alloc2>
-	static typename
-       	enable_if<__maxsize_helper<_Alloc2>::value, size_type>::type
-       	_S_max_size(_Alloc2& __a)
-	{ return __a.max_size(); }
-
-      template<typename _Alloc2>
-	static typename
-       	enable_if<!__maxsize_helper<_Alloc2>::value, size_type>::type
-	_S_max_size(_Alloc2&)
-	{ return __gnu_cxx::__numeric_traits<size_type>::__max; }
-
-      template<typename _Alloc2>
-	struct __select_helper
-	{
-	  template<typename _Alloc3, typename
-	    = decltype(std::declval<_Alloc3*>()
-		->select_on_container_copy_construction())>
-	    static true_type __test(int);
-
-	  template<typename>
-	    static false_type __test(...);
-
-	  typedef decltype(__test<_Alloc2>(0)) type;
-	  static const bool value = type::value;
-	};
-      template<typename _Alloc2>
-	static typename
-       	enable_if<__select_helper<_Alloc2>::value, _Alloc2>::type
-       	_S_select(_Alloc2& __a)
-	{ return __a.select_on_container_copy_construction(); }
-
-      template<typename _Alloc2>
-	static typename
-       	enable_if<!__select_helper<_Alloc2>::value, _Alloc2>::type
-       	_S_select(_Alloc2& __a)
-	{ return __a; }
-
-    public:
-
-      /**
-       *  @brief  Allocate memory.
-       *  @param  a  An allocator.
-       *  @param  n  The number of objects to allocate space for.
-       *
-       *  Calls @c a.allocate(n)
-      */
-      static pointer
-      allocate(_Alloc& __a, size_type __n)
-      { return __a.allocate(__n); }
-
-      /**
-       *  @brief  Allocate memory.
-       *  @param  a  An allocator.
-       *  @param  n  The number of objects to allocate space for.
-       *  @param  hint Aid to locality.
-       *  @return Memory of suitable size and alignment for @a n objects
-       *          of type @c value_type
-       *
-       *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
-       *  well-formed, otherwise returns @c a.allocate(n)
-      */
-      static pointer
-      allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
-      { return _S_allocate(__a, __n, __hint); }
-
-      /**
-       *  @brief  Deallocate memory.
-       *  @param  a  An allocator.
-       *  @param  p  Pointer to the memory to deallocate.
-       *  @param  n  The number of objects space was allocated for.
-       *
-       *  Calls <tt> a.deallocate(p, n) </tt>
-      */
-      static void deallocate(_Alloc& __a, pointer __p, size_type __n)
-      { __a.deallocate(__p, __n); }
-
-      /**
-       *  @brief  Construct an object of type @a Tp
-       *  @param  a  An allocator.
-       *  @param  p  Pointer to memory of suitable size and alignment for Tp
-       *  @param  args Constructor arguments.
-       *
-       *  Calls <tt> a.construct(p, std::forward<Args>(args)...) </tt>
-       *  if that expression is well-formed, otherwise uses placement-new
-       *  to construct an object of type @a Tp at location @a p from the
-       *  arguments @a args...
-      */
-      template<typename _Tp, typename... _Args>
-	static void construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
-	{ _S_construct(__a, __p, std::forward<_Args>(__args)...); }
-
-      /**
-       *  @brief  Destroy an object of type @a Tp
-       *  @param  a  An allocator.
-       *  @param  p  Pointer to the object to destroy
-       *
-       *  Calls @c a.destroy(p) if that expression is well-formed,
-       *  otherwise calls @c p->~Tp()
-      */
-      template <class _Tp>
-	static void destroy(_Alloc& __a, _Tp* __p)
-	{ _S_destroy(__a, __p); }
-
-      /**
-       *  @brief  The maximum supported allocation size
-       *  @param  a  An allocator.
-       *  @return @c a.max_size() or @c %numeric_limits<size_type>::max()
-       *
-       *  Returns @c a.max_size() if that expression is well-formed,
-       *  otherwise returns @c %numeric_limits<size_type>::max()
-      */
-      static size_type max_size(const _Alloc& __a)
-      { return _S_max_size(__a); }
-
-      /**
-       *  @brief  Obtain an allocator to use when copying a container.
-       *  @param  rhs  An allocator.
-       *  @return @c rhs.select_on_container_copy_construction() or @a rhs
-       *
-       *  Returns @c rhs.select_on_container_copy_construction() if that
-       *  expression is well-formed, otherwise returns @a rhs
-      */
-      static _Alloc
-      select_on_container_copy_construction(const _Alloc& __rhs)
-      { return _S_select(__rhs); }
-    };
-
+  // Declare uses_allocator so it can be specialized in <queue> etc.
+  template<typename, typename>
+    struct uses_allocator;
 #endif
 
 _GLIBCXX_END_NAMESPACE_VERSION
diff --git a/libstdc++-v3/include/bits/stl_construct.h b/libstdc++-v3/include/bits/stl_construct.h
index 2efba93..c9090e5 100644
--- a/libstdc++-v3/include/bits/stl_construct.h
+++ b/libstdc++-v3/include/bits/stl_construct.h
@@ -60,6 +60,7 @@
 
 #include <new>
 #include <bits/move.h>
+#include <ext/alloc_traits.h>
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
@@ -141,8 +142,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _Destroy(_ForwardIterator __first, _ForwardIterator __last,
 	     _Allocator& __alloc)
     {
+      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
       for (; __first != __last; ++__first)
-	__alloc.destroy(std::__addressof(*__first));
+	__traits::destroy(__alloc, std::__addressof(*__first));
     }
 
   template<typename _ForwardIterator, typename _Tp>
diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h
index 246d5c3..ff0495b 100644
--- a/libstdc++-v3/include/bits/stl_uninitialized.h
+++ b/libstdc++-v3/include/bits/stl_uninitialized.h
@@ -241,8 +241,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _ForwardIterator __cur = __result;
       __try
 	{
+	  typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
 	  for (; __first != __last; ++__first, ++__cur)
-	    __alloc.construct(std::__addressof(*__cur), *__first);
+	    __traits::construct(__alloc, std::__addressof(*__cur), *__first);
 	  return __cur;
 	}
       __catch(...)
@@ -290,8 +291,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _ForwardIterator __cur = __first;
       __try
 	{
+	  typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
 	  for (; __cur != __last; ++__cur)
-	    __alloc.construct(std::__addressof(*__cur), __x);
+	    __traits::construct(__alloc, std::__addressof(*__cur), __x);
 	}
       __catch(...)
 	{
@@ -315,8 +317,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _ForwardIterator __cur = __first;
       __try
 	{
+	  typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
 	  for (; __n > 0; --__n, ++__cur)
-	    __alloc.construct(std::__addressof(*__cur), __x);
+	    __traits::construct(__alloc, std::__addressof(*__cur), __x);
 	}
       __catch(...)
 	{
@@ -556,8 +559,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _ForwardIterator __cur = __first;
       __try
 	{
+	  typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
 	  for (; __cur != __last; ++__cur)
-	    __alloc.construct(std::__addressof(*__cur));
+	    __traits::construct(__alloc, std::__addressof(*__cur));
 	}
       __catch(...)
 	{
@@ -585,8 +589,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _ForwardIterator __cur = __first;
       __try
 	{
+	  typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
 	  for (; __n > 0; --__n, ++__cur)
-	    __alloc.construct(std::__addressof(*__cur));
+	    __traits::construct(__alloc, std::__addressof(*__cur));
 	}
       __catch(...)
 	{
diff --git a/libstdc++-v3/include/ext/alloc_traits.h b/libstdc++-v3/include/ext/alloc_traits.h
new file mode 100644
index 0000000..0d50fe1
--- /dev/null
+++ b/libstdc++-v3/include/ext/alloc_traits.h
@@ -0,0 +1,121 @@
+// Allocator traits -*- C++ -*-
+
+// Copyright (C) 2011 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 3, 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.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file ext/alloc_traits.h
+ *  This file is a GNU extension to the Standard C++ Library.
+ */
+
+#ifndef _EXT_ALLOC_TRAITS_H
+#define _EXT_ALLOC_TRAITS_H 1
+
+#pragma GCC system_header
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+# include <bits/alloc_traits.h>
+#else
+# include <bits/allocator.h>  // for __alloc_swap
+#endif
+
+namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  /**
+   * @brief  Uniform interface to C++98 and C++0x allocators.
+   * @ingroup allocators
+  */
+template<typename _Alloc>
+  struct __alloc_traits
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+  : std::allocator_traits<_Alloc>
+#endif
+  {
+    typedef _Alloc allocator_type;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    typedef std::allocator_traits<_Alloc>           _Base_type;
+    typedef typename _Base_type::value_type         value_type;
+    typedef typename _Base_type::pointer            pointer;
+    typedef typename _Base_type::const_pointer      const_pointer;
+    typedef typename _Base_type::size_type          size_type;
+    // C++0x allocators do not define reference or const_reference
+    typedef value_type&                             reference;
+    typedef const value_type&                       const_reference;
+    using _Base_type::allocate;
+    using _Base_type::deallocate;
+    using _Base_type::construct;
+    using _Base_type::destroy;
+
+    static _Alloc _S_select_on_copy(const _Alloc& __a)
+    { return _Base_type::select_on_container_copy_construction(__a); }
+
+    static void _S_on_swap(_Alloc& __a, _Alloc& __b)
+    { std::__alloc_on_swap(__a, __b); }
+
+    static constexpr bool _S_propagate_on_copy_assign()
+    { return _Base_type::propagate_on_container_copy_assignment::value; }
+
+    static constexpr bool _S_propagate_on_move_assign()
+    { return _Base_type::propagate_on_container_move_assignment::value; }
+
+    static constexpr bool _S_propagate_on_swap()
+    { return _Base_type::propagate_on_container_swap::value; }
+
+#else
+
+    typedef typename _Alloc::pointer                pointer;
+    typedef typename _Alloc::const_pointer          const_pointer;
+    typedef typename _Alloc::value_type             value_type;
+    typedef typename _Alloc::reference              reference;
+    typedef typename _Alloc::const_reference        const_reference;
+    typedef typename _Alloc::size_type              size_type;
+
+    static pointer
+    allocate(_Alloc& __a, size_type __n)
+    { return __a.allocate(__n); }
+
+    static void deallocate(_Alloc& __a, pointer __p, size_type __n)
+    { __a.deallocate(__p, __n); }
+
+    template<typename _Tp>
+      static void construct(_Alloc& __a, pointer __p, const _Tp& __arg)
+      { __a.construct(__p, __arg); }
+
+    static void destroy(_Alloc& __a, pointer __p)
+    { __a.destroy(__p); }
+
+    static const _Alloc& _S_select_on_copy(const _Alloc& __a) { return __a; }
+
+    static void _S_on_swap(_Alloc& __a, _Alloc& __b)
+    {
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 431. Swapping containers with unequal allocators.
+      std::__alloc_swap<_Alloc>::_S_do_it(__a, __b);
+    }
+#endif
+  };
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace
+
+#endif
diff --git a/libstdc++-v3/include/std/memory b/libstdc++-v3/include/std/memory
index 791ffe0..e846eba 100644
--- a/libstdc++-v3/include/std/memory
+++ b/libstdc++-v3/include/std/memory
@@ -76,6 +76,7 @@
 #  include <ext/concurrence.h>
 #  include <bits/functexcept.h>
 #  include <bits/stl_function.h>  // std::less
+#  include <bits/uses_allocator.h>
 #  include <type_traits>
 #  include <functional>
 #  include <debug/debug.h>