summaryrefslogtreecommitdiff
path: root/absl/container/inlined_vector.h
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2019-03-19 11:14:01 -0700
committerGravatar Derek Mauro <dmauro@google.com>2019-03-19 14:19:10 -0400
commitbf29470384a101b307873b26d358433138c857fc (patch)
tree1a8374bafdbfc606b4e70c0f581c3d6b34a08d7d /absl/container/inlined_vector.h
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/inlined_vector.h')
-rw-r--r--absl/container/inlined_vector.h180
1 files changed, 54 insertions, 126 deletions
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_;
};
// -----------------------------------------------------------------------------