The TargetData is not used for the isPowerOfTwo determination. It has never

[oota-llvm.git] / include / llvm / ADT / IntervalMap.h

diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
index c13846dce709f8019d75170e7b32db88de1889a8..da6ee4297efb41af43ffefe679c89fab46675163 100644 (file)
--- a/include/llvm/ADT/IntervalMap.h
+++ b/include/llvm/ADT/IntervalMap.h
@@ -99,8 +99,8 @@
 #ifndef LLVM_ADT_INTERVALMAP_H
 #define LLVM_ADT_INTERVALMAP_H
 
-#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/RecyclingAllocator.h"
 #include <iterator>
@@ -739,7 +739,7 @@ public:
 // A Path is used by iterators to represent a position in a B+-tree, and the
 // path to get there from the root.
 //
-// The Path class also constains the tree navigation code that doesn't have to
+// The Path class also contains the tree navigation code that doesn't have to
 // be templatized.
 //
 //===----------------------------------------------------------------------===//
@@ -1328,9 +1328,16 @@ public:
   /// const_iterator - Create an iterator that isn't pointing anywhere.
   const_iterator() : map(0) {}
 
+  /// setMap - Change the map iterated over. This call must be followed by a
+  /// call to goToBegin(), goToEnd(), or find()
+  void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); }
+
   /// valid - Return true if the current position is valid, false for end().
   bool valid() const { return path.valid(); }
 
+  /// atBegin - Return true if the current position is the first map entry.
+  bool atBegin() const { return path.atBegin(); }
+
   /// start - Return the beginning of the current interval.
   const KeyT &start() const { return unsafeStart(); }
 
@@ -1970,7 +1977,7 @@ iterator::overflow(unsigned Level) {
     CurSize[Nodes] = CurSize[NewNode];
     Node[Nodes] = Node[NewNode];
     CurSize[NewNode] = 0;
-    Node[NewNode] = this->map->newNode<NodeT>();
+    Node[NewNode] = this->map->template newNode<NodeT>();
     ++Nodes;
   }
 
@@ -2040,6 +2047,21 @@ class IntervalMapOverlaps {
   void advance() {
     if (!valid())
       return;
+
+    if (Traits::stopLess(posA.stop(), posB.start())) {
+      // A ends before B begins. Catch up.
+      posA.advanceTo(posB.start());
+      if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
+        return;
+    } else if (Traits::stopLess(posB.stop(), posA.start())) {
+      // B ends before A begins. Catch up.
+      posB.advanceTo(posA.start());
+      if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
+        return;
+    } else
+      // Already overlapping.
+      return;
+
     for (;;) {
       // Make a.end > b.start.
       posA.advanceTo(posB.start());
@@ -2076,7 +2098,7 @@ public:
     return Traits::startLess(ak, bk) ? bk : ak;
   }
 
-  /// stop - End of the overlaping interval.
+  /// stop - End of the overlapping interval.
   KeyType stop() const {
     KeyType ak = a().stop();
     KeyType bk = b().stop();
@@ -2086,20 +2108,12 @@ public:
   /// skipA - Move to the next overlap that doesn't involve a().
   void skipA() {
     ++posA;
-    if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
-      return;
-    // Second half-loop of advance().
-    posB.advanceTo(posA.start());
-    if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
-      return;
     advance();
   }
 
   /// skipB - Move to the next overlap that doesn't involve b().
   void skipB() {
     ++posB;
-    if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
-      return;
     advance();
   }
 
@@ -2116,8 +2130,13 @@ public:
   /// advanceTo - Move to the first overlapping interval with
   /// stopLess(x, stop()).
   void advanceTo(KeyType x) {
-    posA.advanceTo(x);
-    posB.advanceTo(x);
+    if (!valid())
+      return;
+    // Make sure advanceTo sees monotonic keys.
+    if (Traits::stopLess(posA.stop(), x))
+      posA.advanceTo(x);
+    if (Traits::stopLess(posB.stop(), x))
+      posB.advanceTo(x);
     advance();
   }
 };