X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FIntervalMap.h;h=931b67e40911dd801fa865e4c86c3fd22e41c6a3;hb=e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807;hp=d0a3b53087da1558a46d0161c7b63f5837f9a24a;hpb=5f456cda98c57b6dea8bc716978b69776d0d0e8f;p=oota-llvm.git

diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
index d0a3b53087d..931b67e4091 100644
--- a/include/llvm/ADT/IntervalMap.h
+++ b/include/llvm/ADT/IntervalMap.h
@@ -103,12 +103,8 @@
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/RecyclingAllocator.h"
-#include <limits>
 #include <iterator>
 
-// FIXME: Remove debugging code.
-#include "llvm/Support/raw_ostream.h"
-
 namespace llvm {
 
 
@@ -211,8 +207,10 @@ public:
             unsigned j, unsigned Count) {
     assert(i + Count <= M && "Invalid source range");
     assert(j + Count <= N && "Invalid dest range");
-    std::copy(Other.first + i, Other.first + i + Count, first + j);
-    std::copy(Other.second + i, Other.second + i + Count, second + j);
+    for (unsigned e = i + Count; i != e; ++i, ++j) {
+      first[j]  = Other.first[i];
+      second[j] = Other.second[i];
+    }
   }
 
   /// moveLeft - Move elements to the left.
@@ -231,8 +229,10 @@ public:
   void moveRight(unsigned i, unsigned j, unsigned Count) {
     assert(i <= j && "Use moveLeft shift elements left");
     assert(j + Count <= N && "Invalid range");
-    std::copy_backward(first + i, first + i + Count, first + j + Count);
-    std::copy_backward(second + i, second + i + Count, second + j + Count);
+    while (Count--) {
+      first[j + Count]  = first[i + Count];
+      second[j + Count] = second[i + Count];
+    }
   }
 
   /// erase - Erase elements [i;j).
@@ -587,16 +587,6 @@ public:
   }
 
   unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);
-
-#ifndef NDEBUG
-  void dump(raw_ostream &OS, unsigned Size) {
-    OS << "  N" << this << " [shape=record label=\"{ " << Size << '/' << N;
-    for (unsigned i = 0; i != Size; ++i)
-      OS << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}';
-    OS << "}\"];\n";
-  }
-#endif
-
 };
 
 /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
@@ -740,19 +730,6 @@ public:
     subtree(i) = Node;
     stop(i) = Stop;
   }
-
-#ifndef NDEBUG
-  void dump(raw_ostream &OS, unsigned Size) {
-    OS << "  N" << this << " [shape=record label=\"" << Size << '/' << N;
-    for (unsigned i = 0; i != Size; ++i)
-      OS << " | <s" << i << "> " << stop(i);
-    OS << "\"];\n";
-    for (unsigned i = 0; i != Size; ++i)
-      OS << "  N" << this << ":s" << i << " -> N"
-         << &subtree(i).template get<BranchNode>() << ";\n";
-  }
-#endif
-
 };
 
 //===----------------------------------------------------------------------===//
@@ -762,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.
 //
 //===----------------------------------------------------------------------===//
@@ -901,10 +878,10 @@ public:
     return true;
   }
 
-  /// atLastBranch - Return true if the path is at the last branch of the node
-  /// at Level.
+  /// atLastEntry - Return true if the path is at the last entry of the node at
+  /// Level.
   /// @param Level Node to examine.
-  bool atLastBranch(unsigned Level) const {
+  bool atLastEntry(unsigned Level) const {
     return path[Level].offset == path[Level].size - 1;
   }
 
@@ -919,14 +896,6 @@ public:
     moveLeft(Level);
     ++path[Level].offset;
   }
-
-#ifndef NDEBUG
-  void dump() const {
-    for (unsigned l = 0, e = path.size(); l != e; ++l)
-      errs() << l << ": " << path[l].node << ' ' << path[l].size << ' '
-             << path[l].offset << '\n';
-  }
-#endif
 };
 
 } // namespace IntervalMapImpl
@@ -971,6 +940,9 @@ class IntervalMap {
 
 public:
   typedef typename Sizer::Allocator Allocator;
+  typedef KeyT KeyType;
+  typedef ValT ValueType;
+  typedef Traits KeyTraits;
 
 private:
   // The root data is either a RootLeaf or a RootBranchData instance.
@@ -1116,7 +1088,7 @@ public:
   friend class iterator;
 
   const_iterator begin() const {
-    iterator I(*this);
+    const_iterator I(*this);
     I.goToBegin();
     return I;
   }
@@ -1128,7 +1100,7 @@ public:
   }
 
   const_iterator end() const {
-    iterator I(*this);
+    const_iterator I(*this);
     I.goToEnd();
     return I;
   }
@@ -1142,7 +1114,7 @@ public:
   /// find - Return an iterator pointing to the first interval ending at or
   /// after x, or end().
   const_iterator find(KeyT x) const {
-    iterator I(*this);
+    const_iterator I(*this);
     I.find(x);
     return I;
   }
@@ -1152,12 +1124,6 @@ public:
     I.find(x);
     return I;
   }
-
-#ifndef NDEBUG
-  raw_ostream *OS;
-  void dump();
-  void dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height);
-#endif
 };
 
 /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
@@ -1301,32 +1267,6 @@ clear() {
   rootSize = 0;
 }
 
-#ifndef NDEBUG
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-void IntervalMap<KeyT, ValT, N, Traits>::
-dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height) {
-  if (Height)
-    Node.get<Branch>().dump(*OS, Node.size());
-  else
-    Node.get<Leaf>().dump(*OS, Node.size());
-}
-
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-void IntervalMap<KeyT, ValT, N, Traits>::
-dump() {
-  std::string errors;
-  raw_fd_ostream ofs("tree.dot", errors);
-  OS = &ofs;
-  ofs << "digraph {\n";
-  if (branched())
-    rootBranch().dump(ofs, rootSize);
-  else
-    rootLeaf().dump(ofs, rootSize);
-  visitNodes(&IntervalMap::dumpNode);
-  ofs << "}\n";
-}
-#endif
-
 //===----------------------------------------------------------------------===//
 //---                   IntervalMap::const_iterator                       ----//
 //===----------------------------------------------------------------------===//
@@ -1344,7 +1284,8 @@ protected:
   // The path may be partially filled, but never between iterator calls.
   IntervalMapImpl::Path path;
 
