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
TEST(ArrayRecyclerTest,Capacity)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
TEST(ArrayRecyclerTest,Basics)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
110