Show More
@@ -272,17 +272,82 b' impl NodeTree {' | |||
|
272 | 272 | &self, |
|
273 | 273 | prefix: NodePrefixRef<'p>, |
|
274 | 274 | ) -> Result<Option<Revision>, NodeMapError> { |
|
275 | let mut visit = self.len() - 1; | |
|
276 | for i in 0..prefix.len() { | |
|
277 | let nybble = prefix.get_nybble(i); | |
|
278 | match self[visit].get(nybble) { | |
|
279 | Element::None => return Ok(None), | |
|
280 | Element::Rev(r) => return Ok(Some(r)), | |
|
281 | Element::Block(idx) => visit = idx, | |
|
275 | for visit_item in self.visit(prefix) { | |
|
276 | if let Some(opt) = visit_item.final_revision() { | |
|
277 | return Ok(opt); | |
|
282 | 278 | } |
|
283 | 279 | } |
|
284 | 280 | Err(NodeMapError::MultipleResults) |
|
285 | 281 | } |
|
282 | ||
|
283 | fn visit<'n, 'p>( | |
|
284 | &'n self, | |
|
285 | prefix: NodePrefixRef<'p>, | |
|
286 | ) -> NodeTreeVisitor<'n, 'p> { | |
|
287 | NodeTreeVisitor { | |
|
288 | nt: self, | |
|
289 | prefix: prefix, | |
|
290 | visit: self.len() - 1, | |
|
291 | nybble_idx: 0, | |
|
292 | done: false, | |
|
293 | } | |
|
294 | } | |
|
295 | } | |
|
296 | ||
|
297 | struct NodeTreeVisitor<'n, 'p> { | |
|
298 | nt: &'n NodeTree, | |
|
299 | prefix: NodePrefixRef<'p>, | |
|
300 | visit: usize, | |
|
301 | nybble_idx: usize, | |
|
302 | done: bool, | |
|
303 | } | |
|
304 | ||
|
305 | #[derive(Debug, PartialEq, Clone)] | |
|
306 | struct NodeTreeVisitItem { | |
|
307 | block_idx: usize, | |
|
308 | nybble: u8, | |
|
309 | element: Element, | |
|
310 | } | |
|
311 | ||
|
312 | impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> { | |
|
313 | type Item = NodeTreeVisitItem; | |
|
314 | ||
|
315 | fn next(&mut self) -> Option<Self::Item> { | |
|
316 | if self.done || self.nybble_idx >= self.prefix.len() { | |
|
317 | return None; | |
|
318 | } | |
|
319 | ||
|
320 | let nybble = self.prefix.get_nybble(self.nybble_idx); | |
|
321 | self.nybble_idx += 1; | |
|
322 | ||
|
323 | let visit = self.visit; | |
|
324 | let element = self.nt[visit].get(nybble); | |
|
325 | if let Element::Block(idx) = element { | |
|
326 | self.visit = idx; | |
|
327 | } else { | |
|
328 | self.done = true; | |
|
329 | } | |
|
330 | ||
|
331 | Some(NodeTreeVisitItem { | |
|
332 | block_idx: visit, | |
|
333 | nybble: nybble, | |
|
334 | element: element, | |
|
335 | }) | |
|
336 | } | |
|
337 | } | |
|
338 | ||
|
339 | impl NodeTreeVisitItem { | |
|
340 | // Return `Some(opt)` if this item is final, with `opt` being the | |
|
341 | // `Revision` that it may represent. | |
|
342 | // | |
|
343 | // If the item is not terminal, return `None` | |
|
344 | fn final_revision(&self) -> Option<Option<Revision>> { | |
|
345 | match self.element { | |
|
346 | Element::Block(_) => None, | |
|
347 | Element::Rev(r) => Some(Some(r)), | |
|
348 | Element::None => Some(None), | |
|
349 | } | |
|
350 | } | |
|
286 | 351 | } |
|
287 | 352 | |
|
288 | 353 | impl From<Vec<Block>> for NodeTree { |
General Comments 0
You need to be logged in to leave comments.
Login now