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
15using namespace llvm;
16
17namespace {
18
19struct Object {
20  int Num;
21  Object *Other;
22};
23typedef ArrayRecycler<Object> ARO;
24
25TEST(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
51TEST(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
110