Disallow overlapping inserts, even when inserting the same value.

We always disallowed overlapping inserts with different values, and this makes
the insertion code smaller and faster.

If an overwriting insert is needed, it can be added as a separate method that
trims any existing intervals before inserting. The immediate use cases for
IntervalMap don't need this - they only use disjoint insertions.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120264 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 45 insertions, 77 deletions

diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
index 8416f71b7f..d0a3b53087 100644
--- a/include/llvm/ADT/IntervalMap.h
+++ b/include/llvm/ADT/IntervalMap.h
@@ -586,8 +586,7 @@ public:
     return Traits::startLess(x, start(i)) ? NotFound : value(i);
   }
 
-  IdxPair insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y);
-  unsigned extendStop(unsigned i, unsigned Size, KeyT b);
+  unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);
 
 #ifndef NDEBUG
   void dump(raw_ostream &OS, unsigned Size) {
@@ -610,91 +609,58 @@ public:
 /// @param y    Value be mapped.
 /// @return     (insert position, new size), or (i, Capacity+1) on overflow.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
-IdxPair LeafNode<KeyT, ValT, N, Traits>::
-insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y) {
+unsigned LeafNode<KeyT, ValT, N, Traits>::
+insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) {
+  unsigned i = Pos;
   assert(i <= Size && Size <= N && "Invalid index");
   assert(!Traits::stopLess(b, a) && "Invalid interval");
 
   // Verify the findFrom invariant.
   assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
   assert((i == Size || !Traits::stopLess(stop(i), a)));
+  assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");
 
   // Coalesce with previous interval.
-  if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a))
-    return IdxPair(i - 1, extendStop(i - 1, Size, b));
+  if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
+    Pos = i - 1;
+    // Also coalesce with next interval?
+    if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {
+      stop(i - 1) = stop(i);
+      this->erase(i, Size);
+      return Size - 1;
+    }
+    stop(i - 1) = b;
+    return Size;
+  }
 
   // Detect overflow.
   if (i == N)
-    return IdxPair(i, N + 1);
+    return N + 1;
 
   // Add new interval at end.
   if (i == Size) {
     start(i) = a;
     stop(i) = b;
     value(i) = y;
-    return IdxPair(i, Size + 1);
-  }
-
-  // Overlapping intervals?
-  if (!Traits::stopLess(b, start(i))) {
-    assert(value(i) == y && "Inconsistent values in overlapping intervals");
-    if (Traits::startLess(a, start(i)))
-      start(i) = a;
-    return IdxPair(i, extendStop(i, Size, b));
+    return Size + 1;
   }
 
   // Try to coalesce with following interval.
   if (value(i) == y && Traits::adjacent(b, start(i))) {
     start(i) = a;
-    return IdxPair(i, Size);
+    return Size;
   }
 
   // We must insert before i. Detect overflow.
   if (Size == N)
-    return IdxPair(i, N + 1);
+    return N + 1;
 
   // Insert before i.
   this->shift(i, Size);
   start(i) = a;
   stop(i) = b;
   value(i) = y;
-  return IdxPair(i, Size + 1);
-}
-
-/// extendStop - Extend stop(i) to b, coalescing with following intervals.
-/// @param i    Interval to extend.
-/// @param Size Number of elements in node.
-/// @param b    New interval end point.
-/// @return     New node size after coalescing.
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-unsigned LeafNode<KeyT, ValT, N, Traits>::
-extendStop(unsigned i, unsigned Size, KeyT b) {
-  assert(i < Size && Size <= N && "Bad indices");
-
-  // Are we even extending the interval?
-  if (Traits::startLess(b, stop(i)))
-    return Size;
-
-  // Find the first interval that may be preserved.
-  unsigned j = findFrom(i + 1, Size, b);
-  if (j < Size) {
-    // Would key[i] overlap key[j] after the extension?
-    if (Traits::stopLess(b, start(j))) {
-      // Not overlapping. Perhaps adjacent and coalescable?
-      if (value(i) == value(j) && Traits::adjacent(b, start(j)))
-        b = stop(j++);
-    } else {
-      // Overlap. Include key[j] in the new interval.
-      assert(value(i) == value(j) && "Overlapping values");
-      b = stop(j++);
-    }
-  }
-  stop(i) =  b;
-
-  // Entries [i+1;j) were coalesced.
-  if (i + 1 < j && j < Size)
-    this->erase(i + 1, j, Size);
-  return Size - (j - (i + 1));
+  return Size + 1;
 }
 
 
