[ADT] IntervalMap: use AlignedCharArray.

[friss]

Summary

Currently IntervalMap would assert when used with keys bigger than host
pointers. This patch uses the AlignedCharArray functionality to overcome
that limitation.

The patch looks trivial enough, but the comment I'm removing was pretty
explicit about not supporting keys with bigger alignment than pointers,
thus I'm wondering if I'm not missing something.

[dblaikie]

include/llvm/ADT/IntervalMap.h

970 ↗

(On Diff #21770)

Like llvm::Optional you could probably use AlignedCharArrayUnion to save you having to pull out the alignment and size explicitly?

AlignedCharArrayUnion<RootLeaf, RootBranchData> should give you something with sufficient size and alignment for either type, if I'm not mistaken

[friss]

Use AlignedCharArrayUnion, which also means we can get rid of the RootDataSize enum.

[dblaikie]

Looks good - thanks!

llvm/trunk/include/llvm/ADT/IntervalMap.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_INTERVALMAP_H
 #define LLVM_ADT_INTERVALMAP_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>
 
 namespace llvm {
 
 
 //===----------------------------------------------------------------------===//
typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>
     RootBranch;
 
   // When branched, we store a global start key as well as the branch node.
   struct RootBranchData {
     KeyT start;
     RootBranch node;
   };
 
-  enum {
-    RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
-                   sizeof(RootBranchData) : sizeof(RootLeaf)
-  };
-
 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.
-  // 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.
   // 1: Root points to leaf.
   // 2: root->branch->leaf ...
   unsigned height;
 
   // Number of entries in the root node.
   unsigned rootSize;
 
   // Allocator used for creating external nodes.
   Allocator &allocator;
 
   /// dataAs - Represent data as a node type without breaking aliasing rules.
   template <typename T>
   T &dataAs() const {
     union {
       const char *d;
       T *t;
     } u;
-    u.d = data;
+    u.d = data.buffer;
     return *u.t;
   }
 
   const RootLeaf &rootLeaf() const {
     assert(!branched() && "Cannot acces leaf data in branched root");
     return dataAs<RootLeaf>();
   }
   RootLeaf &rootLeaf() {
private:
 
   ValT treeSafeLookup(KeyT x, ValT NotFound) const;
   void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,
                   unsigned Level));
   void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
 
 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();
   }
 
   ~IntervalMap() {
     clear();
     rootLeaf().~RootLeaf();
   }