about summary refs log tree commit diff
path: root/absl/container/internal
diff options
context:
space:
mode:
authorAbseil Team <absl-team@google.com>2019-03-19T18·14-0700
committerDerek Mauro <dmauro@google.com>2019-03-19T18·19-0400
commitbf29470384a101b307873b26d358433138c857fc (patch)
tree1a8374bafdbfc606b4e70c0f581c3d6b34a08d7d /absl/container/internal
parent6fd827124facd8336981e73218997f9e73029b4f (diff)
Export of internal Abseil changes.
--
bdce7e57e9e886eff1114d0266781b443f7ec639 by Derek Mauro <dmauro@google.com>:

Change {Get|Set}EnvironmentVariable to {Get|Set}EnvironmentVariableA for
compatibility with /DUNICODE.

PiperOrigin-RevId: 239229514

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

Import of CCTZ from GitHub.

PiperOrigin-RevId: 239228622

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

Adding linking of CoreFoundation to CMakeLists in absl/time.
Import https://github.com/abseil/abseil-cpp/pull/280.

Fix #283

PiperOrigin-RevId: 239220785

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

Add hermetic test script that uses Docker to build with a very recent
version of gcc (8.3.0 today) with libstdc++ and bazel.

PiperOrigin-RevId: 239220448

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

Disable part of the variant exeception safety test on move assignment
when using versions of libstd++ that contain a bug.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87431#c7

PiperOrigin-RevId: 239062455

--
799722217aeda79679577843c91d5be62cbcbb42 by Matt Calabrese <calabrese@google.com>:

Add internal-only IsSwappable traits corresponding to std::is_swappable and std::is_nothrow_swappable, which are used with the swap implementations of optional and variant.

PiperOrigin-RevId: 239049448

--
aa46a036038a3de5c68ac5e5d3b4bf76f818d2ea by CJ Johnson <johnsoncj@google.com>:

Make InlinedVectorStorage constructor explicit

PiperOrigin-RevId: 239044361

--
17949715b3aa21c794701f69f2154e91b6acabc3 by CJ Johnson <johnsoncj@google.com>:

Add absl namesapce to internal/inlined_vector.h

PiperOrigin-RevId: 239030789

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

Add test script that uses Docker to build Abseil with gcc-4.8,
libstdc++, and cmake.

PiperOrigin-RevId: 239028433

--
80fe24149ed73ed2ced995ad1e372fb060c60427 by CJ Johnson <johnsoncj@google.com>:

Factors data members of InlinedVector into an impl type called InlinedVectorStorage so that (in future changes) the contents of a vector can be grouped together with a single pointer.

PiperOrigin-RevId: 239021086

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

Add -Wno-missing-field-initializers to gcc compiler flags.
gcc-4.x has spurious missing field initializer warnings.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=36750

PiperOrigin-RevId: 239017217

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

Formatting fixes.

PiperOrigin-RevId: 238983038

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

Add hermetic test script that uses Docker to build with a very recent
version of clang with libc++ and bazel.

PiperOrigin-RevId: 238669118

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

Disable the test optionalTest.InPlaceTSFINAEBug until libc++ is updated.

PiperOrigin-RevId: 238661703

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

Correct the check for the FlatHashMap-Any test bug (list conditions
instead of platforms when possible)

PiperOrigin-RevId: 238653344

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

Add install rules for Abseil CMake.

These are attempted to be limited to in-project installation.  This serves two purposes -- first it's morally the same as using Abseil in-source, except you don't have to rebuild us every time.  Second, the presence of an install rule makes life massively simpler for package manager maintainers.

Currently this doesn't install absl tests or testonly libraries.  This can be added in a follow-up patch.

Fixes #38, Fixes #80, Closes #182

PiperOrigin-RevId: 238645836

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

Add hermetic test script that uses Docker to build with a very recent
version of clang with libstdc++ and bazel.

PiperOrigin-RevId: 238517815
GitOrigin-RevId: bdce7e57e9e886eff1114d0266781b443f7ec639
Change-Id: I6f745869cb8ef63851891ccac05ae9a7dd241c4f
Diffstat (limited to 'absl/container/internal')
-rw-r--r--absl/container/internal/hashtablez_sampler.h1
-rw-r--r--absl/container/internal/inlined_vector.h130
-rw-r--r--absl/container/internal/raw_hash_set_test.cc2
3 files changed, 132 insertions, 1 deletions
diff --git a/absl/container/internal/hashtablez_sampler.h b/absl/container/internal/hashtablez_sampler.h
index aff8d15f4940..a308e7881962 100644
--- a/absl/container/internal/hashtablez_sampler.h
+++ b/absl/container/internal/hashtablez_sampler.h
@@ -34,7 +34,6 @@
 // are using a table in an unusual circumstance where allocation or calling a
 // linux syscall is unacceptable, this could interfere.
 //
