llvm/ADT/IntervalMap.h

189 // Both leaf and branch nodes store vectors of pairs.
432     // Compute the leaf node branching factor that makes a node fit in three
446     // Now that we have the leaf branching factor, compute the actual allocation
455   /// Allocator - The recycling allocator used for both branch and leaf nodes.
478 // A NodeRef doesn't know whether it references a leaf node or a branch node.
690 // When all of the leaf nodes from all the subtrees are concatenated, they must
691 // satisfy the same constraints as a single leaf node. They must be sorted,
786   /// path - The path entries, path[0] is the root node, path.back() is a leaf.
799   template <typename NodeT> NodeT &leaf() const {
979   // 1: Root points to leaf.
980   // 2: root->branch->leaf ...
1001     assert(!branched() && "Cannot acces leaf data in branched root");
1005     assert(!branched() && "Cannot acces leaf data in branched root");
1097     // Easy insert into root leaf.
1163 // branchRoot - Switch from a leaf root to a branched root.
1169   // How many external leaf nodes to hold RootLeaf+1?
1193   // Destroy the old leaf node, construct branch node instead.
1210   // How many external leaf nodes to hold RootBranch+1?
1266   // Visit all leaf nodes.
1329     return branched() ? path.leaf<Leaf>().start(path.leafOffset()) :
1330                         path.leaf<RootLeaf>().start(path.leafOffset());
1336     return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
1337                         path.leaf<RootLeaf>().stop(path.leafOffset());
1343     return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
1344                         path.leaf<RootLeaf>().value(path.leafOffset());
1378     return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
1481   // Can we stay on the same leaf node?
1482   if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
1483     path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x);
1487   // Drop the current leaf.
1617     RootLeaf &Node = P.leaf<RootLeaf>();
1623     Leaf &Node = P.leaf<Leaf>();
1647     RootLeaf &Node = P.leaf<RootLeaf>();
1652     Leaf &Node = P.leaf<Leaf>();
1786   // Try simple root leaf insert.
1795   // Root leaf node is full, we must branch.
1799   // Now it fits in the new leaf.
1814   if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
1826         Leaf &CurLeaf = P.leaf<Leaf>();
1846   // When we are inserting at the end of a leaf node, we must update stops.
1849   Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y);
1855     Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
1859   // Inserted, update offset and leaf size.
1886   Leaf &Node = P.leaf<Leaf>();
1894       IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1907     IM.rootBranchStart() = P.leaf<Leaf>().start(0);