unsigned extendStop(unsigned i, unsigned Size, KeyT b);
#ifndef NDEBUG
- void dump(unsigned Size) {
- errs() << " N" << this << " [shape=record label=\"{ " << Size << '/' << N;
+ void dump(raw_ostream &OS, unsigned Size) {
+ OS << " N" << this << " [shape=record label=\"{ " << Size << '/' << N;
for (unsigned i = 0; i != Size; ++i)
- errs() << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}';
- errs() << "}\"];\n";
+ OS << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}';
+ OS << "}\"];\n";
}
#endif
}
#ifndef NDEBUG
- void dump(unsigned Size) {
- errs() << " N" << this << " [shape=record label=\"" << Size << '/' << N;
+ void dump(raw_ostream &OS, unsigned Size) {
+ OS << " N" << this << " [shape=record label=\"" << Size << '/' << N;
for (unsigned i = 0; i != Size; ++i)
- errs() << " | <s" << i << "> " << stop(i);
- errs() << "\"];\n";
+ OS << " | <s" << i << "> " << stop(i);
+ OS << "\"];\n";
for (unsigned i = 0; i != Size; ++i)
- errs() << " N" << this << ":s" << i << " -> N"
- << &subtree(i).template get<BranchNode>() << ";\n";
+ OS << " N" << this << ":s" << i << " -> N"
+ << &subtree(i).template get<BranchNode>() << ";\n";
}
#endif
return path[Level].subtree(path[Level].offset);
}
+ /// reset - Reset cached information about node(Level) from subtree(Level -1).
+ /// @param Level 1..height. THe node to update after parent node changed.
+ void reset(unsigned Level) {
+ path[Level] = Entry(subtree(Level - 1), offset(Level));
+ }
+
/// push - Add entry to path.
/// @param Node Node to add, should be subtree(path.size()-1).
/// @param Offset Offset into Node.
}
#ifndef NDEBUG
+ raw_ostream *OS;
void dump();
void dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height);
#endif
void IntervalMap<KeyT, ValT, N, Traits>::
dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height) {
if (Height)
- Node.get<Branch>().dump(Node.size());
+ Node.get<Branch>().dump(*OS, Node.size());
else
- Node.get<Leaf>().dump(Node.size());
+ Node.get<Leaf>().dump(*OS, Node.size());
}
template <typename KeyT, typename ValT, unsigned N, typename Traits>
void IntervalMap<KeyT, ValT, N, Traits>::
dump() {
- errs() << "digraph {\n";
+ std::string errors;
+ raw_fd_ostream ofs("tree.dot", errors);
+ OS = &ofs;
+ ofs << "digraph {\n";
if (branched())
- rootBranch().dump(rootSize);
+ rootBranch().dump(ofs, rootSize);
else
- rootLeaf().dump(rootSize);
+ rootLeaf().dump(ofs, rootSize);
visitNodes(&IntervalMap::dumpNode);
- errs() << "}\n";
+ ofs << "}\n";
}
#endif
if (IM.rootSize < RootBranch::Capacity) {
IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);
P.setSize(0, ++IM.rootSize);
+ P.reset(Level);
return SplitRoot;
}
}
P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
P.setSize(Level, P.size(Level) + 1);
+ if (P.atLastBranch(Level))
+ setNodeStop(Level, Stop);
+ P.reset(Level + 1);
return SplitRoot;
}
namespace {
typedef IntervalMap<unsigned, unsigned> UUMap;
+typedef IntervalMap<unsigned, unsigned, 4> UU4Map;
// Empty map tests
TEST(IntervalMapTest, EmptyMap) {
EXPECT_TRUE(map.begin() == map.end());
}
+// Branched, high, non-coalescing tests.
+TEST(IntervalMapTest, Branched2) {
+ UU4Map::Allocator allocator;
+ UU4Map map(allocator);
+
+ // Insert enough intervals to force a height >= 2 tree.
+ for (unsigned i = 1; i < 1000; ++i)
+ map.insert(10*i, 10*i+5, i);
+
+ // Tree limits.
+ EXPECT_FALSE(map.empty());
+ EXPECT_EQ(10u, map.start());
+ EXPECT_EQ(9995u, map.stop());
+
+ // Tree lookup.
+ for (unsigned i = 1; i < 1000; ++i) {
+ EXPECT_EQ(0u, map.lookup(10*i-1));
+ EXPECT_EQ(i, map.lookup(10*i));
+ EXPECT_EQ(i, map.lookup(10*i+5));
+ EXPECT_EQ(0u, map.lookup(10*i+6));
+ }
+
+ // Forward iteration.
+ UU4Map::iterator I = map.begin();
+ for (unsigned i = 1; i < 1000; ++i) {
+ ASSERT_TRUE(I.valid());
+ EXPECT_EQ(10*i, I.start());
+ EXPECT_EQ(10*i+5, I.stop());
+ EXPECT_EQ(i, *I);
+ ++I;
+ }
+ EXPECT_FALSE(I.valid());
+ EXPECT_TRUE(I == map.end());
+
+ // Backwards iteration.
+ for (unsigned i = 999; i; --i) {
+ --I;
+ ASSERT_TRUE(I.valid());
+ EXPECT_EQ(10*i, I.start());
+ EXPECT_EQ(10*i+5, I.stop());
+ EXPECT_EQ(i, *I);
+ }
+ EXPECT_TRUE(I == map.begin());
+
+ // Test clear() on branched map.
+ map.clear();
+ EXPECT_TRUE(map.empty());
+ EXPECT_TRUE(map.begin() == map.end());
+}
+
} // namespace