-//
 // This utility is internal-only. Use at your own risk.
 
 #ifndef ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_
diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
new file mode 100644
index 000000000000..308506093300
--- /dev/null
+++ b/absl/container/internal/inlined_vector.h
@@ -0,0 +1,130 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
+#define ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
+
+#include <cstddef>
+#include <iterator>
+#include <memory>
+
+#include "absl/meta/type_traits.h"
+
+namespace absl {
+namespace inlined_vector_internal {
+
+template <typename T, size_t N, typename A>
+class InlinedVectorStorage {
+  static_assert(
+      N > 0, "InlinedVector cannot be instantiated with `0` inline elements.");
+
+ public:
+  using allocator_type = A;
+  using value_type = typename allocator_type::value_type;
+  using pointer = typename allocator_type::pointer;
+  using const_pointer = typename allocator_type::const_pointer;
+  using reference = typename allocator_type::reference;
+  using const_reference = typename allocator_type::const_reference;
+  using rvalue_reference = typename allocator_type::value_type&&;
+  using size_type = typename allocator_type::size_type;
+  using difference_type = typename allocator_type::difference_type;
+  using iterator = pointer;
+  using const_iterator = const_pointer;
+  using reverse_iterator = std::reverse_iterator<iterator>;
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+  constexpr static size_type GetInlinedCapacity() {
+    return static_cast<size_type>(N);
+  }
+
+  explicit InlinedVectorStorage(const allocator_type& a)
+      : allocator_and_tag_(a) {}
+
+  // TODO(johnsoncj): Make the below types and members private after migration
+
+  // Holds whether the vector is allocated or not in the lowest bit and the size
+  // in the high bits:
+  //   `size_ = (size << 1) | is_allocated;`
+  class Tag {
+    size_type size_;
+
+   public:
+    Tag() : size_(0) {}
+    size_type size() const { return size_ / 2; }
+    void add_size(size_type n) { size_ += n * 2; }
+    void set_inline_size(size_type n) { size_ = n * 2; }
+    void set_allocated_size(size_type n) { size_ = (n * 2) + 1; }
+    bool allocated() const { return size_ % 2; }
+  };
+
+  // Derives from `allocator_type` to use the empty base class optimization.
+  // If the `allocator_type` is stateless, we can store our instance for free.
+  class AllocatorAndTag : private allocator_type {
+    Tag tag_;
+
+   public:
+    explicit AllocatorAndTag(const allocator_type& a) : allocator_type(a) {}
+    Tag& tag() { return tag_; }
+    const Tag& tag() const { return tag_; }
+    allocator_type& allocator() { return *this; }
+    const allocator_type& allocator() const { return *this; }
+  };
+
+  class Allocation {
+    size_type capacity_;
+    pointer buffer_;
+
+   public:
+    Allocation(allocator_type& a, size_type capacity)
+        : capacity_(capacity), buffer_(Create(a, capacity)) {}
+    void Dealloc(allocator_type& a) {
+      std::allocator_traits<allocator_type>::deallocate(a, buffer_, capacity_);
+    }
+    size_type capacity() const { return capacity_; }
+    const_pointer buffer() const { return buffer_; }
+    pointer buffer() { return buffer_; }
+    static pointer Create(allocator_type& a, size_type n) {
+      return std::allocator_traits<allocator_type>::allocate(a, n);
+    }
+  };
+
+  // Stores either the inlined or allocated representation
+  union Rep {
+    using ValueTypeBuffer =
+        absl::aligned_storage_t<sizeof(value_type), alignof(value_type)>;
+    using AllocationBuffer =
+        absl::aligned_storage_t<sizeof(Allocation), alignof(Allocation)>;
+
+    // Structs wrap the buffers to perform indirection that solves a bizarre
+    // compilation error on Visual Studio (all known versions).
+    struct InlinedRep {
+      ValueTypeBuffer inlined[N];
+    };
+
+    struct AllocatedRep {
+      AllocationBuffer allocation;
+    };
+
+    InlinedRep inlined_storage;
+    AllocatedRep allocation_storage;
+  };
+
+  AllocatorAndTag allocator_and_tag_;
+  Rep rep_;
+};
+
+}  // namespace inlined_vector_internal
+}  // namespace absl
+
+#endif  // ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 9e79cb38c363..87511148d04a 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1080,6 +1080,7 @@ ExpectedStats XorSeedExpectedStats() {
   ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
   return {};
 }
+
 TEST(Table, DISABLED_EnsureNonQuadraticTopNXorSeedByProbeSeqLength) {
   ProbeStatsPerSize stats;
   std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};
@@ -1173,6 +1174,7 @@ ExpectedStats LinearTransformExpectedStats() {
   ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
   return {};
 }
+
 TEST(Table, DISABLED_EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) {
   ProbeStatsPerSize stats;
   std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};