summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel10
-rw-r--r--absl/container/CMakeLists.txt12
-rw-r--r--absl/container/fixed_array.h1
-rw-r--r--absl/container/flat_hash_map_test.cc7
-rw-r--r--absl/container/inlined_vector.h180
-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
8 files changed, 214 insertions, 129 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index b6592ca5..cd914baf 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -112,10 +112,20 @@ cc_test(
)
cc_library(
+ name = "inlined_vector_internal",
+ hdrs = ["internal/inlined_vector.h"],
+ copts = ABSL_DEFAULT_COPTS,
+ deps = [
+ "//absl/meta:type_traits",
+ ],
+)
+
+cc_library(
name = "inlined_vector",
hdrs = ["inlined_vector.h"],
copts = ABSL_DEFAULT_COPTS,
deps = [
+ ":inlined_vector_internal",
"//absl/algorithm",
"//absl/base:core_headers",
"//absl/base:throw_delegate",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index 76542be1..292fea2a 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -109,6 +109,18 @@ absl_cc_test(
absl_cc_library(
NAME
+ inlined_vector_internal
+ HDRS
+ "internal/inlined_vector.h"
+ COPTS
+ ${ABSL_DEFAULT_COPTS}
+ DEPS
+ absl::type_traits
+ PUBLIC
+)
+
+absl_cc_library(
+ NAME
inlined_vector
HDRS
"inlined_vector.h"
diff --git a/absl/container/fixed_array.h b/absl/container/fixed_array.h
index 0161d0a9..2a8240ae 100644
--- a/absl/container/fixed_array.h
+++ b/absl/container/fixed_array.h
@@ -515,4 +515,5 @@ void FixedArray<T, N, A>::NonEmptyInlinedStorage::AnnotateDestruct(
static_cast<void>(n); // Mark used when not in asan mode
}
} // namespace absl
+
#endif // ABSL_CONTAINER_FIXED_ARRAY_H_
diff --git a/absl/container/flat_hash_map_test.cc b/absl/container/flat_hash_map_test.cc
index bae5c15d..ebcb560f 100644
--- a/absl/container/flat_hash_map_test.cc
+++ b/absl/container/flat_hash_map_test.cc
@@ -206,7 +206,9 @@ TEST(FlatHashMap, MergeExtractInsert) {
m.insert(std::move(node));
EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 17), Pair(2, 9)));
}
-#if !defined(__ANDROID__) && !defined(__APPLE__) && !defined(__EMSCRIPTEN__)
+
+#if (defined(ABSL_HAVE_STD_ANY) || !defined(_LIBCPP_VERSION)) && \
+ !defined(__EMSCRIPTEN__)
TEST(FlatHashMap, Any) {
absl::flat_hash_map<int, absl::any> m;
m.emplace(1, 7);
@@ -237,7 +239,8 @@ TEST(FlatHashMap, Any) {
ASSERT_NE(it2, m2.end());
EXPECT_EQ(7, it2->second);
}
-#endif // __ANDROID__
+#endif // (defined(ABSL_HAVE_STD_ANY) || !defined(_LIBCPP_VERSION)) &&
+ // !defined(__EMSCRIPTEN__)
} // namespace
} // namespace container_internal
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 80929e36..68308750 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -1,4 +1,4 @@
-// Copyright 2018 The Abseil Authors.
+// 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.
@@ -50,6 +50,7 @@
#include "absl/base/internal/throw_delegate.h"
#include "absl/base/optimization.h"
#include "absl/base/port.h"
+#include "absl/container/internal/inlined_vector.h"
#include "absl/memory/memory.h"
namespace absl {
@@ -65,10 +66,10 @@ namespace absl {
// 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 {
- static_assert(N > 0, "InlinedVector requires inline capacity greater than 0");
- constexpr static typename A::size_type GetInlinedCapacity() {
- return static_cast<typename A::size_type>(N);
- }
+ using Storage = inlined_vector_internal::InlinedVectorStorage<T, N, A>;
+ using Tag = typename Storage::Tag;
+ using AllocatorAndTag = typename Storage::AllocatorAndTag;
+ using Allocation = typename Storage::Allocation;
template <typename Iterator>
using IsAtLeastForwardIterator = std::is_convertible<
@@ -83,21 +84,21 @@ class InlinedVector {
using DisableIfAtLeastForwardIterator =
absl::enable_if_t<!IsAtLeastForwardIterator<Iterator>::value>;
- using rvalue_reference = typename A::value_type&&;
+ using rvalue_reference = typename Storage::rvalue_reference;
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 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>;
+ using allocator_type = typename Storage::allocator_type;
+ using value_type = typename Storage::value_type;
+ using pointer = typename Storage::pointer;
+ using const_pointer = typename Storage::const_pointer;
+ using reference = typename Storage::reference;
+ using const_reference = typename Storage::const_reference;
+ using size_type = typename Storage::size_type;
+ using difference_type = typename Storage::difference_type;
+ using iterator = typename Storage::iterator;
+ using const_iterator = typename Storage::const_iterator;
+ using reverse_iterator = typename Storage::reverse_iterator;
+ using const_reverse_iterator = typename Storage::const_reverse_iterator;
// ---------------------------------------------------------------------------
// InlinedVector Constructors and Destructor
@@ -105,30 +106,30 @@ class InlinedVector {
// Creates an empty inlined vector with a default initialized allocator.
InlinedVector() noexcept(noexcept(allocator_type()))
- : allocator_and_tag_(allocator_type()) {}
+ : storage_(allocator_type()) {}
// Creates an empty inlined vector with a specified allocator.
explicit InlinedVector(const allocator_type& alloc) noexcept
- : allocator_and_tag_(alloc) {}
+ : storage_(alloc) {}
// Creates an inlined vector with `n` copies of `value_type()`.
explicit InlinedVector(size_type n,
const allocator_type& alloc = allocator_type())
- : allocator_and_tag_(alloc) {
+ : storage_(alloc) {
InitAssign(n);
}
// Creates an inlined vector with `n` copies of `v`.
InlinedVector(size_type n, const_reference v,
const allocator_type& alloc = allocator_type())
- : allocator_and_tag_(alloc) {
+ : storage_(alloc) {
InitAssign(n, v);
}
// Creates an inlined vector of copies of the values in `list`.
InlinedVector(std::initializer_list<value_type> list,
const allocator_type& alloc = allocator_type())
- : allocator_and_tag_(alloc) {
+ : storage_(alloc) {
AppendForwardRange(list.begin(), list.end());
}
@@ -142,7 +143,7 @@ class InlinedVector {
EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr>
InlinedVector(ForwardIterator first, ForwardIterator last,
const allocator_type& alloc = allocator_type())
- : allocator_and_tag_(alloc) {
+ : storage_(alloc) {
AppendForwardRange(first, last);
}
@@ -152,7 +153,7 @@ class InlinedVector {
DisableIfAtLeastForwardIterator<InputIterator>* = nullptr>
InlinedVector(InputIterator first, InputIterator last,
const allocator_type& alloc = allocator_type())
- : allocator_and_tag_(alloc) {
+ : storage_(alloc) {
std::copy(first, last, std::back_inserter(*this));
}
@@ -162,7 +163,7 @@ class InlinedVector {
// Creates a copy of an `other` inlined vector using a specified allocator.
InlinedVector(const InlinedVector& other, const allocator_type& alloc)
- : allocator_and_tag_(alloc) {
+ : storage_(alloc) {
reserve(other.size());
if (allocated()) {
UninitializedCopy(other.begin(), other.end(), allocated_space());
@@ -191,7 +192,7 @@ class InlinedVector {
InlinedVector(InlinedVector&& other) noexcept(
absl::allocator_is_nothrow<allocator_type>::value ||
std::is_nothrow_move_constructible<value_type>::value)
- : allocator_and_tag_(other.allocator()) {
+ : storage_(other.allocator()) {
if (other.allocated()) {
// We can just steal the underlying buffer from the source.
// That leaves the source empty, so we clear its size.
@@ -222,7 +223,7 @@ class InlinedVector {
// ownership of `other`'s allocated memory.
InlinedVector(InlinedVector&& other, const allocator_type& alloc) noexcept(
absl::allocator_is_nothrow<allocator_type>::value)
- : allocator_and_tag_(alloc) {
+ : storage_(alloc) {
if (other.allocated()) {
if (alloc == other.allocator()) {
// We can just steal the allocation from the source.
@@ -282,7 +283,8 @@ class InlinedVector {
// will no longer be inlined and `capacity()` will equal its capacity on the
// allocated heap.
size_type capacity() const noexcept {
- return allocated() ? allocation().capacity() : GetInlinedCapacity();
+ return allocated() ? allocation().capacity()
+ : Storage::GetInlinedCapacity();
}
// `InlinedVector::data()`
@@ -800,19 +802,19 @@ class InlinedVector {
// `InlinedVector::shrink_to_fit()`
//
// Reduces memory usage by freeing unused memory. After this call, calls to
- // `capacity()` will be equal to `(std::max)(GetInlinedCapacity(), size())`.
+ // `capacity()` will be equal to `max(Storage::GetInlinedCapacity(), size())`.
//
- // If `size() <= GetInlinedCapacity()` and the elements are currently stored
- // on the heap, they will be moved to the inlined storage and the heap memory
- // will be deallocated.
+ // If `size() <= Storage::GetInlinedCapacity()` and the elements are currently
+ // stored on the heap, they will be moved to the inlined storage and the heap
+ // memory will be deallocated.
//
- // If `size() > GetInlinedCapacity()` and `size() < capacity()` the elements
- // will be moved to a smaller heap allocation.
+ // If `size() > Storage::GetInlinedCapacity()` and `size() < capacity()` the
+ // elements will be moved to a smaller heap allocation.
void shrink_to_fit() {
const auto s = size();
if (ABSL_PREDICT_FALSE(!allocated() || s == capacity())) return;
- if (s <= GetInlinedCapacity()) {
+ if (s <= Storage::GetInlinedCapacity()) {
// Move the elements to the inlined storage.
// We have to do this using a temporary, because `inlined_storage` and
// `allocation_storage` are in a union field.
@@ -845,88 +847,33 @@ class InlinedVector {
template <typename H, typename TheT, size_t TheN, typename TheA>
friend auto AbslHashValue(H h, const InlinedVector<TheT, TheN, TheA>& v) -> H;
- // 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 {
- 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; }
-
- private:
- size_type size_;
- };
-
- // 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 {
- 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; }
-
- private:
- Tag tag_;
- };
-
- class Allocation {
- 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_; }
+ const Tag& tag() const { return storage_.allocator_and_tag_.tag(); }
- private:
- static pointer Create(allocator_type& a, size_type n) {
- return std::allocator_traits<allocator_type>::allocate(a, n);
- }
-
- size_type capacity_;
- pointer buffer_;
- };
-
- const Tag& tag() const { return allocator_and_tag_.tag(); }
-
- Tag& tag() { return allocator_and_tag_.tag(); }
+ Tag& tag() { return storage_.allocator_and_tag_.tag(); }
Allocation& allocation() {
- return reinterpret_cast<Allocation&>(rep_.allocation_storage.allocation);
+ return reinterpret_cast<Allocation&>(
+ storage_.rep_.allocation_storage.allocation);
}
const Allocation& allocation() const {
return reinterpret_cast<const Allocation&>(
- rep_.allocation_storage.allocation);
+ storage_.rep_.allocation_storage.allocation);
}
void init_allocation(const Allocation& allocation) {
- new (&rep_.allocation_storage.allocation) Allocation(allocation);
+ new (&storage_.rep_.allocation_storage.allocation) Allocation(allocation);
}
// TODO(absl-team): investigate whether the reinterpret_cast is appropriate.
pointer inlined_space() {
return reinterpret_cast<pointer>(
- std::addressof(rep_.inlined_storage.inlined[0]));
+ std::addressof(storage_.rep_.inlined_storage.inlined[0]));
}
const_pointer inlined_space() const {
return reinterpret_cast<const_pointer>(
- std::addressof(rep_.inlined_storage.inlined[0]));
+ std::addressof(storage_.rep_.inlined_storage.inlined[0]));
}
pointer allocated_space() { return allocation().buffer(); }
@@ -934,10 +881,12 @@ class InlinedVector {
const_pointer allocated_space() const { return allocation().buffer(); }
const allocator_type& allocator() const {
- return allocator_and_tag_.allocator();
+ return storage_.allocator_and_tag_.allocator();
}
- allocator_type& allocator() { return allocator_and_tag_.allocator(); }
+ allocator_type& allocator() {
+ return storage_.allocator_and_tag_.allocator();
+ }
bool allocated() const { return tag().allocated(); }
@@ -994,7 +943,7 @@ class InlinedVector {
const size_type s = size();
assert(s <= capacity());
- size_type target = (std::max)(GetInlinedCapacity(), s + delta);
+ size_type target = (std::max)(Storage::GetInlinedCapacity(), s + delta);
// Compute new capacity by repeatedly doubling current capacity
// TODO(psrc): Check and avoid overflow?
@@ -1097,7 +1046,7 @@ class InlinedVector {
}
void InitAssign(size_type n) {
- if (n > GetInlinedCapacity()) {
+ if (n > Storage::GetInlinedCapacity()) {
Allocation new_allocation(allocator(), n);
init_allocation(new_allocation);
UninitializedFill(allocated_space(), allocated_space() + n);
@@ -1109,7 +1058,7 @@ class InlinedVector {
}
void InitAssign(size_type n, const_reference v) {
- if (n > GetInlinedCapacity()) {
+ if (n > Storage::GetInlinedCapacity()) {
Allocation new_allocation(allocator(), n);
init_allocation(new_allocation);
UninitializedFill(allocated_space(), allocated_space() + n, v);
@@ -1267,28 +1216,7 @@ class InlinedVector {
assert(a->size() == b_size);
}
- // 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_;
+ Storage storage_;
};
// -----------------------------------------------------------------------------
diff --git a/absl/container/internal/hashtablez_sampler.h b/absl/container/internal/hashtablez_sampler.h
index aff8d15f..a308e788 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 00000000..30850609
--- /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 9e79cb38..87511148 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};
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-07 12:58:03 +0000