unittests/Support/ArrayRecyclerTest.cpp

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