| 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 |