#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>
};
+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 {
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>
/// 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.
RootBranch node;
};
- enum {
- RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
- sizeof(RootBranchData) : sizeof(RootLeaf)
- };
-
public:
typedef typename Sizer::Allocator Allocator;
typedef KeyT KeyType;
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.
const char *d;
T *t;
} u;
- u.d = data;
+ u.d = data.buffer;
return *u.t;
}
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();
}
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.
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.
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()
/// 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>