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