grovedb_path/
subtree_path_iter.rs

1// MIT LICENSE
2//
3// Copyright (c) 2023 Dash Core Group
4//
5// Permission is hereby granted, free of charge, to any
6// person obtaining a copy of this software and associated
7// documentation files (the "Software"), to deal in the
8// Software without restriction, including without
9// limitation the rights to use, copy, modify, merge,
10// publish, distribute, sublicense, and/or sell copies of
11// the Software, and to permit persons to whom the Software
12// is furnished to do so, subject to the following
13// conditions:
14//
15// The above copyright notice and this permission notice
16// shall be included in all copies or substantial portions
17// of the Software.
18//
19// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
20// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
21// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
22// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
23// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
24// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
25// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
26// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27// DEALINGS IN THE SOFTWARE.
28
29//! Reverse iterator for a subtree path definition and implementation.
30
31use std::slice;
32
33use crate::{subtree_path::SubtreePath, util::CompactBytesIter};
34
35/// (Reverse) iterator for a subtree path.
36/// Because of implementation details (one way link between derivations) it
37/// cannot effectively iterate from the most shallow path segment to the
38/// deepest, so it have to go in reverse direction.
39#[derive(Debug)]
40pub struct SubtreePathIter<'b, B> {
41    current_iter: CurrentSubtreePathIter<'b, B>,
42    next_subtree_path: Option<&'b SubtreePath<'b, B>>,
43}
44
45impl<B> Clone for SubtreePathIter<'_, B> {
46    fn clone(&self) -> Self {
47        SubtreePathIter {
48            current_iter: self.current_iter.clone(),
49            next_subtree_path: self.next_subtree_path,
50        }
51    }
52}
53
54impl<'b, B> SubtreePathIter<'b, B> {
55    pub(crate) fn len(&self) -> usize {
56        self.current_iter.len() + self.next_subtree_path.map(|p| p.len()).unwrap_or_default()
57    }
58
59    pub(crate) fn new<I>(iter: I) -> Self
60    where
61        I: Into<CurrentSubtreePathIter<'b, B>>,
62    {
63        SubtreePathIter {
64            current_iter: iter.into(),
65            next_subtree_path: None,
66        }
67    }
68
69    pub(crate) fn new_with_next<I>(iter: I, next: &'b SubtreePath<'b, B>) -> Self
70    where
71        I: Into<CurrentSubtreePathIter<'b, B>>,
72    {
73        SubtreePathIter {
74            current_iter: iter.into(),
75            next_subtree_path: Some(next),
76        }
77    }
78
79    pub(crate) fn is_empty(&self) -> bool {
80        self.next_subtree_path.is_none()
81            && match &self.current_iter {
82                CurrentSubtreePathIter::Single(_) => false,
83                CurrentSubtreePathIter::Slice(slice) => slice.len() == 0,
84                CurrentSubtreePathIter::OwnedBytes(bytes_iter) => bytes_iter.len() == 0,
85            }
86    }
87}
88
89impl<'b, B: AsRef<[u8]>> Iterator for SubtreePathIter<'b, B> {
90    type Item = &'b [u8];
91
92    fn next(&mut self) -> Option<Self::Item> {
93        match &mut self.current_iter {
94            CurrentSubtreePathIter::Single(item) => {
95                let path_segment = *item;
96                if let Some(next_path) = self.next_subtree_path {
97                    *self = next_path.clone().into_reverse_iter();
98                }
99                Some(path_segment)
100            }
101            CurrentSubtreePathIter::Slice(slice_iter) => {
102                if let Some(item) = slice_iter.next_back() {
103                    Some(item.as_ref())
104                } else if let Some(next_path) = self.next_subtree_path {
105                    *self = next_path.clone().into_reverse_iter();
106                    self.next()
107                } else {
108                    None
109                }
110            }
111            CurrentSubtreePathIter::OwnedBytes(bytes_iter) => {
112                if let Some(item) = bytes_iter.next() {
113                    Some(item)
114                } else if let Some(next_path) = self.next_subtree_path {
115                    *self = next_path.clone().into_reverse_iter();
116                    self.next()
117                } else {
118                    None
119                }
120            }
121        }
122    }
123}
124
125/// An iterator variant depending on how the current subtree path's derivation
126/// point looks like.
127#[derive(Debug)]
128pub(crate) enum CurrentSubtreePathIter<'b, B> {
129    /// Current derivation point is a [SubtreePathBuilder] with one child
130    /// segment
131    Single(&'b [u8]),
132    /// Current (and last) part of the subtree path is a base slice of data,
133    /// will just reuse slice's iterator there
134    Slice(slice::Iter<'b, B>),
135    /// Current derivation point is a [SubtreePathBuilder] with multiple path
136    /// segments, will reuse it's own iterator type to keep track
137    OwnedBytes(CompactBytesIter<'b>),
138}
139
140impl<B> CurrentSubtreePathIter<'_, B> {
141    pub fn len(&self) -> usize {
142        match self {
143            CurrentSubtreePathIter::Single(_) => 1,
144            CurrentSubtreePathIter::Slice(s) => s.len(),
145            CurrentSubtreePathIter::OwnedBytes(cb) => cb.len(),
146        }
147    }
148}
149
150impl<B> Clone for CurrentSubtreePathIter<'_, B> {
151    fn clone(&self) -> Self {
152        match self {
153            CurrentSubtreePathIter::Single(x) => CurrentSubtreePathIter::Single(x),
154            CurrentSubtreePathIter::Slice(x) => CurrentSubtreePathIter::Slice(x.clone()),
155            CurrentSubtreePathIter::OwnedBytes(x) => CurrentSubtreePathIter::OwnedBytes(*x),
156        }
157    }
158}
159
160impl<'b, B> From<CompactBytesIter<'b>> for CurrentSubtreePathIter<'b, B> {
161    fn from(value: CompactBytesIter<'b>) -> Self {
162        CurrentSubtreePathIter::<B>::OwnedBytes(value)
163    }
164}
165
166impl<'b, B> From<slice::Iter<'b, B>> for CurrentSubtreePathIter<'b, B> {
167    fn from(value: slice::Iter<'b, B>) -> Self {
168        CurrentSubtreePathIter::Slice(value)
169    }
170}
171
172impl<'b, B> From<&'b [u8]> for CurrentSubtreePathIter<'b, B> {
173    fn from(value: &'b [u8]) -> Self {
174        CurrentSubtreePathIter::Single(value)
175    }
176}
grovedb_path/subtree_path_iter.rs

grovedb_path/
subtree_path_iter.rs
