In-memory `find_block`: the vertex containing `pos`, preferring a non-empty vertex (matching `GraphTxnT::find_block`).
(&self, pos: Position<NodeId>)
| 84 | /// In-memory `find_block`: the vertex containing `pos`, preferring a |
| 85 | /// non-empty vertex (matching `GraphTxnT::find_block`). |
| 86 | fn find_block_cached(&self, pos: Position<NodeId>) -> Option<GraphNode<NodeId>> { |
| 87 | let key = (pos.change.get(), pos.pos.get()); |
| 88 | // First index with change == pos.change and start <= pos.pos. |
| 89 | let mut lo = 0usize; |
| 90 | let mut hi = self.vertices.len(); |
| 91 | while lo < hi { |
| 92 | let mid = (lo + hi) / 2; |
| 93 | let node = &self.vertices[mid]; |
| 94 | let order = (node.change.get(), node.start.get()); |
| 95 | if order <= (key.0, key.1) { |
| 96 | lo = mid + 1; |
| 97 | } else { |
| 98 | hi = mid; |
| 99 | } |
| 100 | } |
| 101 | // Scan backwards over vertices with the same change for a match, |
| 102 | // preferring a non-empty containing vertex. |
| 103 | let mut empty_match = None; |
| 104 | let mut index = lo; |
| 105 | while index > 0 { |
| 106 | index -= 1; |
| 107 | let node = &self.vertices[index]; |
| 108 | if node.change.get() != key.0 { |
| 109 | break; |
| 110 | } |
| 111 | if node.start.get() == node.end.get() { |
| 112 | if node.start.get() == key.1 { |
| 113 | empty_match = Some(*node); |
| 114 | } |
| 115 | continue; |
| 116 | } |
| 117 | if node.start.get() <= key.1 && key.1 < node.end.get() { |
| 118 | return Some(*node); |
| 119 | } |
| 120 | } |
| 121 | empty_match |
| 122 | } |
| 123 | } |
| 124 | |
| 125 | impl<'a, T> GraphTxnT for InodeScopedGraph<'a, T> |
no test coverage detected