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