[libcxx] Fix max_size() across all containers

Summary: The `max_size()` method of containers should respect both the allocator's reported `max_size` and the range of the `difference_type`. This patch makes all containers choose the smallest of those two values.

Reviewers: mclow.lists, EricWF

Subscribers: cfe-commits

Differential Revision: https://reviews.llvm.org/D26885

llvm-svn: 287729

12 files changed, 385 insertions, 100 deletions

diff --git a/libcxx/test/std/containers/associative/map/map.access/max_size.pass.cpp b/libcxx/test/std/containers/associative/map/map.access/max_size.pass.cpp
index c67d8b1f674..82a817a1f4a 100644
--- a/libcxx/test/std/containers/associative/map/map.access/max_size.pass.cpp
+++ b/libcxx/test/std/containers/associative/map/map.access/max_size.pass.cpp
@@ -13,23 +13,39 @@
 
 // size_type max_size() const;
 
-#include <map>
 #include <cassert>
+#include <limits>
+#include <map>
+#include <type_traits>
 
-#include "min_allocator.h"
+#include "test_allocator.h"
+#include "test_macros.h"
 
 int main()
 {
-    {
-    typedef std::map<int, double> M;
-    M m;
-    assert(m.max_size() != 0);
+  typedef std::pair<const int, int> KV;
+  {
+    typedef limited_allocator<KV, 10> A;
+    typedef std::map<int, int, std::less<int>, A> C;
+    C c;
+    assert(c.max_size() <= 10);
+    LIBCPP_ASSERT(c.max_size() == 10);
+  }
+  {
+    typedef limited_allocator<KV, (size_t)-1> A;
+    typedef std::map<int, int, std::less<int>, A> C;
+    const C::difference_type max_dist =
+        std::numeric_limits<C::difference_type>::max();
+    C c;
+    assert(c.max_size() <= max_dist);
+    LIBCPP_ASSERT(c.max_size() == max_dist);
     }
-#if TEST_STD_VER >= 11
     {
-    typedef std::map<int, double, std::less<int>, min_allocator<std::pair<const int, double>>> M;
-    M m;
-    assert(m.max_size() != 0);
+      typedef std::map<char, int> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      assert(c.max_size() <= alloc_max_size(c.get_allocator()));
     }
-#endif
 }
diff --git a/libcxx/test/std/containers/associative/multimap/max_size.pass.cpp b/libcxx/test/std/containers/associative/multimap/max_size.pass.cpp
index b7cf226d8f1..8d5ec1148a2 100644
--- a/libcxx/test/std/containers/associative/multimap/max_size.pass.cpp
+++ b/libcxx/test/std/containers/associative/multimap/max_size.pass.cpp
@@ -13,23 +13,39 @@
 
 // size_type max_size() const;
 
-#include <map>
 #include <cassert>
+#include <limits>
+#include <map>
+#include <type_traits>
 
-#include "min_allocator.h"
+#include "test_allocator.h"
+#include "test_macros.h"
 
 int main()
 {
-    {
-    typedef std::multimap<int, double> M;
-    M m;
-    assert(m.max_size() != 0);
+  typedef std::pair<const int, int> KV;
+  {
+    typedef limited_allocator<KV, 10> A;
+    typedef std::multimap<int, int, std::less<int>, A> C;
+    C c;
+    assert(c.max_size() <= 10);
+    LIBCPP_ASSERT(c.max_size() == 10);
+  }
+  {
+    typedef limited_allocator<KV, (size_t)-1> A;
+    typedef std::multimap<int, int, std::less<int>, A> C;
+    const C::difference_type max_dist =
+        std::numeric_limits<C::difference_type>::max();
+    C c;
+    assert(c.max_size() <= max_dist);
+    LIBCPP_ASSERT(c.max_size() == max_dist);
     }
-#if TEST_STD_VER >= 11
     {
-    typedef std::multimap<int, double, std::less<int>, min_allocator<std::pair<const int, double>>> M;
-    M m;
-    assert(m.max_size() != 0);
+      typedef std::multimap<char, int> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      assert(c.max_size() <= alloc_max_size(c.get_allocator()));
     }
-#endif
 }
diff --git a/libcxx/test/std/containers/associative/multiset/max_size.pass.cpp b/libcxx/test/std/containers/associative/multiset/max_size.pass.cpp
index 79492c9b1c4..8ca34ba8273 100644
--- a/libcxx/test/std/containers/associative/multiset/max_size.pass.cpp
+++ b/libcxx/test/std/containers/associative/multiset/max_size.pass.cpp
@@ -13,23 +13,38 @@
 
 // size_type max_size() const;
 
-#include <set>
 #include <cassert>
+#include <limits>
+#include <set>
+#include <type_traits>
 
-#include "min_allocator.h"
+#include "test_allocator.h"
+#include "test_macros.h"
 
 int main()
 {
     {
-    typedef std::multiset<int> M;
-    M m;
-    assert(m.max_size() != 0);
+      typedef limited_allocator<int, 10> A;
+      typedef std::multiset<int, std::less<int>, A> C;
+      C c;
+      assert(c.max_size() <= 10);
+      LIBCPP_ASSERT(c.max_size() == 10);
+    }
+    {
+      typedef limited_allocator<int, (size_t)-1> A;
+      typedef std::multiset<int, std::less<int>, A> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      LIBCPP_ASSERT(c.max_size() == max_dist);
     }
-#if TEST_STD_VER >= 11
     {
-    typedef std::multiset<int, std::less<int>, min_allocator<int>> M;
-    M m;
-    assert(m.max_size() != 0);
+      typedef std::multiset<char> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      assert(c.max_size() <= alloc_max_size(c.get_allocator()));
     }
-#endif
 }
diff --git a/libcxx/test/std/containers/associative/set/max_size.pass.cpp b/libcxx/test/std/containers/associative/set/max_size.pass.cpp
index 9df6a4157e1..c894eb51b1e 100644
--- a/libcxx/test/std/containers/associative/set/max_size.pass.cpp
+++ b/libcxx/test/std/containers/associative/set/max_size.pass.cpp
@@ -13,23 +13,38 @@
 
 // size_type max_size() const;
 
-#include <set>
 #include <cassert>
+#include <limits>
+#include <set>
+#include <type_traits>
 
-#include "min_allocator.h"
+#include "test_allocator.h"
+#include "test_macros.h"
 
 int main()
 {
     {
-    typedef std::set<int> M;
-    M m;
-    assert(m.max_size() != 0);
+      typedef limited_allocator<int, 10> A;
+      typedef std::set<int, std::less<int>, A> C;
+      C c;
+      assert(c.max_size() <= 10);
+      LIBCPP_ASSERT(c.max_size() == 10);
+    }
+    {
+      typedef limited_allocator<int, (size_t)-1> A;
+      typedef std::set<int, std::less<int>, A> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      LIBCPP_ASSERT(c.max_size() == max_dist);
     }
-#if TEST_STD_VER >= 11
     {
-    typedef std::set<int, std::less<int>, min_allocator<int>> M;
-    M m;
-    assert(m.max_size() != 0);
+      typedef std::set<char> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      assert(c.max_size() <= alloc_max_size(c.get_allocator()));
     }
-#endif
 }
diff --git a/libcxx/test/std/containers/sequences/deque/deque.capacity/max_size.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.capacity/max_size.pass.cpp
new file mode 100644
index 00000000000..11ce9d2f689
--- /dev/null
+++ b/libcxx/test/std/containers/sequences/deque/deque.capacity/max_size.pass.cpp
@@ -0,0 +1,47 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <deque>
+
+// size_type max_size() const;
+
+#include <cassert>
+#include <deque>
+#include <limits>
+#include <type_traits>
+
+#include "test_allocator.h"
+#include "test_macros.h"
+
+int main() {
+  {
+    typedef limited_allocator<int, 10> A;
+    typedef std::deque<int, A> C;
+    C c;
+    assert(c.max_size() <= 10);
+    LIBCPP_ASSERT(c.max_size() == 10);
+  }
+  {
+    typedef limited_allocator<int, (size_t)-1> A;
+    typedef std::deque<int, A> C;
+    const C::difference_type max_dist =
+        std::numeric_limits<C::difference_type>::max();
+    C c;
+    assert(c.max_size() <= max_dist);
+    LIBCPP_ASSERT(c.max_size() == max_dist);
+  }
+  {
+    typedef std::deque<char> C;
+    const C::difference_type max_dist =
+        std::numeric_limits<C::difference_type>::max();
+    C c;
+    assert(c.max_size() <= max_dist);
+    assert(c.max_size() <= alloc_max_size(c.get_allocator()));
+  }
+}
diff --git a/libcxx/test/std/containers/sequences/forwardlist/max_size.pass.cpp b/libcxx/test/std/containers/sequences/forwardlist/max_size.pass.cpp
index a7f39bf90fb..916d12a9f67 100644
--- a/libcxx/test/std/containers/sequences/forwardlist/max_size.pass.cpp
+++ b/libcxx/test/std/containers/sequences/forwardlist/max_size.pass.cpp
@@ -11,25 +11,38 @@
 
 // size_type max_size() const;
 
-#include <forward_list>
 #include <cassert>
+#include <forward_list>
+#include <limits>
+#include <type_traits>
 
-#include "min_allocator.h"
+#include "test_allocator.h"
+#include "test_macros.h"
 
 int main()
 {
     {
-        typedef int T;
-        typedef std::forward_list<T> C;
-        C c;
-        assert(c.max_size() > 0);
+      typedef limited_allocator<int, 10> A;
+      typedef std::forward_list<int, A> C;
+      C c;
+      assert(c.max_size() <= 10);
+      LIBCPP_ASSERT(c.max_size() == 10);
+    }
+    {
+      typedef limited_allocator<int, (size_t)-1> A;
+      typedef std::forward_list<int, A> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      LIBCPP_ASSERT(c.max_size() == max_dist);
     }
-#if TEST_STD_VER >= 11
     {
-        typedef int T;
-        typedef std::forward_list<T, min_allocator<T>> C;
-        C c;
-        assert(c.max_size() > 0);
+      typedef std::forward_list<char> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      assert(c.max_size() <= alloc_max_size(c.get_allocator()));
     }
-#endif
 }
diff --git a/libcxx/test/std/containers/sequences/list/list.capacity/max_size.pass.cpp b/libcxx/test/std/containers/sequences/list/list.capacity/max_size.pass.cpp
new file mode 100644
index 00000000000..bd1b65e63d7
--- /dev/null
+++ b/libcxx/test/std/containers/sequences/list/list.capacity/max_size.pass.cpp
@@ -0,0 +1,47 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <list>
+
+// size_type max_size() const noexcept
+
+#include <cassert>
+#include <limits>
+#include <list>
+#include <type_traits>
+
+#include "test_allocator.h"
+#include "test_macros.h"
+
+int main() {
+  {
+    typedef limited_allocator<int, 10> A;
+    typedef std::list<int, A> C;
+    C c;
+    assert(c.max_size() <= 10);
+    LIBCPP_ASSERT(c.max_size() == 10);
+  }
+  {
+    typedef limited_allocator<int, (size_t)-1> A;
+    typedef std::list<int, A> C;
+    const C::difference_type max_dist =
+        std::numeric_limits<C::difference_type>::max();
+    C c;
+    assert(c.max_size() <= max_dist);
+    LIBCPP_ASSERT(c.max_size() == max_dist);
+  }
+  {
+    typedef std::list<char> C;
+    const C::difference_type max_dist =
+        std::numeric_limits<C::difference_type>::max();
+    C c;
+    assert(c.max_size() <= max_dist);
+    assert(c.max_size() <= alloc_max_size(c.get_allocator()));
+  }
+}
diff --git a/libcxx/test/std/containers/sequences/vector/vector.capacity/max_size.pass.cpp b/libcxx/test/std/containers/sequences/vector/vector.capacity/max_size.pass.cpp
new file mode 100644
index 00000000000..5f7a6268d55
--- /dev/null
+++ b/libcxx/test/std/containers/sequences/vector/vector.capacity/max_size.pass.cpp
@@ -0,0 +1,48 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <vector>
+
+// size_type max_size() const;
+
+#include <cassert>
+#include <limits>
+#include <type_traits>
+#include <vector>
+
+#include "test_allocator.h"
+#include "test_macros.h"
+
+
+int main() {
+  {
+    typedef limited_allocator<int, 10> A;
+    typedef std::vector<int, A> C;
+    C c;
+    assert(c.max_size() <= 10);
+    LIBCPP_ASSERT(c.max_size() == 10);
+  }
+  {
+    typedef limited_allocator<int, (size_t)-1> A;
+    typedef std::vector<int, A> C;
+    const C::difference_type max_dist =
+        std::numeric_limits<C::difference_type>::max();
+    C c;
+    assert(c.max_size() <= max_dist);
+    LIBCPP_ASSERT(c.max_size() == max_dist);
+  }
+  {
+    typedef std::vector<char> C;
+    const C::difference_type max_dist =
+        std::numeric_limits<C::difference_type>::max();
+    C c;
+    assert(c.max_size() <= max_dist);
+    assert(c.max_size() <= alloc_max_size(c.get_allocator()));
+  }
+}
diff --git a/libcxx/test/std/containers/unord/unord.map/max_size.pass.cpp b/libcxx/test/std/containers/unord/unord.map/max_size.pass.cpp
index 9c1ca18c305..15274198146 100644
--- a/libcxx/test/std/containers/unord/unord.map/max_size.pass.cpp
+++ b/libcxx/test/std/containers/unord/unord.map/max_size.pass.cpp
@@ -9,28 +9,45 @@
 
 // <unordered_map>
 
-// template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
-//           class Alloc = allocator<pair<const Key, T>>>
 // class unordered_map
 
 // size_type max_size() const;
 
-#include <unordered_map>
 #include <cassert>
+#include <limits>
+#include <type_traits>
+#include <unordered_map>
 
-#include "min_allocator.h"
+#include "test_allocator.h"
+#include "test_macros.h"
 
 int main()
 {
-    {
-        std::unordered_map<int, int> u;
-        assert(u.max_size() > 0);
+  typedef std::pair<const int, int> KV;
+  {
+    typedef limited_allocator<KV, 10> A;
+    typedef std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, A>
+        C;
+    C c;
+    assert(c.max_size() <= 10);
+    LIBCPP_ASSERT(c.max_size() == 10);
+  }
+  {
+    typedef limited_allocator<KV, (size_t)-1> A;
+    typedef std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, A>
+        C;
+    const C::difference_type max_dist =
+        std::numeric_limits<C::difference_type>::max();
+    C c;
+    assert(c.max_size() <= max_dist);
+    LIBCPP_ASSERT(c.max_size() == max_dist);
     }
-#if TEST_STD_VER >= 11
     {
-        std::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
-                                    min_allocator<std::pair<const int, int>>> u;
-        assert(u.max_size() > 0);
+      typedef std::unordered_map<char, int> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      assert(c.max_size() <= alloc_max_size(c.get_allocator()));
     }
-#endif
 }
diff --git a/libcxx/test/std/containers/unord/unord.multimap/max_size.pass.cpp b/libcxx/test/std/containers/unord/unord.multimap/max_size.pass.cpp
index 3bf1f1496f6..5b58bac385a 100644
--- a/libcxx/test/std/containers/unord/unord.multimap/max_size.pass.cpp
+++ b/libcxx/test/std/containers/unord/unord.multimap/max_size.pass.cpp
@@ -9,28 +9,47 @@
 
 // <unordered_map>
 
-// template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
-//           class Alloc = allocator<pair<const Key, T>>>
 // class unordered_multimap
 
 // size_type max_size() const;
 
-#include <unordered_map>
 #include <cassert>
+#include <limits>
+#include <type_traits>
+#include <unordered_map>
 
-#include "min_allocator.h"
+#include "test_allocator.h"
+#include "test_macros.h"
 
 int main()
 {
-    {
-        std::unordered_multimap<int, int> u;
-        assert(u.max_size() > 0);
+  typedef std::pair<const int, int> KV;
+  {
+    typedef limited_allocator<KV, 10> A;
+    typedef std::unordered_multimap<int, int, std::hash<int>,
+                                    std::equal_to<int>, A>
+        C;
+    C c;
+    assert(c.max_size() <= 10);
+    LIBCPP_ASSERT(c.max_size() == 10);
+  }
+  {
+    typedef limited_allocator<KV, (size_t)-1> A;
+    typedef std::unordered_multimap<int, int, std::hash<int>,
+                                    std::equal_to<int>, A>
+        C;
+    const C::difference_type max_dist =
+        std::numeric_limits<C::difference_type>::max();
+    C c;
+    assert(c.max_size() <= max_dist);
+    LIBCPP_ASSERT(c.max_size() == max_dist);
     }
-#if TEST_STD_VER >= 11
     {
-        std::unordered_multimap<int, int, std::hash<int>, std::equal_to<int>,
-                            min_allocator<std::pair<const int, int>>> u;
-        assert(u.max_size() > 0);
+      typedef std::unordered_multimap<char, int> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      assert(c.max_size() <= alloc_max_size(c.get_allocator()));
     }
-#endif
 }
diff --git a/libcxx/test/std/containers/unord/unord.multiset/max_size.pass.cpp b/libcxx/test/std/containers/unord/unord.multiset/max_size.pass.cpp
index b26ad73fed2..eac4db8b0a9 100644
--- a/libcxx/test/std/containers/unord/unord.multiset/max_size.pass.cpp
+++ b/libcxx/test/std/containers/unord/unord.multiset/max_size.pass.cpp
@@ -9,28 +9,46 @@
 
 // <unordered_set>
 
-// template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
-//           class Alloc = allocator<Value>>
 // class unordered_multiset
 
 // size_type max_size() const;
 
-#include <unordered_set>
 #include <cassert>
+#include <limits>
+#include <type_traits>
+#include <unordered_set>
 
-#include "min_allocator.h"
+#include "test_allocator.h"
+#include "test_macros.h"
 
 int main()
 {
     {
-        std::unordered_multiset<int> u;
-        assert(u.max_size() > 0);
+      typedef limited_allocator<int, 10> A;
+      typedef std::unordered_multiset<int, std::hash<int>, std::equal_to<int>,
+                                      A>
+          C;
+      C c;
+      assert(c.max_size() <= 10);
+      LIBCPP_ASSERT(c.max_size() == 10);
+    }
+    {
+      typedef limited_allocator<int, (size_t)-1> A;
+      typedef std::unordered_multiset<int, std::hash<int>, std::equal_to<int>,
+                                      A>
+          C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      LIBCPP_ASSERT(c.max_size() == max_dist);
     }
-#if TEST_STD_VER >= 11
     {
-        std::unordered_multiset<int, std::hash<int>,
-                                      std::equal_to<int>, min_allocator<int>> u;
-        assert(u.max_size() > 0);
+      typedef std::unordered_multiset<char> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      assert(c.max_size() <= alloc_max_size(c.get_allocator()));
     }
-#endif
 }
diff --git a/libcxx/test/std/containers/unord/unord.set/max_size.pass.cpp b/libcxx/test/std/containers/unord/unord.set/max_size.pass.cpp
index 3135ad99473..1b902660d48 100644
--- a/libcxx/test/std/containers/unord/unord.set/max_size.pass.cpp
+++ b/libcxx/test/std/containers/unord/unord.set/max_size.pass.cpp
@@ -9,28 +9,42 @@
 
 // <unordered_set>
 
-// template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
-//           class Alloc = allocator<Value>>
 // class unordered_set
 
 // size_type max_size() const;
 
-#include <unordered_set>
 #include <cassert>
+#include <limits>
+#include <type_traits>
+#include <unordered_set>
 
-#include "min_allocator.h"
+#include "test_allocator.h"
+#include "test_macros.h"
 
 int main()
 {
     {
-        std::unordered_set<int> u;
-        assert(u.max_size() > 0);
+      typedef limited_allocator<int, 10> A;
+      typedef std::unordered_set<int, std::hash<int>, std::equal_to<int>, A> C;
+      C c;
+      assert(c.max_size() <= 10);
+      LIBCPP_ASSERT(c.max_size() == 10);
+    }
+    {
+      typedef limited_allocator<int, (size_t)-1> A;
+      typedef std::unordered_set<int, std::hash<int>, std::equal_to<int>, A> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      LIBCPP_ASSERT(c.max_size() == max_dist);
     }
-#if TEST_STD_VER >= 11
     {
-        std::unordered_set<int, std::hash<int>,
-                                      std::equal_to<int>, min_allocator<int>> u;
-        assert(u.max_size() > 0);
+      typedef std::unordered_set<char> C;
+      const C::difference_type max_dist =
+          std::numeric_limits<C::difference_type>::max();
+      C c;
+      assert(c.max_size() <= max_dist);
+      assert(c.max_size() <= alloc_max_size(c.get_allocator()));
     }
-#endif
 }