tree_cache/
lib.rs

1// Copyright (c) 2022 myl7
2// SPDX-License-Identifier: Apache-2.0
3
4use std::sync::{Arc, RwLock};
5
6pub struct Tree {
7    root: Arc<RwLock<Box<Node>>>,
8}
9
10impl Tree {
11    pub fn new() -> Self {
12        Self {
13            root: Arc::new(RwLock::new(Box::new(Node::new("", Some(""))))),
14        }
15    }
16
17    pub fn insert(&mut self, path: impl AsRef<str>, id: impl AsRef<str>) {
18        let p = path.as_ref().to_owned();
19        let mut components = p.split("/").collect::<Vec<_>>();
20        components = format_components(components);
21
22        let mut node = self.root.clone();
23        for &c in components.iter() {
24            let next_node = match node
25                .read()
26                .unwrap()
27                .children
28                .iter()
29                .find(|child| child.read().unwrap().name.as_str() == c)
30            {
31                Some(child) => Some(child.clone()),
32                None => None,
33            };
34            node = next_node.unwrap_or_else(|| {
35                let mut node_write = node.write().unwrap();
36                node_write
37                    .children
38                    .push(Arc::new(RwLock::new(Box::new(Node::new(
39                        c,
40                        None as Option<String>,
41                    )))));
42                node_write.children.last().unwrap().clone()
43            });
44        }
45        node.write().unwrap().id = Some(id.as_ref().to_owned());
46    }
47
48    pub fn get(&self, path: impl AsRef<str>) -> Option<String> {
49        let p = path.as_ref().to_owned();
50        let mut components = p.split("/").collect::<Vec<_>>();
51        components = format_components(components);
52
53        let mut node = self.root.clone();
54        for &c in components.iter() {
55            let next_node = match node
56                .read()
57                .unwrap()
58                .children
59                .iter()
60                .find(|child| child.read().unwrap().name.as_str() == c)
61            {
62                Some(child) => child.clone(),
63                None => return None,
64            };
65            node = next_node;
66        }
67        let id = node.read().unwrap().id.clone();
68        id
69    }
70
71    pub fn invalid(&self, path: impl AsRef<str>) {
72        let p = path.as_ref().to_owned();
73        let mut components = p.split("/").collect::<Vec<_>>();
74        components = format_components(components);
75        let last_component = match components.last() {
76            Some(&c) => c,
77            None => return,
78        };
79        components.pop();
80
81        let mut node = self.root.clone();
82        for &c in components.iter() {
83            let next_node = match node
84                .read()
85                .unwrap()
86                .children
87                .iter()
88                .find(|child| child.read().unwrap().name.as_str() == c)
89            {
90                Some(child) => child.clone(),
91                None => return,
92            };
93            node = next_node
94        }
95        let mut node_write = node.write().unwrap();
96        if let Some(i) = node_write
97            .children
98            .iter()
99            .enumerate()
100            .find(|(_, child)| child.read().unwrap().name.as_str() == last_component)
101            .map(|(i, _)| i)
102        {
103            node_write.children.remove(i);
104        }
105    }
106}
107
108fn format_components(mut components: Vec<&str>) -> Vec<&str> {
109    if components.first().map(|&c| c == "").unwrap_or(false) {
110        components.remove(0);
111    }
112    if components.last().map(|&c| c == "").unwrap_or(false) {
113        components.pop();
114    }
115    components
116}
117
118struct Node {
119    name: String,
120    id: Option<String>,
121    children: Vec<Arc<RwLock<Box<Node>>>>,
122}
123
124impl Node {
125    fn new(name: impl AsRef<str>, id: Option<impl AsRef<str>>) -> Self {
126        Self {
127            name: name.as_ref().to_owned(),
128            id: id.map(|i| i.as_ref().to_owned()),
129            children: Vec::new(),
130        }
131    }
132}
133
134#[cfg(test)]
135mod tests {
136    use super::*;
137
138    #[test]
139    fn test_insert() {
140        let mut tree = Tree::new();
141        tree.insert("/test", "0");
142        let root = tree.root.read().unwrap();
143        assert_eq!(root.children.len(), 1);
144        let new_node = root.children[0].read().unwrap();
145        assert_eq!(new_node.name, "test");
146        assert_eq!(new_node.id.as_deref(), Some("0"));
147    }
148
149    #[test]
150    fn test_get() {
151        let mut tree = Tree::new();
152        tree.insert("/test", "0");
153        tree.insert("/test/test/test", "1");
154        assert_eq!(tree.get("/test").as_deref(), Some("0"));
155        assert_eq!(tree.get("/test/test/test").as_deref(), Some("1"));
156        assert_eq!(tree.get("/test/test"), None);
157        assert_eq!(tree.get("/test/test/test/test"), None);
158    }
159
160    #[test]
161    fn test_invalid() {
162        let mut tree = Tree::new();
163        tree.insert("/test", "0");
164        tree.insert("/test/test", "1");
165        tree.insert("/test/test/test", "2");
166        tree.invalid("/test/test/test/test");
167        tree.invalid("/test/test");
168        assert_eq!(tree.get("/test/test/test"), None);
169        assert_eq!(tree.get("/test").as_deref(), Some("0"));
170    }
171}
tree_cache/lib.rs

tree_cache/
lib.rs
