Lines Matching refs:Path
756 //--- IntervalMapImpl::Path ---//
759 // A Path is used by iterators to represent a position in a B+-tree, and the
760 // path to get there from the root.
762 // The Path class also contains the tree navigation code that doesn't have to
767 class Path {
768 /// Entry - Each step in the path is a node pointer and an offset into that
786 /// path - The path entries, path[0] is the root node, path.back() is a leaf.
787 SmallVector<Entry, 4> path;
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; }
800 return *reinterpret_cast<NodeT*>(path.back().node);
802 unsigned leafSize() const { return path.back().size; }
803 unsigned leafOffset() const { return path.back().offset; }
804 unsigned &leafOffset() { return path.back().offset; }
806 /// valid - Return true if path is at a valid node, not at end().
808 return !path.empty() && path.front().offset < path.front().size;
811 /// height - Return the height of the tree corresponding to this path.
812 /// This matches map->height in a full path.
813 unsigned height() const { return path.size() - 1; }
815 /// subtree - Get the subtree referenced from Level. When the path is
819 return path[Level].subtree(path[Level].offset);
825 path[Level] = Entry(subtree(Level - 1), offset(Level));
828 /// push - Add entry to path.
829 /// @param Node Node to add, should be subtree(path.size()-1).
832 path.push_back(Entry(Node, Offset));
835 /// pop - Remove the last path entry.
837 path.pop_back();
840 /// setSize - Set the size of a node both in the path and in the tree.
845 path[Level].size = Size;
850 /// setRoot - Clear the path and set a new root node.
855 path.clear();
856 path.push_back(Entry(Node, Size, Offset));
871 /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level
876 /// fillLeft - Grow path to Height by taking leftmost branches.
888 /// moveRight - Move path to the left sibling at Level. Leave nodes below
893 /// atBegin - Return true if path is at begin().
895 for (unsigned i = 0, e = path.size(); i != e; ++i)
896 if (path[i].offset != 0)
901 /// atLastEntry - Return true if the path is at the last entry of the node at
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
917 ++path[Level].offset;
1303 // We store a full path from the root to the current position.
1304 // The path may be partially filled, but never between iterator calls.
1305 IntervalMapImpl::Path path;
1317 path.setRoot(&map->rootBranch(), map->rootSize, Offset);
1319 path.setRoot(&map->rootLeaf(), map->rootSize, Offset);
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());
1356 bool valid() const { return path.valid(); }
1359 bool atBegin() const { return path.atBegin(); }
1376 if (path.leafOffset() != RHS.path.leafOffset())
1378 return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
1389 path.fillLeft(map->height);
1400 if (++path.leafOffset() == path.leafSize() && branched())
1401 path
1414 if (path.leafOffset() && (valid() || !branched()))
1415 --path.leafOffset();
1417 path.moveLeft(map->height);
1446 path.leafOffset() =
1447 map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x);
1452 /// pathFillFind - Complete path by searching for x.
1457 IntervalMapImpl::NodeRef NR = path.subtree(path.height());
1458 for (unsigned i = map->height - path.height() - 1; i; --i) {
1460 path.push(NR, p);
1463 path.push(NR, NR.get<Leaf>().safeFind(0, x));
1482 if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
1483 path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x);
1488 path.pop();
1491 if (path.height()) {
1492 for (unsigned l = path.height() - 1; l; --l) {
1493 if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {
1495 path.offset(l + 1) =
1496 path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x);
1499 path.pop();
1502 if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
1503 path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x);
1509 setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x));
1566 if (this->path.atLastEntry(this->path.height()))
1567 setNodeStop(this->path.height(), b);
1614 Path &P = this->path;
1642 Path &P = this->path;
1668 IntervalMapImpl::Path &P = this->path;
1727 /// insertNode - insert a node before the current path at level.
1728 /// Leave the current path pointing at the new node.
1729 /// @param Level path index of the node to be inserted.
1739 IntervalMapImpl::Path &P = this->path;
1759 // When inserting before end(), make sure we have a valid path.
1784 IntervalMapImpl::Path &P = this->path;
1808 Path &P = this->path;
1872 IntervalMapImpl::Path &P = this->path;
1885 IntervalMapImpl::Path &P = this->path;
1910 /// eraseNode - Erase the current node at Level from its parent and move path to
1919 IntervalMapImpl::Path &P = this->path;
1949 // Update path cache for the new right sibling position.
1960 /// @param Level path index of the overflowing node.
1967 Path &P = this->path;
