1 | //===- llvm/unittest/Support/AddresRangeTest.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/ADT/AddressRanges.h" |
10 | #include "llvm/Testing/Support/Error.h" |
11 | |
12 | #include "gmock/gmock.h" |
13 | #include "gtest/gtest.h" |
14 | |
15 | using namespace llvm; |
16 | |
17 | TEST(AddressRangeTest, TestRanges) { |
18 | // test llvm::AddressRange. |
19 | const uint64_t StartAddr = 0x1000; |
20 | const uint64_t EndAddr = 0x2000; |
21 | // Verify constructor and API to ensure it takes start and end address. |
22 | const AddressRange Range(StartAddr, EndAddr); |
23 | EXPECT_EQ(Range.size(), EndAddr - StartAddr); |
24 | |
25 | // Verify llvm::AddressRange::contains(). |
26 | EXPECT_FALSE(Range.contains(0)); |
27 | EXPECT_FALSE(Range.contains(StartAddr - 1)); |
28 | EXPECT_TRUE(Range.contains(StartAddr)); |
29 | EXPECT_TRUE(Range.contains(EndAddr - 1)); |
30 | EXPECT_FALSE(Range.contains(EndAddr)); |
31 | EXPECT_FALSE(Range.contains(UINT64_MAX)); |
32 | |
33 | const AddressRange RangeSame(StartAddr, EndAddr); |
34 | const AddressRange RangeDifferentStart(StartAddr + 1, EndAddr); |
35 | const AddressRange RangeDifferentEnd(StartAddr, EndAddr + 1); |
36 | const AddressRange RangeDifferentStartEnd(StartAddr + 1, EndAddr + 1); |
37 | // Test == and != with values that are the same |
38 | EXPECT_EQ(Range, RangeSame); |
39 | EXPECT_FALSE(Range != RangeSame); |
40 | // Test == and != with values that are the different |
41 | EXPECT_NE(Range, RangeDifferentStart); |
42 | EXPECT_NE(Range, RangeDifferentEnd); |
43 | EXPECT_NE(Range, RangeDifferentStartEnd); |
44 | EXPECT_FALSE(Range == RangeDifferentStart); |
45 | EXPECT_FALSE(Range == RangeDifferentEnd); |
46 | EXPECT_FALSE(Range == RangeDifferentStartEnd); |
47 | |
48 | // Test "bool operator<(const AddressRange &, const AddressRange &)". |
49 | EXPECT_FALSE(Range < RangeSame); |
50 | EXPECT_FALSE(RangeSame < Range); |
51 | EXPECT_LT(Range, RangeDifferentStart); |
52 | EXPECT_LT(Range, RangeDifferentEnd); |
53 | EXPECT_LT(Range, RangeDifferentStartEnd); |
54 | // Test "bool operator<(const AddressRange &, uint64_t)" |
55 | EXPECT_LT(Range.start(), StartAddr + 1); |
56 | // Test "bool operator<(uint64_t, const AddressRange &)" |
57 | EXPECT_LT(StartAddr - 1, Range.start()); |
58 | |
59 | // Verify llvm::AddressRange::isContiguousWith() and |
60 | // llvm::AddressRange::intersects(). |
61 | const AddressRange EndsBeforeRangeStart(0, StartAddr - 1); |
62 | const AddressRange EndsAtRangeStart(0, StartAddr); |
63 | const AddressRange OverlapsRangeStart(StartAddr - 1, StartAddr + 1); |
64 | const AddressRange InsideRange(StartAddr + 1, EndAddr - 1); |
65 | const AddressRange OverlapsRangeEnd(EndAddr - 1, EndAddr + 1); |
66 | const AddressRange StartsAtRangeEnd(EndAddr, EndAddr + 0x100); |
67 | const AddressRange StartsAfterRangeEnd(EndAddr + 1, EndAddr + 0x100); |
68 | |
69 | EXPECT_FALSE(Range.intersects(EndsBeforeRangeStart)); |
70 | EXPECT_FALSE(Range.intersects(EndsAtRangeStart)); |
71 | EXPECT_TRUE(Range.intersects(OverlapsRangeStart)); |
72 | EXPECT_TRUE(Range.intersects(InsideRange)); |
73 | EXPECT_TRUE(Range.intersects(OverlapsRangeEnd)); |
74 | EXPECT_FALSE(Range.intersects(StartsAtRangeEnd)); |
75 | EXPECT_FALSE(Range.intersects(StartsAfterRangeEnd)); |
76 | |
77 | // Test the functions that maintain address ranges: |
78 | // "bool AddressRange::contains(uint64_t Addr) const;" |
79 | // "void AddressRanges::insert(const AddressRange &R);" |
80 | AddressRanges Ranges; |
81 | Ranges.insert(Range: AddressRange(0x1000, 0x2000)); |
82 | Ranges.insert(Range: AddressRange(0x2000, 0x3000)); |
83 | Ranges.insert(Range: AddressRange(0x4000, 0x5000)); |
84 | |
85 | EXPECT_FALSE(Ranges.contains(0)); |
86 | EXPECT_FALSE(Ranges.contains(0x1000 - 1)); |
87 | EXPECT_TRUE(Ranges.contains(0x1000)); |
88 | EXPECT_TRUE(Ranges.contains(0x2000)); |
89 | EXPECT_TRUE(Ranges.contains(0x4000)); |
90 | EXPECT_TRUE(Ranges.contains(0x2000 - 1)); |
91 | EXPECT_TRUE(Ranges.contains(0x3000 - 1)); |
92 | EXPECT_FALSE(Ranges.contains(0x3000 + 1)); |
93 | EXPECT_TRUE(Ranges.contains(0x5000 - 1)); |
94 | EXPECT_FALSE(Ranges.contains(0x5000 + 1)); |
95 | EXPECT_FALSE(Ranges.contains(UINT64_MAX)); |
96 | |
97 | EXPECT_FALSE(Ranges.contains(AddressRange())); |
98 | EXPECT_FALSE(Ranges.contains(AddressRange(0x1000 - 1, 0x1000))); |
99 | EXPECT_FALSE(Ranges.contains(AddressRange(0x1000, 0x1000))); |
100 | EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x1000 + 1))); |
101 | EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2000))); |
102 | EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2001))); |
103 | EXPECT_TRUE(Ranges.contains(AddressRange(0x2000, 0x3000))); |
104 | EXPECT_FALSE(Ranges.contains(AddressRange(0x2000, 0x3001))); |
105 | EXPECT_FALSE(Ranges.contains(AddressRange(0x3000, 0x3001))); |
106 | EXPECT_FALSE(Ranges.contains(AddressRange(0x1500, 0x4500))); |
107 | EXPECT_FALSE(Ranges.contains(AddressRange(0x5000, 0x5001))); |
108 | |
109 | // Verify that intersecting ranges get combined |
110 | Ranges.clear(); |
111 | Ranges.insert(Range: AddressRange(0x1100, 0x1F00)); |
112 | // Verify a wholy contained range that is added doesn't do anything. |
113 | Ranges.insert(Range: AddressRange(0x1500, 0x1F00)); |
114 | EXPECT_EQ(Ranges.size(), 1u); |
115 | EXPECT_EQ(Ranges[0], AddressRange(0x1100, 0x1F00)); |
116 | |
117 | // Verify a range that starts before and intersects gets combined. |
118 | Ranges.insert(Range: AddressRange(0x1000, Ranges[0].start() + 1)); |
119 | EXPECT_EQ(Ranges.size(), 1u); |
120 | EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x1F00)); |
121 | |
122 | // Verify a range that starts inside and extends ranges gets combined. |
123 | Ranges.insert(Range: AddressRange(Ranges[0].end() - 1, 0x2000)); |
124 | EXPECT_EQ(Ranges.size(), 1u); |
125 | EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2000)); |
126 | |
127 | // Verify that adjacent ranges get combined |
128 | Ranges.insert(Range: AddressRange(0x2000, 0x2fff)); |
129 | EXPECT_EQ(Ranges.size(), 1u); |
130 | EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2fff)); |
131 | |
132 | // Verify that ranges having 1 byte gap do not get combined |
133 | Ranges.insert(Range: AddressRange(0x3000, 0x4000)); |
134 | EXPECT_EQ(Ranges.size(), 2u); |
135 | EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2fff)); |
136 | EXPECT_EQ(Ranges[1], AddressRange(0x3000, 0x4000)); |
137 | |
138 | // Verify if we add an address range that intersects two ranges |
139 | // that they get combined |
140 | Ranges.insert(Range: AddressRange(Ranges[0].end() - 1, Ranges[1].start() + 1)); |
141 | EXPECT_EQ(Ranges.size(), 1u); |
142 | EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x4000)); |
143 | |
144 | Ranges.insert(Range: AddressRange(0x3000, 0x4000)); |
145 | Ranges.insert(Range: AddressRange(0x4000, 0x5000)); |
146 | Ranges.insert(Range: AddressRange(0x2000, 0x4500)); |
147 | EXPECT_EQ(Ranges.size(), 1u); |
148 | EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x5000)); |
149 | } |
150 | |
151 | TEST(AddressRangeTest, TestRangesRandom) { |
152 | AddressRanges Ranges; |
153 | size_t NumElements = 100; |
154 | |
155 | std::srand(seed: std::time(timer: nullptr)); |
156 | |
157 | // Fill ranges. |
158 | for (size_t Idx = 0; Idx < NumElements; Idx++) { |
159 | uint64_t Start = static_cast<uint64_t>(std::rand() % 1000); |
160 | uint64_t End = Start + static_cast<uint64_t>(std::rand() % 1000); |
161 | Ranges.insert(Range: {Start, End}); |
162 | } |
163 | |
164 | // Check ranges. |
165 | for (size_t Idx = 0; Idx + 1 < Ranges.size(); Idx++) { |
166 | // Check that ranges are not intersected. |
167 | EXPECT_FALSE(Ranges[Idx].intersects(Ranges[Idx + 1])); |
168 | |
169 | // Check that ranges are sorted and not adjusted. |
170 | EXPECT_TRUE(Ranges[Idx].end() < Ranges[Idx + 1].start()); |
171 | } |
172 | } |
173 | |
174 | TEST(AddressRangeTest, TestRangesMap) { |
175 | AddressRangesMap Ranges; |
176 | |
177 | EXPECT_EQ(Ranges.size(), 0u); |
178 | EXPECT_TRUE(Ranges.empty()); |
179 | |
180 | // Add single range. |
181 | Ranges.insert(Range: AddressRange(0x1000, 0x2000), Value: 0xfe); |
182 | EXPECT_EQ(Ranges.size(), 1u); |
183 | EXPECT_FALSE(Ranges.empty()); |
184 | EXPECT_TRUE(Ranges.contains(0x1500)); |
185 | EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2000))); |
186 | |
187 | /////////////////////////////////////// |
188 | /// Check ranges with the same mapped value. |
189 | |
190 | // Clear ranges. |
191 | Ranges.clear(); |
192 | EXPECT_EQ(Ranges.size(), 0u); |
193 | EXPECT_TRUE(Ranges.empty()); |
194 | |
195 | // Add range and check mapped value. |
196 | Ranges.insert(Range: AddressRange(0x1000, 0x2000), Value: 0x11); |
197 | EXPECT_EQ(Ranges.size(), 1u); |
198 | EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0x11); |
199 | |
200 | // Add adjacent range and check mapped value. |
201 | Ranges.insert(Range: AddressRange(0x2000, 0x3000), Value: 0x11); |
202 | EXPECT_EQ(Ranges.size(), 2u); |
203 | EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0x11); |
204 | EXPECT_EQ(Ranges.getRangeThatContains(0x2000)->Value, 0x11); |
205 | EXPECT_EQ(Ranges.getRangeThatContains(0x2900)->Value, 0x11); |
206 | EXPECT_FALSE(Ranges.getRangeThatContains(0x3000)); |
207 | |
208 | // Add intersecting range and check mapped value. |
209 | Ranges.insert(Range: AddressRange(0x1000, 0x3000), Value: 0x11); |
210 | EXPECT_EQ(Ranges.size(), 2u); |
211 | EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0x11); |
212 | |
213 | // Add second range and check mapped values. |
214 | Ranges.insert(Range: AddressRange(0x4000, 0x5000), Value: 0x11); |
215 | EXPECT_EQ(Ranges.size(), 3u); |
216 | EXPECT_EQ(Ranges[0].Range, AddressRange(0x1000, 0x2000)); |
217 | EXPECT_EQ(Ranges[0].Value, 0x11); |
218 | EXPECT_EQ(Ranges[1].Range, AddressRange(0x2000, 0x3000)); |
219 | EXPECT_EQ(Ranges[1].Value, 0x11); |
220 | EXPECT_EQ(Ranges[2].Range, AddressRange(0x4000, 0x5000)); |
221 | EXPECT_EQ(Ranges[2].Value, 0x11); |
222 | EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0x11); |
223 | EXPECT_EQ(Ranges.getRangeThatContains(0x4000)->Value, 0x11); |
224 | |
225 | // Add intersecting range and check mapped value. |
226 | Ranges.insert(Range: AddressRange(0x0, 0x6000), Value: 0x11); |
227 | EXPECT_EQ(Ranges.size(), 6u); |
228 | EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0x11); |
229 | |
230 | // Check that mapped values are correctly preserved for combined ranges. |
231 | Ranges.clear(); |
232 | Ranges.insert(Range: AddressRange(0x0, 0xff), Value: 0x11); |
233 | Ranges.insert(Range: AddressRange(0x100, 0x1ff), Value: 0x11); |
234 | Ranges.insert(Range: AddressRange(0x200, 0x2ff), Value: 0x11); |
235 | Ranges.insert(Range: AddressRange(0x500, 0x5ff), Value: 0x11); |
236 | Ranges.insert(Range: AddressRange(0x300, 0x3ff), Value: 0x11); |
237 | Ranges.insert(Range: AddressRange(0x400, 0x4ff), Value: 0x11); |
238 | Ranges.insert(Range: AddressRange(0x600, 0x6ff), Value: 0x11); |
239 | EXPECT_EQ(Ranges.size(), 7u); |
240 | |
241 | Ranges.insert(Range: AddressRange(0x150, 0x350), Value: 0x11); |
242 | EXPECT_EQ(Ranges.size(), 9u); |
243 | EXPECT_EQ(Ranges[0].Range, AddressRange(0x0, 0xff)); |
244 | EXPECT_EQ(Ranges[0].Value, 0x11); |
245 | EXPECT_EQ(Ranges[1].Range, AddressRange(0x100, 0x1ff)); |
246 | EXPECT_EQ(Ranges[1].Value, 0x11); |
247 | EXPECT_EQ(Ranges[2].Range, AddressRange(0x1ff, 0x200)); |
248 | EXPECT_EQ(Ranges[2].Value, 0x11); |
249 | EXPECT_EQ(Ranges[3].Range, AddressRange(0x200, 0x2ff)); |
250 | EXPECT_EQ(Ranges[3].Value, 0x11); |
251 | EXPECT_EQ(Ranges[4].Range, AddressRange(0x2ff, 0x300)); |
252 | EXPECT_EQ(Ranges[4].Value, 0x11); |
253 | EXPECT_EQ(Ranges[5].Range, AddressRange(0x300, 0x3ff)); |
254 | EXPECT_EQ(Ranges[5].Value, 0x11); |
255 | EXPECT_EQ(Ranges[6].Range, AddressRange(0x400, 0x4ff)); |
256 | EXPECT_EQ(Ranges[6].Value, 0x11); |
257 | EXPECT_EQ(Ranges[7].Range, AddressRange(0x500, 0x5ff)); |
258 | EXPECT_EQ(Ranges[7].Value, 0x11); |
259 | EXPECT_EQ(Ranges[8].Range, AddressRange(0x600, 0x6ff)); |
260 | EXPECT_EQ(Ranges[8].Value, 0x11); |
261 | |
262 | Ranges.insert(Range: AddressRange(0x3ff, 0x400), Value: 0x11); |
263 | EXPECT_EQ(Ranges.size(), 10u); |
264 | EXPECT_EQ(Ranges[0].Range, AddressRange(0x0, 0xff)); |
265 | EXPECT_EQ(Ranges[0].Value, 0x11); |
266 | EXPECT_EQ(Ranges[1].Range, AddressRange(0x100, 0x1ff)); |
267 | EXPECT_EQ(Ranges[1].Value, 0x11); |
268 | EXPECT_EQ(Ranges[2].Range, AddressRange(0x1ff, 0x200)); |
269 | EXPECT_EQ(Ranges[2].Value, 0x11); |
270 | EXPECT_EQ(Ranges[3].Range, AddressRange(0x200, 0x2ff)); |
271 | EXPECT_EQ(Ranges[3].Value, 0x11); |
272 | EXPECT_EQ(Ranges[4].Range, AddressRange(0x2ff, 0x300)); |
273 | EXPECT_EQ(Ranges[4].Value, 0x11); |
274 | EXPECT_EQ(Ranges[5].Range, AddressRange(0x300, 0x3ff)); |
275 | EXPECT_EQ(Ranges[5].Value, 0x11); |
276 | EXPECT_EQ(Ranges[6].Range, AddressRange(0x3ff, 0x400)); |
277 | EXPECT_EQ(Ranges[6].Value, 0x11); |
278 | EXPECT_EQ(Ranges[7].Range, AddressRange(0x400, 0x4ff)); |
279 | EXPECT_EQ(Ranges[7].Value, 0x11); |
280 | EXPECT_EQ(Ranges[8].Range, AddressRange(0x500, 0x5ff)); |
281 | EXPECT_EQ(Ranges[8].Value, 0x11); |
282 | EXPECT_EQ(Ranges[9].Range, AddressRange(0x600, 0x6ff)); |
283 | EXPECT_EQ(Ranges[9].Value, 0x11); |
284 | |
285 | ///////////////////////////////////////////// |
286 | /// Check ranges with various mapped values. |
287 | |
288 | // Clear ranges. |
289 | Ranges.clear(); |
290 | EXPECT_EQ(Ranges.size(), 0u); |
291 | EXPECT_TRUE(Ranges.empty()); |
292 | |
293 | // Add range and check mapped value. |
294 | Ranges.insert(Range: AddressRange(0x1000, 0x2000), Value: 0xfe); |
295 | EXPECT_EQ(Ranges.size(), 1u); |
296 | EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0xfe); |
297 | |
298 | // Add adjacent range and check mapped value. |
299 | Ranges.insert(Range: AddressRange(0x2000, 0x3000), Value: 0xfc); |
300 | EXPECT_EQ(Ranges.size(), 2u); |
301 | EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0xfe); |
302 | EXPECT_EQ(Ranges.getRangeThatContains(0x2000)->Value, 0xfc); |
303 | EXPECT_EQ(Ranges.getRangeThatContains(0x2900)->Value, 0xfc); |
304 | EXPECT_FALSE(Ranges.getRangeThatContains(0x3000)); |
305 | |
306 | // Add intersecting range and check mapped value. |
307 | Ranges.insert(Range: AddressRange(0x1000, 0x3000), Value: 0xff); |
308 | EXPECT_EQ(Ranges.size(), 2u); |
309 | EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0xfe); |
310 | |
311 | // Add one more range and check mapped values. |
312 | Ranges.insert(Range: AddressRange(0x4000, 0x5000), Value: 0x0); |
313 | EXPECT_EQ(Ranges.size(), 3u); |
314 | EXPECT_EQ(Ranges[0].Value, 0xfe); |
315 | EXPECT_EQ(Ranges[1].Value, 0xfc); |
316 | EXPECT_EQ(Ranges[2].Value, 0x0); |
317 | EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0xfe); |
318 | EXPECT_EQ(Ranges.getRangeThatContains(0x4000)->Value, 0x0); |
319 | |
320 | // Add intersecting range and check mapped value. |
321 | Ranges.insert(Range: AddressRange(0x0, 0x6000), Value: 0x1); |
322 | EXPECT_EQ(Ranges.size(), 6u); |
323 | EXPECT_EQ(Ranges[0].Value, 0x1); |
324 | EXPECT_EQ(Ranges[1].Value, 0xfe); |
325 | EXPECT_EQ(Ranges[2].Value, 0xfc); |
326 | EXPECT_EQ(Ranges[3].Value, 0x1); |
327 | EXPECT_EQ(Ranges[4].Value, 0x0); |
328 | EXPECT_EQ(Ranges[5].Value, 0x1); |
329 | EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0xfe); |
330 | |
331 | // Check that mapped values are correctly preserved for combined ranges. |
332 | Ranges.clear(); |
333 | Ranges.insert(Range: AddressRange(0x0, 0xff), Value: 0x1); |
334 | Ranges.insert(Range: AddressRange(0x100, 0x1ff), Value: 0x2); |
335 | Ranges.insert(Range: AddressRange(0x200, 0x2ff), Value: 0x3); |
336 | Ranges.insert(Range: AddressRange(0x300, 0x3ff), Value: 0x4); |
337 | Ranges.insert(Range: AddressRange(0x500, 0x5ff), Value: 0x6); |
338 | Ranges.insert(Range: AddressRange(0x400, 0x4ff), Value: 0x5); |
339 | Ranges.insert(Range: AddressRange(0x600, 0x6ff), Value: 0x7); |
340 | EXPECT_EQ(Ranges.size(), 7u); |
341 | |
342 | Ranges.insert(Range: AddressRange(0x150, 0x350), Value: 0xff); |
343 | EXPECT_EQ(Ranges.size(), 9u); |
344 | EXPECT_EQ(Ranges[0].Range, AddressRange(0x0, 0xff)); |
345 | EXPECT_EQ(Ranges[0].Value, 0x1); |
346 | EXPECT_EQ(Ranges[1].Range, AddressRange(0x100, 0x1ff)); |
347 | EXPECT_EQ(Ranges[1].Value, 0x2); |
348 | EXPECT_EQ(Ranges[2].Range, AddressRange(0x1ff, 0x200)); |
349 | EXPECT_EQ(Ranges[2].Value, 0xff); |
350 | EXPECT_EQ(Ranges[3].Range, AddressRange(0x200, 0x2ff)); |
351 | EXPECT_EQ(Ranges[3].Value, 0x3); |
352 | EXPECT_EQ(Ranges[4].Range, AddressRange(0x2ff, 0x300)); |
353 | EXPECT_EQ(Ranges[4].Value, 0xff); |
354 | EXPECT_EQ(Ranges[5].Range, AddressRange(0x300, 0x3ff)); |
355 | EXPECT_EQ(Ranges[5].Value, 0x4); |
356 | EXPECT_EQ(Ranges[6].Range, AddressRange(0x400, 0x4ff)); |
357 | EXPECT_EQ(Ranges[6].Value, 0x5); |
358 | EXPECT_EQ(Ranges[7].Range, AddressRange(0x500, 0x5ff)); |
359 | EXPECT_EQ(Ranges[7].Value, 0x6); |
360 | EXPECT_EQ(Ranges[8].Range, AddressRange(0x600, 0x6ff)); |
361 | EXPECT_EQ(Ranges[8].Value, 0x7); |
362 | |
363 | Ranges.insert(Range: AddressRange(0x650, 0x700), Value: 0x8); |
364 | Ranges.insert(Range: AddressRange(0x3ff, 0x400), Value: 0x5); |
365 | Ranges.insert(Range: AddressRange(0x0, 0x40), Value: 0xee); |
366 | EXPECT_EQ(Ranges.size(), 11u); |
367 | EXPECT_EQ(Ranges[0].Range, AddressRange(0x0, 0xff)); |
368 | EXPECT_EQ(Ranges[0].Value, 0x1); |
369 | EXPECT_EQ(Ranges[1].Range, AddressRange(0x100, 0x1ff)); |
370 | EXPECT_EQ(Ranges[1].Value, 0x2); |
371 | EXPECT_EQ(Ranges[2].Range, AddressRange(0x1ff, 0x200)); |
372 | EXPECT_EQ(Ranges[2].Value, 0xff); |
373 | EXPECT_EQ(Ranges[3].Range, AddressRange(0x200, 0x2ff)); |
374 | EXPECT_EQ(Ranges[3].Value, 0x3); |
375 | EXPECT_EQ(Ranges[4].Range, AddressRange(0x2ff, 0x300)); |
376 | EXPECT_EQ(Ranges[4].Value, 0xff); |
377 | EXPECT_EQ(Ranges[5].Range, AddressRange(0x300, 0x3ff)); |
378 | EXPECT_EQ(Ranges[5].Value, 0x4); |
379 | EXPECT_EQ(Ranges[6].Range, AddressRange(0x3ff, 0x400)); |
380 | EXPECT_EQ(Ranges[6].Value, 0x5); |
381 | EXPECT_EQ(Ranges[7].Range, AddressRange(0x400, 0x4ff)); |
382 | EXPECT_EQ(Ranges[7].Value, 0x5); |
383 | EXPECT_EQ(Ranges[8].Range, AddressRange(0x500, 0x5ff)); |
384 | EXPECT_EQ(Ranges[8].Value, 0x6); |
385 | EXPECT_EQ(Ranges[9].Range, AddressRange(0x600, 0x6ff)); |
386 | EXPECT_EQ(Ranges[9].Value, 0x7); |
387 | EXPECT_EQ(Ranges[10].Range, AddressRange(0x6ff, 0x700)); |
388 | EXPECT_EQ(Ranges[10].Value, 0x8); |
389 | } |
390 | |
391 | TEST(AddressRangeTest, TestRangesMapRandom) { |
392 | AddressRangesMap Ranges; |
393 | size_t NumElements = 100; |
394 | |
395 | std::srand(seed: std::time(timer: nullptr)); |
396 | |
397 | // Fill ranges. Use the same mapped value. |
398 | for (size_t Idx = 0; Idx < NumElements; Idx++) { |
399 | uint64_t Start = static_cast<uint64_t>(std::rand() % 1000); |
400 | uint64_t End = Start + static_cast<uint64_t>(std::rand() % 1000); |
401 | Ranges.insert(Range: {Start, End}, Value: 0xffLL); |
402 | } |
403 | |
404 | // Check ranges. |
405 | for (size_t Idx = 0; Idx + 1 < Ranges.size(); Idx++) { |
406 | // Check that ranges are not intersected. |
407 | EXPECT_FALSE(Ranges[Idx].Range.intersects(Ranges[Idx + 1].Range)); |
408 | |
409 | // Check that ranges are sorted and not adjusted. |
410 | EXPECT_TRUE(Ranges[Idx].Range.end() <= Ranges[Idx + 1].Range.start()); |
411 | } |
412 | |
413 | Ranges.clear(); |
414 | // Fill ranges. Use the various mapped value. |
415 | for (size_t Idx = 0; Idx < NumElements; Idx++) { |
416 | uint64_t Start = static_cast<uint64_t>(std::rand() % 1000); |
417 | uint64_t End = Start + static_cast<uint64_t>(std::rand() % 1000); |
418 | int64_t Value = static_cast<int64_t>(std::rand() % 10); |
419 | Ranges.insert(Range: {Start, End}, Value); |
420 | } |
421 | |
422 | // Check ranges. |
423 | for (size_t Idx = 0; Idx + 1 < Ranges.size(); Idx++) { |
424 | // Check that ranges are not intersected. |
425 | EXPECT_FALSE(Ranges[Idx].Range.intersects(Ranges[Idx + 1].Range)); |
426 | |
427 | // Check that ranges are sorted and not adjusted. |
428 | EXPECT_TRUE(Ranges[Idx].Range.end() <= Ranges[Idx + 1].Range.start()); |
429 | } |
430 | } |
431 | |