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
 210   // Coalesce left with followers.
 211   // [100;110] [120;130] [140;150] [160;170]
 212   map.insert(111, 115, 1);
 213   I = map.begin();
 214   ASSERT_TRUE(I.valid());
 215   EXPECT_EQ(100u, I.start());
 216   EXPECT_EQ(115u, I.stop());
 217   ++I;
 218   ASSERT_TRUE(I.valid());
 219   EXPECT_EQ(120u, I.start());
 220   EXPECT_EQ(130u, I.stop());
 221   ++I;
 222   ASSERT_TRUE(I.valid());
 223   EXPECT_EQ(140u, I.start());
 224   EXPECT_EQ(150u, I.stop());
 225   ++I;
 226   ASSERT_TRUE(I.valid());
 227   EXPECT_EQ(160u, I.start());
 228   EXPECT_EQ(170u, I.stop());
 229   ++I;
 230   EXPECT_FALSE(I.valid());
 231
 232   // Coalesce right with followers.
 233   // [100;115] [120;130] [140;150] [160;170]
 234   map.insert(135, 139, 1);
 235   I = map.begin();
 236   ASSERT_TRUE(I.valid());
 237   EXPECT_EQ(100u, I.start());
 238   EXPECT_EQ(115u, I.stop());
 239   ++I;
 240   ASSERT_TRUE(I.valid());
 241   EXPECT_EQ(120u, I.start());
 242   EXPECT_EQ(130u, I.stop());
 243   ++I;
 244   ASSERT_TRUE(I.valid());
 245   EXPECT_EQ(135u, I.start());
 246   EXPECT_EQ(150u, I.stop());
 247   ++I;
 248   ASSERT_TRUE(I.valid());
 249   EXPECT_EQ(160u, I.start());
 250   EXPECT_EQ(170u, I.stop());
 251   ++I;
 252   EXPECT_FALSE(I.valid());
 253
 254   // Coalesce left and right with followers.
 255   // [100;115] [120;130] [135;150] [160;170]
 256   map.insert(131, 134, 1);
 257   I = map.begin();
 258   ASSERT_TRUE(I.valid());
 259   EXPECT_EQ(100u, I.start());
 260   EXPECT_EQ(115u, I.stop());
 261   ++I;
 262   ASSERT_TRUE(I.valid());
 263   EXPECT_EQ(120u, 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 multiple with overlap right.
 273   // [100;115] [120;150] [160;170]
 274   map.insert(116, 165, 1);
 275   I = map.begin();
 276   ASSERT_TRUE(I.valid());
 277   EXPECT_EQ(100u, I.start());
 278   EXPECT_EQ(170u, I.stop());
 279   ++I;
 280   EXPECT_FALSE(I.valid());
 281
 282   // Coalesce multiple with overlap left
 283   // [100;170]
 284   map.insert(180, 190, 1);
 285   map.insert(200, 210, 1);
 286   map.insert(220, 230, 1);
 287   // [100;170] [180;190] [200;210] [220;230]
 288   map.insert(160, 199, 1);
 289   I = map.begin();
 290   ASSERT_TRUE(I.valid());
 291   EXPECT_EQ(100u, I.start());
 292   EXPECT_EQ(210u, I.stop());
 293   ++I;
 294   ASSERT_TRUE(I.valid());
 295   EXPECT_EQ(220u, I.start());
 296   EXPECT_EQ(230u, I.stop());
 297   ++I;
 298   EXPECT_FALSE(I.valid());
 299
 300   // Overwrite 2 from gap to gap.
 301   // [100;210] [220;230]
 302   map.insert(50, 250, 1);
 303   I = map.begin();
 304   ASSERT_TRUE(I.valid());
 305   EXPECT_EQ(50u, I.start());
 306   EXPECT_EQ(250u, I.stop());
 307   ++I;
 308   EXPECT_FALSE(I.valid());
 309
 310   // Coalesce at end of full root.
 311   // [50;250]
 312   map.insert(260, 270, 1);
 313   map.insert(280, 290, 1);
 314   map.insert(300, 310, 1);
 315   // [50;250] [260;270] [280;290] [300;310]
 316   map.insert(311, 320, 1);
 317   I = map.begin();
 318   ASSERT_TRUE(I.valid());
 319   EXPECT_EQ(50u, I.start());
 320   EXPECT_EQ(250u, I.stop());
 321   ++I;
 322   ASSERT_TRUE(I.valid());
 323   EXPECT_EQ(260u, I.start());
 324   EXPECT_EQ(270u, I.stop());
 325   ++I;
 326   ASSERT_TRUE(I.valid());
 327   EXPECT_EQ(280u, I.start());
 328   EXPECT_EQ(290u, I.stop());
 329   ++I;
 330   ASSERT_TRUE(I.valid());
 331   EXPECT_EQ(300u, I.start());
 332   EXPECT_EQ(320u, I.stop());
 333   ++I;
 334   EXPECT_FALSE(I.valid());
 335
 336   // Test clear() on non-branched map.
 337   map.clear();
 338   EXPECT_TRUE(map.empty());
 339   EXPECT_TRUE(map.begin() == map.end());
 340 }
 341
 342 // Branched, non-coalescing tests.
 343 TEST(IntervalMapTest, Branched) {
 344   UUMap::Allocator allocator;
 345   UUMap map(allocator);
 346
 347   // Insert enough intervals to force a branched tree.
 348   // This creates 9 leaf nodes with 11 elements each, tree height = 1.
 349   for (unsigned i = 1; i < 100; ++i) {
 350     map.insert(10*i, 10*i+5, i);
 351     EXPECT_EQ(10u, map.start());
 352     EXPECT_EQ(10*i+5, map.stop());
 353   }
 354
 355   // Tree limits.
 356   EXPECT_FALSE(map.empty());
 357   EXPECT_EQ(10u, map.start());
 358   EXPECT_EQ(995u, map.stop());
 359
 360   // Tree lookup.
 361   for (unsigned i = 1; i < 100; ++i) {
 362     EXPECT_EQ(0u, map.lookup(10*i-1));
 363     EXPECT_EQ(i, map.lookup(10*i));
 364     EXPECT_EQ(i, map.lookup(10*i+5));
 365     EXPECT_EQ(0u, map.lookup(10*i+6));
 366   }
 367
 368   // Forward iteration.
 369   UUMap::iterator I = map.begin();
 370   for (unsigned i = 1; i < 100; ++i) {
 371     ASSERT_TRUE(I.valid());
 372     EXPECT_EQ(10*i, I.start());
 373     EXPECT_EQ(10*i+5, I.stop());
 374     EXPECT_EQ(i, *I);
 375     ++I;
 376   }
 377   EXPECT_FALSE(I.valid());
 378   EXPECT_TRUE(I == map.end());
 379
 380   // Backwards iteration.
 381   for (unsigned i = 99; i; --i) {
 382     --I;
 383     ASSERT_TRUE(I.valid());
 384     EXPECT_EQ(10*i, I.start());
 385     EXPECT_EQ(10*i+5, I.stop());
 386     EXPECT_EQ(i, *I);
 387   }
 388   EXPECT_TRUE(I == map.begin());
 389
 390   // Erase from the front.
 391   for (unsigned i = 0; i != 20; ++i) {
 392     I.erase();
 393     EXPECT_TRUE(I == map.begin());
 394     EXPECT_FALSE(map.empty());
 395     EXPECT_EQ(I.start(), map.start());
 396     EXPECT_EQ(995u, map.stop());
 397   }
 398
 399   // Test clear() on branched map.
 400   map.clear();
 401   EXPECT_TRUE(map.empty());
 402   EXPECT_TRUE(map.begin() == map.end());
 403 }
 404
 405 // Branched, high, non-coalescing tests.
 406 TEST(IntervalMapTest, Branched2) {
 407   UU4Map::Allocator allocator;
 408   UU4Map map(allocator);
 409
 410   // Insert enough intervals to force a height >= 2 tree.
 411   for (unsigned i = 1; i < 1000; ++i)
 412     map.insert(10*i, 10*i+5, i);
 413
 414   // Tree limits.
 415   EXPECT_FALSE(map.empty());
 416   EXPECT_EQ(10u, map.start());
 417   EXPECT_EQ(9995u, map.stop());
 418
 419   // Tree lookup.
 420   for (unsigned i = 1; i < 1000; ++i) {
 421     EXPECT_EQ(0u, map.lookup(10*i-1));
 422     EXPECT_EQ(i, map.lookup(10*i));
 423     EXPECT_EQ(i, map.lookup(10*i+5));
 424     EXPECT_EQ(0u, map.lookup(10*i+6));
 425   }
 426
 427   // Forward iteration.
 428   UU4Map::iterator I = map.begin();
 429   for (unsigned i = 1; i < 1000; ++i) {
 430     ASSERT_TRUE(I.valid());
 431     EXPECT_EQ(10*i, I.start());
 432     EXPECT_EQ(10*i+5, I.stop());
 433     EXPECT_EQ(i, *I);
 434     ++I;
 435   }
 436   EXPECT_FALSE(I.valid());
 437   EXPECT_TRUE(I == map.end());
 438
 439   // Backwards iteration.
 440   for (unsigned i = 999; i; --i) {
 441     --I;
 442     ASSERT_TRUE(I.valid());
 443     EXPECT_EQ(10*i, I.start());
 444     EXPECT_EQ(10*i+5, I.stop());
 445     EXPECT_EQ(i, *I);
 446   }
 447   EXPECT_TRUE(I == map.begin());
 448
 449   // Test clear() on branched map.
 450   map.clear();
 451   EXPECT_TRUE(map.empty());
 452   EXPECT_TRUE(map.begin() == map.end());
 453 }
 454
 455 // Random insertions, coalescing to a single interval.
 456 TEST(IntervalMapTest, RandomCoalescing) {
 457   UU4Map::Allocator allocator;
 458   UU4Map map(allocator);
 459
 460   // This is a poor PRNG with maximal period:
 461   // x_n = 5 x_{n-1} + 1 mod 2^N
 462
 463   unsigned x = 100;
 464   for (unsigned i = 0; i != 4096; ++i) {
 465     map.insert(10*x, 10*x+9, 1);
 466     EXPECT_GE(10*x, map.start());
 467     EXPECT_LE(10*x+9, map.stop());
 468     x = (5*x+1)%4096;
 469   }
 470
 471   // Map should be fully coalesced after that exercise.
 472   EXPECT_FALSE(map.empty());
 473   EXPECT_EQ(0u, map.start());
 474   EXPECT_EQ(40959u, map.stop());
 475   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 476
 477 }
 478
 479 } // namespace