about summary refs log tree commit diff
path: root/absl/container
diff options
context:
space:
mode:
authorAbseil Team <absl-team@google.com>2018-11-13T21·22-0800
committerJon Cohen <cohenjon@google.com>2018-11-13T22·56-0500
commit7b46e1d31a6b08b1c6da2a13e7b151a20446fa07 (patch)
tree0e4f4ad83ffb009e5e54004b2f3c003ecd216135 /absl/container
parent070f6e47b33a2909d039e620c873204f78809492 (diff)
Export of internal Abseil changes.
--
07575526242a8e1275ac4223a3d2822795f46569 by CJ Johnson <johnsoncj@google.com>:

Comment cleanup on InlinedVector

PiperOrigin-RevId: 221322176

--
49a5e643f85e34d53c41f5e6cc33357c55c9115d by Matt Kulukundis <kfm@google.com>:

Internal cleanup

PiperOrigin-RevId: 221309185

--
bb35be87ec9c74244b7d902e7e7d2d33ab139d76 by Abseil Team <absl-team@google.com>:

Fix typo in comment.

PiperOrigin-RevId: 221145354

--
afd4d7c106919708004e06aeea068a57c28aec44 by Derek Mauro <dmauro@google.com>:

Update the debugging log message in CallOnceImpl()

PiperOrigin-RevId: 221103254

--
0b9dace8b88113777bf26a6d38f9bc0bcaf053a1 by Abseil Team <absl-team@google.com>:

Workaround an MSVC 2015 bug in compile-time initialization.

PiperOrigin-RevId: 220871483

--
ea0a3854511ed26beab827e5a5113766b334db86 by Marek Gilbert <mcg@google.com>:

Fix ABSL_HAVE_THREAD_LOCAL when compiling for iOS 8 with Xcode 10.

Xcode 10 has moved the check for thread_local to a link time, so
clang reports __has_feature(cxx_thread_local) but then linking fails
with messages like this:

ld: targeted OS version does not support use of thread local variables
PiperOrigin-RevId: 220815885

--
485b6876c158c3dcf37eb32d7e512242d5d4ecc6 by Greg Falcon <gfalcon@google.com>:

Make the absl::c_set_xxxx() algorithms refuse to compile when passed an unordered collection from std:: or absl::.

These algorithms operate on sorted sequences; passing an unordered container to them is nearly certainly a bug.  This change is technically an API break, but it only breaks incorrect code.

We could try to be more clever and detect unordered collections from other libraries, but false positives will break legal code, and this would constitute an API break Abseil cannot afford.

PiperOrigin-RevId: 220794190

--
c47cff7f9cc70a4c1604eee0131af552f40e46d6 by Jon Cohen <cohenjon@google.com>:

MSVC 2017's STL throws a Structured Exception (not a C++ exception, essentially equivalent to SIGSEGV) when variant::emplace calls a throwing constructor when using the debug multithreaded MSVC runtime DLL.  This manifests in dbg mode in Bazel builds.  Disable tests which trigger this bug.

It's impossible to specifically pull out MSVC 2017 -dbg modes because there's no way for Bazel to know when version of MSVC is being used -- you tell Bazel the directory where the MSVC tools live, not which version of MSVC tools to use.  Thus the best we can do is switch on _DEBUG, which is set whenever the debug runtime is selected with the /MDd build flag, as in Bazel -dbg modes.  See https://msdn.microsoft.com/en-us/library/b0084kay.aspx ctrl-f "_DEBUG"

PiperOrigin-RevId: 220706161

--
43993d4af309d92f4ebff38391dcc245f154ecc7 by Shaindel Schwartz <shaindel@google.com>:

Internal change

PiperOrigin-RevId: 220688429

--
2448802972dcc261af153af464f2b022ef54a2a9 by Abseil Team <absl-team@google.com>:

Speed up operator* for uint128 in WIN64.

PiperOrigin-RevId: 220678790

--
7b376403dd05ba10152fb52e40b29d8af79b58bb by Abseil Team <absl-team@google.com>:

Import of CCTZ from GitHub.

PiperOrigin-RevId: 220654834

--
ae08af58111c3f838b8d4de25f501c3559c86002 by Abseil Team <absl-team@google.com>:

CMake: Add absl_cc_test function

