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