summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel12
-rw-r--r--absl/container/CMakeLists.txt16
-rw-r--r--absl/container/inlined_vector.h20
-rw-r--r--absl/container/inlined_vector_benchmark.cc74
-rw-r--r--absl/container/inlined_vector_exception_safety_test.cc55
-rw-r--r--absl/container/internal/inlined_vector.h28
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: