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
  95 // Flat coalescing tests.
  96 TEST(IntervalMapTest, RootCoalescing) {
  97   UUMap::Allocator allocator;
  98   UUMap map(allocator);
  99   map.insert(100, 150, 1);
 100
 101   // Coalesce from the left.
 102   map.insert(90, 99, 1);
 103   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 104   EXPECT_EQ(90u, map.start());
 105   EXPECT_EQ(150u, map.stop());
 106
 107   // Overlap left.
 108   map.insert(80, 100, 1);
 109   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 110   EXPECT_EQ(80u, map.start());
 111   EXPECT_EQ(150u, map.stop());
 112
 113   // Inside.
 114   map.insert(100, 130, 1);
 115   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 116   EXPECT_EQ(80u, map.start());
 117   EXPECT_EQ(150u, map.stop());
 118
 119   // Overlap both.
 120   map.insert(70, 160, 1);
 121   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 122   EXPECT_EQ(70u, map.start());
 123   EXPECT_EQ(160u, map.stop());
 124
 125   // Overlap right.
 126   map.insert(80, 170, 1);
 127   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 128   EXPECT_EQ(70u, map.start());
 129   EXPECT_EQ(170u, map.stop());
 130
 131   // Coalesce from the right.
 132   map.insert(170, 200, 1);
 133   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 134   EXPECT_EQ(70u, map.start());
 135   EXPECT_EQ(200u, map.stop());
 136
 137   // Non-coalesce from the left.
 138   map.insert(60, 69, 2);
 139   EXPECT_EQ(2, std::distance(map.begin(), map.end()));
 140   EXPECT_EQ(60u, map.start());
 141   EXPECT_EQ(200u, map.stop());
 142   EXPECT_EQ(2u, map.lookup(69));
 143   EXPECT_EQ(1u, map.lookup(70));
 144
 145   UUMap::iterator I = map.begin();
 146   EXPECT_EQ(60u, I.start());
 147   EXPECT_EQ(69u, I.stop());
 148   EXPECT_EQ(2u, I.value());
 149   ++I;
 150   EXPECT_EQ(70u, I.start());
 151   EXPECT_EQ(200u, I.stop());
 152   EXPECT_EQ(1u, I.value());
 153   ++I;
 154   EXPECT_FALSE(I.valid());
 155
 156   // Non-coalesce from the right.
 157   map.insert(201, 210, 2);
 158   EXPECT_EQ(3, std::distance(map.begin(), map.end()));
 159   EXPECT_EQ(60u, map.start());
 160   EXPECT_EQ(210u, map.stop());
 161   EXPECT_EQ(2u, map.lookup(201));
 162   EXPECT_EQ(1u, map.lookup(200));
 163 }
 164
 165 // Flat multi-coalescing tests.
 166 TEST(IntervalMapTest, RootMultiCoalescing) {
 167   UUMap::Allocator allocator;
 168   UUMap map(allocator);
 169   map.insert(140, 150, 1);
 170   map.insert(160, 170, 1);
 171   map.insert(100, 110, 1);
 172   map.insert(120, 130, 1);
 173   EXPECT_EQ(4, std::distance(map.begin(), map.end()));
 174   EXPECT_EQ(100u, map.start());
 175   EXPECT_EQ(170u, map.stop());
 176
 177   // Verify inserts.
 178   UUMap::iterator I = map.begin();
 179   EXPECT_EQ(100u, I.start());
 180   EXPECT_EQ(110u, I.stop());
 181   ++I;
 182   EXPECT_EQ(120u, I.start());
 183   EXPECT_EQ(130u, I.stop());
 184   ++I;
 185   EXPECT_EQ(140u, I.start());
 186   EXPECT_EQ(150u, I.stop());
 187   ++I;
 188   EXPECT_EQ(160u, I.start());
 189   EXPECT_EQ(170u, I.stop());
 190   ++I;
 191   EXPECT_FALSE(I.valid());
 192
 193
 194   // Coalesce left with followers.
 195   // [100;110] [120;130] [140;150] [160;170]
 196   map.insert(111, 115, 1);
 197   I = map.begin();
 198   ASSERT_TRUE(I.valid());
 199   EXPECT_EQ(100u, I.start());
 200   EXPECT_EQ(115u, I.stop());
 201   ++I;
 202   ASSERT_TRUE(I.valid());
 203   EXPECT_EQ(120u, I.start());
 204   EXPECT_EQ(130u, I.stop());
 205   ++I;
 206   ASSERT_TRUE(I.valid());
 207   EXPECT_EQ(140u, I.start());
 208   EXPECT_EQ(150u, I.stop());
 209   ++I;
 210   ASSERT_TRUE(I.valid());
 211   EXPECT_EQ(160u, I.start());
 212   EXPECT_EQ(170u, I.stop());
 213   ++I;
 214   EXPECT_FALSE(I.valid());
 215
 216   // Coalesce right with followers.
 217   // [100;115] [120;130] [140;150] [160;170]
 218   map.insert(135, 139, 1);
 219   I = map.begin();
 220   ASSERT_TRUE(I.valid());
 221   EXPECT_EQ(100u, I.start());
 222   EXPECT_EQ(115u, I.stop());
 223   ++I;
 224   ASSERT_TRUE(I.valid());
 225   EXPECT_EQ(120u, I.start());
 226   EXPECT_EQ(130u, I.stop());
 227   ++I;
 228   ASSERT_TRUE(I.valid());
 229   EXPECT_EQ(135u, I.start());
 230   EXPECT_EQ(150u, I.stop());
 231   ++I;
 232   ASSERT_TRUE(I.valid());
 233   EXPECT_EQ(160u, I.start());
 234   EXPECT_EQ(170u, I.stop());
 235   ++I;
 236   EXPECT_FALSE(I.valid());
 237
 238   // Coalesce left and right with followers.
 239   // [100;115] [120;130] [135;150] [160;170]
 240   map.insert(131, 134, 1);
 241   I = map.begin();
 242   ASSERT_TRUE(I.valid());
 243   EXPECT_EQ(100u, I.start());
 244   EXPECT_EQ(115u, I.stop());
 245   ++I;
 246   ASSERT_TRUE(I.valid());
 247   EXPECT_EQ(120u, I.start());
 248   EXPECT_EQ(150u, I.stop());
 249   ++I;
 250   ASSERT_TRUE(I.valid());
 251   EXPECT_EQ(160u, I.start());
 252   EXPECT_EQ(170u, I.stop());
 253   ++I;
 254   EXPECT_FALSE(I.valid());
 255
 256   // Coalesce multiple with overlap right.
 257   // [100;115] [120;150] [160;170]
 258   map.insert(116, 165, 1);
 259   I = map.begin();
 260   ASSERT_TRUE(I.valid());
 261   EXPECT_EQ(100u, I.start());
 262   EXPECT_EQ(170u, I.stop());
 263   ++I;
 264   EXPECT_FALSE(I.valid());
 265
 266   // Coalesce multiple with overlap left
 267   // [100;170]
 268   map.insert(180, 190, 1);
 269   map.insert(200, 210, 1);
 270   map.insert(220, 230, 1);
 271   // [100;170] [180;190] [200;210] [220;230]
 272   map.insert(160, 199, 1);
 273   I = map.begin();
 274   ASSERT_TRUE(I.valid());
 275   EXPECT_EQ(100u, I.start());
 276   EXPECT_EQ(210u, I.stop());
 277   ++I;
 278   ASSERT_TRUE(I.valid());
 279   EXPECT_EQ(220u, I.start());
 280   EXPECT_EQ(230u, I.stop());
 281   ++I;
 282   EXPECT_FALSE(I.valid());
 283
 284   // Overwrite 2 from gap to gap.
 285   // [100;210] [220;230]
 286   map.insert(50, 250, 1);
 287   I = map.begin();
 288   ASSERT_TRUE(I.valid());
 289   EXPECT_EQ(50u, I.start());
 290   EXPECT_EQ(250u, I.stop());
 291   ++I;
 292   EXPECT_FALSE(I.valid());
 293
 294   // Coalesce at end of full root.
 295   // [50;250]
 296   map.insert(260, 270, 1);
 297   map.insert(280, 290, 1);
 298   map.insert(300, 310, 1);
 299   // [50;250] [260;270] [280;290] [300;310]
 300   map.insert(311, 320, 1);
 301   I = map.begin();
 302   ASSERT_TRUE(I.valid());
 303   EXPECT_EQ(50u, I.start());
 304   EXPECT_EQ(250u, I.stop());
 305   ++I;
 306   ASSERT_TRUE(I.valid());
 307   EXPECT_EQ(260u, I.start());
 308   EXPECT_EQ(270u, I.stop());
 309   ++I;
 310   ASSERT_TRUE(I.valid());
 311   EXPECT_EQ(280u, I.start());
 312   EXPECT_EQ(290u, I.stop());
 313   ++I;
 314   ASSERT_TRUE(I.valid());
 315   EXPECT_EQ(300u, I.start());
 316   EXPECT_EQ(320u, I.stop());
 317   ++I;
 318   EXPECT_FALSE(I.valid());
 319
 320   // Test clear() on non-branched map.
 321   map.clear();
 322   EXPECT_TRUE(map.empty());
 323   EXPECT_TRUE(map.begin() == map.end());
 324 }
 325
 326 // Branched, non-coalescing tests.
 327 TEST(IntervalMapTest, Branched) {
 328   UUMap::Allocator allocator;
 329   UUMap map(allocator);
 330
 331   // Insert enough intervals to force a branched tree.
 332   // This creates 9 leaf nodes with 11 elements each, tree height = 1.
 333   for (unsigned i = 1; i < 100; ++i)
 334     map.insert(10*i, 10*i+5, i);
 335
 336   // Tree limits.
 337   EXPECT_FALSE(map.empty());
 338   EXPECT_EQ(10u, map.start());
 339   EXPECT_EQ(995u, map.stop());
 340
 341   // Tree lookup.
 342   for (unsigned i = 1; i < 100; ++i) {
 343     EXPECT_EQ(0u, map.lookup(10*i-1));
 344     EXPECT_EQ(i, map.lookup(10*i));
 345     EXPECT_EQ(i, map.lookup(10*i+5));
 346     EXPECT_EQ(0u, map.lookup(10*i+6));
 347   }
 348
 349   // Forward iteration.
 350   UUMap::iterator I = map.begin();
 351   for (unsigned i = 1; i < 100; ++i) {
 352     ASSERT_TRUE(I.valid());
 353     EXPECT_EQ(10*i, I.start());
 354     EXPECT_EQ(10*i+5, I.stop());
 355     EXPECT_EQ(i, *I);
 356     ++I;
 357   }
 358   EXPECT_FALSE(I.valid());
 359   EXPECT_TRUE(I == map.end());
 360
 361   // Backwards iteration.
 362   for (unsigned i = 99; i; --i) {
 363     --I;
 364     ASSERT_TRUE(I.valid());
 365     EXPECT_EQ(10*i, I.start());
 366     EXPECT_EQ(10*i+5, I.stop());
 367     EXPECT_EQ(i, *I);
 368   }
 369   EXPECT_TRUE(I == map.begin());
 370
 371   // Test clear() on branched map.
 372   map.clear();
 373   EXPECT_TRUE(map.empty());
 374   EXPECT_TRUE(map.begin() == map.end());
 375 }
 376
 377 // Branched, high, non-coalescing tests.
 378 TEST(IntervalMapTest, Branched2) {
 379   UU4Map::Allocator allocator;
 380   UU4Map map(allocator);
 381
 382   // Insert enough intervals to force a height >= 2 tree.
 383   for (unsigned i = 1; i < 1000; ++i)
 384     map.insert(10*i, 10*i+5, i);
 385
 386   // Tree limits.
 387   EXPECT_FALSE(map.empty());
 388   EXPECT_EQ(10u, map.start());
 389   EXPECT_EQ(9995u, map.stop());
 390
 391   // Tree lookup.
 392   for (unsigned i = 1; i < 1000; ++i) {
 393     EXPECT_EQ(0u, map.lookup(10*i-1));
 394     EXPECT_EQ(i, map.lookup(10*i));
 395     EXPECT_EQ(i, map.lookup(10*i+5));
 396     EXPECT_EQ(0u, map.lookup(10*i+6));
 397   }
 398
 399   // Forward iteration.
 400   UU4Map::iterator I = map.begin();
 401   for (unsigned i = 1; i < 1000; ++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     ++I;
 407   }
 408   EXPECT_FALSE(I.valid());
 409   EXPECT_TRUE(I == map.end());
 410
 411   // Backwards iteration.
 412   for (unsigned i = 999; i; --i) {
 413     --I;
 414     ASSERT_TRUE(I.valid());
 415     EXPECT_EQ(10*i, I.start());
 416     EXPECT_EQ(10*i+5, I.stop());
 417     EXPECT_EQ(i, *I);
 418   }
 419   EXPECT_TRUE(I == map.begin());
 420
 421   // Test clear() on branched map.
 422   map.clear();
 423   EXPECT_TRUE(map.empty());
 424   EXPECT_TRUE(map.begin() == map.end());
 425 }
 426
 427 // Random insertions, coalescing to a single interval.
 428 TEST(IntervalMapTest, RandomCoalescing) {
 429   UU4Map::Allocator allocator;
 430   UU4Map map(allocator);
 431
 432   // This is a poor PRNG with maximal period:
 433   // x_n = 5 x_{n-1} + 1 mod 2^N
 434
 435   unsigned x = 100;
 436   for (unsigned i = 0; i != 4096; ++i) {
 437     map.insert(10*x, 10*x+9, 1);
 438     EXPECT_GE(10*x, map.start());
 439     EXPECT_LE(10*x+9, map.stop());
 440     x = (5*x+1)%4096;
 441   }
 442
 443   // Map should be fully coalesced after that exercise.
 444   EXPECT_FALSE(map.empty());
 445   EXPECT_EQ(0u, map.start());
 446   EXPECT_EQ(40959u, map.stop());
 447   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 448
 449 }
 450
 451 } // namespace