unittests/ADT/IntervalMapTest.cpp

   1 //===---- ADT/IntervalMapTest.cpp - IntervalMap unit tests ------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/ADT/IntervalMap.h"
  11 #include "gtest/gtest.h"
  12
  13 using namespace llvm;
  14
  15 namespace {
  16
  17 typedef IntervalMap<unsigned, unsigned> UUMap;
  18 typedef IntervalMap<unsigned, unsigned, 4> UU4Map;
  19
  20 // Empty map tests
  21 TEST(IntervalMapTest, EmptyMap) {
  22   UUMap::Allocator allocator;
  23   UUMap map(allocator);
  24   EXPECT_TRUE(map.empty());
  25
  26   // Lookup on empty map.
  27   EXPECT_EQ(0u, map.lookup(0));
  28   EXPECT_EQ(7u, map.lookup(0, 7));
  29   EXPECT_EQ(0u, map.lookup(~0u-1));
  30   EXPECT_EQ(7u, map.lookup(~0u-1, 7));
  31
  32   // Iterators.
  33   EXPECT_TRUE(map.begin() == map.begin());
  34   EXPECT_TRUE(map.begin() == map.end());
  35   EXPECT_TRUE(map.end() == map.end());
  36   EXPECT_FALSE(map.begin() != map.begin());
  37   EXPECT_FALSE(map.begin() != map.end());
  38   EXPECT_FALSE(map.end() != map.end());
  39   EXPECT_FALSE(map.begin().valid());
  40   EXPECT_FALSE(map.end().valid());
  41   UUMap::iterator I = map.begin();
  42   EXPECT_FALSE(I.valid());
  43   EXPECT_TRUE(I == map.end());
  44
  45   // Default constructor and cross-constness compares.
  46   UUMap::const_iterator CI;
  47   CI = map.begin();
  48   EXPECT_TRUE(CI == I);
  49   UUMap::iterator I2;
  50   I2 = map.end();
  51   EXPECT_TRUE(I2 == CI);
  52 }
  53
  54 // Single entry map tests
  55 TEST(IntervalMapTest, SingleEntryMap) {
  56   UUMap::Allocator allocator;
  57   UUMap map(allocator);
  58   map.insert(100, 150, 1);
  59   EXPECT_FALSE(map.empty());
  60
  61   // Lookup around interval.
  62   EXPECT_EQ(0u, map.lookup(0));
  63   EXPECT_EQ(0u, map.lookup(99));
  64   EXPECT_EQ(1u, map.lookup(100));
  65   EXPECT_EQ(1u, map.lookup(101));
  66   EXPECT_EQ(1u, map.lookup(125));
  67   EXPECT_EQ(1u, map.lookup(149));
  68   EXPECT_EQ(1u, map.lookup(150));
  69   EXPECT_EQ(0u, map.lookup(151));
  70   EXPECT_EQ(0u, map.lookup(200));
  71   EXPECT_EQ(0u, map.lookup(~0u-1));
  72
  73   // Iterators.
  74   EXPECT_TRUE(map.begin() == map.begin());
  75   EXPECT_FALSE(map.begin() == map.end());
  76   EXPECT_TRUE(map.end() == map.end());
  77   EXPECT_TRUE(map.begin().valid());
  78   EXPECT_FALSE(map.end().valid());
  79
  80   // Iter deref.
  81   UUMap::iterator I = map.begin();
  82   ASSERT_TRUE(I.valid());
  83   EXPECT_EQ(100u, I.start());
  84   EXPECT_EQ(150u, I.stop());
  85   EXPECT_EQ(1u, I.value());
  86
  87   // Preincrement.
  88   ++I;
  89   EXPECT_FALSE(I.valid());
  90   EXPECT_FALSE(I == map.begin());
  91   EXPECT_TRUE(I == map.end());
  92
  93   // PreDecrement.
  94   --I;
  95   ASSERT_TRUE(I.valid());
  96   EXPECT_EQ(100u, I.start());
  97   EXPECT_EQ(150u, I.stop());
  98   EXPECT_EQ(1u, I.value());
  99   EXPECT_TRUE(I == map.begin());
 100   EXPECT_FALSE(I == map.end());
 101
 102   I.erase();
 103   EXPECT_TRUE(map.empty());
 104   EXPECT_EQ(0, std::distance(map.begin(), map.end()));
 105 }
 106
 107 // Flat coalescing tests.
 108 TEST(IntervalMapTest, RootCoalescing) {
 109   UUMap::Allocator allocator;
 110   UUMap map(allocator);
 111   map.insert(100, 150, 1);
 112
 113   // Coalesce from the left.
 114   map.insert(90, 99, 1);
 115   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 116   EXPECT_EQ(90u, map.start());
 117   EXPECT_EQ(150u, map.stop());
 118
 119   // Overlap left.
 120   map.insert(80, 100, 1);
 121   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 122   EXPECT_EQ(80u, map.start());
 123   EXPECT_EQ(150u, map.stop());
 124
 125   // Inside.
 126   map.insert(100, 130, 1);
 127   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 128   EXPECT_EQ(80u, map.start());
 129   EXPECT_EQ(150u, map.stop());
 130
 131   // Overlap both.
 132   map.insert(70, 160, 1);
 133   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 134   EXPECT_EQ(70u, map.start());
 135   EXPECT_EQ(160u, map.stop());
 136
 137   // Overlap right.
 138   map.insert(80, 170, 1);
 139   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 140   EXPECT_EQ(70u, map.start());
 141   EXPECT_EQ(170u, map.stop());
 142
 143   // Coalesce from the right.
 144   map.insert(170, 200, 1);
 145   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 146   EXPECT_EQ(70u, map.start());
 147   EXPECT_EQ(200u, map.stop());
 148
 149   // Non-coalesce from the left.
 150   map.insert(60, 69, 2);
 151   EXPECT_EQ(2, std::distance(map.begin(), map.end()));
 152   EXPECT_EQ(60u, map.start());
 153   EXPECT_EQ(200u, map.stop());
 154   EXPECT_EQ(2u, map.lookup(69));
 155   EXPECT_EQ(1u, map.lookup(70));
 156
 157   UUMap::iterator I = map.begin();
 158   EXPECT_EQ(60u, I.start());
 159   EXPECT_EQ(69u, I.stop());
 160   EXPECT_EQ(2u, I.value());
 161   ++I;
 162   EXPECT_EQ(70u, I.start());
 163   EXPECT_EQ(200u, I.stop());
 164   EXPECT_EQ(1u, I.value());
 165   ++I;
 166   EXPECT_FALSE(I.valid());
 167
 168   // Non-coalesce from the right.
 169   map.insert(201, 210, 2);
 170   EXPECT_EQ(3, std::distance(map.begin(), map.end()));
 171   EXPECT_EQ(60u, map.start());
 172   EXPECT_EQ(210u, map.stop());
 173   EXPECT_EQ(2u, map.lookup(201));
 174   EXPECT_EQ(1u, map.lookup(200));
 175
 176   // Erase from the left.
 177   map.begin().erase();
 178   EXPECT_EQ(2, std::distance(map.begin(), map.end()));
 179   EXPECT_EQ(70u, map.start());
 180   EXPECT_EQ(210u, map.stop());
 181
 182   // Erase from the right.
 183   (--map.end()).erase();
 184   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 185   EXPECT_EQ(70u, map.start());
 186   EXPECT_EQ(200u, map.stop());
 187 }
 188
 189 // Flat multi-coalescing tests.
 190 TEST(IntervalMapTest, RootMultiCoalescing) {
 191   UUMap::Allocator allocator;
 192   UUMap map(allocator);
 193   map.insert(140, 150, 1);
 194   map.insert(160, 170, 1);
 195   map.insert(100, 110, 1);
 196   map.insert(120, 130, 1);
 197   EXPECT_EQ(4, std::distance(map.begin(), map.end()));
 198   EXPECT_EQ(100u, map.start());
 199   EXPECT_EQ(170u, map.stop());
 200
 201   // Verify inserts.
 202   UUMap::iterator I = map.begin();
 203   EXPECT_EQ(100u, I.start());
 204   EXPECT_EQ(110u, I.stop());
 205   ++I;
 206   EXPECT_EQ(120u, I.start());
 207   EXPECT_EQ(130u, I.stop());
 208   ++I;
 209   EXPECT_EQ(140u, I.start());
 210   EXPECT_EQ(150u, I.stop());
 211   ++I;
 212   EXPECT_EQ(160u, I.start());
 213   EXPECT_EQ(170u, I.stop());
 214   ++I;
 215   EXPECT_FALSE(I.valid());
 216
 217   // Test advanceTo on flat tree.
 218   I = map.begin();
 219   I.advanceTo(135);
 220   ASSERT_TRUE(I.valid());
 221   EXPECT_EQ(140u, I.start());
 222   EXPECT_EQ(150u, I.stop());
 223
 224   I.advanceTo(145);
 225   ASSERT_TRUE(I.valid());
 226   EXPECT_EQ(140u, I.start());
 227   EXPECT_EQ(150u, I.stop());
 228
 229   // Coalesce left with followers.
 230   // [100;110] [120;130] [140;150] [160;170]
 231   map.insert(111, 115, 1);
 232   I = map.begin();
 233   ASSERT_TRUE(I.valid());
 234   EXPECT_EQ(100u, I.start());
 235   EXPECT_EQ(115u, I.stop());
 236   ++I;
 237   ASSERT_TRUE(I.valid());
 238   EXPECT_EQ(120u, I.start());
 239   EXPECT_EQ(130u, I.stop());
 240   ++I;
 241   ASSERT_TRUE(I.valid());
 242   EXPECT_EQ(140u, I.start());
 243   EXPECT_EQ(150u, I.stop());
 244   ++I;
 245   ASSERT_TRUE(I.valid());
 246   EXPECT_EQ(160u, I.start());
 247   EXPECT_EQ(170u, I.stop());
 248   ++I;
 249   EXPECT_FALSE(I.valid());
 250
 251   // Coalesce right with followers.
 252   // [100;115] [120;130] [140;150] [160;170]
 253   map.insert(135, 139, 1);
 254   I = map.begin();
 255   ASSERT_TRUE(I.valid());
 256   EXPECT_EQ(100u, I.start());
 257   EXPECT_EQ(115u, I.stop());
 258   ++I;
 259   ASSERT_TRUE(I.valid());
 260   EXPECT_EQ(120u, I.start());
 261   EXPECT_EQ(130u, I.stop());
 262   ++I;
 263   ASSERT_TRUE(I.valid());
 264   EXPECT_EQ(135u, I.start());
 265   EXPECT_EQ(150u, I.stop());
 266   ++I;
 267   ASSERT_TRUE(I.valid());
 268   EXPECT_EQ(160u, I.start());
 269   EXPECT_EQ(170u, I.stop());
 270   ++I;
 271   EXPECT_FALSE(I.valid());
 272
 273   // Coalesce left and right with followers.
 274   // [100;115] [120;130] [135;150] [160;170]
 275   map.insert(131, 134, 1);
 276   I = map.begin();
 277   ASSERT_TRUE(I.valid());
 278   EXPECT_EQ(100u, I.start());
 279   EXPECT_EQ(115u, I.stop());
 280   ++I;
 281   ASSERT_TRUE(I.valid());
 282   EXPECT_EQ(120u, I.start());
 283   EXPECT_EQ(150u, I.stop());
 284   ++I;
 285   ASSERT_TRUE(I.valid());
 286   EXPECT_EQ(160u, I.start());
 287   EXPECT_EQ(170u, I.stop());
 288   ++I;
 289   EXPECT_FALSE(I.valid());
 290
 291   // Coalesce multiple with overlap right.
 292   // [100;115] [120;150] [160;170]
 293   map.insert(116, 165, 1);
 294   I = map.begin();
 295   ASSERT_TRUE(I.valid());
 296   EXPECT_EQ(100u, I.start());
 297   EXPECT_EQ(170u, I.stop());
 298   ++I;
 299   EXPECT_FALSE(I.valid());
 300
 301   // Coalesce multiple with overlap left
 302   // [100;170]
 303   map.insert(180, 190, 1);
 304   map.insert(200, 210, 1);
 305   map.insert(220, 230, 1);
 306   // [100;170] [180;190] [200;210] [220;230]
 307   map.insert(160, 199, 1);
 308   I = map.begin();
 309   ASSERT_TRUE(I.valid());
 310   EXPECT_EQ(100u, I.start());
 311   EXPECT_EQ(210u, I.stop());
 312   ++I;
 313   ASSERT_TRUE(I.valid());
 314   EXPECT_EQ(220u, I.start());
 315   EXPECT_EQ(230u, I.stop());
 316   ++I;
 317   EXPECT_FALSE(I.valid());
 318
 319   // Overwrite 2 from gap to gap.
 320   // [100;210] [220;230]
 321   map.insert(50, 250, 1);
 322   I = map.begin();
 323   ASSERT_TRUE(I.valid());
 324   EXPECT_EQ(50u, I.start());
 325   EXPECT_EQ(250u, I.stop());
 326   ++I;
 327   EXPECT_FALSE(I.valid());
 328
 329   // Coalesce at end of full root.
 330   // [50;250]
 331   map.insert(260, 270, 1);
 332   map.insert(280, 290, 1);
 333   map.insert(300, 310, 1);
 334   // [50;250] [260;270] [280;290] [300;310]
 335   map.insert(311, 320, 1);
 336   I = map.begin();
 337   ASSERT_TRUE(I.valid());
 338   EXPECT_EQ(50u, I.start());
 339   EXPECT_EQ(250u, I.stop());
 340   ++I;
 341   ASSERT_TRUE(I.valid());
 342   EXPECT_EQ(260u, I.start());
 343   EXPECT_EQ(270u, I.stop());
 344   ++I;
 345   ASSERT_TRUE(I.valid());
 346   EXPECT_EQ(280u, I.start());
 347   EXPECT_EQ(290u, I.stop());
 348   ++I;
 349   ASSERT_TRUE(I.valid());
 350   EXPECT_EQ(300u, I.start());
 351   EXPECT_EQ(320u, I.stop());
 352   ++I;
 353   EXPECT_FALSE(I.valid());
 354
 355   // Test clear() on non-branched map.
 356   map.clear();
 357   EXPECT_TRUE(map.empty());
 358   EXPECT_TRUE(map.begin() == map.end());
 359 }
 360
 361 // Branched, non-coalescing tests.
 362 TEST(IntervalMapTest, Branched) {
 363   UUMap::Allocator allocator;
 364   UUMap map(allocator);
 365
 366   // Insert enough intervals to force a branched tree.
 367   // This creates 9 leaf nodes with 11 elements each, tree height = 1.
 368   for (unsigned i = 1; i < 100; ++i) {
 369     map.insert(10*i, 10*i+5, i);
 370     EXPECT_EQ(10u, map.start());
 371     EXPECT_EQ(10*i+5, map.stop());
 372   }
 373
 374   // Tree limits.
 375   EXPECT_FALSE(map.empty());
 376   EXPECT_EQ(10u, map.start());
 377   EXPECT_EQ(995u, map.stop());
 378
 379   // Tree lookup.
 380   for (unsigned i = 1; i < 100; ++i) {
 381     EXPECT_EQ(0u, map.lookup(10*i-1));
 382     EXPECT_EQ(i, map.lookup(10*i));
 383     EXPECT_EQ(i, map.lookup(10*i+5));
 384     EXPECT_EQ(0u, map.lookup(10*i+6));
 385   }
 386
 387   // Forward iteration.
 388   UUMap::iterator I = map.begin();
 389   for (unsigned i = 1; i < 100; ++i) {
 390     ASSERT_TRUE(I.valid());
 391     EXPECT_EQ(10*i, I.start());
 392     EXPECT_EQ(10*i+5, I.stop());
 393     EXPECT_EQ(i, *I);
 394     ++I;
 395   }
 396   EXPECT_FALSE(I.valid());
 397   EXPECT_TRUE(I == map.end());
 398
 399   // Backwards iteration.
 400   for (unsigned i = 99; i; --i) {
 401     --I;
 402     ASSERT_TRUE(I.valid());
 403     EXPECT_EQ(10*i, I.start());
 404     EXPECT_EQ(10*i+5, I.stop());
 405     EXPECT_EQ(i, *I);
 406   }
 407   EXPECT_TRUE(I == map.begin());
 408
 409   // Test advanceTo in same node.
 410   I.advanceTo(20);
 411   ASSERT_TRUE(I.valid());
 412   EXPECT_EQ(20u, I.start());
 413   EXPECT_EQ(25u, I.stop());
 414
 415   // advanceTo another node.
 416   I.advanceTo(200);
 417   ASSERT_TRUE(I.valid());
 418   EXPECT_EQ(200u, I.start());
 419   EXPECT_EQ(205u, I.stop());
 420
 421   // Erase from the front.
 422   I = map.begin();
 423   for (unsigned i = 0; i != 20; ++i) {
 424     I.erase();
 425     EXPECT_TRUE(I == map.begin());
 426     EXPECT_FALSE(map.empty());
 427     EXPECT_EQ(I.start(), map.start());
 428     EXPECT_EQ(995u, map.stop());
 429   }
 430
 431   // Test clear() on branched map.
 432   map.clear();
 433   EXPECT_TRUE(map.empty());
 434   EXPECT_TRUE(map.begin() == map.end());
 435 }
 436
 437 // Branched, high, non-coalescing tests.
 438 TEST(IntervalMapTest, Branched2) {
 439   UU4Map::Allocator allocator;
 440   UU4Map map(allocator);
 441
 442   // Insert enough intervals to force a height >= 2 tree.
 443   for (unsigned i = 1; i < 1000; ++i)
 444     map.insert(10*i, 10*i+5, i);
 445
 446   // Tree limits.
 447   EXPECT_FALSE(map.empty());
 448   EXPECT_EQ(10u, map.start());
 449   EXPECT_EQ(9995u, map.stop());
 450
 451   // Tree lookup.
 452   for (unsigned i = 1; i < 1000; ++i) {
 453     EXPECT_EQ(0u, map.lookup(10*i-1));
 454     EXPECT_EQ(i, map.lookup(10*i));
 455     EXPECT_EQ(i, map.lookup(10*i+5));
 456     EXPECT_EQ(0u, map.lookup(10*i+6));
 457   }
 458
 459   // Forward iteration.
 460   UU4Map::iterator I = map.begin();
 461   for (unsigned i = 1; i < 1000; ++i) {
 462     ASSERT_TRUE(I.valid());
 463     EXPECT_EQ(10*i, I.start());
 464     EXPECT_EQ(10*i+5, I.stop());
 465     EXPECT_EQ(i, *I);
 466     ++I;
 467   }
 468   EXPECT_FALSE(I.valid());
 469   EXPECT_TRUE(I == map.end());
 470
 471   // Backwards iteration.
 472   for (unsigned i = 999; i; --i) {
 473     --I;
 474     ASSERT_TRUE(I.valid());
 475     EXPECT_EQ(10*i, I.start());
 476     EXPECT_EQ(10*i+5, I.stop());
 477     EXPECT_EQ(i, *I);
 478   }
 479   EXPECT_TRUE(I == map.begin());
 480
 481   // Test advanceTo in same node.
 482   I.advanceTo(20);
 483   ASSERT_TRUE(I.valid());
 484   EXPECT_EQ(20u, I.start());
 485   EXPECT_EQ(25u, I.stop());
 486
 487   // advanceTo sibling leaf node.
 488   I.advanceTo(200);
 489   ASSERT_TRUE(I.valid());
 490   EXPECT_EQ(200u, I.start());
 491   EXPECT_EQ(205u, I.stop());
 492
 493   // advanceTo further.
 494   I.advanceTo(2000);
 495   ASSERT_TRUE(I.valid());
 496   EXPECT_EQ(2000u, I.start());
 497   EXPECT_EQ(2005u, I.stop());
 498
 499   // Test clear() on branched map.
 500   map.clear();
 501   EXPECT_TRUE(map.empty());
 502   EXPECT_TRUE(map.begin() == map.end());
 503 }
 504
 505 // Random insertions, coalescing to a single interval.
 506 TEST(IntervalMapTest, RandomCoalescing) {
 507   UU4Map::Allocator allocator;
 508   UU4Map map(allocator);
 509
 510   // This is a poor PRNG with maximal period:
 511   // x_n = 5 x_{n-1} + 1 mod 2^N
 512
 513   unsigned x = 100;
 514   for (unsigned i = 0; i != 4096; ++i) {
 515     map.insert(10*x, 10*x+9, 1);
 516     EXPECT_GE(10*x, map.start());
 517     EXPECT_LE(10*x+9, map.stop());
 518     x = (5*x+1)%4096;
 519   }
 520
 521   // Map should be fully coalesced after that exercise.
 522   EXPECT_FALSE(map.empty());
 523   EXPECT_EQ(0u, map.start());
 524   EXPECT_EQ(40959u, map.stop());
 525   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 526
 527 }
 528
 529 } // namespace