aboutsummaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel13
-rw-r--r--absl/container/CMakeLists.txt23
-rw-r--r--absl/container/flat_hash_set.h6
-rw-r--r--absl/container/inlined_vector.h979
-rw-r--r--absl/container/internal/compressed_tuple.h28
-rw-r--r--absl/container/internal/compressed_tuple_test.cc43
-rw-r--r--absl/container/internal/hashtable_debug.h2
-rw-r--r--absl/container/internal/have_sse.h49
-rw-r--r--absl/container/internal/layout.h4
-rw-r--r--absl/container/internal/layout_test.cc28
-rw-r--r--absl/container/internal/raw_hash_set.cc3
-rw-r--r--absl/container/internal/raw_hash_set.h33
-rw-r--r--absl/container/node_hash_set.h6
13 files changed, 611 insertions, 606 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index afc869f4..55aea397 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -15,11 +15,11 @@
#
load(
- "//absl:copts.bzl",
+ "//absl:copts/configure_copts.bzl",
"ABSL_DEFAULT_COPTS",
- "ABSL_TEST_COPTS",
"ABSL_EXCEPTIONS_FLAG",
"ABSL_EXCEPTIONS_FLAG_LINKOPTS",
+ "ABSL_TEST_COPTS",
)
package(default_visibility = ["//visibility:public"])
@@ -41,6 +41,8 @@ cc_test(
copts = ABSL_TEST_COPTS,
deps = [
":compressed_tuple",
+ "//absl/memory",
+ "//absl/utility",
"@com_google_googletest//:gtest_main",
],
)
@@ -462,6 +464,12 @@ cc_library(
)
cc_library(
+ name = "have_sse",
+ hdrs = ["internal/have_sse.h"],
+ copts = ABSL_DEFAULT_COPTS,
+)
+
+cc_library(
name = "raw_hash_set",
srcs = ["internal/raw_hash_set.cc"],
hdrs = ["internal/raw_hash_set.h"],
@@ -471,6 +479,7 @@ cc_library(
":container_memory",
":hash_policy_traits",
":hashtable_debug_hooks",
+ ":have_sse",
":layout",
"//absl/base:bits",
"//absl/base:config",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index 7cddd84b..9f781004 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -30,7 +30,7 @@ absl_cc_library(
absl_cc_library(
NAME
compressed_tuple
- SRCS
+ HDRS
"internal/compressed_tuple.h"
DEPS
absl::utility
@@ -44,6 +44,8 @@ absl_cc_test(
"internal/compressed_tuple_test.cc"
DEPS
absl::compressed_tuple
+ absl::memory
+ absl::utility
gmock_main
)
@@ -452,6 +454,16 @@ absl_cc_library(
absl_cc_library(
NAME
+ have_sse
+ HDRS
+ "internal/have_sse.h"
+ COPTS
+ ${ABSL_DEFAULT_COPTS}
+ PUBLIC
+)
+
+absl_cc_library(
+ NAME
node_hash_policy
HDRS
"internal/node_hash_policy.h"
@@ -494,15 +506,16 @@ absl_cc_library(
COPTS
${ABSL_DEFAULT_COPTS}
DEPS
+ absl::bits
absl::compressed_tuple
+ absl::config
absl::container_memory
+ absl::core_headers
+ absl::endian
absl::hash_policy_traits
absl::hashtable_debug_hooks
+ absl::have_sse
absl::layout
- absl::bits
- absl::config
- absl::core_headers
- absl::endian
absl::memory
absl::meta
absl::optional
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h
index 5ea6a816..84984cc4 100644
--- a/absl/container/flat_hash_set.h
+++ b/absl/container/flat_hash_set.h
@@ -279,8 +279,7 @@ class flat_hash_set
//
// The element may be constructed even if there already is an element with the
// key in the container, in which case the newly constructed element will be
- // destroyed immediately. Prefer `try_emplace()` unless your key is not
- // copyable or moveable.
+ // destroyed immediately.
//
// If rehashing occurs due to the insertion, all iterators are invalidated.
using Base::emplace;
@@ -294,8 +293,7 @@ class flat_hash_set
//
// The element may be constructed even if there already is an element with the
// key in the container, in which case the newly constructed element will be
- // destroyed immediately. Prefer `try_emplace()` unless your key is not
- // copyable or moveable.
+ // destroyed immediately.
//
// If rehashing occurs due to the insertion, all iterators are invalidated.
using Base::emplace_hint;
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 642dae6c..fe228001 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -66,12 +66,11 @@ 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 inlined_capacity() {
return static_cast<typename A::size_type>(N);
}
- static_assert(inlined_capacity() > 0, "InlinedVector needs inlined capacity");
-
template <typename Iterator>
using DisableIfIntegral =
absl::enable_if_t<!std::is_integral<Iterator>::value>;
@@ -131,7 +130,8 @@ class InlinedVector {
InlinedVector(std::initializer_list<value_type> init_list,
const allocator_type& alloc = allocator_type())
: allocator_and_tag_(alloc) {
- AppendRange(init_list.begin(), init_list.end());
+ AppendRange(init_list.begin(), init_list.end(),
+ IteratorCategory<decltype(init_list.begin())>{});
}
// Creates an inlined vector with elements constructed from the provided
@@ -144,14 +144,25 @@ class InlinedVector {
InlinedVector(InputIterator first, InputIterator last,
const allocator_type& alloc = allocator_type())
: allocator_and_tag_(alloc) {
- AppendRange(first, last);
+ AppendRange(first, last, IteratorCategory<InputIterator>{});
}
// Creates a copy of `other` using `other`'s allocator.
- InlinedVector(const InlinedVector& other);
+ InlinedVector(const InlinedVector& other)
+ : InlinedVector(other, other.get_allocator()) {}
// Creates a copy of `other` but with a specified allocator.
- InlinedVector(const InlinedVector& other, const allocator_type& alloc);
+ InlinedVector(const InlinedVector& other, const allocator_type& alloc)
+ : allocator_and_tag_(alloc) {
+ reserve(other.size());
+ if (allocated()) {
+ UninitializedCopy(other.begin(), other.end(), allocated_space());
+ tag().set_allocated_size(other.size());
+ } else {
+ UninitializedCopy(other.begin(), other.end(), inlined_space());
+ tag().set_inline_size(other.size());
+ }
+ }
// Creates an inlined vector by moving in the contents of `other`.
//
@@ -163,9 +174,22 @@ class InlinedVector {
// allocation function as the `InlinedVector`'s allocator, so the move
// constructor is non-throwing if the allocator is non-throwing or
// `value_type`'s move constructor is specified as `noexcept`.
- InlinedVector(InlinedVector&& v) noexcept(
+ InlinedVector(InlinedVector&& other) noexcept(
absl::allocator_is_nothrow<allocator_type>::value ||
- std::is_nothrow_move_constructible<value_type>::value);
+ std::is_nothrow_move_constructible<value_type>::value)
+ : allocator_and_tag_(other.allocator_and_tag_) {
+ if (other.allocated()) {
+ // We can just steal the underlying buffer from the source.
+ // That leaves the source empty, so we clear its size.
+ init_allocation(other.allocation());
+ other.tag() = Tag();
+ } else {
+ UninitializedCopy(
+ std::make_move_iterator(other.inlined_space()),
+ std::make_move_iterator(other.inlined_space() + other.size()),
+ inlined_space());
+ }
+ }
// Creates an inlined vector by moving in the contents of `other`.
//
@@ -175,8 +199,31 @@ class InlinedVector {
// same assumptions as above, the `noexcept` specification is dominated by
// whether the allocation can throw regardless of whether `value_type`'s move
// constructor is specified as `noexcept`.
- InlinedVector(InlinedVector&& v, const allocator_type& alloc) noexcept(
- absl::allocator_is_nothrow<allocator_type>::value);
+ InlinedVector(InlinedVector&& other, const allocator_type& alloc) noexcept(
+ absl::allocator_is_nothrow<allocator_type>::value)
+ : allocator_and_tag_(alloc) {
+ if (other.allocated()) {
+ if (alloc == other.allocator()) {
+ // We can just steal the allocation from the source.
+ tag() = other.tag();
+ init_allocation(other.allocation());
+ other.tag() = Tag();
+ } else {
+ // We need to use our own allocator
+ reserve(other.size());
+ UninitializedCopy(std::make_move_iterator(other.begin()),
+ std::make_move_iterator(other.end()),
+ allocated_space());
+ tag().set_allocated_size(other.size());
+ }
+ } else {
+ UninitializedCopy(
+ std::make_move_iterator(other.inlined_space()),
+ std::make_move_iterator(other.inlined_space() + other.size()),
+ inlined_space());
+ tag().set_inline_size(other.size());
+ }
+ }
~InlinedVector() { clear(); }
@@ -255,7 +302,7 @@ class InlinedVector {
reference at(size_type i) {
if (ABSL_PREDICT_FALSE(i >= size())) {
base_internal::ThrowStdOutOfRange(
- "InlinedVector::at() failed bounds check");
+ "`InlinedVector::at(size_type)` failed bounds check");
}
return data()[i];
}
@@ -265,7 +312,7 @@ class InlinedVector {
const_reference at(size_type i) const {
if (ABSL_PREDICT_FALSE(i >= size())) {
base_internal::ThrowStdOutOfRange(
- "InlinedVector::at() failed bounds check");
+ "`InlinedVector::at(size_type) const` failed bounds check");
}
return data()[i];
}
@@ -366,7 +413,6 @@ class InlinedVector {
// Returns a copy of the allocator of the inlined vector.
allocator_type get_allocator() const { return allocator(); }
-
// ---------------------------------------------------------------------------
// InlinedVector Member Mutators
// ---------------------------------------------------------------------------
@@ -376,7 +422,8 @@ class InlinedVector {
// Replaces the contents of the inlined vector with copies of the elements in
// the provided `std::initializer_list`.
InlinedVector& operator=(std::initializer_list<value_type> init_list) {
- AssignRange(init_list.begin(), init_list.end());
+ AssignRange(init_list.begin(), init_list.end(),
+ IteratorCategory<decltype(init_list.begin())>{});
return *this;
}
@@ -453,14 +500,15 @@ class InlinedVector {
// inlined vector with copies of the values in the provided
// `std::initializer_list`.
void assign(std::initializer_list<value_type> init_list) {
- AssignRange(init_list.begin(), init_list.end());
+ AssignRange(init_list.begin(), init_list.end(),
+ IteratorCategory<decltype(init_list.begin())>{});
}
// Overload of `InlinedVector::assign()` to replace the contents of the
// inlined vector with values constructed from the range [`first`, `last`).
template <typename InputIterator, DisableIfIntegral<InputIterator>* = nullptr>
void assign(InputIterator first, InputIterator last) {
- AssignRange(first, last);
+ AssignRange(first, last, IteratorCategory<InputIterator>{});
}
// `InlinedVector::resize()`
@@ -468,12 +516,46 @@ class InlinedVector {
// Resizes the inlined vector to contain `n` elements. If `n` is smaller than
// the inlined vector's current size, extra elements are destroyed. If `n` is
// larger than the initial size, new elements are value-initialized.
- void resize(size_type n);
+ void resize(size_type n) {
+ size_type s = size();
+ if (n < s) {
+ erase(begin() + n, end());
+ return;
+ }
+ reserve(n);
+ assert(capacity() >= n);
+
+ // Fill new space with elements constructed in-place.
+ if (allocated()) {
+ UninitializedFill(allocated_space() + s, allocated_space() + n);
+ tag().set_allocated_size(n);
+ } else {
+ UninitializedFill(inlined_space() + s, inlined_space() + n);
+ tag().set_inline_size(n);
+ }
+ }
// Overload of `InlinedVector::resize()` to resize the inlined vector to
// contain `n` elements where, if `n` is larger than `size()`, the new values
// will be copy-constructed from `v`.
- void resize(size_type n, const_reference v);
+ void resize(size_type n, const_reference v) {
+ size_type s = size();
+ if (n < s) {
+ erase(begin() + n, end());
+ return;
+ }
+ reserve(n);
+ assert(capacity() >= n);
+
+ // Fill new space with copies of `v`.
+ if (allocated()) {
+ UninitializedFill(allocated_space() + s, allocated_space() + n, v);
+ tag().set_allocated_size(n);
+ } else {
+ UninitializedFill(inlined_space() + s, inlined_space() + n, v);
+ tag().set_inline_size(n);
+ }
+ }
// `InlinedVector::insert()`
//
@@ -523,7 +605,27 @@ class InlinedVector {
// Constructs and inserts an object in the inlined vector at the given
// `position`, returning an `iterator` pointing to the newly emplaced element.
template <typename... Args>
- iterator emplace(const_iterator position, Args&&... args);
+ iterator emplace(const_iterator position, Args&&... args) {
+ assert(position >= begin());
+ assert(position <= end());
+ if (ABSL_PREDICT_FALSE(position == end())) {
+ emplace_back(std::forward<Args>(args)...);
+ return end() - 1;
+ }
+
+ T new_t = T(std::forward<Args>(args)...);
+
+ auto range = ShiftRight(position, 1);
+ if (range.first == range.second) {
+ // constructing into uninitialized memory
+ Construct(range.first, std::move(new_t));
+ } else {
+ // assigning into moved-from object
+ *range.first = T(std::move(new_t));
+ }
+
+ return range.first;
+ }
// `InlinedVector::emplace_back()`
//
@@ -596,7 +698,30 @@ class InlinedVector {
// range [`from`, `to`) in the inlined vector. Returns an `iterator` pointing
// to the first element following the range erased or the end iterator if `to`
// was the end iterator.
- iterator erase(const_iterator from, const_iterator to);
+ iterator erase(const_iterator from, const_iterator to) {
+ assert(begin() <= from);
+ assert(from <= to);
+ assert(to <= end());
+
+ iterator range_start = const_cast<iterator>(from);
+ iterator range_end = const_cast<iterator>(to);
+
+ size_type s = size();
+ ptrdiff_t erase_gap = std::distance(range_start, range_end);
+ if (erase_gap > 0) {
+ pointer space;
+ if (allocated()) {
+ space = allocated_space();
+ tag().set_allocated_size(s - erase_gap);
+ } else {
+ space = inlined_space();
+ tag().set_inline_size(s - erase_gap);
+ }
+ std::move(range_end, space + s, range_start);
+ Destroy(space + s - erase_gap, space + s);
+ }
+ return range_start;
+ }
// `InlinedVector::clear()`
//
@@ -667,16 +792,88 @@ class InlinedVector {
// `InlinedVector::swap()`
//
// Swaps the contents of this inlined vector with the contents of `other`.
- void swap(InlinedVector& other);
+ void swap(InlinedVector& other) {
+ if (ABSL_PREDICT_FALSE(this == &other)) return;
+
+ using std::swap; // Augment ADL with `std::swap`.
+ if (allocated() && other.allocated()) {
+ // Both out of line, so just swap the tag, allocation, and allocator.
+ swap(tag(), other.tag());
+ swap(allocation(), other.allocation());
+ swap(allocator(), other.allocator());
+ return;
+ }
+ if (!allocated() && !other.allocated()) {
+ // Both inlined: swap up to smaller size, then move remaining elements.
+ InlinedVector* a = this;
+ InlinedVector* b = &other;
+ if (size() < other.size()) {
+ swap(a, b);
+ }
- template <typename Hash>
- friend Hash AbslHashValue(Hash hash, const InlinedVector& inlined_vector) {
- const_pointer p = inlined_vector.data();
- size_type n = inlined_vector.size();
- return Hash::combine(Hash::combine_contiguous(std::move(hash), p, n), n);
+ const size_type a_size = a->size();
+ const size_type b_size = b->size();
+ assert(a_size >= b_size);
+ // `a` is larger. Swap the elements up to the smaller array size.
+ std::swap_ranges(a->inlined_space(), a->inlined_space() + b_size,
+ b->inlined_space());
+
+ // Move the remaining elements:
+ // [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b`
+ b->UninitializedCopy(a->inlined_space() + b_size,
+ a->inlined_space() + a_size,
+ b->inlined_space() + b_size);
+ a->Destroy(a->inlined_space() + b_size, a->inlined_space() + a_size);
+
+ swap(a->tag(), b->tag());
+ swap(a->allocator(), b->allocator());
+ assert(b->size() == a_size);
+ assert(a->size() == b_size);
+ return;
+ }
+
+ // One is out of line, one is inline.
+ // We first move the elements from the inlined vector into the
+ // inlined space in the other vector. We then put the other vector's
+ // pointer/capacity into the originally inlined vector and swap
+ // the tags.
+ InlinedVector* a = this;
+ InlinedVector* b = &other;
+ if (a->allocated()) {
+ swap(a, b);
+ }
+ assert(!a->allocated());
+ assert(b->allocated());
+ const size_type a_size = a->size();
+ const size_type b_size = b->size();
+ // In an optimized build, `b_size` would be unused.
+ static_cast<void>(b_size);
+
+ // Made Local copies of `size()`, don't need `tag()` accurate anymore
+ swap(a->tag(), b->tag());
+
+ // Copy `b_allocation` out before `b`'s union gets clobbered by
+ // `inline_space`
+ Allocation b_allocation = b->allocation();
+
+ b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size,
+ b->inlined_space());
+ a->Destroy(a->inlined_space(), a->inlined_space() + a_size);
+
+ a->allocation() = b_allocation;
+
+ if (a->allocator() != b->allocator()) {
+ swap(a->allocator(), b->allocator());
+ }
+
+ assert(b->size() == a_size);
+ assert(a->size() == b_size);
}
private:
+ template <typename Hash, typename OtherT, size_t OtherN, typename OtherA>
+ friend Hash AbslHashValue(Hash, const InlinedVector<OtherT, OtherN, OtherA>&);
+
// Holds whether the vector is allocated or not in the lowest bit and the size
// in the high bits:
// `size_ = (size << 1) | is_allocated;`
@@ -773,10 +970,76 @@ class InlinedVector {
bool allocated() const { return tag().allocated(); }
+ void ResetAllocation(Allocation new_allocation, size_type new_size) {
+ if (allocated()) {
+ Destroy(allocated_space(), allocated_space() + size());
+ assert(begin() == allocated_space());
+ allocation().Dealloc(allocator());
+ allocation() = new_allocation;
+ } else {
+ Destroy(inlined_space(), inlined_space() + size());
+ init_allocation(new_allocation); // bug: only init once
+ }
+ tag().set_allocated_size(new_size);
+ }
+
+ template <typename... Args>
+ reference Construct(pointer p, Args&&... args) {
+ std::allocator_traits<allocator_type>::construct(
+ allocator(), p, std::forward<Args>(args)...);
+ return *p;
+ }
+
+ template <typename Iterator>
+ void UninitializedCopy(Iterator src, Iterator src_last, pointer dst) {
+ for (; src != src_last; ++dst, ++src) Construct(dst, *src);
+ }
+
+ template <typename... Args>
+ void UninitializedFill(pointer dst, pointer dst_last, const Args&... args) {
+ for (; dst != dst_last; ++dst) Construct(dst, args...);
+ }
+
+ // Destroy [`from`, `to`) in place.
+ void Destroy(pointer from, pointer to) {
+ for (pointer cur = from; cur != to; ++cur) {
+ std::allocator_traits<allocator_type>::destroy(allocator(), cur);
+ }
+#if !defined(NDEBUG)
+ // Overwrite unused memory with `0xab` so we can catch uninitialized usage.
+ // Cast to `void*` to tell the compiler that we don't care that we might be
+ // scribbling on a vtable pointer.
+ if (from != to) {
+ auto len = sizeof(value_type) * std::distance(from, to);
+ std::memset(reinterpret_cast<void*>(from), 0xab, len);
+ }
+#endif // !defined(NDEBUG)
+ }
+
// Enlarge the underlying representation so we can store `size_ + delta` elems
// in allocated space. The size is not changed, and any newly added memory is
// not initialized.
- void EnlargeBy(size_type delta);
+ void EnlargeBy(size_type delta) {
+ const size_type s = size();
+ assert(s <= capacity());
+
+ size_type target = (std::max)(inlined_capacity(), s + delta);
+
+ // Compute new capacity by repeatedly doubling current capacity
+ // TODO(psrc): Check and avoid overflow?
+ size_type new_capacity = capacity();
+ while (new_capacity < target) {
+ new_capacity <<= 1;
+ }
+
+ Allocation new_allocation(allocator(), new_capacity);
+
+ UninitializedCopy(std::make_move_iterator(data()),
+ std::make_move_iterator(data() + s),
+ new_allocation.buffer());
+
+ ResetAllocation(new_allocation, s);
+ }
// Shift all elements from `position` to `end()` by `n` places to the right.
// If the vector needs to be enlarged, memory will be allocated.
@@ -787,19 +1050,61 @@ class InlinedVector {
//
// Updates the size of the InlinedVector internally.
std::pair<iterator, iterator> ShiftRight(const_iterator position,
- size_type n);
+ size_type n) {
+ iterator start_used = const_cast<iterator>(position);
+ iterator start_raw = const_cast<iterator>(position);
+ size_type s = size();
+ size_type required_size = s + n;
- void ResetAllocation(Allocation new_allocation, size_type new_size) {
- if (allocated()) {
- Destroy(allocated_space(), allocated_space() + size());
- assert(begin() == allocated_space());
- allocation().Dealloc(allocator());
- allocation() = new_allocation;
+ if (required_size > capacity()) {
+ // Compute new capacity by repeatedly doubling current capacity
+ size_type new_capacity = capacity();
+ while (new_capacity < required_size) {
+ new_capacity <<= 1;
+ }
+ // Move everyone into the new allocation, leaving a gap of `n` for the
+ // requested shift.
+ Allocation new_allocation(allocator(), new_capacity);
+ size_type index = position - begin();
+ UninitializedCopy(std::make_move_iterator(data()),
+ std::make_move_iterator(data() + index),
+ new_allocation.buffer());
+ UninitializedCopy(std::make_move_iterator(data() + index),
+ std::make_move_iterator(data() + s),
+ new_allocation.buffer() + index + n);
+ ResetAllocation(new_allocation, s);
+
+ // New allocation means our iterator is invalid, so we'll recalculate.
+ // Since the entire gap is in new space, there's no used space to reuse.
+ start_raw = begin() + index;
+ start_used = start_raw;
} else {
- Destroy(inlined_space(), inlined_space() + size());
- init_allocation(new_allocation); // bug: only init once
+ // If we had enough space, it's a two-part move. Elements going into
+ // previously-unoccupied space need an `UninitializedCopy()`. Elements
+ // going into a previously-occupied space are just a `std::move()`.
+ iterator pos = const_cast<iterator>(position);
+ iterator raw_space = end();
+ size_type slots_in_used_space = raw_space - pos;
+ size_type new_elements_in_used_space = (std::min)(n, slots_in_used_space);
+ size_type new_elements_in_raw_space = n - new_elements_in_used_space;
+ size_type old_elements_in_used_space =
+ slots_in_used_space - new_elements_in_used_space;
+
+ UninitializedCopy(
+ std::make_move_iterator(pos + old_elements_in_used_space),
+ std::make_move_iterator(raw_space),
+ raw_space + new_elements_in_raw_space);
+ std::move_backward(pos, pos + old_elements_in_used_space, raw_space);
+
+ // If the gap is entirely in raw space, the used space starts where the
+ // raw space starts, leaving no elements in used space. If the gap is
+ // entirely in used space, the raw space starts at the end of the gap,
+ // leaving all elements accounted for within the used space.
+ start_used = pos;
+ start_raw = pos + new_elements_in_used_space;
}
- tag().set_allocated_size(new_size);
+ tag().add_size(n);
+ return std::make_pair(start_used, start_raw);
}
template <typename... Args>
@@ -820,64 +1125,118 @@ class InlinedVector {
return new_element;
}
- void InitAssign(size_type n);
-
- void InitAssign(size_type n, const_reference v);
-
- template <typename... Args>
- reference Construct(pointer p, Args&&... args) {
- std::allocator_traits<allocator_type>::construct(
- allocator(), p, std::forward<Args>(args)...);
- return *p;
+ void InitAssign(size_type n) {
+ if (n > inlined_capacity()) {
+ Allocation new_allocation(allocator(), n);
+ init_allocation(new_allocation);
+ UninitializedFill(allocated_space(), allocated_space() + n);
+ tag().set_allocated_size(n);
+ } else {
+ UninitializedFill(inlined_space(), inlined_space() + n);
+ tag().set_inline_size(n);
+ }
}
- template <typename Iterator>
- void UninitializedCopy(Iterator src, Iterator src_last, pointer dst) {
- for (; src != src_last; ++dst, ++src) Construct(dst, *src);
+ void InitAssign(size_type n, const_reference v) {
+ if (n > inlined_capacity()) {
+ Allocation new_allocation(allocator(), n);
+ init_allocation(new_allocation);
+ UninitializedFill(allocated_space(), allocated_space() + n, v);
+ tag().set_allocated_size(n);
+ } else {
+ UninitializedFill(inlined_space(), inlined_space() + n, v);
+ tag().set_inline_size(n);
+ }
}
- template <typename... Args>
- void UninitializedFill(pointer dst, pointer dst_last, const Args&... args) {
- for (; dst != dst_last; ++dst) Construct(dst, args...);
+ template <typename Iterator>
+ void AssignRange(Iterator first, Iterator last, std::forward_iterator_tag) {
+ auto length = std::distance(first, last);
+ // Prefer reassignment to copy construction for elements.
+ if (static_cast<size_type>(length) <= size()) {
+ erase(std::copy(first, last, begin()), end());
+ return;
+ }
+ reserve(length);
+ iterator out = begin();
+ for (; out != end(); ++first, ++out) *out = *first;
+ if (allocated()) {
+ UninitializedCopy(first, last, out);
+ tag().set_allocated_size(length);
+ } else {
+ UninitializedCopy(first, last, out);
+ tag().set_inline_size(length);
+ }
}
- // Destroy [`from`, `to`) in place.
- void Destroy(pointer from, pointer to);
-
template <typename Iterator>
- void AppendRange(Iterator first, Iterator last, std::input_iterator_tag) {
+ void AssignRange(Iterator first, Iterator last, std::input_iterator_tag) {
+ // Optimized to avoid reallocation.
+ // Prefer reassignment to copy construction for elements.
+ iterator out = begin();
+ for (; first != last && out != end(); ++first, ++out) {
+ *out = *first;
+ }
+ erase(out, end());
std::copy(first, last, std::back_inserter(*this));
}
template <typename Iterator>
- void AppendRange(Iterator first, Iterator last, std::forward_iterator_tag);
+ void AppendRange(Iterator first, Iterator last, std::forward_iterator_tag) {
+ auto length = std::distance(first, last);
+ reserve(size() + length);
+ if (allocated()) {
+ UninitializedCopy(first, last, allocated_space() + size());
+ tag().set_allocated_size(size() + length);
+ } else {
+ UninitializedCopy(first, last, inlined_space() + size());
+ tag().set_inline_size(size() + length);
+ }
+ }
template <typename Iterator>
- void AppendRange(Iterator first, Iterator last) {
- AppendRange(first, last, IteratorCategory<Iterator>());
+ void AppendRange(Iterator first, Iterator last, std::input_iterator_tag) {
+ std::copy(first, last, std::back_inserter(*this));
}
- template <typename Iterator>
- void AssignRange(Iterator first, Iterator last, std::input_iterator_tag);
+ iterator InsertWithCount(const_iterator position, size_type n,
+ const_reference v) {
+ assert(position >= begin() && position <= end());
+ if (ABSL_PREDICT_FALSE(n == 0)) return const_cast<iterator>(position);
- template <typename Iterator>
- void AssignRange(Iterator first, Iterator last, std::forward_iterator_tag);
+ value_type copy = v;
+ std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
+ std::fill(it_pair.first, it_pair.second, copy);
+ UninitializedFill(it_pair.second, it_pair.first + n, copy);
- template <typename Iterator>
- void AssignRange(Iterator first, Iterator last) {
- AssignRange(first, last, IteratorCategory<Iterator>());
+ return it_pair.first;
}
- iterator InsertWithCount(const_iterator position, size_type n,
- const_reference v);
+ template <typename ForwardIterator>
+ iterator InsertWithRange(const_iterator position, ForwardIterator first,
+ ForwardIterator last, std::forward_iterator_tag) {
+ assert(position >= begin() && position <= end());
+ if (ABSL_PREDICT_FALSE(first == last))
+ return const_cast<iterator>(position);
+
+ auto n = std::distance(first, last);
+ std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
+ size_type used_spots = it_pair.second - it_pair.first;
+ ForwardIterator open_spot = std::next(first, used_spots);
+ std::copy(first, open_spot, it_pair.first);
+ UninitializedCopy(open_spot, last, it_pair.second);
+ return it_pair.first;
+ }
template <typename InputIterator>
iterator InsertWithRange(const_iterator position, InputIterator first,
- InputIterator last, std::input_iterator_tag);
-
- template <typename ForwardIterator>
- iterator InsertWithRange(const_iterator position, ForwardIterator first,
- ForwardIterator last, std::forward_iterator_tag);
+ InputIterator last, std::input_iterator_tag) {
+ assert(position >= begin() && position <= end());
+ size_type index = position - cbegin();
+ size_type i = index;
+ while (first != last) insert(begin() + i++, *first++);
+ return begin() + index;
+ }
// Stores either the inlined or allocated representation
union Rep {
@@ -889,7 +1248,7 @@ class InlinedVector {
// Structs wrap the buffers to perform indirection that solves a bizarre
// compilation error on Visual Studio (all known versions).
struct InlinedRep {
- ValueTypeBuffer inlined[inlined_capacity()];
+ ValueTypeBuffer inlined[N];
};
struct AllocatedRep {
AllocationBuffer allocation;
@@ -975,477 +1334,19 @@ bool operator>=(const InlinedVector<T, N, A>& a,
return !(a < b);
}
+template <typename Hash, typename T, size_t N, typename A>
+Hash AbslHashValue(Hash hash, const InlinedVector<T, N, A>& inlined_vector) {
+ auto p = inlined_vector.data();
+ auto n = inlined_vector.size();
+ return Hash::combine(Hash::combine_contiguous(std::move(hash), p, n), n);
+}
+
// -----------------------------------------------------------------------------
// Implementation of InlinedVector
//
// Do not depend on any below implementation details!
// -----------------------------------------------------------------------------
-template <typename T, size_t N, typename A>
-InlinedVector<T, N, A>::InlinedVector(const InlinedVector& other)
- : allocator_and_tag_(other.allocator()) {
- reserve(other.size());
- if (allocated()) {
- UninitializedCopy(other.begin(), other.end(), allocated_space());
- tag().set_allocated_size(other.size());
- } else {
- UninitializedCopy(other.begin(), other.end(), inlined_space());
- tag().set_inline_size(other.size());
- }
-}
-
-template <typename T, size_t N, typename A>
-InlinedVector<T, N, A>::InlinedVector(const InlinedVector& other,
- const allocator_type& alloc)
- : allocator_and_tag_(alloc) {
- reserve(other.size());
- if (allocated()) {
- UninitializedCopy(other.begin(), other.end(), allocated_space());
- tag().set_allocated_size(other.size());
- } else {
- UninitializedCopy(other.begin(), other.end(), inlined_space());
- tag().set_inline_size(other.size());
- }
-}
-
-template <typename T, size_t N, typename A>
-InlinedVector<T, N, A>::InlinedVector(InlinedVector&& other) noexcept(
- absl::allocator_is_nothrow<allocator_type>::value ||
- std::is_nothrow_move_constructible<value_type>::value)
- : allocator_and_tag_(other.allocator_and_tag_) {
- if (other.allocated()) {
- // We can just steal the underlying buffer from the source.
- // That leaves the source empty, so we clear its size.
- init_allocation(other.allocation());
- other.tag() = Tag();
- } else {
- UninitializedCopy(
- std::make_move_iterator(other.inlined_space()),
- std::make_move_iterator(other.inlined_space() + other.size()),
- inlined_space());
- }
-}
-
-template <typename T, size_t N, typename A>
-InlinedVector<T, N, A>::InlinedVector(InlinedVector&& other,
- const allocator_type& alloc) noexcept( //
- absl::allocator_is_nothrow<allocator_type>::value)
- : allocator_and_tag_(alloc) {
- if (other.allocated()) {
- if (alloc == other.allocator()) {
- // We can just steal the allocation from the source.
- tag() = other.tag();
- init_allocation(other.allocation());
- other.tag() = Tag();
- } else {
- // We need to use our own allocator
- reserve(other.size());
- UninitializedCopy(std::make_move_iterator(other.begin()),
- std::make_move_iterator(other.end()),
- allocated_space());
- tag().set_allocated_size(other.size());
- }
- } else {
- UninitializedCopy(
- std::make_move_iterator(other.inlined_space()),
- std::make_move_iterator(other.inlined_space() + other.size()),
- inlined_space());
- tag().set_inline_size(other.size());
- }
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::InitAssign(size_type n, const_reference v) {
- if (n > inlined_capacity()) {
- Allocation new_allocation(allocator(), n);
- init_allocation(new_allocation);
- UninitializedFill(allocated_space(), allocated_space() + n, v);
- tag().set_allocated_size(n);
- } else {
- UninitializedFill(inlined_space(), inlined_space() + n, v);
- tag().set_inline_size(n);
- }
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::InitAssign(size_type n) {
- if (n > inlined_capacity()) {
- Allocation new_allocation(allocator(), n);
- init_allocation(new_allocation);
- UninitializedFill(allocated_space(), allocated_space() + n);
- tag().set_allocated_size(n);
- } else {
- UninitializedFill(inlined_space(), inlined_space() + n);
- tag().set_inline_size(n);
- }
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::resize(size_type n) {
- size_type s = size();
- if (n < s) {
- erase(begin() + n, end());
- return;
- }
- reserve(n);
- assert(capacity() >= n);
-
- // Fill new space with elements constructed in-place.
- if (allocated()) {
- UninitializedFill(allocated_space() + s, allocated_space() + n);
- tag().set_allocated_size(n);
- } else {
- UninitializedFill(inlined_space() + s, inlined_space() + n);
- tag().set_inline_size(n);
- }
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::resize(size_type n, const_reference v) {
- size_type s = size();
- if (n < s) {
- erase(begin() + n, end());
- return;
- }
- reserve(n);
- assert(capacity() >= n);
-
- // Fill new space with copies of 'v'.
- if (allocated()) {
- UninitializedFill(allocated_space() + s, allocated_space() + n, v);
- tag().set_allocated_size(n);
- } else {
- UninitializedFill(inlined_space() + s, inlined_space() + n, v);
- tag().set_inline_size(n);
- }
-}
-
-template <typename T, size_t N, typename A>
-template <typename... Args>
-auto InlinedVector<T, N, A>::emplace(const_iterator position, Args&&... args)
- -> iterator {
- assert(position >= begin());
- assert(position <= end());
- if (ABSL_PREDICT_FALSE(position == end())) {
- emplace_back(std::forward<Args>(args)...);
- return end() - 1;
- }
-
- T new_t = T(std::forward<Args>(args)...);
-
- auto range = ShiftRight(position, 1);
- if (range.first == range.second) {
- // constructing into uninitialized memory
- Construct(range.first, std::move(new_t));
- } else {
- // assigning into moved-from object
- *range.first = T(std::move(new_t));
- }
-
- return range.first;
-}
-
-template <typename T, size_t N, typename A>
-auto InlinedVector<T, N, A>::erase(const_iterator from, const_iterator to)
- -> iterator {
- assert(begin() <= from);
- assert(from <= to);
- assert(to <= end());
-
- iterator range_start = const_cast<iterator>(from);
- iterator range_end = const_cast<iterator>(to);
-
- size_type s = size();
- ptrdiff_t erase_gap = std::distance(range_start, range_end);
- if (erase_gap > 0) {
- pointer space;
- if (allocated()) {
- space = allocated_space();
- tag().set_allocated_size(s - erase_gap);
- } else {
- space = inlined_space();
- tag().set_inline_size(s - erase_gap);
- }
- std::move(range_end, space + s, range_start);
- Destroy(space + s - erase_gap, space + s);
- }
- return range_start;
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::swap(InlinedVector& other) {
- using std::swap; // Augment ADL with `std::swap`.
- if (ABSL_PREDICT_FALSE(this == &other)) return;
-
- if (allocated() && other.allocated()) {
- // Both out of line, so just swap the tag, allocation, and allocator.
- swap(tag(), other.tag());
- swap(allocation(), other.allocation());
- swap(allocator(), other.allocator());
- return;
- }
- if (!allocated() && !other.allocated()) {
- // Both inlined: swap up to smaller size, then move remaining elements.
- InlinedVector* a = this;
- InlinedVector* b = &other;
- if (size() < other.size()) {
- swap(a, b);
- }
-
- const size_type a_size = a->size();
- const size_type b_size = b->size();
- assert(a_size >= b_size);
- // `a` is larger. Swap the elements up to the smaller array size.
- std::swap_ranges(a->inlined_space(), a->inlined_space() + b_size,
- b->inlined_space());
-
- // Move the remaining elements:
- // [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b`
- b->UninitializedCopy(a->inlined_space() + b_size,
- a->inlined_space() + a_size,
- b->inlined_space() + b_size);
- a->Destroy(a->inlined_space() + b_size, a->inlined_space() + a_size);
-
- swap(a->tag(), b->tag());
- swap(a->allocator(), b->allocator());
- assert(b->size() == a_size);
- assert(a->size() == b_size);
- return;
- }
-
- // One is out of line, one is inline.
- // We first move the elements from the inlined vector into the
- // inlined space in the other vector. We then put the other vector's
- // pointer/capacity into the originally inlined vector and swap
- // the tags.
- InlinedVector* a = this;
- InlinedVector* b = &other;
- if (a->allocated()) {
- swap(a, b);
- }
- assert(!a->allocated());
- assert(b->allocated());
- const size_type a_size = a->size();
- const size_type b_size = b->size();
- // In an optimized build, `b_size` would be unused.
- static_cast<void>(b_size);
-
- // Made Local copies of `size()`, don't need `tag()` accurate anymore
- swap(a->tag(), b->tag());
-
- // Copy `b_allocation` out before `b`'s union gets clobbered by `inline_space`
- Allocation b_allocation = b->allocation();
-
- b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size,
- b->inlined_space());
- a->Destroy(a->inlined_space(), a->inlined_space() + a_size);
-
- a->allocation() = b_allocation;
-
- if (a->allocator() != b->allocator()) {
- swap(a->allocator(), b->allocator());
- }
-
- assert(b->size() == a_size);
- assert(a->size() == b_size);
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::EnlargeBy(size_type delta) {
- const size_type s = size();
- assert(s <= capacity());
-
- size_type target = std::max(inlined_capacity(), s + delta);
-
- // Compute new capacity by repeatedly doubling current capacity
- // TODO(psrc): Check and avoid overflow?
- size_type new_capacity = capacity();
- while (new_capacity < target) {
- new_capacity <<= 1;
- }
-
- Allocation new_allocation(allocator(), new_capacity);
-
- UninitializedCopy(std::make_move_iterator(data()),
- std::make_move_iterator(data() + s),
- new_allocation.buffer());
-
- ResetAllocation(new_allocation, s);
-}
-
-template <typename T, size_t N, typename A>
-auto InlinedVector<T, N, A>::ShiftRight(const_iterator position, size_type n)
- -> std::pair<iterator, iterator> {
- iterator start_used = const_cast<iterator>(position);
- iterator start_raw = const_cast<iterator>(position);
- size_type s = size();
- size_type required_size = s + n;
-
- if (required_size > capacity()) {
- // Compute new capacity by repeatedly doubling current capacity
- size_type new_capacity = capacity();
- while (new_capacity < required_size) {
- new_capacity <<= 1;
- }
- // Move everyone into the new allocation, leaving a gap of `n` for the
- // requested shift.
- Allocation new_allocation(allocator(), new_capacity);
- size_type index = position - begin();
- UninitializedCopy(std::make_move_iterator(data()),
- std::make_move_iterator(data() + index),
- new_allocation.buffer());
- UninitializedCopy(std::make_move_iterator(data() + index),
- std::make_move_iterator(data() + s),
- new_allocation.buffer() + index + n);
- ResetAllocation(new_allocation, s);
-
- // New allocation means our iterator is invalid, so we'll recalculate.
- // Since the entire gap is in new space, there's no used space to reuse.
- start_raw = begin() + index;
- start_used = start_raw;
- } else {
- // If we had enough space, it's a two-part move. Elements going into
- // previously-unoccupied space need an `UninitializedCopy()`. Elements
- // going into a previously-occupied space are just a `std::move()`.
- iterator pos = const_cast<iterator>(position);
- iterator raw_space = end();
- size_type slots_in_used_space = raw_space - pos;
- size_type new_elements_in_used_space = std::min(n, slots_in_used_space);
- size_type new_elements_in_raw_space = n - new_elements_in_used_space;
- size_type old_elements_in_used_space =
- slots_in_used_space - new_elements_in_used_space;
-
- UninitializedCopy(std::make_move_iterator(pos + old_elements_in_used_space),
- std::make_move_iterator(raw_space),
- raw_space + new_elements_in_raw_space);
- std::move_backward(pos, pos + old_elements_in_used_space, raw_space);
-
- // If the gap is entirely in raw space, the used space starts where the raw
- // space starts, leaving no elements in used space. If the gap is entirely
- // in used space, the raw space starts at the end of the gap, leaving all
- // elements accounted for within the used space.
- start_used = pos;
- start_raw = pos + new_elements_in_used_space;
- }
- tag().add_size(n);
- return std::make_pair(start_used, start_raw);
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::Destroy(pointer from, pointer to) {
- for (pointer cur = from; cur != to; ++cur) {
- std::allocator_traits<allocator_type>::destroy(allocator(), cur);
- }
-#ifndef NDEBUG
- // Overwrite unused memory with `0xab` so we can catch uninitialized usage.
- // Cast to `void*` to tell the compiler that we don't care that we might be
- // scribbling on a vtable pointer.
- if (from != to) {
- auto len = sizeof(value_type) * std::distance(from, to);
- std::memset(reinterpret_cast<void*>(from), 0xab, len);
- }
-#endif
-}
-
-template <typename T, size_t N, typename A>
-template <typename Iterator>
-void InlinedVector<T, N, A>::AppendRange(Iterator first, Iterator last,
- std::forward_iterator_tag) {
- auto length = std::distance(first, last);
- reserve(size() + length);
- if (allocated()) {
- UninitializedCopy(first, last, allocated_space() + size());
- tag().set_allocated_size(size() + length);
- } else {
- UninitializedCopy(first, last, inlined_space() + size());
- tag().set_inline_size(size() + length);
- }
-}
-
-template <typename T, size_t N, typename A>
-template <typename Iterator>
-void InlinedVector<T, N, A>::AssignRange(Iterator first, Iterator last,
- std::input_iterator_tag) {
- // Optimized to avoid reallocation.
- // Prefer reassignment to copy construction for elements.
- iterator out = begin();
- for (; first != last && out != end(); ++first, ++out) {
- *out = *first;
- }
- erase(out, end());
- std::copy(first, last, std::back_inserter(*this));
-}
-
-template <typename T, size_t N, typename A>
-template <typename Iterator>
-void InlinedVector<T, N, A>::AssignRange(Iterator first, Iterator last,
- std::forward_iterator_tag) {
- auto length = std::distance(first, last);
- // Prefer reassignment to copy construction for elements.
- if (static_cast<size_type>(length) <= size()) {
- erase(std::copy(first, last, begin()), end());
- return;
- }
- reserve(length);
- iterator out = begin();
- for (; out != end(); ++first, ++out) *out = *first;
- if (allocated()) {
- UninitializedCopy(first, last, out);
- tag().set_allocated_size(length);
- } else {
- UninitializedCopy(first, last, out);
- tag().set_inline_size(length);
- }
-}
-
-template <typename T, size_t N, typename A>
-auto InlinedVector<T, N, A>::InsertWithCount(const_iterator position,
- size_type n, const_reference v)
- -> iterator {
- assert(position >= begin() && position <= end());
- if (ABSL_PREDICT_FALSE(n == 0)) return const_cast<iterator>(position);
-
- value_type copy = v;
- std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
- std::fill(it_pair.first, it_pair.second, copy);
- UninitializedFill(it_pair.second, it_pair.first + n, copy);
-
- return it_pair.first;
-}
-
-template <typename T, size_t N, typename A>
-template <typename InputIterator>
-auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position,
- InputIterator first,
- InputIterator last,
- std::input_iterator_tag)
- -> iterator {
- assert(position >= begin() && position <= end());
- size_type index = position - cbegin();
- size_type i = index;
- while (first != last) insert(begin() + i++, *first++);
- return begin() + index;
-}
-
-template <typename T, size_t N, typename A>
-template <typename ForwardIterator>
-auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position,
- ForwardIterator first,
- ForwardIterator last,
- std::forward_iterator_tag)
- -> iterator {
- assert(position >= begin() && position <= end());
- if (ABSL_PREDICT_FALSE(first == last)) return const_cast<iterator>(position);
-
- auto n = std::distance(first, last);
- std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
- size_type used_spots = it_pair.second - it_pair.first;
- ForwardIterator open_spot = std::next(first, used_spots);
- std::copy(first, open_spot, it_pair.first);
- UninitializedCopy(open_spot, last, it_pair.second);
- return it_pair.first;
-}
-
} // namespace absl
#endif // ABSL_CONTAINER_INLINED_VECTOR_H_
diff --git a/absl/container/internal/compressed_tuple.h b/absl/container/internal/compressed_tuple.h
index cc52614f..b883ae26 100644
--- a/absl/container/internal/compressed_tuple.h
+++ b/absl/container/internal/compressed_tuple.h
@@ -89,8 +89,10 @@ struct Storage {
T value;
constexpr Storage() = default;
explicit constexpr Storage(T&& v) : value(absl::forward<T>(v)) {}
- constexpr const T& get() const { return value; }
- T& get() { return value; }
+ constexpr const T& get() const& { return value; }
+ T& get() & { return value; }
+ constexpr const T&& get() const&& { return absl::move(*this).value; }
+ T&& get() && { return std::move(*this).value; }
};
template <typename D, size_t I>
@@ -99,8 +101,10 @@ struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC Storage<D, I, true>
using T = internal_compressed_tuple::ElemT<D, I>;
constexpr Storage() = default;
explicit constexpr Storage(T&& v) : T(absl::forward<T>(v)) {}
- constexpr const T& get() const { return *this; }
- T& get() { return *this; }
+ constexpr const T& get() const& { return *this; }
+ T& get() & { return *this; }
+ constexpr const T&& get() const&& { return absl::move(*this); }
+ T&& get() && { return std::move(*this); }
};
template <typename D, typename I>
@@ -152,14 +156,26 @@ class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple
: CompressedTuple::CompressedTupleImpl(absl::forward<Ts>(base)...) {}
template <int I>
- ElemT<I>& get() {
+ ElemT<I>& get() & {
return internal_compressed_tuple::Storage<CompressedTuple, I>::get();
}
template <int I>
- constexpr const ElemT<I>& get() const {
+ constexpr const ElemT<I>& get() const& {
return internal_compressed_tuple::Storage<CompressedTuple, I>::get();
}
+
+ template <int I>
+ ElemT<I>&& get() && {
+ return std::move(*this)
+ .internal_compressed_tuple::template Storage<CompressedTuple, I>::get();
+ }
+
+ template <int I>
+ constexpr const ElemT<I>&& get() const&& {
+ return absl::move(*this)
+ .internal_compressed_tuple::template Storage<CompressedTuple, I>::get();
+ }
};
// Explicit specialization for a zero-element tuple
diff --git a/absl/container/internal/compressed_tuple_test.cc b/absl/container/internal/compressed_tuple_test.cc
index 45030c67..04ead100 100644
--- a/absl/container/internal/compressed_tuple_test.cc
+++ b/absl/container/internal/compressed_tuple_test.cc
@@ -14,17 +14,25 @@
#include "absl/container/internal/compressed_tuple.h"
+#include <memory>
#include <string>
#include "gmock/gmock.h"
#include "gtest/gtest.h"
+#include "absl/memory/memory.h"
+#include "absl/utility/utility.h"
namespace absl {
namespace container_internal {
namespace {
+enum class CallType { kConstRef, kConstMove };
+
template <int>
-struct Empty {};
+struct Empty {
+ constexpr CallType value() const& { return CallType::kConstRef; }
+ constexpr CallType value() const&& { return CallType::kConstMove; }
+};
template <typename T>
struct NotEmpty {
@@ -140,15 +148,44 @@ TEST(CompressedTupleTest, NoElements) {
EXPECT_TRUE(std::is_empty<CompressedTuple<>>::value);
}
+TEST(CompressedTupleTest, MoveOnlyElements) {
+ CompressedTuple<std::unique_ptr<std::string>> str_tup(
+ absl::make_unique<std::string>("str"));
+
+ CompressedTuple<CompressedTuple<std::unique_ptr<std::string>>,
+ std::unique_ptr<int>>
+ x(std::move(str_tup), absl::make_unique<int>(5));
+
+ EXPECT_EQ(*x.get<0>().get<0>(), "str");
+ EXPECT_EQ(*x.get<1>(), 5);
+
+ std::unique_ptr<std::string> x0 = std::move(x.get<0>()).get<0>();
+ std::unique_ptr<int> x1 = std::move(x).get<1>();
+
+ EXPECT_EQ(*x0, "str");
+ EXPECT_EQ(*x1, 5);
+}
+
TEST(CompressedTupleTest, Constexpr) {
- constexpr CompressedTuple<int, double, CompressedTuple<int>> x(
- 7, 1.25, CompressedTuple<int>(5));
+ constexpr CompressedTuple<int, double, CompressedTuple<int>, Empty<0>> x(
+ 7, 1.25, CompressedTuple<int>(5), {});
constexpr int x0 = x.get<0>();
constexpr double x1 = x.get<1>();
constexpr int x2 = x.get<2>().get<0>();
+ constexpr CallType x3 = x.get<3>().value();
+
EXPECT_EQ(x0, 7);
EXPECT_EQ(x1, 1.25);
EXPECT_EQ(x2, 5);
+ EXPECT_EQ(x3, CallType::kConstRef);
+
+#if defined(__clang__)
+ // An apparent bug in earlier versions of gcc claims these are ambiguous.
+ constexpr int x2m = absl::move(x.get<2>()).get<0>();
+ constexpr CallType x3m = absl::move(x).get<3>().value();
+ EXPECT_EQ(x2m, 5);
+ EXPECT_EQ(x3m, CallType::kConstMove);
+#endif
}
#if defined(__clang__) || defined(__GNUC__)
diff --git a/absl/container/internal/hashtable_debug.h b/absl/container/internal/hashtable_debug.h
index c3bd65c9..38050c69 100644
--- a/absl/container/internal/hashtable_debug.h
+++ b/absl/container/internal/hashtable_debug.h
@@ -60,7 +60,7 @@ std::vector<size_t> GetHashtableDebugNumProbesHistogram(const C& container) {
size_t num_probes = GetHashtableDebugNumProbes(
container,
absl::container_internal::hashtable_debug_internal::GetKey<C>(*it, 0));
- v.resize(std::max(v.size(), num_probes + 1));
+ v.resize((std::max)(v.size(), num_probes + 1));
v[num_probes]++;
}
return v;
diff --git a/absl/container/internal/have_sse.h b/absl/container/internal/have_sse.h
new file mode 100644
index 00000000..29347889
--- /dev/null
+++ b/absl/container/internal/have_sse.h
@@ -0,0 +1,49 @@
+// Copyright 2018 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
+//
+// http://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.
+//
+// Shared config probing for SSE instructions used in Swiss tables.
+#ifndef ABSL_CONTAINER_INTERNAL_HAVE_SSE_H_
+#define ABSL_CONTAINER_INTERNAL_HAVE_SSE_H_
+
+#ifndef SWISSTABLE_HAVE_SSE2
+#if defined(__SSE2__) || \
+ (defined(_MSC_VER) && \
+ (defined(_M_X64) || (defined(_M_IX86) && _M_IX86_FP >= 2)))
+#define SWISSTABLE_HAVE_SSE2 1
+#else
+#define SWISSTABLE_HAVE_SSE2 0
+#endif
+#endif
+
+#ifndef SWISSTABLE_HAVE_SSSE3
+#ifdef __SSSE3__
+#define SWISSTABLE_HAVE_SSSE3 1
+#else
+#define SWISSTABLE_HAVE_SSSE3 0
+#endif
+#endif
+
+#if SWISSTABLE_HAVE_SSSE3 && !SWISSTABLE_HAVE_SSE2
+#error "Bad configuration!"
+#endif
+
+#if SWISSTABLE_HAVE_SSE2
+#include <emmintrin.h>
+#endif
+
+#if SWISSTABLE_HAVE_SSSE3
+#include <tmmintrin.h>
+#endif
+
+#endif // ABSL_CONTAINER_INTERNAL_HAVE_SSE_H_
diff --git a/absl/container/internal/layout.h b/absl/container/internal/layout.h
index a9c1244a..3d21ac96 100644
--- a/absl/container/internal/layout.h
+++ b/absl/container/internal/layout.h
@@ -253,8 +253,10 @@ template <class From, class To>
using CopyConst =
typename std::conditional<std::is_const<From>::value, const To, To>::type;
+// Note: We're not qualifying this with absl:: because it doesn't compile under
+// MSVC.
template <class T>
-using SliceType = absl::Span<T>;
+using SliceType = Span<T>;
// This namespace contains no types. It prevents functions defined in it from
// being found by ADL.
diff --git a/absl/container/internal/layout_test.cc b/absl/container/internal/layout_test.cc
index 224f741a..301e9f78 100644
--- a/absl/container/internal/layout_test.cc
+++ b/absl/container/internal/layout_test.cc
@@ -45,7 +45,7 @@ Expected Type(Actual val) {
return val;
}
-// Helper class to test different size and alignments.
+// Helper classes to test different size and alignments.
struct alignas(8) Int128 {
uint64_t a, b;
friend bool operator==(Int128 lhs, Int128 rhs) {
@@ -57,6 +57,14 @@ struct alignas(8) Int128 {
}
};
+// int64_t is *not* 8-byte aligned on all platforms!
+struct alignas(8) Int64 {
+ int64_t a;
+ friend bool operator==(Int64 lhs, Int64 rhs) {
+ return lhs.a == rhs.a;
+ }
+};
+
// Properties of types that this test relies on.
static_assert(sizeof(int8_t) == 1, "");
static_assert(alignof(int8_t) == 1, "");
@@ -64,6 +72,8 @@ static_assert(sizeof(int16_t) == 2, "");
static_assert(alignof(int16_t) == 2, "");
static_assert(sizeof(int32_t) == 4, "");
static_assert(alignof(int32_t) == 4, "");
+static_assert(sizeof(Int64) == 8, "");
+static_assert(alignof(Int64) == 8, "");
static_assert(sizeof(Int128) == 16, "");
static_assert(alignof(Int128) == 8, "");
@@ -1281,14 +1291,14 @@ TEST(Layout, OverAligned) {
TEST(Layout, Alignment) {
static_assert(Layout<int8_t>::Alignment() == 1, "");
static_assert(Layout<int32_t>::Alignment() == 4, "");
- static_assert(Layout<int64_t>::Alignment() == 8, "");
+ static_assert(Layout<Int64>::Alignment() == 8, "");
static_assert(Layout<Aligned<int8_t, 64>>::Alignment() == 64, "");
- static_assert(Layout<int8_t, int32_t, int64_t>::Alignment() == 8, "");
- static_assert(Layout<int8_t, int64_t, int32_t>::Alignment() == 8, "");
- static_assert(Layout<int32_t, int8_t, int64_t>::Alignment() == 8, "");
- static_assert(Layout<int32_t, int64_t, int8_t>::Alignment() == 8, "");
- static_assert(Layout<int64_t, int8_t, int32_t>::Alignment() == 8, "");
- static_assert(Layout<int64_t, int32_t, int8_t>::Alignment() == 8, "");
+ static_assert(Layout<int8_t, int32_t, Int64>::Alignment() == 8, "");
+ static_assert(Layout<int8_t, Int64, int32_t>::Alignment() == 8, "");
+ static_assert(Layout<int32_t, int8_t, Int64>::Alignment() == 8, "");
+ static_assert(Layout<int32_t, Int64, int8_t>::Alignment() == 8, "");
+ static_assert(Layout<Int64, int8_t, int32_t>::Alignment() == 8, "");
+ static_assert(Layout<Int64, int32_t, int8_t>::Alignment() == 8, "");
}
TEST(Layout, ConstexprPartial) {
@@ -1323,7 +1333,7 @@ void ExpectPoisoned(const unsigned char (&buf)[N],
}
TEST(Layout, PoisonPadding) {
- using L = Layout<int8_t, int64_t, int32_t, Int128>;
+ using L = Layout<int8_t, Int64, int32_t, Int128>;
constexpr size_t n = L::Partial(1, 2, 3, 4).AllocSize();
{
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc
index 10153129..180d3fe5 100644
--- a/absl/container/internal/raw_hash_set.cc
+++ b/absl/container/internal/raw_hash_set.cc
@@ -14,6 +14,7 @@
#include "absl/container/internal/raw_hash_set.h"
+#include <atomic>
#include <cstddef>
#include "absl/base/config.h"
@@ -29,7 +30,7 @@ inline size_t RandomSeed() {
static thread_local size_t counter = 0;
size_t value = ++counter;
#else // ABSL_HAVE_THREAD_LOCAL
- static std::atomic<size_t> counter;
+ static std::atomic<size_t> counter(0);
size_t value = counter.fetch_add(1, std::memory_order_relaxed);
#endif // ABSL_HAVE_THREAD_LOCAL
return value ^ static_cast<size_t>(reinterpret_cast<uintptr_t>(&counter));
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 575f1b00..b7b5ef8c 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -91,36 +91,6 @@
#ifndef ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_
#define ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_
-#ifndef SWISSTABLE_HAVE_SSE2
-#if defined(__SSE2__) || \
- (defined(_MSC_VER) && \
- (defined(_M_X64) || (defined(_M_IX86) && _M_IX86_FP >= 2)))
-#define SWISSTABLE_HAVE_SSE2 1
-#else
-#define SWISSTABLE_HAVE_SSE2 0
-#endif
-#endif
-
-#ifndef SWISSTABLE_HAVE_SSSE3
-#ifdef __SSSE3__
-#define SWISSTABLE_HAVE_SSSE3 1
-#else
-#define SWISSTABLE_HAVE_SSSE3 0
-#endif
-#endif
-
-#if SWISSTABLE_HAVE_SSSE3 && !SWISSTABLE_HAVE_SSE2
-#error "Bad configuration!"
-#endif
-
-#if SWISSTABLE_HAVE_SSE2
-#include <emmintrin.h>
-#endif
-
-#if SWISSTABLE_HAVE_SSSE3
-#include <tmmintrin.h>
-#endif
-
#include <algorithm>
#include <cmath>
#include <cstdint>
@@ -139,6 +109,7 @@
#include "absl/container/internal/container_memory.h"
#include "absl/container/internal/hash_policy_traits.h"
#include "absl/container/internal/hashtable_debug_hooks.h"
+#include "absl/container/internal/have_sse.h"
#include "absl/container/internal/layout.h"
#include "absl/memory/memory.h"
#include "absl/meta/type_traits.h"
@@ -1363,7 +1334,7 @@ class raw_hash_set {
void rehash(size_t n) {
if (n == 0 && capacity_ == 0) return;
if (n == 0 && size_ == 0) return destroy_slots();
- auto m = NormalizeCapacity(std::max(n, NumSlotsFast(size())));
+ auto m = NormalizeCapacity((std::max)(n, NumSlotsFast(size())));
// n == 0 unconditionally rehashes as per the standard.
if (n == 0 || m > capacity_) {
resize(m);
diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h
index e4034461..843b11aa 100644
--- a/absl/container/node_hash_set.h
+++ b/absl/container/node_hash_set.h
@@ -273,8 +273,7 @@ class node_hash_set
//
// The element may be constructed even if there already is an element with the
// key in the container, in which case the newly constructed element will be
- // destroyed immediately. Prefer `try_emplace()` unless your key is not
- // copyable or moveable.
+ // destroyed immediately.
//
// If rehashing occurs due to the insertion, all iterators are invalidated.
using Base::emplace;
@@ -288,8 +287,7 @@ class node_hash_set
//
// The element may be constructed even if there already is an element with the
// key in the container, in which case the newly constructed element will be
- // destroyed immediately. Prefer `try_emplace()` unless your key is not
- // copyable or moveable.
+ // destroyed immediately.
//
// If rehashing occurs due to the insertion, all iterators are invalidated.
using Base::emplace_hint;
generated by cgit v1.2.3 (git 2.39.1) at 2025-06-04 06:19:16 +0000