Fix read-of-uninitialized introduced in r253277 exposed on some buildbots

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

diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
index f28ebf3b9a5f09f0d68e156229e0395888ca99f6..f8843b2a4e507a81de13fd73522e801c95fdf0fc 100644 (file)
--- a/include/llvm/ADT/IntervalMap.h
+++ b/include/llvm/ADT/IntervalMap.h
@@ -99,8 +99,9 @@
 #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/AlignOf.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/RecyclingAllocator.h"
 #include <iterator>
@@ -151,6 +152,26 @@ struct IntervalMapInfo {
 
 };
 
+template <typename T>
+struct IntervalMapHalfOpenInfo {
+
+  /// startLess - Return true if x is not in [a;b).
+  static inline bool startLess(const T &x, const T &a) {
+    return x < a;
+  }
+
+  /// stopLess - Return true if x is not in [a;b).
+  static inline bool stopLess(const T &b, const T &x) {
+    return b <= x;
+  }
+
+  /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.
+  static inline bool adjacent(const T &a, const T &b) {
+    return a == b;
+  }
+
+};
+
 /// IntervalMapImpl - Namespace used for IntervalMap implementation details.
 /// It should be considered private to the implementation.
 namespace IntervalMapImpl {
@@ -476,7 +497,7 @@ public:
   NodeRef() {}
 
   /// operator bool - Detect a null ref.
-  operator bool() const { return pip.getOpaqueValue(); }
+  explicit operator bool() const { return pip.getOpaqueValue(); }
 
   /// NodeRef - Create a reference to the node p with n elements.
   template <typename NodeT>
@@ -592,7 +613,7 @@ public:
 /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
 /// possible. This may cause the node to grow by 1, or it may cause the node
 /// to shrink because of coalescing.
-/// @param i    Starting index = insertFrom(0, size, a)
+/// @param Pos  Starting index = insertFrom(0, size, a)
 /// @param Size Number of elements in node.
 /// @param a    Interval start.
 /// @param b    Interval stop.
@@ -739,7 +760,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.
 //
 //===----------------------------------------------------------------------===//
@@ -933,11 +954,6 @@ class IntervalMap {
     RootBranch node;
   };
 
-  enum {
-    RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
-                   sizeof(RootBranchData) : sizeof(RootLeaf)
-  };
-
 public:
   typedef typename Sizer::Allocator Allocator;
   typedef KeyT KeyType;
@@ -946,13 +962,7 @@ public:
 
 private:
   // The root data is either a RootLeaf or a RootBranchData instance.
-  // We can't put them in a union since C++03 doesn't allow non-trivial
-  // constructors in unions.
-  // Instead, we use a char array with pointer alignment. The alignment is
-  // ensured by the allocator member in the class, but still verified in the
-  // constructor. We don't support keys or values that are more aligned than a
-  // pointer.
-  char data[RootDataSize];
+  AlignedCharArrayUnion<RootLeaf, RootBranchData> data;
 
   // Tree height.
   // 0: Leaves in root.
@@ -973,7 +983,7 @@ private:
       const char *d;
       T *t;
     } u;
-    u.d = data;
+    u.d = data.buffer;
     return *u.t;
   }
 
@@ -1031,7 +1041,7 @@ private:
 
 public:
   explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
-    assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 &&
+    assert((uintptr_t(data.buffer) & (alignOf<RootLeaf>() - 1)) == 0 &&
            "Insufficient alignment");
     new(&rootLeaf()) RootLeaf();
   }
@@ -1157,7 +1167,7 @@ branchRoot(unsigned Position) {
   if (Nodes == 1)
     size[0] = rootSize;
   else
-    NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  NULL, size,
+    NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  nullptr, size,
                            Position, true);
 
   // Allocate new nodes.
@@ -1198,7 +1208,7 @@ splitRoot(unsigned Position) {
   if (Nodes == 1)
     Size[0] = rootSize;
   else
-    NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  NULL, Size,
+    NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  nullptr, Size,
                            Position, true);
 
   // Allocate new nodes.
@@ -1326,7 +1336,7 @@ protected:
 
 public:
   /// const_iterator - Create an iterator that isn't pointing anywhere.
-  const_iterator() : map(0) {}
+  const_iterator() : map(nullptr) {}
 
   /// setMap - Change the map iterated over. This call must be followed by a
   /// call to goToBegin(), goToEnd(), or find()
@@ -1335,6 +1345,9 @@ public:
   /// 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(); }
 
@@ -1933,7 +1946,7 @@ iterator::eraseNode(unsigned Level) {
 /// overflow - Distribute entries of the current node evenly among
 /// its siblings and ensure that the current node is not full.
 /// This may require allocating a new node.
-/// @param NodeT The type of node at Level (Leaf or Branch).
+/// @tparam NodeT The type of node at Level (Leaf or Branch).
 /// @param Level path index of the overflowing node.
 /// @return True when the tree height was changed.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
@@ -1974,7 +1987,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;
   }