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 109