Lines Matching refs:Level
791 template <typename NodeT> NodeT &node(unsigned Level) const {
792 return *reinterpret_cast<NodeT*>(path[Level].node);
794 unsigned size(unsigned Level) const { return path[Level].size; }
795 unsigned offset(unsigned Level) const { return path[Level].offset; }
796 unsigned &offset(unsigned Level) { return path[Level].offset; }
815 /// subtree - Get the subtree referenced from Level. When the path is
816 /// consistent, node(Level + 1) == subtree(Level).
817 /// @param Level 0..height-1. The leaves have no subtrees.
818 NodeRef &subtree(unsigned Level) const {
819 return path[Level].subtree(path[Level].offset);
822 /// reset - Reset cached information about node(Level) from subtree(Level -1).
823 /// @param Level 1..height. THe node to update after parent node changed.
824 void reset(unsigned Level) {
825 path[Level] = Entry(subtree(Level - 1), offset(Level));
841 /// @param Level 0..height. Note that setting the root size won't change
844 void setSize(unsigned Level, unsigned Size) {
845 path[Level].size = Size;
846 if (Level)
847 subtree(Level - 1).setSize(Size);
866 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
867 /// @param Level Get the sibling to node(Level).
869 NodeRef getLeftSibling(unsigned Level) const;
871 /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level
873 /// @param Level Move node(Level).
874 void moveLeft(unsigned Level);
883 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
884 /// @param Level Get the sinbling to node(Level).
886 Level) const;
888 /// moveRight - Move path to the left sibling at Level. Leave nodes below
889 /// Level unaltered.
890 /// @param Level Move node(Level).
891 void moveRight(unsigned Level);
902 /// Level.
903 /// @param Level Node to examine.
904 bool atLastEntry(unsigned Level) const {
905 return path[Level].offset == path[Level].size - 1;
908 /// legalizeForInsert - Prepare the path for an insertion at Level. When the
909 /// path is at end(), node(Level) may not be a legal node. legalizeForInsert
910 /// ensures that node(Level) is real by moving back to the last node at Level,
911 /// and setting offset(Level) to size(Level) if required.
912 /// @param Level The level where an insertion is about to take place.
913 void legalizeForInsert(unsigned Level) {
916 moveLeft(Level);
917 ++path[Level].offset;
1049 unsigned Level));
1050 void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
1251 // Collect level 0 nodes from the root.
1273 deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {
1274 if (Level)
1501 // Is the level-1 Branch usable?
1525 void setNodeStop(unsigned Level, KeyT Stop);
1526 bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1527 template <typename NodeT> bool overflow(unsigned Level);
1529 void eraseNode(unsigned Level);
1661 /// setNodeStop - Update the stop key of the current node at level and above.
1664 iterator::setNodeStop(unsigned Level, KeyT Stop) {
1666 if (!Level)
1670 while (--Level) {
1671 P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
1672 if (!P.atLastEntry(Level))
1676 P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
1727 /// insertNode - insert a node before the current path at level.
1729 /// @param Level path index of the node to be inserted.
1735 iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
1736 assert(Level && "Cannot insert next to the root");
1741 if (Level == 1) {
1746 P.reset(Level);
1755 // Fall through to insert at the new higher level.
1756 ++Level;
1760 P.legalizeForInsert(--Level);
1762 // Insert into the branch node at Level-1.
1763 if (P.size(Level) == Branch::Capacity) {
1766 SplitRoot = overflow<Branch>(Level);
1767 Level += SplitRoot;
1769 P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
1770 P.setSize(Level, P.size(Level) + 1);
1771 if (P.atLastEntry(Level))
1772 setNodeStop(Level, Stop);
1773 P.reset(Level + 1);
1910 /// eraseNode - Erase the current node at Level from its parent and move path to
1913 /// @param Level 1..height, the root node cannot be erased.
1916 iterator::eraseNode(unsigned Level) {
1917 assert(Level && "Cannot erase root node");
1921 if (--Level == 0) {
1931 // Remove node ref from branch node at Level.
1932 Branch &Parent = P.node<Branch>(Level);
1933 if (P.size(Level) == 1) {
1936 eraseNode(Level);
1939 Parent.erase(P.offset(Level), P.size(Level));
1940 unsigned NewSize = P.size(Level) - 1;
1941 P.setSize(Level, NewSize);
1943 if (P.offset(Level) == NewSize) {
1944 setNodeStop(Level, Parent.stop(NewSize - 1));
1945 P.moveRight(Level);
1951 P.reset(Level + 1);
1952 P.offset(Level + 1) = 0;
1959 /// @tparam NodeT The type of node at Level (Leaf or Branch).
1960 /// @param Level path index of the overflowing node.
1965 iterator::overflow(unsigned Level) {
1972 unsigned Offset = P.offset(Level);
1975 NodeRef LeftSib = P.getLeftSibling(Level);
1982 Elements += CurSize[Nodes] = P.size(Level);
1983 Node[Nodes++] = &P.node<NodeT>(Level);
1986 NodeRef RightSib = P.getRightSibling(Level);
2012 P.moveLeft(Level);
2020 SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
2021 Level += SplitRoot;
2023 P.setSize(Level, NewSize[Pos]);
2024 setNodeStop(Level, Stop);
2028 P.moveRight(Level);
2034 P.moveLeft(Level);
2037 P.offset(Level) = NewOffset.second;