-  explicit const_iterator(IntervalMap &map) : map(&map) {}
+  explicit const_iterator(const IntervalMap &map) :
+    map(const_cast<IntervalMap*>(&map)) {}
 
   bool branched() const {
     assert(map && "Invalid iterator");
@@ -1362,37 +1303,51 @@ protected:
   void treeFind(KeyT x);
   void treeAdvanceTo(KeyT x);
 
-public:
-  /// const_iterator - Create an iterator that isn't pointing anywhere.
-  const_iterator() : map(0) {}
-
-  /// valid - Return true if the current position is valid, false for end().
-  bool valid() const { return path.valid(); }
-
-  /// start - Return the beginning of the current interval.
-  const KeyT &start() const {
+  /// unsafeStart - Writable access to start() for iterator.
+  KeyT &unsafeStart() const {
     assert(valid() && "Cannot access invalid iterator");
     return branched() ? path.leaf<Leaf>().start(path.leafOffset()) :
                         path.leaf<RootLeaf>().start(path.leafOffset());
   }
 
-  /// stop - Return the end of the current interval.
-  const KeyT &stop() const {
+  /// unsafeStop - Writable access to stop() for iterator.
+  KeyT &unsafeStop() const {
     assert(valid() && "Cannot access invalid iterator");
     return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
                         path.leaf<RootLeaf>().stop(path.leafOffset());
   }
 
-  /// value - Return the mapped value at the current interval.
-  const ValT &value() const {
+  /// unsafeValue - Writable access to value() for iterator.
+  ValT &unsafeValue() const {
     assert(valid() && "Cannot access invalid iterator");
     return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
                         path.leaf<RootLeaf>().value(path.leafOffset());
   }
 
-  const ValT &operator*() const {
-    return value();
-  }
+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(); }
+
+  /// stop - Return the end of the current interval.
+  const KeyT &stop() const { return unsafeStop(); }
+
+  /// value - Return the mapped value at the current interval.
+  const ValT &value() const { return unsafeValue(); }
+
+  const ValT &operator*() const { return value(); }
 
   bool operator==(const const_iterator &RHS) const {
     assert(map == RHS.map && "Cannot compare iterators from different maps");
@@ -1463,6 +1418,8 @@ public:
   /// The search is started from the current position, and no earlier positions
   /// can be found. This is much faster than find() for small moves.
   void advanceTo(KeyT x) {
+    if (!valid())
+      return;
     if (branched())
       treeAdvanceTo(x);
     else
@@ -1551,10 +1508,50 @@ class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
   void treeInsert(KeyT a, KeyT b, ValT y);
   void eraseNode(unsigned Level);
   void treeErase(bool UpdateRoot = true);
+  bool canCoalesceLeft(KeyT Start, ValT x);
+  bool canCoalesceRight(KeyT Stop, ValT x);
+
 public:
   /// iterator - Create null iterator.
   iterator() {}
 
+  /// setStart - Move the start of the current interval.
+  /// This may cause coalescing with the previous interval.
+  /// @param a New start key, must not overlap the previous interval.
+  void setStart(KeyT a);
+
+  /// setStop - Move the end of the current interval.
+  /// This may cause coalescing with the following interval.
+  /// @param b New stop key, must not overlap the following interval.
+  void setStop(KeyT b);
+
+  /// setValue - Change the mapped value of the current interval.
+  /// This may cause coalescing with the previous and following intervals.
+  /// @param x New value.
+  void setValue(ValT x);
+
+  /// setStartUnchecked - Move the start of the current interval without
+  /// checking for coalescing or overlaps.
+  /// This should only be used when it is known that coalescing is not required.
+  /// @param a New start key.
+  void setStartUnchecked(KeyT a) { this->unsafeStart() = a; }
+
+  /// setStopUnchecked - Move the end of the current interval without checking
+  /// for coalescing or overlaps.
+  /// This should only be used when it is known that coalescing is not required.
+  /// @param b New stop key.
+  void setStopUnchecked(KeyT b) {
+    this->unsafeStop() = b;
+    // Update keys in branch nodes as well.
+    if (this->path.atLastEntry(this->path.height()))
+      setNodeStop(this->path.height(), b);
+  }
+
+  /// setValueUnchecked - Change the mapped value of the current interval
+  /// without checking for coalescing.
+  /// @param x New value.
+  void setValueUnchecked(ValT x) { this->unsafeValue() = x; }
+
   /// insert - Insert mapping [a;b] -> y before the current position.
   void insert(KeyT a, KeyT b, ValT y);
 
@@ -1585,6 +1582,62 @@ public:
 
 };
 
+/// canCoalesceLeft - Can the current interval coalesce to the left after
+/// changing start or value?
+/// @param Start New start of current interval.
+/// @param Value New value for current interval.
+/// @return True when updating the current interval would enable coalescing.
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+bool IntervalMap<KeyT, ValT, N, Traits>::
+iterator::canCoalesceLeft(KeyT Start, ValT Value) {
+  using namespace IntervalMapImpl;
+  Path &P = this->path;
+  if (!this->branched()) {
+    unsigned i = P.leafOffset();
+    RootLeaf &Node = P.leaf<RootLeaf>();
+    return i && Node.value(i-1) == Value &&
+                Traits::adjacent(Node.stop(i-1), Start);
+  }
+  // Branched.
+  if (unsigned i = P.leafOffset()) {
+    Leaf &Node = P.leaf<Leaf>();
+    return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);
+  } else if (NodeRef NR = P.getLeftSibling(P.height())) {
+    unsigned i = NR.size() - 1;
+    Leaf &Node = NR.get<Leaf>();
+    return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);
+  }
+  return false;
+}
+
+/// canCoalesceRight - Can the current interval coalesce to the right after
+/// changing stop or value?
+/// @param Stop New stop of current interval.
+/// @param Value New value for current interval.
+/// @return True when updating the current interval would enable coalescing.
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+bool IntervalMap<KeyT, ValT, N, Traits>::
+iterator::canCoalesceRight(KeyT Stop, ValT Value) {
+  using namespace IntervalMapImpl;
+  Path &P = this->path;
+  unsigned i = P.leafOffset() + 1;
+  if (!this->branched()) {
+    if (i >= P.leafSize())
+      return false;
+    RootLeaf &Node = P.leaf<RootLeaf>();
+    return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
+  }
+  // Branched.
+  if (i < P.leafSize()) {
+    Leaf &Node = P.leaf<Leaf>();
+    return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
+  } else if (NodeRef NR = P.getRightSibling(P.height())) {
+    Leaf &Node = NR.get<Leaf>();
+    return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));
+  }
+  return false;
+}
+
 /// setNodeStop - Update the stop key of the current node at level and above.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
