container/internal/test_allocator.h

0001 // Copyright 2018 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014
0015 #ifndef ABSL_CONTAINER_INTERNAL_TEST_ALLOCATOR_H_
0016 #define ABSL_CONTAINER_INTERNAL_TEST_ALLOCATOR_H_
0017
0018 #include <cassert>
0019 #include <cstddef>
0020 #include <cstdint>
0021 #include <memory>
0022 #include <type_traits>
0023
0024 #include "gtest/gtest.h"
0025 #include "absl/base/config.h"
0026
0027 namespace absl {
0028 ABSL_NAMESPACE_BEGIN
0029 namespace container_internal {
0030
0031 // This is a stateful allocator, but the state lives outside of the
0032 // allocator (in whatever test is using the allocator). This is odd
0033 // but helps in tests where the allocator is propagated into nested
0034 // containers - that chain of allocators uses the same state and is
0035 // thus easier to query for aggregate allocation information.
0036 template <typename T>
0037 class CountingAllocator {
0038  public:
0039   using Allocator = std::allocator<T>;
0040   using AllocatorTraits = std::allocator_traits<Allocator>;
0041   using value_type = typename AllocatorTraits::value_type;
0042   using pointer = typename AllocatorTraits::pointer;
0043   using const_pointer = typename AllocatorTraits::const_pointer;
0044   using size_type = typename AllocatorTraits::size_type;
0045   using difference_type = typename AllocatorTraits::difference_type;
0046
0047   CountingAllocator() = default;
0048   explicit CountingAllocator(int64_t* bytes_used) : bytes_used_(bytes_used) {}
0049   CountingAllocator(int64_t* bytes_used, int64_t* instance_count)
0050       : bytes_used_(bytes_used), instance_count_(instance_count) {}
0051
0052   template <typename U>
0053   CountingAllocator(const CountingAllocator<U>& x)
0054       : bytes_used_(x.bytes_used_), instance_count_(x.instance_count_) {}
0055
0056   pointer allocate(
0057       size_type n,
0058       typename AllocatorTraits::const_void_pointer hint = nullptr) {
0059     Allocator allocator;
0060     pointer ptr = AllocatorTraits::allocate(allocator, n, hint);
0061     if (bytes_used_ != nullptr) {
0062       *bytes_used_ += n * sizeof(T);
0063     }
0064     return ptr;
0065   }
0066
0067   void deallocate(pointer p, size_type n) {
0068     Allocator allocator;
0069     AllocatorTraits::deallocate(allocator, p, n);
0070     if (bytes_used_ != nullptr) {
0071       *bytes_used_ -= n * sizeof(T);
0072     }
0073   }
0074
0075   template <typename U, typename... Args>
0076   void construct(U* p, Args&&... args) {
0077     Allocator allocator;
0078     AllocatorTraits::construct(allocator, p, std::forward<Args>(args)...);
0079     if (instance_count_ != nullptr) {
0080       *instance_count_ += 1;
0081     }
0082   }
0083
0084   template <typename U>
0085   void destroy(U* p) {
0086     Allocator allocator;
0087     // Ignore GCC warning bug.
0088 #if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0)
0089 #pragma GCC diagnostic push
0090 #pragma GCC diagnostic ignored "-Wuse-after-free"
0091 #endif
0092     AllocatorTraits::destroy(allocator, p);
0093 #if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0)
0094 #pragma GCC diagnostic pop
0095 #endif
0096     if (instance_count_ != nullptr) {
0097       *instance_count_ -= 1;
0098     }
0099   }
0100
0101   template <typename U>
0102   class rebind {
0103    public:
0104     using other = CountingAllocator<U>;
0105   };
0106
0107   friend bool operator==(const CountingAllocator& a,
0108                          const CountingAllocator& b) {
0109     return a.bytes_used_ == b.bytes_used_ &&
0110            a.instance_count_ == b.instance_count_;
0111   }
0112
0113   friend bool operator!=(const CountingAllocator& a,
0114                          const CountingAllocator& b) {
0115     return !(a == b);
0116   }
0117
0118   int64_t* bytes_used_ = nullptr;
0119   int64_t* instance_count_ = nullptr;
0120 };
0121
0122 template <typename T>
0123 struct CopyAssignPropagatingCountingAlloc : public CountingAllocator<T> {
0124   using propagate_on_container_copy_assignment = std::true_type;
0125
0126   using Base = CountingAllocator<T>;
0127   using Base::Base;
0128
0129   template <typename U>
0130   explicit CopyAssignPropagatingCountingAlloc(
0131       const CopyAssignPropagatingCountingAlloc<U>& other)
0132       : Base(other.bytes_used_, other.instance_count_) {}
0133
0134   template <typename U>
0135   struct rebind {
0136     using other = CopyAssignPropagatingCountingAlloc<U>;
0137   };
0138 };
0139
0140 template <typename T>
0141 struct MoveAssignPropagatingCountingAlloc : public CountingAllocator<T> {
0142   using propagate_on_container_move_assignment = std::true_type;
0143
0144   using Base = CountingAllocator<T>;
0145   using Base::Base;
0146
0147   template <typename U>
0148   explicit MoveAssignPropagatingCountingAlloc(
0149       const MoveAssignPropagatingCountingAlloc<U>& other)
0150       : Base(other.bytes_used_, other.instance_count_) {}
0151
0152   template <typename U>
0153   struct rebind {
0154     using other = MoveAssignPropagatingCountingAlloc<U>;
0155   };
0156 };
0157
0158 template <typename T>
0159 struct SwapPropagatingCountingAlloc : public CountingAllocator<T> {
0160   using propagate_on_container_swap = std::true_type;
0161
0162   using Base = CountingAllocator<T>;
0163   using Base::Base;
0164
0165   template <typename U>
0166   explicit SwapPropagatingCountingAlloc(
0167       const SwapPropagatingCountingAlloc<U>& other)
0168       : Base(other.bytes_used_, other.instance_count_) {}
0169
0170   template <typename U>
0171   struct rebind {
0172     using other = SwapPropagatingCountingAlloc<U>;
0173   };
0174 };
0175
0176 // Tries to allocate memory at the minimum alignment even when the default
0177 // allocator uses a higher alignment.
0178 template <typename T>
0179 struct MinimumAlignmentAlloc : std::allocator<T> {
0180   MinimumAlignmentAlloc() = default;
0181
0182   template <typename U>
0183   explicit MinimumAlignmentAlloc(const MinimumAlignmentAlloc<U>& /*other*/) {}
0184
0185   template <class U>
0186   struct rebind {
0187     using other = MinimumAlignmentAlloc<U>;
0188   };
0189
0190   T* allocate(size_t n) {
0191     T* ptr = std::allocator<T>::allocate(n + 1);
0192     char* cptr = reinterpret_cast<char*>(ptr);
0193     cptr += alignof(T);
0194     return reinterpret_cast<T*>(cptr);
0195   }
0196
0197   void deallocate(T* ptr, size_t n) {
0198     char* cptr = reinterpret_cast<char*>(ptr);
0199     cptr -= alignof(T);
0200     std::allocator<T>::deallocate(reinterpret_cast<T*>(cptr), n + 1);
0201   }
0202 };
0203
0204 inline bool IsAssertEnabled() {
0205   // Use an assert with side-effects to figure out if they are actually enabled.
0206   bool assert_enabled = false;
0207   assert([&]() {  // NOLINT
0208     assert_enabled = true;
0209     return true;
0210   }());
0211   return assert_enabled;
0212 }
0213
0214 template <template <class Alloc> class Container>
0215 void TestCopyAssignAllocPropagation() {
0216   int64_t bytes1 = 0, instances1 = 0, bytes2 = 0, instances2 = 0;
0217   CopyAssignPropagatingCountingAlloc<int> allocator1(&bytes1, &instances1);
0218   CopyAssignPropagatingCountingAlloc<int> allocator2(&bytes2, &instances2);
0219
0220   // Test propagating allocator_type.
0221   {
0222     Container<CopyAssignPropagatingCountingAlloc<int>> c1(allocator1);
0223     Container<CopyAssignPropagatingCountingAlloc<int>> c2(allocator2);
0224
0225     for (int i = 0; i < 100; ++i) c1.insert(i);
0226
0227     EXPECT_NE(c2.get_allocator(), allocator1);
0228     EXPECT_EQ(instances1, 100);
0229     EXPECT_EQ(instances2, 0);
0230
0231     c2 = c1;
0232
0233     EXPECT_EQ(c2.get_allocator(), allocator1);
0234     EXPECT_EQ(instances1, 200);
0235     EXPECT_EQ(instances2, 0);
0236   }
0237   // Test non-propagating allocator_type with different allocators.
0238   {
0239     Container<CountingAllocator<int>> c1(allocator1), c2(allocator2);
0240
0241     for (int i = 0; i < 100; ++i) c1.insert(i);
0242
0243     EXPECT_EQ(c2.get_allocator(), allocator2);
0244     EXPECT_EQ(instances1, 100);
0245     EXPECT_EQ(instances2, 0);
0246
0247     c2 = c1;
0248
0249     EXPECT_EQ(c2.get_allocator(), allocator2);
0250     EXPECT_EQ(instances1, 100);
0251     EXPECT_EQ(instances2, 100);
0252   }
0253   EXPECT_EQ(bytes1, 0);
0254   EXPECT_EQ(instances1, 0);
0255   EXPECT_EQ(bytes2, 0);
0256   EXPECT_EQ(instances2, 0);
0257 }
0258
0259 template <template <class Alloc> class Container>
0260 void TestMoveAssignAllocPropagation() {
0261   int64_t bytes1 = 0, instances1 = 0, bytes2 = 0, instances2 = 0;
0262   MoveAssignPropagatingCountingAlloc<int> allocator1(&bytes1, &instances1);
0263   MoveAssignPropagatingCountingAlloc<int> allocator2(&bytes2, &instances2);
0264
0265   // Test propagating allocator_type.
0266   {
0267     Container<MoveAssignPropagatingCountingAlloc<int>> c1(allocator1);
0268     Container<MoveAssignPropagatingCountingAlloc<int>> c2(allocator2);
0269
0270     for (int i = 0; i < 100; ++i) c1.insert(i);
0271
0272     EXPECT_NE(c2.get_allocator(), allocator1);
0273     EXPECT_EQ(instances1, 100);
0274     EXPECT_EQ(instances2, 0);
0275
0276     c2 = std::move(c1);
0277
0278     EXPECT_EQ(c2.get_allocator(), allocator1);
0279     EXPECT_EQ(instances1, 100);
0280     EXPECT_EQ(instances2, 0);
0281   }
0282   // Test non-propagating allocator_type with equal allocators.
0283   {
0284     Container<CountingAllocator<int>> c1(allocator1), c2(allocator1);
0285
0286     for (int i = 0; i < 100; ++i) c1.insert(i);
0287
0288     EXPECT_EQ(c2.get_allocator(), allocator1);
0289     EXPECT_EQ(instances1, 100);
0290     EXPECT_EQ(instances2, 0);
0291
0292     c2 = std::move(c1);
0293
0294     EXPECT_EQ(c2.get_allocator(), allocator1);
0295     EXPECT_EQ(instances1, 100);
0296     EXPECT_EQ(instances2, 0);
0297   }
0298   // Test non-propagating allocator_type with different allocators.
0299   {
0300     Container<CountingAllocator<int>> c1(allocator1), c2(allocator2);
0301
0302     for (int i = 0; i < 100; ++i) c1.insert(i);
0303
0304     EXPECT_NE(c2.get_allocator(), allocator1);
0305     EXPECT_EQ(instances1, 100);
0306     EXPECT_EQ(instances2, 0);
0307
0308     c2 = std::move(c1);
0309
0310     EXPECT_EQ(c2.get_allocator(), allocator2);
0311     EXPECT_LE(instances1, 100);  // The values in c1 may or may not have been
0312                                  // destroyed at this point.
0313     EXPECT_EQ(instances2, 100);
0314   }
0315   EXPECT_EQ(bytes1, 0);
0316   EXPECT_EQ(instances1, 0);
0317   EXPECT_EQ(bytes2, 0);
0318   EXPECT_EQ(instances2, 0);
0319 }
0320
0321 template <template <class Alloc> class Container>
0322 void TestSwapAllocPropagation() {
0323   int64_t bytes1 = 0, instances1 = 0, bytes2 = 0, instances2 = 0;
0324   SwapPropagatingCountingAlloc<int> allocator1(&bytes1, &instances1);
0325   SwapPropagatingCountingAlloc<int> allocator2(&bytes2, &instances2);
0326
0327   // Test propagating allocator_type.
0328   {
0329     Container<SwapPropagatingCountingAlloc<int>> c1(allocator1), c2(allocator2);
0330
0331     for (int i = 0; i < 100; ++i) c1.insert(i);
0332
0333     EXPECT_NE(c2.get_allocator(), allocator1);
0334     EXPECT_EQ(instances1, 100);
0335     EXPECT_EQ(instances2, 0);
0336
0337     c2.swap(c1);
0338
0339     EXPECT_EQ(c2.get_allocator(), allocator1);
0340     EXPECT_EQ(instances1, 100);
0341     EXPECT_EQ(instances2, 0);
0342   }
0343   // Test non-propagating allocator_type with equal allocators.
0344   {
0345     Container<CountingAllocator<int>> c1(allocator1), c2(allocator1);
0346
0347     for (int i = 0; i < 100; ++i) c1.insert(i);
0348
0349     EXPECT_EQ(c2.get_allocator(), allocator1);
0350     EXPECT_EQ(instances1, 100);
0351     EXPECT_EQ(instances2, 0);
0352
0353     c2.swap(c1);
0354
0355     EXPECT_EQ(c2.get_allocator(), allocator1);
0356     EXPECT_EQ(instances1, 100);
0357     EXPECT_EQ(instances2, 0);
0358   }
0359   // Test non-propagating allocator_type with different allocators.
0360   {
0361     Container<CountingAllocator<int>> c1(allocator1), c2(allocator2);
0362
0363     for (int i = 0; i < 100; ++i) c1.insert(i);
0364
0365     EXPECT_NE(c1.get_allocator(), c2.get_allocator());
0366     if (IsAssertEnabled()) {
0367       EXPECT_DEATH_IF_SUPPORTED(c2.swap(c1), "");
0368     }
0369   }
0370   EXPECT_EQ(bytes1, 0);
0371   EXPECT_EQ(instances1, 0);
0372   EXPECT_EQ(bytes2, 0);
0373   EXPECT_EQ(instances2, 0);
0374 }
0375
0376 template <template <class Alloc> class Container>
0377 void TestAllocPropagation() {
0378   TestCopyAssignAllocPropagation<Container>();
0379   TestMoveAssignAllocPropagation<Container>();
0380   TestSwapAllocPropagation<Container>();
0381 }
0382
0383 }  // namespace container_internal
0384 ABSL_NAMESPACE_END
0385 }  // namespace absl
0386
0387 #endif  // ABSL_CONTAINER_INTERNAL_TEST_ALLOCATOR_H_