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
  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
  45 // Single entry map tests
  46 TEST(IntervalMapTest, SingleEntryMap) {
  47   UUMap::Allocator allocator;
  48   UUMap map(allocator);
  49   map.insert(100, 150, 1);
  50   EXPECT_FALSE(map.empty());
  51
  52   // Lookup around interval.
  53   EXPECT_EQ(0u, map.lookup(0));
  54   EXPECT_EQ(0u, map.lookup(99));
  55   EXPECT_EQ(1u, map.lookup(100));
  56   EXPECT_EQ(1u, map.lookup(101));
  57   EXPECT_EQ(1u, map.lookup(125));
  58   EXPECT_EQ(1u, map.lookup(149));
  59   EXPECT_EQ(1u, map.lookup(150));
  60   EXPECT_EQ(0u, map.lookup(151));
  61   EXPECT_EQ(0u, map.lookup(200));
  62   EXPECT_EQ(0u, map.lookup(~0u-1));
  63
  64   // Iterators.
  65   EXPECT_TRUE(map.begin() == map.begin());
  66   EXPECT_FALSE(map.begin() == map.end());
  67   EXPECT_TRUE(map.end() == map.end());
  68   EXPECT_TRUE(map.begin().valid());
  69   EXPECT_FALSE(map.end().valid());
  70
  71   // Iter deref.
  72   UUMap::iterator I = map.begin();
  73   ASSERT_TRUE(I.valid());
  74   EXPECT_EQ(100u, I.start());
  75   EXPECT_EQ(150u, I.stop());
  76   EXPECT_EQ(1u, I.value());
  77
  78   // Preincrement.
  79   ++I;
  80   EXPECT_FALSE(I.valid());
  81   EXPECT_FALSE(I == map.begin());
  82   EXPECT_TRUE(I == map.end());
  83
  84   // PreDecrement.
  85   --I;
  86   ASSERT_TRUE(I.valid());
  87   EXPECT_EQ(100u, I.start());
  88   EXPECT_EQ(150u, I.stop());
  89   EXPECT_EQ(1u, I.value());
  90   EXPECT_TRUE(I == map.begin());
  91   EXPECT_FALSE(I == map.end());
  92 }
  93
  94 // Flat coalescing tests.
  95 TEST(IntervalMapTest, RootCoalescing) {
  96   UUMap::Allocator allocator;
  97   UUMap map(allocator);
  98   map.insert(100, 150, 1);
  99
 100   // Coalesce from the left.
 101   map.insert(90, 99, 1);
 102   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 103   EXPECT_EQ(90u, map.start());
 104   EXPECT_EQ(150u, map.stop());
 105
 106   // Overlap left.
 107   map.insert(80, 100, 1);
 108   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 109   EXPECT_EQ(80u, map.start());
 110   EXPECT_EQ(150u, map.stop());
 111
 112   // Inside.
 113   map.insert(100, 130, 1);
 114   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 115   EXPECT_EQ(80u, map.start());
 116   EXPECT_EQ(150u, map.stop());
 117
 118   // Overlap both.
 119   map.insert(70, 160, 1);
 120   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 121   EXPECT_EQ(70u, map.start());
 122   EXPECT_EQ(160u, map.stop());
 123
 124   // Overlap right.
 125   map.insert(80, 170, 1);
 126   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 127   EXPECT_EQ(70u, map.start());
 128   EXPECT_EQ(170u, map.stop());
 129
 130   // Coalesce from the right.
 131   map.insert(170, 200, 1);
 132   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 133   EXPECT_EQ(70u, map.start());
 134   EXPECT_EQ(200u, map.stop());
 135
 136   // Non-coalesce from the left.
 137   map.insert(60, 69, 2);
 138   EXPECT_EQ(2, std::distance(map.begin(), map.end()));
 139   EXPECT_EQ(60u, map.start());
 140   EXPECT_EQ(200u, map.stop());
 141   EXPECT_EQ(2u, map.lookup(69));
 142   EXPECT_EQ(1u, map.lookup(70));
 143
 144   UUMap::iterator I = map.begin();
 145   EXPECT_EQ(60u, I.start());
 146   EXPECT_EQ(69u, I.stop());
 147   EXPECT_EQ(2u, I.value());
 148   ++I;
 149   EXPECT_EQ(70u, I.start());
 150   EXPECT_EQ(200u, I.stop());
 151   EXPECT_EQ(1u, I.value());
 152   ++I;
 153   EXPECT_FALSE(I.valid());
 154
 155   // Non-coalesce from the right.
 156   map.insert(201, 210, 2);
 157   EXPECT_EQ(3, std::distance(map.begin(), map.end()));
 158   EXPECT_EQ(60u, map.start());
 159   EXPECT_EQ(210u, map.stop());
 160   EXPECT_EQ(2u, map.lookup(201));
 161   EXPECT_EQ(1u, map.lookup(200));
 162 }
 163
 164 // Flat multi-coalescing tests.
 165 TEST(IntervalMapTest, RootMultiCoalescing) {
 166   UUMap::Allocator allocator;
 167   UUMap map(allocator);
 168   map.insert(140, 150, 1);
 169   map.insert(160, 170, 1);
 170   map.insert(100, 110, 1);
 171   map.insert(120, 130, 1);
 172   EXPECT_EQ(4, std::distance(map.begin(), map.end()));
 173   EXPECT_EQ(100u, map.start());
 174   EXPECT_EQ(170u, map.stop());
 175
 176   // Verify inserts.
 177   UUMap::iterator I = map.begin();
 178   EXPECT_EQ(100u, I.start());
 179   EXPECT_EQ(110u, I.stop());
 180   ++I;
 181   EXPECT_EQ(120u, I.start());
 182   EXPECT_EQ(130u, I.stop());
 183   ++I;
 184   EXPECT_EQ(140u, I.start());
 185   EXPECT_EQ(150u, I.stop());
 186   ++I;
 187   EXPECT_EQ(160u, I.start());
 188   EXPECT_EQ(170u, I.stop());
 189   ++I;
 190   EXPECT_FALSE(I.valid());
 191
 192
 193   // Coalesce left with followers.
 194   // [100;110] [120;130] [140;150] [160;170]
 195   map.insert(111, 115, 1);
 196   I = map.begin();
 197   ASSERT_TRUE(I.valid());
 198   EXPECT_EQ(100u, I.start());
 199   EXPECT_EQ(115u, I.stop());
 200   ++I;
 201   ASSERT_TRUE(I.valid());
 202   EXPECT_EQ(120u, I.start());
 203   EXPECT_EQ(130u, I.stop());
 204   ++I;
 205   ASSERT_TRUE(I.valid());
 206   EXPECT_EQ(140u, I.start());
 207   EXPECT_EQ(150u, I.stop());
 208   ++I;
 209   ASSERT_TRUE(I.valid());
 210   EXPECT_EQ(160u, I.start());
 211   EXPECT_EQ(170u, I.stop());
 212   ++I;
 213   EXPECT_FALSE(I.valid());
 214
 215   // Coalesce right with followers.
 216   // [100;115] [120;130] [140;150] [160;170]
 217   map.insert(135, 139, 1);
 218   I = map.begin();
 219   ASSERT_TRUE(I.valid());
 220   EXPECT_EQ(100u, I.start());
 221   EXPECT_EQ(115u, I.stop());
 222   ++I;
 223   ASSERT_TRUE(I.valid());
 224   EXPECT_EQ(120u, I.start());
 225   EXPECT_EQ(130u, I.stop());
 226   ++I;
 227   ASSERT_TRUE(I.valid());
 228   EXPECT_EQ(135u, I.start());
 229   EXPECT_EQ(150u, I.stop());
 230   ++I;
 231   ASSERT_TRUE(I.valid());
 232   EXPECT_EQ(160u, I.start());
 233   EXPECT_EQ(170u, I.stop());
 234   ++I;
 235   EXPECT_FALSE(I.valid());
 236
 237   // Coalesce left and right with followers.
 238   // [100;115] [120;130] [135;150] [160;170]
 239   map.insert(131, 134, 1);
 240   I = map.begin();
 241   ASSERT_TRUE(I.valid());
 242   EXPECT_EQ(100u, I.start());
 243   EXPECT_EQ(115u, I.stop());
 244   ++I;
 245   ASSERT_TRUE(I.valid());
 246   EXPECT_EQ(120u, I.start());
 247   EXPECT_EQ(150u, I.stop());
 248   ++I;
 249   ASSERT_TRUE(I.valid());
 250   EXPECT_EQ(160u, I.start());
 251   EXPECT_EQ(170u, I.stop());
 252   ++I;
 253   EXPECT_FALSE(I.valid());
 254
 255   // Coalesce multiple with overlap right.
 256   // [100;115] [120;150] [160;170]
 257   map.insert(116, 165, 1);
 258   I = map.begin();
 259   ASSERT_TRUE(I.valid());
 260   EXPECT_EQ(100u, I.start());
 261   EXPECT_EQ(170u, I.stop());
 262   ++I;
 263   EXPECT_FALSE(I.valid());
 264
 265   // Coalesce multiple with overlap left
 266   // [100;170]
 267   map.insert(180, 190, 1);
 268   map.insert(200, 210, 1);
 269   map.insert(220, 230, 1);
 270   // [100;170] [180;190] [200;210] [220;230]
 271   map.insert(160, 199, 1);
 272   I = map.begin();
 273   ASSERT_TRUE(I.valid());
 274   EXPECT_EQ(100u, I.start());
 275   EXPECT_EQ(210u, I.stop());
 276   ++I;
 277   ASSERT_TRUE(I.valid());
 278   EXPECT_EQ(220u, I.start());
 279   EXPECT_EQ(230u, I.stop());
 280   ++I;
 281   EXPECT_FALSE(I.valid());
 282
 283   // Overwrite 2 from gap to gap.
 284   // [100;210] [220;230]
 285   map.insert(50, 250, 1);
 286   I = map.begin();
 287   ASSERT_TRUE(I.valid());
 288   EXPECT_EQ(50u, I.start());
 289   EXPECT_EQ(250u, I.stop());
 290   ++I;
 291   EXPECT_FALSE(I.valid());
 292
 293   // Coalesce at end of full root.
 294   // [50;250]
 295   map.insert(260, 270, 1);
 296   map.insert(280, 290, 1);
 297   map.insert(300, 310, 1);
 298   // [50;250] [260;270] [280;290] [300;310]
 299   map.insert(311, 320, 1);
 300   I = map.begin();
 301   ASSERT_TRUE(I.valid());
 302   EXPECT_EQ(50u, I.start());
 303   EXPECT_EQ(250u, I.stop());
 304   ++I;
 305   ASSERT_TRUE(I.valid());
 306   EXPECT_EQ(260u, I.start());
 307   EXPECT_EQ(270u, I.stop());
 308   ++I;
 309   ASSERT_TRUE(I.valid());
 310   EXPECT_EQ(280u, I.start());
 311   EXPECT_EQ(290u, I.stop());
 312   ++I;
 313   ASSERT_TRUE(I.valid());
 314   EXPECT_EQ(300u, I.start());
 315   EXPECT_EQ(320u, I.stop());
 316   ++I;
 317   EXPECT_FALSE(I.valid());
 318 }
 319
 320 // Branched, non-coalescing tests.
 321 TEST(IntervalMapTest, Branched) {
 322   UUMap::Allocator allocator;
 323   UUMap map(allocator);
 324
 325   // Insert enough intervals to force a branched tree.
 326   // This creates 9 leaf nodes with 11 elements each, tree height = 1.
 327   for (unsigned i = 1; i < 100; ++i)
 328     map.insert(10*i, 10*i+5, i);
 329
 330   // Tree limits.
 331   EXPECT_FALSE(map.empty());
 332   EXPECT_EQ(10u, map.start());
 333   EXPECT_EQ(995u, map.stop());
 334
 335   // Tree lookup.
 336   for (unsigned i = 1; i < 100; ++i) {
 337     EXPECT_EQ(0u, map.lookup(10*i-1));
 338     EXPECT_EQ(i, map.lookup(10*i));
 339     EXPECT_EQ(i, map.lookup(10*i+5));
 340     EXPECT_EQ(0u, map.lookup(10*i+6));
 341   }
 342
 343   // Forward iteration.
 344   UUMap::iterator I = map.begin();
 345   for (unsigned i = 1; i < 100; ++i) {
 346     ASSERT_TRUE(I.valid());
 347     EXPECT_EQ(10*i, I.start());
 348     EXPECT_EQ(10*i+5, I.stop());
 349     EXPECT_EQ(i, *I);
 350     ++I;
 351   }
 352   EXPECT_FALSE(I.valid());
 353   EXPECT_TRUE(I == map.end());
 354
 355   // Backwards iteration.
 356   for (unsigned i = 99; i; --i) {
 357     --I;
 358     ASSERT_TRUE(I.valid());
 359     EXPECT_EQ(10*i, I.start());
 360     EXPECT_EQ(10*i+5, I.stop());
 361     EXPECT_EQ(i, *I);
 362   }
 363   EXPECT_TRUE(I == map.begin());
 364
 365 }
 366
 367 } // namespace