PiperOrigin-RevId: 220603940
GitOrigin-RevId: 07575526242a8e1275ac4223a3d2822795f46569
Change-Id: Iba7f53eb394c8a9de564582a976793f9bb0596d9
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel4
-rw-r--r--absl/container/flat_hash_map.h12
-rw-r--r--absl/container/flat_hash_set.h12
-rw-r--r--absl/container/inlined_vector.h41
-rw-r--r--absl/container/internal/hash_generator_testing.cc8
-rw-r--r--absl/container/internal/hash_generator_testing.h8
-rw-r--r--absl/container/node_hash_map.h14
-rw-r--r--absl/container/node_hash_set.h11
8 files changed, 80 insertions, 30 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index d75f8916317a..afc869f45aac 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -212,6 +212,7 @@ cc_library(
         ":container_memory",
         ":hash_function_defaults",
         ":raw_hash_map",
+        "//absl/algorithm:container",
         "//absl/memory",
     ],
 )
@@ -240,6 +241,7 @@ cc_library(
         ":container_memory",
         ":hash_function_defaults",
         ":raw_hash_set",
+        "//absl/algorithm:container",
         "//absl/base:core_headers",
         "//absl/memory",
     ],
@@ -271,6 +273,7 @@ cc_library(
         ":hash_function_defaults",
         ":node_hash_policy",
         ":raw_hash_map",
+        "//absl/algorithm:container",
         "//absl/memory",
     ],
 )
@@ -299,6 +302,7 @@ cc_library(
         ":hash_function_defaults",
         ":node_hash_policy",
         ":raw_hash_set",
+        "//absl/algorithm:container",
         "//absl/memory",
     ],
 )
diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h
index de632be2cf21..7bc213802476 100644
--- a/absl/container/flat_hash_map.h
+++ b/absl/container/flat_hash_map.h
@@ -35,6 +35,7 @@
 #include <type_traits>
 #include <utility>
 
+#include "absl/algorithm/container.h"
 #include "absl/container/internal/container_memory.h"
 #include "absl/container/internal/hash_function_defaults.h"  // IWYU pragma: export
 #include "absl/container/internal/raw_hash_map.h"  // IWYU pragma: export
@@ -564,5 +565,16 @@ struct FlatHashMapPolicy {
 };
 
 }  // namespace container_internal
+
+namespace container_algorithm_internal {
+
+// Specialization of trait in absl/algorithm/container.h
+template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+struct IsUnorderedContainer<
+    absl::flat_hash_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {};
+
+}  // namespace container_algorithm_internal
+
 }  // namespace absl
+
 #endif  // ABSL_CONTAINER_FLAT_HASH_MAP_H_
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h
index a2584d66f8e6..f7c1acaaa7b8 100644
--- a/absl/container/flat_hash_set.h
+++ b/absl/container/flat_hash_set.h
@@ -32,6 +32,7 @@
 #include <type_traits>
 #include <utility>
 
+#include "absl/algorithm/container.h"
 #include "absl/base/macros.h"
 #include "absl/container/internal/container_memory.h"
 #include "absl/container/internal/hash_function_defaults.h"  // IWYU pragma: export
@@ -475,5 +476,16 @@ struct FlatHashSetPolicy {
   static size_t space_used(const T*) { return 0; }
 };
 }  // namespace container_internal
+
+namespace container_algorithm_internal {
+
+// Specialization of trait in absl/algorithm/container.h
+template <class Key, class Hash, class KeyEqual, class Allocator>
+struct IsUnorderedContainer<absl::flat_hash_set<Key, Hash, KeyEqual, Allocator>>
+    : std::true_type {};
+
+}  // namespace container_algorithm_internal
+
 }  // namespace absl
+
 #endif  // ABSL_CONTAINER_FLAT_HASH_SET_H_
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index ea8cb02baa61..642dae6cb907 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -20,17 +20,17 @@
 // vector" which behaves in an equivalent fashion to a `std::vector`, except
 // that storage for small sequences of the vector are provided inline without
 // requiring any heap allocation.
-
-// An `absl::InlinedVector<T,N>` specifies the size N at which to inline as one
-// of its template parameters. Vectors of length <= N are provided inline.
-// Typically N is very small (e.g., 4) so that sequences that are expected to be
-// short do not require allocations.
-
-// An `absl::InlinedVector` does not usually require a specific allocator; if
+//
+// An `absl::InlinedVector<T, N>` specifies the default capacity `N` as one of
+// its template parameters. Instances where `size() <= N` hold contained
+// elements in inline space. Typically `N` is very small so that sequences that
+// are expected to be short do not require allocations.
+//
+// An `absl::InlinedVector` does not usually require a specific allocator. If
 // the inlined vector grows beyond its initial constraints, it will need to
-// allocate (as any normal `std::vector` would) and it will generally use the
-// default allocator in that case; optionally, a custom allocator may be
-// specified using an `absl::InlinedVector<T,N,A>` construction.
+// allocate (as any normal `std::vector` would). This is usually performed with
+// the default allocator (defined as `std::allocator<T>`). Optionally, a custom
+// allocator type may be specified as `A` in `absl::InlinedVector<T, N, A>`.
 
 #ifndef ABSL_CONTAINER_INLINED_VECTOR_H_
 #define ABSL_CONTAINER_INLINED_VECTOR_H_
