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