Lines Matching full:leaf
199 // Both leaf and branch nodes store vectors of pairs.
215 // 8 4 16 0 Leaf<4,4>, Branch<4>
216 // 8 8 12 0 Leaf<4,8>, Branch<8>
217 // 16 4 9 12 Leaf<8,4>
218 // 16 8 8 0 Leaf<8,8>
441 // Compute the leaf node branching factor that makes a node fit in three
455 // Now that we have the leaf branching factor, compute the actual allocation
464 /// Allocator - The recycling allocator used for both branch and leaf nodes.
485 // A NodeRef doesn't know whether it references a leaf node or a branch node.
549 // Leaf nodes store up to N disjoint intervals with corresponding values.
696 // When all of the leaf nodes from all the subtrees are concatenated, they must
697 // satisfy the same constraints as a single leaf node. They must be sorted,
792 /// path - The path entries, path[0] is the root node, path.back() is a leaf.
804 // Leaf accessors.
805 template <typename NodeT> NodeT &leaf() const { in leaf() function
938 using Leaf = IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits>; variable
970 RootLeaf leaf; member
976 // 1: Root points to leaf.
977 // 2: root->branch->leaf ...
987 assert(!branched() && "Cannot acces leaf data in branched root"); in rootLeaf()
988 return leaf; in rootLeaf()
991 assert(!branched() && "Cannot acces leaf data in branched root"); in rootLeaf()
992 return leaf; in rootLeaf()
1133 // Easy insert into root leaf. in insert()
1208 return NR.get<Leaf>().safeLookup(x, NotFound); in treeSafeLookup()
1211 // branchRoot - Switch from a leaf root to a branched root.
1217 // How many external leaf nodes to hold RootLeaf+1? in branchRoot()
1218 const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1; in branchRoot()
1228 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, size, in branchRoot()
1235 Leaf *L = newNode<Leaf>(); in branchRoot()
1241 // Destroy the old leaf node, construct branch node instead. in branchRoot()
1244 rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1); in branchRoot()
1247 rootBranchStart() = node[0].template get<Leaf>().start(0); in branchRoot()
1258 // How many external leaf nodes to hold RootBranch+1? in splitRoot()
1269 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, Size, in splitRoot()
1314 // Visit all leaf nodes. in visitNodes()
1325 deleteNode(&Node.get<Leaf>()); in deleteNode()
1383 return branched() ? path.leaf<Leaf>().start(path.leafOffset()) : in unsafeStart()
1384 path.leaf<RootLeaf>().start(path.leafOffset()); in unsafeStart()
1390 return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) : in unsafeStop()
1391 path.leaf<RootLeaf>().stop(path.leafOffset()); in unsafeStop()
1397 return branched() ? path.leaf<Leaf>().value(path.leafOffset()) : in unsafeValue()
1398 path.leaf<RootLeaf>().value(path.leafOffset()); in unsafeValue()
1432 return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
1516 path.push(NR, NR.get<Leaf>().safeFind(0, x)); in pathFillFind()
1534 // Can we stay on the same leaf node? in treeAdvanceTo()
1535 if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) { in treeAdvanceTo()
1536 path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x); in treeAdvanceTo()
1540 // Drop the current leaf. in treeAdvanceTo()
1670 RootLeaf &Node = P.leaf<RootLeaf>(); in canCoalesceLeft()
1676 Leaf &Node = P.leaf<Leaf>(); in canCoalesceLeft()
1680 Leaf &Node = NR.get<Leaf>(); in canCoalesceLeft()
1700 RootLeaf &Node = P.leaf<RootLeaf>(); in canCoalesceRight()
1705 Leaf &Node = P.leaf<Leaf>(); in canCoalesceRight()
1708 Leaf &Node = NR.get<Leaf>(); in canCoalesceRight()
1839 // Try simple root leaf insert. in insert()
1848 // Root leaf node is full, we must branch. in insert()
1852 // Now it fits in the new leaf. in insert()
1866 if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) { in treeInsert()
1869 Leaf &SibLeaf = Sib.get<Leaf>(); in treeInsert()
1878 Leaf &CurLeaf = P.leaf<Leaf>(); in treeInsert()
1898 // When we are inserting at the end of a leaf node, we must update stops. in treeInsert()
1901 Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y); in treeInsert()
1903 // Leaf insertion unsuccessful? Overflow and try again. in treeInsert()
1904 if (Size > Leaf::Capacity) { in treeInsert()
1905 overflow<Leaf>(P.height()); in treeInsert()
1907 Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); in treeInsert()
1908 assert(Size <= Leaf::Capacity && "overflow() didn't make room"); in treeInsert()
1911 // Inserted, update offset and leaf size. in treeInsert()
1938 Leaf &Node = P.leaf<Leaf>(); in treeErase()
1946 IM.rootBranchStart() = P.leaf<Leaf>().start(0); in treeErase()
1959 IM.rootBranchStart() = P.leaf<Leaf>().start(0); in treeErase()
2011 /// @tparam NodeT The type of node at Level (Leaf or Branch).