@@ -61,8 +61,8 @@ namespace absl {
 // An `absl::InlinedVector` is designed to be a drop-in replacement for
 // `std::vector` for use cases where the vector's size is sufficiently small
 // that it can be inlined. If the inlined vector does grow beyond its estimated
-// size, it will trigger an initial allocation on the heap, and will behave as a
-// `std:vector`. The API of the `absl::InlinedVector` within this file is
+// capacity, it will trigger an initial allocation on the heap, and will behave
+// as a `std:vector`. The API of the `absl::InlinedVector` within this file is
 // designed to cover the same API footprint as covered by `std::vector`.
 template <typename T, size_t N, typename A = std::allocator<T>>
 class InlinedVector {
@@ -101,7 +101,6 @@ class InlinedVector {
   using reverse_iterator = std::reverse_iterator<iterator>;
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
-
   // ---------------------------------------------------------------------------
   // InlinedVector Constructors and Destructor
   // ---------------------------------------------------------------------------
@@ -135,11 +134,12 @@ class InlinedVector {
     AppendRange(init_list.begin(), init_list.end());
   }
 
-  // Creates and initialize with the elements [`first`, `last`).
+  // Creates an inlined vector with elements constructed from the provided
+  // Iterator range [`first`, `last`).
   //
   // NOTE: The `enable_if` prevents ambiguous interpretation between a call to
-  // this constructor with two integral arguments and a call to the preceding
-  // `InlinedVector(n, v)` constructor.
+  // this constructor with two integral arguments and a call to the above
+  // `InlinedVector(size_type, const_reference)` constructor.
   template <typename InputIterator, DisableIfIntegral<InputIterator>* = nullptr>
   InlinedVector(InputIterator first, InputIterator last,
                 const allocator_type& alloc = allocator_type())
@@ -153,11 +153,11 @@ class InlinedVector {
   // Creates a copy of `other` but with a specified allocator.
   InlinedVector(const InlinedVector& other, const allocator_type& alloc);
 
-  // Creates an inlined vector with the contents of `other`.
+  // Creates an inlined vector by moving in the contents of `other`.
   //
   // NOTE: This move constructor does not allocate and only moves the underlying
   // objects, so its `noexcept` specification depends on whether moving the
-  // underlying objects can throw or not. We assume
+  // underlying objects can throw or not. We assume:
   //  a) move constructors should only throw due to allocation failure and
   //  b) if `value_type`'s move constructor allocates, it uses the same
   //     allocation function as the `InlinedVector`'s allocator, so the move
@@ -167,9 +167,9 @@ class InlinedVector {
       absl::allocator_is_nothrow<allocator_type>::value ||
       std::is_nothrow_move_constructible<value_type>::value);
 
-  // Creates an inlined vector with the contents of `other`.
+  // Creates an inlined vector by moving in the contents of `other`.
   //
-  // NOTE: This move constructor allocates and also moves the underlying
+  // NOTE: This move constructor allocates and subsequently moves the underlying
   // objects, so its `noexcept` specification depends on whether the allocation
   // can throw and whether moving the underlying objects can throw. Based on the
   // same assumptions as above, the `noexcept` specification is dominated by
@@ -180,7 +180,6 @@ class InlinedVector {
 
   ~InlinedVector() { clear(); }
 
-
   // ---------------------------------------------------------------------------
   // InlinedVector Member Accessors
   // ---------------------------------------------------------------------------
diff --git a/absl/container/internal/hash_generator_testing.cc b/absl/container/internal/hash_generator_testing.cc
index 0d6a9df16f8a..e0fefbffdfa1 100644
--- a/absl/container/internal/hash_generator_testing.cc
+++ b/absl/container/internal/hash_generator_testing.cc
@@ -39,9 +39,9 @@ class RandomDeviceSeedSeq {
 
 }  // namespace
 
-std::mt19937_64* GetThreadLocalRng() {
+std::mt19937_64* GetSharedRng() {
   RandomDeviceSeedSeq seed_seq;
-  thread_local auto* rng = new std::mt19937_64(seed_seq);
+  static auto* rng = new std::mt19937_64(seed_seq);
   return rng;
 }
 
@@ -51,7 +51,7 @@ std::string Generator<std::string>::operator()() const {
   std::string res;
   res.resize(32);
   std::generate(res.begin(), res.end(),
-                [&]() { return chars(*GetThreadLocalRng()); });
+                [&]() { return chars(*GetSharedRng()); });
   return res;
 }
 
@@ -63,7 +63,7 @@ absl::string_view Generator<absl::string_view>::operator()() const {
   auto& res = arena->back();
   res.resize(32);
   std::generate(res.begin(), res.end(),
-                [&]() { return chars(*GetThreadLocalRng()); });
+                [&]() { return chars(*GetSharedRng()); });
   return res;
 }
 
diff --git a/absl/container/internal/hash_generator_testing.h b/absl/container/internal/hash_generator_testing.h
index 50d771026c7b..6521efe87337 100644
--- a/absl/container/internal/hash_generator_testing.h
+++ b/absl/container/internal/hash_generator_testing.h
@@ -43,7 +43,7 @@ struct IsMap<Map, absl::void_t<typename Map::mapped_type>> : std::true_type {};
 
 }  // namespace generator_internal
 
-std::mt19937_64* GetThreadLocalRng();
+std::mt19937_64* GetSharedRng();
 
 enum Enum {
   kEnumEmpty,
@@ -66,7 +66,7 @@ template <class T>
 struct Generator<T, typename std::enable_if<std::is_integral<T>::value>::type> {
   T operator()() const {
     std::uniform_int_distribution<T> dist;
-    return dist(*GetThreadLocalRng());
+    return dist(*GetSharedRng());
   }
 };
 
@@ -76,7 +76,7 @@ struct Generator<Enum> {
     std::uniform_int_distribution<typename std::underlying_type<Enum>::type>
         dist;
     while (true) {
-      auto variate = dist(*GetThreadLocalRng());
+      auto variate = dist(*GetSharedRng());
       if (variate != kEnumEmpty && variate != kEnumDeleted)
         return static_cast<Enum>(variate);
     }
@@ -90,7 +90,7 @@ struct Generator<EnumClass> {
         typename std::underlying_type<EnumClass>::type>
         dist;
     while (true) {
-      EnumClass variate = static_cast<EnumClass>(dist(*GetThreadLocalRng()));
+      EnumClass variate = static_cast<EnumClass>(dist(*GetSharedRng()));
       if (variate != EnumClass::kEmpty && variate != EnumClass::kDeleted)
         return static_cast<EnumClass>(variate);
     }
diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h
index 00710e52c577..18d3f28f2202 100644
--- a/absl/container/node_hash_map.h
+++ b/absl/container/node_hash_map.h
@@ -40,6 +40,7 @@
 #include <type_traits>
 #include <utility>
 
+#include "absl/algorithm/container.h"
 #include "absl/container/internal/container_memory.h"
 #include "absl/container/internal/hash_function_defaults.h"  // IWYU pragma: export
 #include "absl/container/internal/node_hash_policy.h"
@@ -91,7 +92,7 @@ class NodeHashMapPolicy;
 //  std::string search_key = "b";
 //  auto result = ducks.find(search_key);
 //  if (result != ducks.end()) {
-//    std::cout << "Result: " << search_key->second << std::endl;
+//    std::cout << "Result: " << result->second << std::endl;
 //  }
 template <class Key, class Value,
           class Hash = absl::container_internal::hash_default_hash<Key>,
@@ -566,5 +567,16 @@ class NodeHashMapPolicy
   static const Value& value(const value_type* elem) { return elem->second; }
 };
 }  // namespace container_internal
+
+namespace container_algorithm_internal {
+
+// Specialization of trait in absl/algorithm/container.h
+template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+struct IsUnorderedContainer<
+    absl::node_hash_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {};
+
+}  // namespace container_algorithm_internal
+
 }  // namespace absl
+
 #endif  // ABSL_CONTAINER_NODE_HASH_MAP_H_
diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h
index 813fdeffce0e..e0897c99afff 100644
--- a/absl/container/node_hash_set.h
+++ b/absl/container/node_hash_set.h
@@ -37,6 +37,7 @@
 
 #include <type_traits>
 
+#include "absl/algorithm/container.h"
 #include "absl/container/internal/hash_function_defaults.h"  // IWYU pragma: export
 #include "absl/container/internal/node_hash_policy.h"
 #include "absl/container/internal/raw_hash_set.h"  // IWYU pragma: export
@@ -475,5 +476,15 @@ struct NodeHashSetPolicy
   static size_t element_space_used(const T*) { return sizeof(T); }
 };
 }  // namespace container_internal
+
+namespace container_algorithm_internal {
+
+// Specialization of trait in absl/algorithm/container.h
+template <class Key, class Hash, class KeyEqual, class Allocator>
+struct IsUnorderedContainer<absl::node_hash_set<Key, Hash, KeyEqual, Allocator>>
+    : std::true_type {};
+
+}  // namespace container_algorithm_internal
 }  // namespace absl
+
 #endif  // ABSL_CONTAINER_NODE_HASH_SET_H_