Speed up simple insertions into an unbranched tree by not creating an iterator.

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

1 files changed, 6 insertions, 1 deletions

diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
index 0451a762ad..2758cbc562 100644
--- a/include/llvm/ADT/IntervalMap.h
+++ b/include/llvm/ADT/IntervalMap.h
@@ -1128,7 +1128,12 @@ public:
   /// It is assumed that no key in the interval is mapped to another value, but
   /// overlapping intervals already mapped to y will be coalesced.
   void insert(KeyT a, KeyT b, ValT y) {
-    find(a).insert(a, b, y);
+    if (branched() || rootSize == RootLeaf::Capacity)
+      return find(a).insert(a, b, y);
+
+    // Easy insert into root leaf.
+    unsigned p = rootLeaf().findFrom(0, rootSize, a);
+    rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y).second;
   }
 
   /// clear - Remove all entries.