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