diff options
Diffstat (limited to 'absl/container')
-rw-r--r-- | absl/container/BUILD.bazel | 12 | ||||
-rw-r--r-- | absl/container/CMakeLists.txt | 16 | ||||
-rw-r--r-- | absl/container/inlined_vector.h | 20 | ||||
-rw-r--r-- | absl/container/inlined_vector_benchmark.cc | 74 | ||||
-rw-r--r-- | absl/container/inlined_vector_exception_safety_test.cc | 55 | ||||
-rw-r--r-- | absl/container/internal/inlined_vector.h | 28 |
6 files changed, 194 insertions, 11 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 0488857e..99a72482 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -198,11 +198,23 @@ cc_test( deps = [ ":inlined_vector", "//absl/base", + "//absl/base:core_headers", "//absl/strings", "@com_github_google_benchmark//:benchmark_main", ], ) +cc_test( + name = "inlined_vector_exception_safety_test", + srcs = ["inlined_vector_exception_safety_test.cc"], + copts = ABSL_TEST_COPTS + ABSL_EXCEPTIONS_FLAG, + deps = [ + ":inlined_vector", + "//absl/base:exception_safety_testing", + "@com_google_googletest//:gtest_main", + ], +) + cc_library( name = "test_instance_tracker", testonly = 1, diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 1e203dbf..526e37af 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -195,6 +195,22 @@ absl_cc_test( gmock_main ) +absl_cc_test( + NAME + inlined_vector_exception_safety_test + SRCS + "inlined_vector_exception_safety_test.cc" + COPTS + ${ABSL_TEST_COPTS} + ${ABSL_EXCEPTIONS_FLAG} + LINKOPTS + ${ABSL_EXCEPTIONS_FLAG_LINKOPTS} + DEPS + absl::inlined_vector + absl::exception_safety_testing + gmock_main +) + absl_cc_library( NAME test_instance_tracker diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h index 16865272..61e0cfb4 100644 --- a/absl/container/inlined_vector.h +++ b/absl/container/inlined_vector.h @@ -784,16 +784,20 @@ class InlinedVector { // Destroys all elements in the inlined vector, sets the size of `0` and // deallocates the heap allocation if the inlined vector was allocated. void clear() noexcept { - size_type s = size(); - if (storage_.GetIsAllocated()) { - Destroy(storage_.GetAllocatedData(), storage_.GetAllocatedData() + s); - AllocatorTraits::deallocate(storage_.GetAllocator(), - storage_.GetAllocatedData(), + const bool is_allocated = storage_.GetIsAllocated(); + + pointer the_data = + is_allocated ? storage_.GetAllocatedData() : storage_.GetInlinedData(); + + inlined_vector_internal::DestroyElements(storage_.GetAllocator(), the_data, + storage_.GetSize()); + + if (is_allocated) { + AllocatorTraits::deallocate(storage_.GetAllocator(), the_data, storage_.GetAllocatedCapacity()); - } else if (s != 0) { // do nothing for empty vectors - Destroy(storage_.GetInlinedData(), storage_.GetInlinedData() + s); } - storage_.SetInlinedSize(0); + + storage_.SetInlinedSize(/* size = */ 0); } // `InlinedVector::reserve()` diff --git a/absl/container/inlined_vector_benchmark.cc b/absl/container/inlined_vector_benchmark.cc index 867a29ea..7bb3271b 100644 --- a/absl/container/inlined_vector_benchmark.cc +++ b/absl/container/inlined_vector_benchmark.cc @@ -1,4 +1,4 @@ -// Copyright 2017 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. @@ -12,13 +12,13 @@ // See the License for the specific language governing permissions and // limitations under the License. -#include "absl/container/inlined_vector.h" - #include <string> #include <vector> #include "benchmark/benchmark.h" #include "absl/base/internal/raw_logging.h" +#include "absl/base/macros.h" +#include "absl/container/inlined_vector.h" #include "absl/strings/str_cat.h" namespace { @@ -373,4 +373,72 @@ void BM_StdVectorEmpty(benchmark::State& state) { } BENCHMARK(BM_StdVectorEmpty); +constexpr size_t kInlineElements = 4; +constexpr size_t kSmallSize = kInlineElements / 2; +constexpr size_t kLargeSize = kInlineElements * 2; +constexpr size_t kBatchSize = 100; + +struct TrivialType { + size_t val; +}; + +using TrivialVec = absl::InlinedVector<TrivialType, kInlineElements>; + +class NontrivialType { + public: + ABSL_ATTRIBUTE_NOINLINE NontrivialType() : val_() {} + + ABSL_ATTRIBUTE_NOINLINE NontrivialType(const NontrivialType& other) + : val_(other.val_) {} + + ABSL_ATTRIBUTE_NOINLINE NontrivialType& operator=( + const NontrivialType& other) { + val_ = other.val_; + return *this; + } + + ABSL_ATTRIBUTE_NOINLINE ~NontrivialType() noexcept {} + + private: + size_t val_; +}; + +using NontrivialVec = absl::InlinedVector<NontrivialType, kInlineElements>; + +#define BENCHMARK_OPERATION(BM_Function) \ + BENCHMARK_TEMPLATE(BM_Function, TrivialVec, kSmallSize); \ + BENCHMARK_TEMPLATE(BM_Function, TrivialVec, kLargeSize); \ + BENCHMARK_TEMPLATE(BM_Function, NontrivialVec, kSmallSize); \ + BENCHMARK_TEMPLATE(BM_Function, NontrivialVec, kLargeSize) + +template <typename VecT, typename PrepareVec, typename TestVec> +void BatchedBenchmark(benchmark::State& state, PrepareVec prepare_vec, + TestVec test_vec) { + VecT vectors[kBatchSize]; + + while (state.KeepRunningBatch(kBatchSize)) { + // Prepare batch + state.PauseTiming(); + for (auto& vec : vectors) { + prepare_vec(&vec); + } + benchmark::DoNotOptimize(vectors); + state.ResumeTiming(); + + // Test batch + for (auto& vec : vectors) { + test_vec(&vec); + } + } +} + +template <typename VecT, size_t Size> +void BM_Clear(benchmark::State& state) { + BatchedBenchmark<VecT>( + state, + /* prepare_vec = */ [](VecT* vec) { vec->resize(Size); }, + /* test_vec = */ [](VecT* vec) { vec->clear(); }); +} +BENCHMARK_OPERATION(BM_Clear); + } // namespace diff --git a/absl/container/inlined_vector_exception_safety_test.cc b/absl/container/inlined_vector_exception_safety_test.cc new file mode 100644 index 00000000..0af048b1 --- /dev/null +++ b/absl/container/inlined_vector_exception_safety_test.cc @@ -0,0 +1,55 @@ +// 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. + +#include <memory> + +#include "gtest/gtest.h" +#include "absl/base/internal/exception_safety_testing.h" +#include "absl/container/inlined_vector.h" + +namespace { + +constexpr size_t kInlined = 4; +constexpr size_t kSmallSize = kInlined / 2; +constexpr size_t kLargeSize = kInlined * 2; + +using Thrower = testing::ThrowingValue<>; +using ThrowerAlloc = testing::ThrowingAllocator<Thrower>; + +template <typename Allocator = std::allocator<Thrower>> +using InlVec = absl::InlinedVector<Thrower, kInlined, Allocator>; + +TEST(InlinedVector, DefaultConstructor) { + testing::TestThrowingCtor<InlVec<>>(); + + testing::TestThrowingCtor<InlVec<ThrowerAlloc>>(); +} + +TEST(InlinedVector, AllocConstructor) { + auto alloc = std::allocator<Thrower>(); + testing::TestThrowingCtor<InlVec<>>(alloc); + + auto throw_alloc = ThrowerAlloc(); + testing::TestThrowingCtor<InlVec<ThrowerAlloc>>(throw_alloc); +} + +TEST(InlinedVector, Clear) { + auto small_vec = InlVec<>(kSmallSize); + EXPECT_TRUE(testing::TestNothrowOp([&]() { small_vec.clear(); })); + + auto large_vec = InlVec<>(kLargeSize); + EXPECT_TRUE(testing::TestNothrowOp([&]() { large_vec.clear(); })); +} + +} // namespace diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h index 6a5a75be..4589ce08 100644 --- a/absl/container/internal/inlined_vector.h +++ b/absl/container/internal/inlined_vector.h @@ -16,6 +16,7 @@ #define ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_ #include <cstddef> +#include <cstring> #include <iterator> #include <memory> #include <utility> @@ -31,6 +32,33 @@ using IsAtLeastForwardIterator = std::is_convertible< typename std::iterator_traits<Iterator>::iterator_category, std::forward_iterator_tag>; +template <typename AllocatorType, typename ValueType, typename SizeType> +void DestroyElements(AllocatorType alloc, ValueType* destroy_first, + SizeType destroy_size) { + using AllocatorTraits = std::allocator_traits<AllocatorType>; + + // Destroys `destroy_size` elements from `destroy_first`. + // + // Destroys the range + // [`destroy_first`, `destroy_first + destroy_size`). + // + // NOTE: We assume destructors do not throw and thus make no attempt to roll + // back. + for (SizeType i = 0; i < destroy_size; ++i) { + AllocatorTraits::destroy(alloc, destroy_first + i); + } + +#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. + void* memory = reinterpret_cast<void*>(destroy_first); + size_t memory_size = sizeof(ValueType) * destroy_size; + std::memset(memory, 0xab, memory_size); +#endif // NDEBUG +} + template <typename T, size_t N, typename A> class Storage { public: |