1
2 #include <gtest/gtest.h>
3 #include <random>
4
5 #include "utils/HeapAllocator.h"
6
7 using namespace util;
8
9 namespace {
dummyResizer(size_t)10 void dummyResizer(size_t) {}
11 }
12
TEST(HeapAllocatorTests,simpleAllocate)13 TEST(HeapAllocatorTests, simpleAllocate) {
14 HeapAllocator allocator(dummyResizer);
15
16 ASSERT_EQ((size_t)0, allocator.numAllocations());
17
18 auto offset = allocator.allocate(200);
19
20 ASSERT_EQ((size_t)1, allocator.numAllocations());
21
22 allocator.free(offset);
23
24 ASSERT_EQ((size_t)0, allocator.numAllocations());
25 }
26
TEST(HeapAllocatorTests,manySmallAllocations)27 TEST(HeapAllocatorTests, manySmallAllocations) {
28 HeapAllocator allocator(dummyResizer);
29
30 std::random_device rd; //Will be used to obtain a seed for the random number engine
31 std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
32 std::uniform_int_distribution<size_t> sizeDist(1, 50000);
33
34 SCP_vector<size_t> offsets;
35 // Allocate enough small ranges to require a resize at some point
36 for (auto i = 0; i < 1500; ++i) {
37 auto size = sizeDist(gen);
38
39 // Use multiples of 52 since that is what the model code uses as the vertex stride
40 size_t x = allocator.allocate(52 * size);
41
42 // Make sure that all offsets are aligned properly
43 ASSERT_EQ((size_t)0, x % 52);
44
45 offsets.push_back(x);
46 }
47
48 ASSERT_EQ(offsets.size(), allocator.numAllocations());
49
50
51 // Free some ranges in a non-contiguous manner to test range freeing and merging
52 while (offsets.size() > 512) {
53 std::uniform_int_distribution<size_t> dis(0, offsets.size() - 1);
54 auto el = std::next(offsets.begin(), dis(gen));
55
56 allocator.free(*el);
57 offsets.erase(el);
58
59 ASSERT_EQ(offsets.size(), allocator.numAllocations());
60 }
61
62 ASSERT_EQ(offsets.size(), allocator.numAllocations());
63
64 // Allocate some more ranges to test range reuse
65 for (auto i = 0; i < 1500; ++i) {
66 auto size = sizeDist(gen);
67
68 // Use multiples of 52 since that is what the model code uses as the vertex stride
69 size_t x = allocator.allocate(52 * size);
70
71 // Make sure that all offsets are aligned properly
72 ASSERT_EQ((size_t)0, x % 52);
73
74 offsets.push_back(x);
75 }
76
77 ASSERT_EQ(offsets.size(), allocator.numAllocations());
78
79 // And now empty the entire allocator
80 while (!offsets.empty()) {
81 std::uniform_int_distribution<size_t> dis(0, offsets.size() - 1);
82 auto el = std::next(offsets.begin(), dis(gen));
83
84 allocator.free(*el);
85 offsets.erase(el);
86
87 ASSERT_EQ(offsets.size(), allocator.numAllocations());
88 }
89
90 ASSERT_EQ(offsets.size(), allocator.numAllocations());
91 ASSERT_EQ((size_t)0, offsets.size());
92 }
93
TEST(HeapAllocatorTests,largeAllocations)94 TEST(HeapAllocatorTests, largeAllocations) {
95 HeapAllocator allocator(dummyResizer);
96
97 SCP_vector<size_t> offsets;
98 // Allocate enough small ranges to require a resize at some point
99 for (auto i = 0; i < 100; ++i) {
100 offsets.push_back(allocator.allocate(10 * 1024 * 1024));
101 }
102
103 ASSERT_EQ(offsets.size(), allocator.numAllocations());
104
105 std::random_device rd; //Will be used to obtain a seed for the random number engine
106 std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
107
108 // Free some ranges in a non-contiguous manner to test range freeing and merging
109 while (offsets.size() > 50) {
110 std::uniform_int_distribution<size_t> dis(0, offsets.size() - 1);
111 auto el = std::next(offsets.begin(), dis(gen));
112
113 allocator.free(*el);
114 offsets.erase(el);
115
116 ASSERT_EQ(offsets.size(), allocator.numAllocations());
117 }
118
119 ASSERT_EQ(offsets.size(), allocator.numAllocations());
120
121 // Allocate some more ranges to test range reuse
122 for (auto i = 0; i < 100; ++i) {
123 offsets.push_back(allocator.allocate(10 * 1024 * 1024));
124 }
125
126 ASSERT_EQ(offsets.size(), allocator.numAllocations());
127
128 // And now empty the entire allocator
129 while (!offsets.empty()) {
130 std::uniform_int_distribution<size_t> dis(0, offsets.size() - 1);
131 auto el = std::next(offsets.begin(), dis(gen));
132
133 allocator.free(*el);
134 offsets.erase(el);
135
136 ASSERT_EQ(offsets.size(), allocator.numAllocations());
137 }
138
139 ASSERT_EQ(offsets.size(), allocator.numAllocations());
140 ASSERT_EQ((size_t)0, offsets.size());
141 }
142