@@ -1138,7 +1104,7 @@ public:
 
     // Easy insert into root leaf.
     unsigned p = rootLeaf().findFrom(0, rootSize, a);
-    rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y).second;
+    rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);
   }
 
   /// clear - Remove all entries.
@@ -1697,12 +1663,11 @@ iterator::insert(KeyT a, KeyT b, ValT y) {
   IntervalMapImpl::Path &P = this->path;
 
   // Try simple root leaf insert.
-  IdxPair IP = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
+  unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
 
   // Was the root node insert successful?
-  if (IP.second <= RootLeaf::Capacity) {
-    P.leafOffset() = IP.first;
-    P.setSize(0, IM.rootSize = IP.second);
+  if (Size <= RootLeaf::Capacity) {
+    P.setSize(0, IM.rootSize = Size);
     return;
   }
 
@@ -1719,14 +1684,15 @@ template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::treeInsert(KeyT a, KeyT b, ValT y) {
   using namespace IntervalMapImpl;
-  IntervalMap &IM = *this->map;
   Path &P = this->path;
 
+  if (!P.valid())
+    P.legalizeForInsert(this->map->height);
+
   // Check if this insertion will extend the node to the left.
-  if (P.valid() && P.leafOffset() == 0 &&
-      Traits::startLess(a, P.leaf<Leaf>().start(0))) {
+  if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
     // Node is growing to the left, will it affect a left sibling node?
-    if (NodeRef Sib = P.getLeftSibling(IM.height)) {
+    if (NodeRef Sib = P.getLeftSibling(P.height())) {
       Leaf &SibLeaf = Sib.get<Leaf>();
       unsigned SibOfs = Sib.size() - 1;
       if (SibLeaf.value(SibOfs) == y &&
@@ -1737,11 +1703,11 @@ iterator::treeInsert(KeyT a, KeyT b, ValT y) {
         //  2. Extend a to SibLeaf, erase the SibLeaf entry and continue.
         // We prefer 1., but need 2 when coalescing to the right as well.
         Leaf &CurLeaf = P.leaf<Leaf>();
-        P.moveLeft(IM.height);
+        P.moveLeft(P.height());
         if (Traits::stopLess(b, CurLeaf.start(0)) &&
             (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {
           // Easy, just extend SibLeaf and we're done.
-          setNodeStop(IM.height, SibLeaf.stop(SibOfs) = b);
+          setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);
           return;
         } else {
           // We have both left and right coalescing. Erase the old SibLeaf entry
@@ -1752,27 +1718,29 @@ iterator::treeInsert(KeyT a, KeyT b, ValT y) {
       }
     } else {
       // No left sibling means we are at begin(). Update cached bound.
-      IM.rootBranchStart() = a;
+      this->map->rootBranchStart() = a;
     }
   }
 
-  P.legalizeForInsert(IM.height);
-  IdxPair IP = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
+  // When we are inserting at the end of a leaf node, we must update stops.
+  unsigned Size = P.leafSize();
+  bool Grow = P.leafOffset() == Size;
+  Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y);
 
   // Leaf insertion unsuccessful? Overflow and try again.
-  if (IP.second > Leaf::Capacity) {
-    overflow<Leaf>(IM.height);
-    IP = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
-    assert(IP.second <= Leaf::Capacity && "overflow() didn't make room");
+  if (Size > Leaf::Capacity) {
+    overflow<Leaf>(P.height());
+    Grow = P.leafOffset() == P.leafSize();
+    Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
+    assert(Size <= Leaf::Capacity && "overflow() didn't make room");
   }
 
   // Inserted, update offset and leaf size.
-  P.leafOffset() = IP.first;
-  P.setSize(IM.height, IP.second);
+  P.setSize(P.height(), Size);
 
   // Insert was the last node entry, update stops.
-  if (IP.first == IP.second - 1)
-    setNodeStop(IM.height, P.leaf<Leaf>().stop(IP.first));
+  if (Grow)
+    setNodeStop(P.height(), b);
 }
 
 /// erase - erase the current interval and move to the next position.