@@ -1596,13 +1649,61 @@ iterator::setNodeStop(unsigned Level, KeyT Stop) {
   // Update nodes pointing to the current node.
   while (--Level) {
     P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
-    if (!P.atLastBranch(Level))
+    if (!P.atLastEntry(Level))
       return;
   }
   // Update root separately since it has a different layout.
   P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
 }
 
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+void IntervalMap<KeyT, ValT, N, Traits>::
+iterator::setStart(KeyT a) {
+  assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop");
+  KeyT &CurStart = this->unsafeStart();
+  if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {
+    CurStart = a;
+    return;
+  }
+  // Coalesce with the interval to the left.
+  --*this;
+  a = this->start();
+  erase();
+  setStartUnchecked(a);
+}
+
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+void IntervalMap<KeyT, ValT, N, Traits>::
+iterator::setStop(KeyT b) {
+  assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start");
+  if (Traits::startLess(b, this->stop()) ||
+      !canCoalesceRight(b, this->value())) {
+    setStopUnchecked(b);
+    return;
+  }
+  // Coalesce with interval to the right.
+  KeyT a = this->start();
+  erase();
+  setStartUnchecked(a);
+}
+
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+void IntervalMap<KeyT, ValT, N, Traits>::
+iterator::setValue(ValT x) {
+  setValueUnchecked(x);
+  if (canCoalesceRight(this->stop(), x)) {
+    KeyT a = this->start();
+    erase();
+    setStartUnchecked(a);
+  }
+  if (canCoalesceLeft(this->start(), x)) {
+    --*this;
+    KeyT a = this->start();
+    erase();
+    setStartUnchecked(a);
+  }
+}
+
 /// insertNode - insert a node before the current path at level.
 /// Leave the current path pointing at the new node.
 /// @param Level path index of the node to be inserted.
@@ -1647,7 +1748,7 @@ iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
   }
   P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
   P.setSize(Level, P.size(Level) + 1);
-  if (P.atLastBranch(Level))
+  if (P.atLastEntry(Level))
     setNodeStop(Level, Stop);
   P.reset(Level + 1);
   return SplitRoot;
@@ -1876,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;
   }
 
@@ -1917,6 +2018,129 @@ iterator::overflow(unsigned Level) {
   return SplitRoot;
 }
 
+//===----------------------------------------------------------------------===//
+//---                       IntervalMapOverlaps                           ----//
+//===----------------------------------------------------------------------===//
+
+/// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two
+/// IntervalMaps. The maps may be different, but the KeyT and Traits types
+/// should be the same.
+///
+/// Typical uses:
+///
+/// 1. Test for overlap:
+///    bool overlap = IntervalMapOverlaps(a, b).valid();
+///
+/// 2. Enumerate overlaps:
+///    for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... }
+///
+template <typename MapA, typename MapB>
+class IntervalMapOverlaps {
+  typedef typename MapA::KeyType KeyType;
+  typedef typename MapA::KeyTraits Traits;
+  typename MapA::const_iterator posA;
+  typename MapB::const_iterator posB;
+
+  /// advance - Move posA and posB forward until reaching an overlap, or until
+  /// either meets end.
+  /// Don't move the iterators if they are already overlapping.
+  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());
+      if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
+        return;
+      // Make b.end > a.start.
+      posB.advanceTo(posA.start());
+      if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
+        return;
+    }
+  }
+
+public:
+  /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
+  IntervalMapOverlaps(const MapA &a, const MapB &b)
+    : posA(b.empty() ? a.end() : a.find(b.start())),
+      posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); }
+
+  /// valid - Return true if iterator is at an overlap.
+  bool valid() const {
+    return posA.valid() && posB.valid();
+  }
+
+  /// a - access the left hand side in the overlap.
+  const typename MapA::const_iterator &a() const { return posA; }
+
+  /// b - access the right hand side in the overlap.
+  const typename MapB::const_iterator &b() const { return posB; }
+
+  /// start - Beginning of the overlapping interval.
+  KeyType start() const {
+    KeyType ak = a().start();
+    KeyType bk = b().start();
+    return Traits::startLess(ak, bk) ? bk : ak;
+  }
+
+  /// stop - End of the overlapping interval.
+  KeyType stop() const {
+    KeyType ak = a().stop();
+    KeyType bk = b().stop();
+    return Traits::startLess(ak, bk) ? ak : bk;
+  }
+
+  /// skipA - Move to the next overlap that doesn't involve a().
+  void skipA() {
+    ++posA;
+    advance();
+  }
+
+  /// skipB - Move to the next overlap that doesn't involve b().
+  void skipB() {
+    ++posB;
+    advance();
+  }
+
+  /// Preincrement - Move to the next overlap.
+  IntervalMapOverlaps &operator++() {
+    // Bump the iterator that ends first. The other one may have more overlaps.
+    if (Traits::startLess(posB.stop(), posA.stop()))
+      skipB();
+    else
+      skipA();
+    return *this;
+  }
+
+  /// advanceTo - Move to the first overlapping interval with
+  /// stopLess(x, stop()).
+  void advanceTo(KeyType 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();
+  }
+};
+
 } // namespace llvm
 
 #endif