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
TEST(AddressRangeTest,TestRanges)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(AddressRange(0x1000, 0x2000));
82 Ranges.insert(AddressRange(0x2000, 0x3000));
83 Ranges.insert(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(AddressRange(0x1100, 0x1F00));
112 // Verify a wholy contained range that is added doesn't do anything.
113 Ranges.insert(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(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(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(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(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(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(AddressRange(0x3000, 0x4000));
145 Ranges.insert(AddressRange(0x4000, 0x5000));
146 Ranges.insert(AddressRange(0x2000, 0x4500));
147 EXPECT_EQ(Ranges.size(), 1u);
148 EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x5000));
149 }
150
TEST(AddressRangeTest,TestRangesRandom)151 TEST(AddressRangeTest, TestRangesRandom) {
152 AddressRanges Ranges;
153 size_t NumElements = 100;
154
155 std::srand(std::time(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({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
TEST(AddressRangeTest,TestRangesMap)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(AddressRange(0x1000, 0x2000), 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(AddressRange(0x1000, 0x2000), 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(AddressRange(0x2000, 0x3000), 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(AddressRange(0x1000, 0x3000), 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(AddressRange(0x4000, 0x5000), 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(AddressRange(0x0, 0x6000), 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(AddressRange(0x0, 0xff), 0x11);
233 Ranges.insert(AddressRange(0x100, 0x1ff), 0x11);
234 Ranges.insert(AddressRange(0x200, 0x2ff), 0x11);
235 Ranges.insert(AddressRange(0x500, 0x5ff), 0x11);
236 Ranges.insert(AddressRange(0x300, 0x3ff), 0x11);
237 Ranges.insert(AddressRange(0x400, 0x4ff), 0x11);
238 Ranges.insert(AddressRange(0x600, 0x6ff), 0x11);
239 EXPECT_EQ(Ranges.size(), 7u);
240
241 Ranges.insert(AddressRange(0x150, 0x350), 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(AddressRange(0x3ff, 0x400), 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(AddressRange(0x1000, 0x2000), 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(AddressRange(0x2000, 0x3000), 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(AddressRange(0x1000, 0x3000), 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(AddressRange(0x4000, 0x5000), 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(AddressRange(0x0, 0x6000), 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(AddressRange(0x0, 0xff), 0x1);
334 Ranges.insert(AddressRange(0x100, 0x1ff), 0x2);
335 Ranges.insert(AddressRange(0x200, 0x2ff), 0x3);
336 Ranges.insert(AddressRange(0x300, 0x3ff), 0x4);
337 Ranges.insert(AddressRange(0x500, 0x5ff), 0x6);
338 Ranges.insert(AddressRange(0x400, 0x4ff), 0x5);
339 Ranges.insert(AddressRange(0x600, 0x6ff), 0x7);
340 EXPECT_EQ(Ranges.size(), 7u);
341
342 Ranges.insert(AddressRange(0x150, 0x350), 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(AddressRange(0x650, 0x700), 0x8);
364 Ranges.insert(AddressRange(0x3ff, 0x400), 0x5);
365 Ranges.insert(AddressRange(0x0, 0x40), 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
TEST(AddressRangeTest,TestRangesMapRandom)391 TEST(AddressRangeTest, TestRangesMapRandom) {
392 AddressRangesMap Ranges;
393 size_t NumElements = 100;
394
395 std::srand(std::time(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({Start, End}, 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({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