llvm/unittests/ADT/IntervalMapTest.cpp

   1 //===---- ADT/IntervalMapTest.cpp - IntervalMap unit tests ------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/IntervalMap.h"
  10 #include "gtest/gtest.h"
  11 #include <type_traits>
  12
  13 using namespace llvm;
  14
  15 namespace {
  16
  17 typedef IntervalMap<unsigned, unsigned, 4> UUMap;
  18 typedef IntervalMap<unsigned, unsigned, 4,
  19                     IntervalMapHalfOpenInfo<unsigned>> UUHalfOpenMap;
  20
  21 // Empty map tests
  22 TEST(IntervalMapTest, EmptyMap) {
  23   UUMap::Allocator allocator;
  24   UUMap map(allocator);
  25   EXPECT_TRUE(map.empty());
  26
  27   // Lookup on empty map.
  28   EXPECT_EQ(0u, map.lookup(0));
  29   EXPECT_EQ(7u, map.lookup(0, 7));
  30   EXPECT_EQ(0u, map.lookup(~0u-1));
  31   EXPECT_EQ(7u, map.lookup(~0u-1, 7));
  32
  33   // Iterators.
  34   EXPECT_TRUE(map.begin() == map.begin());
  35   EXPECT_TRUE(map.begin() == map.end());
  36   EXPECT_TRUE(map.end() == map.end());
  37   EXPECT_FALSE(map.begin() != map.begin());
  38   EXPECT_FALSE(map.begin() != map.end());
  39   EXPECT_FALSE(map.end() != map.end());
  40   EXPECT_FALSE(map.begin().valid());
  41   EXPECT_FALSE(map.end().valid());
  42   UUMap::iterator I = map.begin();
  43   EXPECT_FALSE(I.valid());
  44   EXPECT_TRUE(I == map.end());
  45
  46   // Default constructor and cross-constness compares.
  47   UUMap::const_iterator CI;
  48   CI = map.begin();
  49   EXPECT_TRUE(CI == I);
  50   UUMap::iterator I2;
  51   I2 = map.end();
  52   EXPECT_TRUE(I2 == CI);
  53 }
  54
  55 // Test one-element closed ranges.
  56 TEST(IntervalMapTest, OneElementRanges) {
  57   UUMap::Allocator allocator;
  58   UUMap map(allocator);
  59   map.insert(1, 1, 1);
  60   map.insert(2, 2, 2);
  61   EXPECT_EQ(1u, map.lookup(1));
  62   EXPECT_EQ(2u, map.lookup(2));
  63 }
  64
  65 // Single entry map tests
  66 TEST(IntervalMapTest, SingleEntryMap) {
  67   UUMap::Allocator allocator;
  68   UUMap map(allocator);
  69   map.insert(100, 150, 1);
  70   EXPECT_FALSE(map.empty());
  71
  72   // Lookup around interval.
  73   EXPECT_EQ(0u, map.lookup(0));
  74   EXPECT_EQ(0u, map.lookup(99));
  75   EXPECT_EQ(1u, map.lookup(100));
  76   EXPECT_EQ(1u, map.lookup(101));
  77   EXPECT_EQ(1u, map.lookup(125));
  78   EXPECT_EQ(1u, map.lookup(149));
  79   EXPECT_EQ(1u, map.lookup(150));
  80   EXPECT_EQ(0u, map.lookup(151));
  81   EXPECT_EQ(0u, map.lookup(200));
  82   EXPECT_EQ(0u, map.lookup(~0u-1));
  83
  84   // Iterators.
  85   EXPECT_TRUE(map.begin() == map.begin());
  86   EXPECT_FALSE(map.begin() == map.end());
  87   EXPECT_TRUE(map.end() == map.end());
  88   EXPECT_TRUE(map.begin().valid());
  89   EXPECT_FALSE(map.end().valid());
  90
  91   // Iter deref.
  92   UUMap::iterator I = map.begin();
  93   ASSERT_TRUE(I.valid());
  94   EXPECT_EQ(100u, I.start());
  95   EXPECT_EQ(150u, I.stop());
  96   EXPECT_EQ(1u, I.value());
  97
  98   // Preincrement.
  99   ++I;
 100   EXPECT_FALSE(I.valid());
 101   EXPECT_FALSE(I == map.begin());
 102   EXPECT_TRUE(I == map.end());
 103
 104   // PreDecrement.
 105   --I;
 106   ASSERT_TRUE(I.valid());
 107   EXPECT_EQ(100u, I.start());
 108   EXPECT_EQ(150u, I.stop());
 109   EXPECT_EQ(1u, I.value());
 110   EXPECT_TRUE(I == map.begin());
 111   EXPECT_FALSE(I == map.end());
 112
 113   // Change the value.
 114   I.setValue(2);
 115   ASSERT_TRUE(I.valid());
 116   EXPECT_EQ(100u, I.start());
 117   EXPECT_EQ(150u, I.stop());
 118   EXPECT_EQ(2u, I.value());
 119
 120   // Grow the bounds.
 121   I.setStart(0);
 122   ASSERT_TRUE(I.valid());
 123   EXPECT_EQ(0u, I.start());
 124   EXPECT_EQ(150u, I.stop());
 125   EXPECT_EQ(2u, I.value());
 126
 127   I.setStop(200);
 128   ASSERT_TRUE(I.valid());
 129   EXPECT_EQ(0u, I.start());
 130   EXPECT_EQ(200u, I.stop());
 131   EXPECT_EQ(2u, I.value());
 132
 133   // Shrink the bounds.
 134   I.setStart(150);
 135   ASSERT_TRUE(I.valid());
 136   EXPECT_EQ(150u, I.start());
 137   EXPECT_EQ(200u, I.stop());
 138   EXPECT_EQ(2u, I.value());
 139
 140   // Shrink the interval to have a length of 1
 141   I.setStop(150);
 142   ASSERT_TRUE(I.valid());
 143   EXPECT_EQ(150u, I.start());
 144   EXPECT_EQ(150u, I.stop());
 145   EXPECT_EQ(2u, I.value());
 146
 147   I.setStop(160);
 148   ASSERT_TRUE(I.valid());
 149   EXPECT_EQ(150u, I.start());
 150   EXPECT_EQ(160u, I.stop());
 151   EXPECT_EQ(2u, I.value());
 152
 153   // Shrink the interval to have a length of 1
 154   I.setStart(160);
 155   ASSERT_TRUE(I.valid());
 156   EXPECT_EQ(160u, I.start());
 157   EXPECT_EQ(160u, I.stop());
 158   EXPECT_EQ(2u, I.value());
 159
 160   // Erase last elem.
 161   I.erase();
 162   EXPECT_TRUE(map.empty());
 163   EXPECT_EQ(0, std::distance(map.begin(), map.end()));
 164 }
 165
 166 // Single entry half-open map tests
 167 TEST(IntervalMapTest, SingleEntryHalfOpenMap) {
 168   UUHalfOpenMap::Allocator allocator;
 169   UUHalfOpenMap map(allocator);
 170   map.insert(100, 150, 1);
 171   EXPECT_FALSE(map.empty());
 172
 173   UUHalfOpenMap::iterator I = map.begin();
 174   ASSERT_TRUE(I.valid());
 175
 176   // Shrink the interval to have a length of 1
 177   I.setStart(149);
 178   ASSERT_TRUE(I.valid());
 179   EXPECT_EQ(149u, I.start());
 180   EXPECT_EQ(150u, I.stop());
 181   EXPECT_EQ(1u, I.value());
 182
 183   I.setStop(160);
 184   ASSERT_TRUE(I.valid());
 185   EXPECT_EQ(149u, I.start());
 186   EXPECT_EQ(160u, I.stop());
 187   EXPECT_EQ(1u, I.value());
 188
 189   // Shrink the interval to have a length of 1
 190   I.setStop(150);
 191   ASSERT_TRUE(I.valid());
 192   EXPECT_EQ(149u, I.start());
 193   EXPECT_EQ(150u, I.stop());
 194   EXPECT_EQ(1u, I.value());
 195 }
 196
 197 // Flat coalescing tests.
 198 TEST(IntervalMapTest, RootCoalescing) {
 199   UUMap::Allocator allocator;
 200   UUMap map(allocator);
 201   map.insert(100, 150, 1);
 202
 203   // Coalesce from the left.
 204   map.insert(90, 99, 1);
 205   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 206   EXPECT_EQ(90u, map.start());
 207   EXPECT_EQ(150u, map.stop());
 208
 209   // Coalesce from the right.
 210   map.insert(151, 200, 1);
 211   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 212   EXPECT_EQ(90u, map.start());
 213   EXPECT_EQ(200u, map.stop());
 214
 215   // Non-coalesce from the left.
 216   map.insert(60, 89, 2);
 217   EXPECT_EQ(2, std::distance(map.begin(), map.end()));
 218   EXPECT_EQ(60u, map.start());
 219   EXPECT_EQ(200u, map.stop());
 220   EXPECT_EQ(2u, map.lookup(89));
 221   EXPECT_EQ(1u, map.lookup(90));
 222
 223   UUMap::iterator I = map.begin();
 224   EXPECT_EQ(60u, I.start());
 225   EXPECT_EQ(89u, I.stop());
 226   EXPECT_EQ(2u, I.value());
 227   ++I;
 228   EXPECT_EQ(90u, I.start());
 229   EXPECT_EQ(200u, I.stop());
 230   EXPECT_EQ(1u, I.value());
 231   ++I;
 232   EXPECT_FALSE(I.valid());
 233
 234   // Non-coalesce from the right.
 235   map.insert(201, 210, 2);
 236   EXPECT_EQ(3, std::distance(map.begin(), map.end()));
 237   EXPECT_EQ(60u, map.start());
 238   EXPECT_EQ(210u, map.stop());
 239   EXPECT_EQ(2u, map.lookup(201));
 240   EXPECT_EQ(1u, map.lookup(200));
 241
 242   // Erase from the left.
 243   map.begin().erase();
 244   EXPECT_EQ(2, std::distance(map.begin(), map.end()));
 245   EXPECT_EQ(90u, map.start());
 246   EXPECT_EQ(210u, map.stop());
 247
 248   // Erase from the right.
 249   (--map.end()).erase();
 250   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 251   EXPECT_EQ(90u, map.start());
 252   EXPECT_EQ(200u, map.stop());
 253
 254   // Add non-coalescing, then trigger coalescing with setValue.
 255   map.insert(80, 89, 2);
 256   map.insert(201, 210, 2);
 257   EXPECT_EQ(3, std::distance(map.begin(), map.end()));
 258   (++map.begin()).setValue(2);
 259   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 260   I = map.begin();
 261   ASSERT_TRUE(I.valid());
 262   EXPECT_EQ(80u, I.start());
 263   EXPECT_EQ(210u, I.stop());
 264   EXPECT_EQ(2u, I.value());
 265 }
 266
 267 // Flat multi-coalescing tests.
 268 TEST(IntervalMapTest, RootMultiCoalescing) {
 269   UUMap::Allocator allocator;
 270   UUMap map(allocator);
 271   map.insert(140, 150, 1);
 272   map.insert(160, 170, 1);
 273   map.insert(100, 110, 1);
 274   map.insert(120, 130, 1);
 275   EXPECT_EQ(4, std::distance(map.begin(), map.end()));
 276   EXPECT_EQ(100u, map.start());
 277   EXPECT_EQ(170u, map.stop());
 278
 279   // Verify inserts.
 280   UUMap::iterator I = map.begin();
 281   EXPECT_EQ(100u, I.start());
 282   EXPECT_EQ(110u, I.stop());
 283   ++I;
 284   EXPECT_EQ(120u, I.start());
 285   EXPECT_EQ(130u, I.stop());
 286   ++I;
 287   EXPECT_EQ(140u, I.start());
 288   EXPECT_EQ(150u, I.stop());
 289   ++I;
 290   EXPECT_EQ(160u, I.start());
 291   EXPECT_EQ(170u, I.stop());
 292   ++I;
 293   EXPECT_FALSE(I.valid());
 294
 295   // Test advanceTo on flat tree.
 296   I = map.begin();
 297   I.advanceTo(135);
 298   ASSERT_TRUE(I.valid());
 299   EXPECT_EQ(140u, I.start());
 300   EXPECT_EQ(150u, I.stop());
 301
 302   I.advanceTo(145);
 303   ASSERT_TRUE(I.valid());
 304   EXPECT_EQ(140u, I.start());
 305   EXPECT_EQ(150u, I.stop());
 306
 307   I.advanceTo(200);
 308   EXPECT_FALSE(I.valid());
 309
 310   I.advanceTo(300);
 311   EXPECT_FALSE(I.valid());
 312
 313   // Coalesce left with followers.
 314   // [100;110] [120;130] [140;150] [160;170]
 315   map.insert(111, 115, 1);
 316   I = map.begin();
 317   ASSERT_TRUE(I.valid());
 318   EXPECT_EQ(100u, I.start());
 319   EXPECT_EQ(115u, I.stop());
 320   ++I;
 321   ASSERT_TRUE(I.valid());
 322   EXPECT_EQ(120u, I.start());
 323   EXPECT_EQ(130u, I.stop());
 324   ++I;
 325   ASSERT_TRUE(I.valid());
 326   EXPECT_EQ(140u, I.start());
 327   EXPECT_EQ(150u, I.stop());
 328   ++I;
 329   ASSERT_TRUE(I.valid());
 330   EXPECT_EQ(160u, I.start());
 331   EXPECT_EQ(170u, I.stop());
 332   ++I;
 333   EXPECT_FALSE(I.valid());
 334
 335   // Coalesce right with followers.
 336   // [100;115] [120;130] [140;150] [160;170]
 337   map.insert(135, 139, 1);
 338   I = map.begin();
 339   ASSERT_TRUE(I.valid());
 340   EXPECT_EQ(100u, I.start());
 341   EXPECT_EQ(115u, I.stop());
 342   ++I;
 343   ASSERT_TRUE(I.valid());
 344   EXPECT_EQ(120u, I.start());
 345   EXPECT_EQ(130u, I.stop());
 346   ++I;
 347   ASSERT_TRUE(I.valid());
 348   EXPECT_EQ(135u, I.start());
 349   EXPECT_EQ(150u, I.stop());
 350   ++I;
 351   ASSERT_TRUE(I.valid());
 352   EXPECT_EQ(160u, I.start());
 353   EXPECT_EQ(170u, I.stop());
 354   ++I;
 355   EXPECT_FALSE(I.valid());
 356
 357   // Coalesce left and right with followers.
 358   // [100;115] [120;130] [135;150] [160;170]
 359   map.insert(131, 134, 1);
 360   I = map.begin();
 361   ASSERT_TRUE(I.valid());
 362   EXPECT_EQ(100u, I.start());
 363   EXPECT_EQ(115u, I.stop());
 364   ++I;
 365   ASSERT_TRUE(I.valid());
 366   EXPECT_EQ(120u, I.start());
 367   EXPECT_EQ(150u, I.stop());
 368   ++I;
 369   ASSERT_TRUE(I.valid());
 370   EXPECT_EQ(160u, I.start());
 371   EXPECT_EQ(170u, I.stop());
 372   ++I;
 373   EXPECT_FALSE(I.valid());
 374
 375   // Test clear() on non-branched map.
 376   map.clear();
 377   EXPECT_TRUE(map.empty());
 378   EXPECT_TRUE(map.begin() == map.end());
 379 }
 380
 381 // Branched, non-coalescing tests.
 382 TEST(IntervalMapTest, Branched) {
 383   UUMap::Allocator allocator;
 384   UUMap map(allocator);
 385
 386   // Insert enough intervals to force a branched tree.
 387   // This creates 9 leaf nodes with 11 elements each, tree height = 1.
 388   for (unsigned i = 1; i < 100; ++i) {
 389     map.insert(10*i, 10*i+5, i);
 390     EXPECT_EQ(10u, map.start());
 391     EXPECT_EQ(10*i+5, map.stop());
 392   }
 393
 394   // Tree limits.
 395   EXPECT_FALSE(map.empty());
 396   EXPECT_EQ(10u, map.start());
 397   EXPECT_EQ(995u, map.stop());
 398
 399   // Tree lookup.
 400   for (unsigned i = 1; i < 100; ++i) {
 401     EXPECT_EQ(0u, map.lookup(10*i-1));
 402     EXPECT_EQ(i, map.lookup(10*i));
 403     EXPECT_EQ(i, map.lookup(10*i+5));
 404     EXPECT_EQ(0u, map.lookup(10*i+6));
 405   }
 406
 407   // Forward iteration.
 408   UUMap::iterator I = map.begin();
 409   for (unsigned i = 1; i < 100; ++i) {
 410     ASSERT_TRUE(I.valid());
 411     EXPECT_EQ(10*i, I.start());
 412     EXPECT_EQ(10*i+5, I.stop());
 413     EXPECT_EQ(i, *I);
 414     ++I;
 415   }
 416   EXPECT_FALSE(I.valid());
 417   EXPECT_TRUE(I == map.end());
 418
 419   // Backwards iteration.
 420   for (unsigned i = 99; i; --i) {
 421     --I;
 422     ASSERT_TRUE(I.valid());
 423     EXPECT_EQ(10*i, I.start());
 424     EXPECT_EQ(10*i+5, I.stop());
 425     EXPECT_EQ(i, *I);
 426   }
 427   EXPECT_TRUE(I == map.begin());
 428
 429   // Test advanceTo in same node.
 430   I.advanceTo(20);
 431   ASSERT_TRUE(I.valid());
 432   EXPECT_EQ(20u, I.start());
 433   EXPECT_EQ(25u, I.stop());
 434
 435   // Change value, no coalescing.
 436   I.setValue(0);
 437   ASSERT_TRUE(I.valid());
 438   EXPECT_EQ(20u, I.start());
 439   EXPECT_EQ(25u, I.stop());
 440   EXPECT_EQ(0u, I.value());
 441
 442   // Close the gap right, no coalescing.
 443   I.setStop(29);
 444   ASSERT_TRUE(I.valid());
 445   EXPECT_EQ(20u, I.start());
 446   EXPECT_EQ(29u, I.stop());
 447   EXPECT_EQ(0u, I.value());
 448
 449   // Change value, no coalescing.
 450   I.setValue(2);
 451   ASSERT_TRUE(I.valid());
 452   EXPECT_EQ(20u, I.start());
 453   EXPECT_EQ(29u, I.stop());
 454   EXPECT_EQ(2u, I.value());
 455
 456   // Change value, now coalescing.
 457   I.setValue(3);
 458   ASSERT_TRUE(I.valid());
 459   EXPECT_EQ(20u, I.start());
 460   EXPECT_EQ(35u, I.stop());
 461   EXPECT_EQ(3u, I.value());
 462
 463   // Close the gap, now coalescing.
 464   I.setValue(4);
 465   ASSERT_TRUE(I.valid());
 466   I.setStop(39);
 467   ASSERT_TRUE(I.valid());
 468   EXPECT_EQ(20u, I.start());
 469   EXPECT_EQ(45u, I.stop());
 470   EXPECT_EQ(4u, I.value());
 471
 472   // advanceTo another node.
 473   I.advanceTo(200);
 474   ASSERT_TRUE(I.valid());
 475   EXPECT_EQ(200u, I.start());
 476   EXPECT_EQ(205u, I.stop());
 477
 478   // Close the gap left, no coalescing.
 479   I.setStart(196);
 480   ASSERT_TRUE(I.valid());
 481   EXPECT_EQ(196u, I.start());
 482   EXPECT_EQ(205u, I.stop());
 483   EXPECT_EQ(20u, I.value());
 484
 485   // Change value, no coalescing.
 486   I.setValue(0);
 487   ASSERT_TRUE(I.valid());
 488   EXPECT_EQ(196u, I.start());
 489   EXPECT_EQ(205u, I.stop());
 490   EXPECT_EQ(0u, I.value());
 491
 492   // Change value, now coalescing.
 493   I.setValue(19);
 494   ASSERT_TRUE(I.valid());
 495   EXPECT_EQ(190u, I.start());
 496   EXPECT_EQ(205u, I.stop());
 497   EXPECT_EQ(19u, I.value());
 498
 499   // Close the gap, now coalescing.
 500   I.setValue(18);
 501   ASSERT_TRUE(I.valid());
 502   I.setStart(186);
 503   ASSERT_TRUE(I.valid());
 504   EXPECT_EQ(180u, I.start());
 505   EXPECT_EQ(205u, I.stop());
 506   EXPECT_EQ(18u, I.value());
 507
 508   // Erase from the front.
 509   I = map.begin();
 510   for (unsigned i = 0; i != 20; ++i) {
 511     I.erase();
 512     EXPECT_TRUE(I == map.begin());
 513     EXPECT_FALSE(map.empty());
 514     EXPECT_EQ(I.start(), map.start());
 515     EXPECT_EQ(995u, map.stop());
 516   }
 517
 518   // Test clear() on branched map.
 519   map.clear();
 520   EXPECT_TRUE(map.empty());
 521   EXPECT_TRUE(map.begin() == map.end());
 522 }
 523
 524 // Branched, high, non-coalescing tests.
 525 TEST(IntervalMapTest, Branched2) {
 526   UUMap::Allocator allocator;
 527   UUMap map(allocator);
 528
 529   // Insert enough intervals to force a height >= 2 tree.
 530   for (unsigned i = 1; i < 1000; ++i)
 531     map.insert(10*i, 10*i+5, i);
 532
 533   // Tree limits.
 534   EXPECT_FALSE(map.empty());
 535   EXPECT_EQ(10u, map.start());
 536   EXPECT_EQ(9995u, map.stop());
 537
 538   // Tree lookup.
 539   for (unsigned i = 1; i < 1000; ++i) {
 540     EXPECT_EQ(0u, map.lookup(10*i-1));
 541     EXPECT_EQ(i, map.lookup(10*i));
 542     EXPECT_EQ(i, map.lookup(10*i+5));
 543     EXPECT_EQ(0u, map.lookup(10*i+6));
 544   }
 545
 546   // Forward iteration.
 547   UUMap::iterator I = map.begin();
 548   for (unsigned i = 1; i < 1000; ++i) {
 549     ASSERT_TRUE(I.valid());
 550     EXPECT_EQ(10*i, I.start());
 551     EXPECT_EQ(10*i+5, I.stop());
 552     EXPECT_EQ(i, *I);
 553     ++I;
 554   }
 555   EXPECT_FALSE(I.valid());
 556   EXPECT_TRUE(I == map.end());
 557
 558   // Backwards iteration.
 559   for (unsigned i = 999; i; --i) {
 560     --I;
 561     ASSERT_TRUE(I.valid());
 562     EXPECT_EQ(10*i, I.start());
 563     EXPECT_EQ(10*i+5, I.stop());
 564     EXPECT_EQ(i, *I);
 565   }
 566   EXPECT_TRUE(I == map.begin());
 567
 568   // Test advanceTo in same node.
 569   I.advanceTo(20);
 570   ASSERT_TRUE(I.valid());
 571   EXPECT_EQ(20u, I.start());
 572   EXPECT_EQ(25u, I.stop());
 573
 574   // advanceTo sibling leaf node.
 575   I.advanceTo(200);
 576   ASSERT_TRUE(I.valid());
 577   EXPECT_EQ(200u, I.start());
 578   EXPECT_EQ(205u, I.stop());
 579
 580   // advanceTo further.
 581   I.advanceTo(2000);
 582   ASSERT_TRUE(I.valid());
 583   EXPECT_EQ(2000u, I.start());
 584   EXPECT_EQ(2005u, I.stop());
 585
 586   // advanceTo beyond end()
 587   I.advanceTo(20000);
 588   EXPECT_FALSE(I.valid());
 589
 590   // end().advanceTo() is valid as long as x > map.stop()
 591   I.advanceTo(30000);
 592   EXPECT_FALSE(I.valid());
 593
 594   // Test clear() on branched map.
 595   map.clear();
 596   EXPECT_TRUE(map.empty());
 597   EXPECT_TRUE(map.begin() == map.end());
 598 }
 599
 600 // Random insertions, coalescing to a single interval.
 601 TEST(IntervalMapTest, RandomCoalescing) {
 602   UUMap::Allocator allocator;
 603   UUMap map(allocator);
 604
 605   // This is a poor PRNG with maximal period:
 606   // x_n = 5 x_{n-1} + 1 mod 2^N
 607
 608   unsigned x = 100;
 609   for (unsigned i = 0; i != 4096; ++i) {
 610     map.insert(10*x, 10*x+9, 1);
 611     EXPECT_GE(10*x, map.start());
 612     EXPECT_LE(10*x+9, map.stop());
 613     x = (5*x+1)%4096;
 614   }
 615
 616   // Map should be fully coalesced after that exercise.
 617   EXPECT_FALSE(map.empty());
 618   EXPECT_EQ(0u, map.start());
 619   EXPECT_EQ(40959u, map.stop());
 620   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 621
 622 }
 623
 624 static void setupOverlaps(UUMap &M) {
 625   M.insert(10, 20, 0);
 626   M.insert(30, 40, 0);
 627   M.insert(50, 60, 0);
 628   // Add extra nodes to force allocations.
 629   for (int i = 70; i < 100; i += 2)
 630     M.insert(i, i + 1, i);
 631 }
 632
 633 static void checkOverlaps(UUMap &M) {
 634   EXPECT_FALSE(M.overlaps(0, 9));
 635   EXPECT_TRUE(M.overlaps(0, 10));
 636   EXPECT_TRUE(M.overlaps(0, 15));
 637   EXPECT_TRUE(M.overlaps(0, 25));
 638   EXPECT_TRUE(M.overlaps(0, 45));
 639   EXPECT_TRUE(M.overlaps(10, 45));
 640   EXPECT_TRUE(M.overlaps(30, 45));
 641   EXPECT_TRUE(M.overlaps(35, 36));
 642   EXPECT_TRUE(M.overlaps(40, 45));
 643   EXPECT_FALSE(M.overlaps(45, 45));
 644   EXPECT_TRUE(M.overlaps(60, 60));
 645   EXPECT_TRUE(M.overlaps(60, 66));
 646   EXPECT_FALSE(M.overlaps(66, 66));
 647 }
 648
 649 TEST(IntervalMapTest, Copy) {
 650   // Test that copy assignment and initialization works.
 651   UUHalfOpenMap::Allocator Allocator;
 652   UUMap Src(Allocator);
 653   setupOverlaps(Src);
 654
 655   UUMap CopyAssignmentDst(Allocator);
 656   CopyAssignmentDst = Src;
 657
 658   UUMap CopyInitDst(Src);
 659
 660   checkOverlaps(Src);
 661   Src.clear();
 662
 663   checkOverlaps(CopyAssignmentDst);
 664   checkOverlaps(CopyInitDst);
 665 }
 666
 667 TEST(IntervalMapTest, Move) {
 668   // Test that move assignment and initialization works.
 669   UUHalfOpenMap::Allocator Allocator;
 670   // Double check that MoveAssignmentDst owns all its data by moving from an
 671   // object that is destroyed before we call checkOverlaps.
 672   UUMap MoveAssignmentDst(Allocator);
 673   {
 674     UUMap Src(Allocator);
 675     setupOverlaps(Src);
 676     MoveAssignmentDst = std::move(Src);
 677   }
 678   checkOverlaps(MoveAssignmentDst);
 679
 680   UUMap MoveInitSrc(Allocator);
 681   setupOverlaps(MoveInitSrc);
 682   UUMap MoveInitDst(std::move(MoveInitSrc));
 683   checkOverlaps(MoveInitDst);
 684 }
 685
 686 TEST(IntervalMapTest, Overlaps) {
 687   UUMap::Allocator allocator;
 688   UUMap map(allocator);
 689   setupOverlaps(map);
 690   checkOverlaps(map);
 691 }
 692
 693 TEST(IntervalMapTest, OverlapsHalfOpen) {
 694   UUHalfOpenMap::Allocator allocator;
 695   UUHalfOpenMap map(allocator);
 696   map.insert(10, 20, 0);
 697   map.insert(30, 40, 0);
 698   map.insert(50, 60, 0);
 699
 700   EXPECT_FALSE(map.overlaps(0, 9));
 701   EXPECT_FALSE(map.overlaps(0, 10));
 702   EXPECT_TRUE(map.overlaps(0, 15));
 703   EXPECT_TRUE(map.overlaps(0, 25));
 704   EXPECT_TRUE(map.overlaps(0, 45));
 705   EXPECT_TRUE(map.overlaps(10, 45));
 706   EXPECT_TRUE(map.overlaps(30, 45));
 707   EXPECT_TRUE(map.overlaps(35, 36));
 708   EXPECT_FALSE(map.overlaps(40, 45));
 709   EXPECT_FALSE(map.overlaps(45, 46));
 710   EXPECT_FALSE(map.overlaps(60, 61));
 711   EXPECT_FALSE(map.overlaps(60, 66));
 712   EXPECT_FALSE(map.overlaps(66, 67));
 713 }
 714
 715 TEST(IntervalMapOverlapsTest, SmallMaps) {
 716   typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps;
 717   UUMap::Allocator allocator;
 718   UUMap mapA(allocator);
 719   UUMap mapB(allocator);
 720
 721   // empty, empty.
 722   EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
 723
 724   mapA.insert(1, 2, 3);
 725
 726   // full, empty
 727   EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
 728   // empty, full
 729   EXPECT_FALSE(UUOverlaps(mapB, mapA).valid());
 730
 731   mapB.insert(3, 4, 5);
 732
 733   // full, full, non-overlapping
 734   EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
 735   EXPECT_FALSE(UUOverlaps(mapB, mapA).valid());
 736
 737   // Add an overlapping segment.
 738   mapA.insert(4, 5, 6);
 739
 740   UUOverlaps AB(mapA, mapB);
 741   ASSERT_TRUE(AB.valid());
 742   EXPECT_EQ(4u, AB.a().start());
 743   EXPECT_EQ(3u, AB.b().start());
 744   ++AB;
 745   EXPECT_FALSE(AB.valid());
 746
 747   UUOverlaps BA(mapB, mapA);
 748   ASSERT_TRUE(BA.valid());
 749   EXPECT_EQ(3u, BA.a().start());
 750   EXPECT_EQ(4u, BA.b().start());
 751   // advance past end.
 752   BA.advanceTo(6);
 753   EXPECT_FALSE(BA.valid());
 754   // advance an invalid iterator.
 755   BA.advanceTo(7);
 756   EXPECT_FALSE(BA.valid());
 757 }
 758
 759 TEST(IntervalMapOverlapsTest, BigMaps) {
 760   typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps;
 761   UUMap::Allocator allocator;
 762   UUMap mapA(allocator);
 763   UUMap mapB(allocator);
 764
 765   // [0;4] [10;14] [20;24] ...
 766   for (unsigned n = 0; n != 100; ++n)
 767     mapA.insert(10*n, 10*n+4, n);
 768
 769   // [5;6] [15;16] [25;26] ...
 770   for (unsigned n = 10; n != 20; ++n)
 771     mapB.insert(10*n+5, 10*n+6, n);
 772
 773   // [208;209] [218;219] ...
 774   for (unsigned n = 20; n != 30; ++n)
 775     mapB.insert(10*n+8, 10*n+9, n);
 776
 777   // insert some overlapping segments.
 778   mapB.insert(400, 400, 400);
 779   mapB.insert(401, 401, 401);
 780   mapB.insert(402, 500, 402);
 781   mapB.insert(600, 601, 402);
 782
 783   UUOverlaps AB(mapA, mapB);
 784   ASSERT_TRUE(AB.valid());
 785   EXPECT_EQ(400u, AB.a().start());
 786   EXPECT_EQ(400u, AB.b().start());
 787   ++AB;
 788   ASSERT_TRUE(AB.valid());
 789   EXPECT_EQ(400u, AB.a().start());
 790   EXPECT_EQ(401u, AB.b().start());
 791   ++AB;
 792   ASSERT_TRUE(AB.valid());
 793   EXPECT_EQ(400u, AB.a().start());
 794   EXPECT_EQ(402u, AB.b().start());
 795   ++AB;
 796   ASSERT_TRUE(AB.valid());
 797   EXPECT_EQ(410u, AB.a().start());
 798   EXPECT_EQ(402u, AB.b().start());
 799   ++AB;
 800   ASSERT_TRUE(AB.valid());
 801   EXPECT_EQ(420u, AB.a().start());
 802   EXPECT_EQ(402u, AB.b().start());
 803   AB.skipB();
 804   ASSERT_TRUE(AB.valid());
 805   EXPECT_EQ(600u, AB.a().start());
 806   EXPECT_EQ(600u, AB.b().start());
 807   ++AB;
 808   EXPECT_FALSE(AB.valid());
 809
 810   // Test advanceTo.
 811   UUOverlaps AB2(mapA, mapB);
 812   AB2.advanceTo(410);
 813   ASSERT_TRUE(AB2.valid());
 814   EXPECT_EQ(410u, AB2.a().start());
 815   EXPECT_EQ(402u, AB2.b().start());
 816
 817   // It is valid to advanceTo with any monotonic sequence.
 818   AB2.advanceTo(411);
 819   ASSERT_TRUE(AB2.valid());
 820   EXPECT_EQ(410u, AB2.a().start());
 821   EXPECT_EQ(402u, AB2.b().start());
 822
 823   // Check reversed maps.
 824   UUOverlaps BA(mapB, mapA);
 825   ASSERT_TRUE(BA.valid());
 826   EXPECT_EQ(400u, BA.b().start());
 827   EXPECT_EQ(400u, BA.a().start());
 828   ++BA;
 829   ASSERT_TRUE(BA.valid());
 830   EXPECT_EQ(400u, BA.b().start());
 831   EXPECT_EQ(401u, BA.a().start());
 832   ++BA;
 833   ASSERT_TRUE(BA.valid());
 834   EXPECT_EQ(400u, BA.b().start());
 835   EXPECT_EQ(402u, BA.a().start());
 836   ++BA;
 837   ASSERT_TRUE(BA.valid());
 838   EXPECT_EQ(410u, BA.b().start());
 839   EXPECT_EQ(402u, BA.a().start());
 840   ++BA;
 841   ASSERT_TRUE(BA.valid());
 842   EXPECT_EQ(420u, BA.b().start());
 843   EXPECT_EQ(402u, BA.a().start());
 844   BA.skipA();
 845   ASSERT_TRUE(BA.valid());
 846   EXPECT_EQ(600u, BA.b().start());
 847   EXPECT_EQ(600u, BA.a().start());
 848   ++BA;
 849   EXPECT_FALSE(BA.valid());
 850
 851   // Test advanceTo.
 852   UUOverlaps BA2(mapB, mapA);
 853   BA2.advanceTo(410);
 854   ASSERT_TRUE(BA2.valid());
 855   EXPECT_EQ(410u, BA2.b().start());
 856   EXPECT_EQ(402u, BA2.a().start());
 857
 858   BA2.advanceTo(411);
 859   ASSERT_TRUE(BA2.valid());
 860   EXPECT_EQ(410u, BA2.b().start());
 861   EXPECT_EQ(402u, BA2.a().start());
 862 }
 863
 864 } // namespace