llvm/unittests/Support/ArrayRecyclerTest.cpp

   1 //===--- unittest/Support/ArrayRecyclerTest.cpp ---------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Support/ArrayRecycler.h"
  10 #include "llvm/Support/Allocator.h"
  11 #include "gtest/gtest.h"
  12 #include <cstdlib>
  13
  14 using namespace llvm;
  15
  16 namespace {
  17
  18 struct Object {
  19   int Num;
  20   Object *Other;
  21 };
  22 typedef ArrayRecycler<Object> ARO;
  23
  24 TEST(ArrayRecyclerTest, Capacity) {
  25   // Capacity size should never be 0.
  26   ARO::Capacity Cap = ARO::Capacity::get(0);
  27   EXPECT_LT(0u, Cap.getSize());
  28
  29   size_t PrevSize = Cap.getSize();
  30   for (unsigned N = 1; N != 100; ++N) {
  31     Cap = ARO::Capacity::get(N);
  32     EXPECT_LE(N, Cap.getSize());
  33     if (PrevSize >= N)
  34       EXPECT_EQ(PrevSize, Cap.getSize());
  35     else
  36       EXPECT_LT(PrevSize, Cap.getSize());
  37     PrevSize = Cap.getSize();
  38   }
  39
  40   // Check that the buckets are monotonically increasing.
  41   Cap = ARO::Capacity::get(0);
  42   PrevSize = Cap.getSize();
  43   for (unsigned N = 0; N != 20; ++N) {
  44     Cap = Cap.getNext();
  45     EXPECT_LT(PrevSize, Cap.getSize());
  46     PrevSize = Cap.getSize();
  47   }
  48 }
  49
  50 TEST(ArrayRecyclerTest, Basics) {
  51   BumpPtrAllocator Allocator;
  52   ArrayRecycler<Object> DUT;
  53
  54   ARO::Capacity Cap = ARO::Capacity::get(8);
  55   Object *A1 = DUT.allocate(Cap, Allocator);
  56   A1[0].Num = 21;
  57   A1[7].Num = 17;
  58
  59   Object *A2 = DUT.allocate(Cap, Allocator);
  60   A2[0].Num = 121;
  61   A2[7].Num = 117;
  62
  63   Object *A3 = DUT.allocate(Cap, Allocator);
  64   A3[0].Num = 221;
  65   A3[7].Num = 217;
  66
  67   EXPECT_EQ(21, A1[0].Num);
  68   EXPECT_EQ(17, A1[7].Num);
  69   EXPECT_EQ(121, A2[0].Num);
  70   EXPECT_EQ(117, A2[7].Num);
  71   EXPECT_EQ(221, A3[0].Num);
  72   EXPECT_EQ(217, A3[7].Num);
  73
  74   DUT.deallocate(Cap, A2);
  75
  76   // Check that deallocation didn't clobber anything.
  77   EXPECT_EQ(21, A1[0].Num);
  78   EXPECT_EQ(17, A1[7].Num);
  79   EXPECT_EQ(221, A3[0].Num);
  80   EXPECT_EQ(217, A3[7].Num);
  81
  82   // Verify recycling.
  83   Object *A2x = DUT.allocate(Cap, Allocator);
  84   EXPECT_EQ(A2, A2x);
  85
  86   DUT.deallocate(Cap, A2x);
  87   DUT.deallocate(Cap, A1);
  88   DUT.deallocate(Cap, A3);
  89
  90   // Objects are not required to be recycled in reverse deallocation order, but
  91   // that is what the current implementation does.
  92   Object *A3x = DUT.allocate(Cap, Allocator);
  93   EXPECT_EQ(A3, A3x);
  94   Object *A1x = DUT.allocate(Cap, Allocator);
  95   EXPECT_EQ(A1, A1x);
  96   Object *A2y = DUT.allocate(Cap, Allocator);
  97   EXPECT_EQ(A2, A2y);
  98
  99   // Back to allocation from the BumpPtrAllocator.
 100   Object *A4 = DUT.allocate(Cap, Allocator);
 101   EXPECT_NE(A1, A4);
 102   EXPECT_NE(A2, A4);
 103   EXPECT_NE(A3, A4);
 104
 105   DUT.clear(Allocator);
 106 }
 107
 108 } // end anonymous namespace