bucky_objects/objects/object_map/
path_iterator.rs

1use super::cache::*;
2use super::iterator::IntoObjectMapContentItem;
3use super::object_map::*;
4use crate::*;
5
6use std::collections::VecDeque;
7
8// 对多级ObjectMap进行遍历的迭代器
9// 树状结构的迭代一般分为广度优先和深度优先，但由于我们支持step>1的优化遍历，所以广度优先会让性能更高些
10// 深度优先遍历话内部节点要使用step(1)来模拟，性能要差些
11
12pub struct ObjectMapPathContentItem {
13    pub path: String,
14    pub value: ObjectMapContentItem,
15    pub content_type: ObjectMapSimpleContentType,
16}
17
18impl std::fmt::Debug for ObjectMapPathContentItem {
19    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
20        write!(
21            f,
22            "{:?} item: {}={}",
23            self.content_type, self.path, self.value
24        )
25    }
26}
27
28#[derive(Debug)]
29pub struct ObjectMapPathContentList {
30    pub list: Vec<ObjectMapPathContentItem>,
31}
32
33impl std::fmt::Display for ObjectMapPathContentList {
34    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
35        write!(f, "path content list: {:?}", self.list)
36    }
37}
38
39impl ObjectMapPathContentList {
40    pub fn new(capacity: usize) -> Self {
41        Self {
42            list: Vec::with_capacity(capacity),
43        }
44    }
45}
46
47struct PathIteratorSeg {
48    path: String,
49    it: ObjectMapBindIterator,
50}
51
52#[derive(Clone, Debug)]
53pub struct ObjectMapPathIteratorOption {
54    pub leaf_object: bool,
55    pub mid_object: bool,
56}
57
58impl Default for ObjectMapPathIteratorOption {
59    fn default() -> Self {
60        Self {
61            leaf_object: true,
62            mid_object: false,
63        }
64    }
65}
66
67impl ObjectMapPathIteratorOption {
68    pub fn new(leaf_object: bool, mid_object: bool) -> Self {
69        Self {
70            leaf_object,
71            mid_object,
72        }
73    }
74}
75
76pub struct ObjectMapPathIterator {
77    cache: ObjectMapOpEnvCacheRef,
78
79    stack: VecDeque<PathIteratorSeg>,
80
81    opt: ObjectMapPathIteratorOption,
82}
83
84impl ObjectMapPathIterator {
85    pub async fn new(target: ObjectMapRef, cache: ObjectMapOpEnvCacheRef, opt: ObjectMapPathIteratorOption) -> Self {
86        let mut ret = Self {
87            cache,
88            stack: VecDeque::new(),
89            opt,
90        };
91
92        let seg = PathIteratorSeg {
93            path: "/".to_owned(),
94            it: ObjectMapBindIterator::new_with_target(target, ret.cache.clone()).await,
95        };
96        ret.stack.push_front(seg);
97
98        ret
99    }
100
101    fn join_path(parent: &str, key: &str) -> String {
102        if parent.ends_with("/") {
103            format!("{}{}", parent, key)
104        } else {
105            format!("{}/{}", parent, key)
106        }
107    }
108
109    pub fn is_end(&self) -> bool {
110        self.stack.is_empty()
111    }
112
113    // 广度优先遍历
114    pub async fn next(&mut self, step: usize) -> BuckyResult<ObjectMapPathContentList> {
115        assert!(step > 0);
116
117        let mut result = ObjectMapPathContentList::new(step);
118        let mut remaining = step;
119        loop {
120            if self.stack.is_empty() {
121                break;
122            }
123
124            let ret;
125            let path;
126            {
127                let current = self.stack.back_mut().unwrap();
128                path = current.path.clone();
129                ret = current.it.next(remaining).await?;
130            }
131
132            if ret.list.len() < remaining {
133                self.stack.pop_back();
134            }
135
136            for item in ret.list {
137                match item {
138                    ObjectMapContentItem::Map((key, value)) => {
139                        match value.obj_type_code() {
140                            ObjectTypeCode::ObjectMap => {
141                                let next_path = Self::join_path(&path, &key);
142
143                                let mut got = self.opt.mid_object;
144                                if let Err(e) = self.pending_objectmap(&next_path, &value).await {
145                                    warn!("iterator over objectmap error, now will treat as normal object! path={}, key={}, value={}, {}", path, key, value, e);
146
147                                    // FIXME 如果其中一个objectmap遍历失败了，是终止遍历，还是把这个id当成一个普通对象来处理？
148                                    got = self.opt.leaf_object;
149                                }
150
151                                if got {
152                                    let item = ObjectMapPathContentItem {
153                                        path: path.clone(),
154                                        value: value.into_content(Some(&key)),
155                                        content_type: ObjectMapSimpleContentType::Map,
156                                    };
157                                    result.list.push(item);
158                                    remaining -= 1;
159                                }
160                            }
161                            _ => {
162                                if self.opt.leaf_object {
163                                    let item = ObjectMapPathContentItem {
164                                        path: path.clone(),
165                                        value: value.into_content(Some(&key)),
166                                        content_type: ObjectMapSimpleContentType::Map,
167                                    };
168    
169                                    result.list.push(item);
170                                    remaining -= 1;
171                                }
172                            }
173                        }
174                    }
175                    ObjectMapContentItem::DiffMap((key, value)) => {
176                        match &value.diff {
177                            Some(diff) => {
178                                let next_path = Self::join_path(&path, &key);
179
180                                let mut got = self.opt.mid_object;
181                                if let Err(e) = self.pending_objectmap(&next_path, &diff).await {
182                                    warn!("iterator over objectmap diff error, now will treat as normal diff object! path={}, key={}, value={}, {}", path, key, value, e);
183
184                                    // FIXME 如果其中一个objectmap遍历失败了，是终止遍历，还是把这个id当成一个普通对象来处理？
185                                    got = self.opt.leaf_object;
186                                }
187
188                                if got {
189                                    let item = ObjectMapPathContentItem {
190                                        path: path.clone(),
191                                        value: value.into_content(Some(&key)),
192                                        content_type: ObjectMapSimpleContentType::DiffMap,
193                                    };
194                                    result.list.push(item);
195                                    remaining -= 1;
196                                }
197                            }
198                            None => {
199                                if self.opt.leaf_object {
200                                    let item = ObjectMapPathContentItem {
201                                        path: path.clone(),
202                                        value: value.into_content(Some(&key)),
203                                        content_type: ObjectMapSimpleContentType::DiffMap,
204                                    };
205    
206                                    result.list.push(item);
207                                    remaining -= 1;
208                                }
209                            }
210                        }
211                    }
212                    ObjectMapContentItem::Set(value) => {
213                        match value.obj_type_code() {
214                            ObjectTypeCode::ObjectMap => {
215
216                                let mut got = self.opt.mid_object;
217                                if let Err(e) = self.pending_objectmap(&path, &value).await
218                                {
219                                    warn!("iterator over objectmap error, now will treat as normal object! path={}, value={}, {}", path, value, e);
220
221                                    // FIXME 如果其中一个objectmap遍历失败了，是终止遍历，还是把这个id当成一个叶子对象来处理？
222                                    got = self.opt.leaf_object;
223                                }
224
225                                if got {
226                                    let item = ObjectMapPathContentItem {
227                                        path: path.clone(),
228                                        value: value.into_content(None),
229                                        content_type: ObjectMapSimpleContentType::Set,
230                                    };
231
232                                    result.list.push(item);
233                                    remaining -= 1;
234                                }
235                            }
236                            _ => {
237                                if self.opt.leaf_object {
238                                    let item = ObjectMapPathContentItem {
239                                        path: path.clone(),
240                                        value: value.into_content(None),
241                                        content_type: ObjectMapSimpleContentType::Set,
242                                    };
243    
244                                    result.list.push(item);
245                                    remaining -= 1;
246                                }
247                            }
248                        }
249                    }
250                    ObjectMapContentItem::DiffSet(value) => {
251                        if self.opt.leaf_object {
252                            let item = ObjectMapPathContentItem {
253                                path: path.clone(),
254                                value: value.into_content(None),
255                                content_type: ObjectMapSimpleContentType::DiffSet,
256                            };
257    
258                            result.list.push(item);
259                            remaining -= 1;
260                        }
261                    }
262                }
263            }
264
265            if remaining == 0 {
266                assert_eq!(result.list.len(), step);
267                break;
268            }
269        }
270
271        Ok(result)
272    }
273
274    async fn pending_objectmap(&mut self, path: &str, value: &ObjectId) -> BuckyResult<()> {
275
276        // 尝试从cache加载目标
277        let target = self.cache.get_object_map(value).await?;
278        if target.is_none() {
279            let msg = format!(
280                "iterator with sub objectmap but not found! path={}, objmap={}",
281                path, value
282            );
283            error!("{}", msg);
284            return Err(BuckyError::new(BuckyErrorCode::NotFound, msg));
285        }
286        let target = target.unwrap();
287        let it = ObjectMapBindIterator::new_with_target(target, self.cache.clone()).await;
288
289        let pending_seg = PathIteratorSeg {
290            path: path.to_owned(),
291            it,
292        };
293
294        self.stack.push_front(pending_seg);
295        Ok(())
296    }
297}
298
299#[cfg(test)]
300mod test {
301    use super::super::cache::*;
302    use super::super::path::*;
303    use super::*;
304
305    use std::str::FromStr;
306
307    async fn gen_path(path: &ObjectMapPath) -> ObjectId {
308        let x1_value = ObjectId::from_str("95RvaS5anntyAoRUBi48vQoivWzX95M8xm4rkB93DdSt").unwrap();
309        let x1_value2 = ObjectId::from_str("95RvaS5aZKKM8ghTYmsTyhSEWD4pAmALoUSJx1yNxSx5").unwrap();
310        info!(
311            "typecode: {:?}, {:?}",
312            x1_value.obj_type_code(),
313            x1_value2.obj_type_code()
314        );
315
316        for i in 0..100 {
317            let key = format!("/a/b/{}", i);
318            path.insert_with_path(&key, &x1_value).await.unwrap();
319        }
320
321        for i in 0..100 {
322            let key = format!("/a/c/{}", i);
323            path.insert_with_path(&key, &x1_value).await.unwrap();
324        }
325
326
327        for i in 0..10 {
328            let key = format!("/a/b_{}", i);
329            path.insert_with_path(&key, &x1_value2).await.unwrap();
330        }
331
332        for i in 0..10 {
333            let key = format!("/a_{}", i);
334            path.insert_with_path(&key, &x1_value2).await.unwrap();
335        }
336
337        path.root()
338    }
339
340    async fn test_path_iterator() {
341        let noc = ObjectMapMemoryNOCCache::new();
342        let root_cache = ObjectMapRootMemoryCache::new_default_ref(None, noc);
343        let cache = ObjectMapOpEnvMemoryCache::new_ref(root_cache.clone());
344
345        // 创建一个空的objectmap作为root
346        let owner = ObjectId::default();
347        let root = ObjectMap::new(
348            ObjectMapSimpleContentType::Map,
349            Some(owner.clone()),
350            Some(owner.clone()),
351        )
352        .no_create_time()
353        .build();
354        let root_id = root.flush_id();
355        cache.put_object_map(&root_id, root, None).unwrap();
356        info!("new root: {}", root_id);
357
358        let path = ObjectMapPath::new(root_id.clone(), cache.clone(), true);
359        let path_root = gen_path(&path).await;
360        info!("generated path root: {}", path_root);
361
362        let root = cache.get_object_map(&path_root).await.unwrap();
363        let mut it = ObjectMapPathIterator::new(root.unwrap(), cache, ObjectMapPathIteratorOption::default()).await;
364        while !it.is_end() {
365            let list = it.next(1).await.unwrap();
366            info!("list: {} {:?}", 1, list.list);
367        }
368    }
369
370    #[test]
371    fn test() {
372        crate::init_simple_log("test-object-map-path-iterator", Some("debug"));
373        async_std::task::block_on(async move {
374            test_path_iterator().await;
375        });
376    }
377}
bucky_objects/objects/object_map/path_iterator.rs

bucky_objects/objects/object_map/
path_iterator.rs
