llvm/unittests/Support/AddressRangeTest.cpp

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