* [yew-devel] [PATCH yew-widget-toolkit 2/3] state: keyed slab tree: add key -> node_id cache
2025-09-29 13:12 [yew-devel] [PATCH yew-widget-toolkit 1/3] state: keyed slab tree: fix typo Dominik Csapak
@ 2025-09-29 13:12 ` Dominik Csapak
2025-09-29 13:12 ` [yew-devel] [PATCH yew-widget-toolkit 3/3] state: keyed slab tree: panic on inserting duplicate keys in debug mode Dominik Csapak
2025-10-03 6:22 ` [yew-devel] applied: [PATCH yew-widget-toolkit 1/3] state: keyed slab tree: fix typo Dietmar Maurer
2 siblings, 0 replies; 4+ messages in thread
From: Dominik Csapak @ 2025-09-29 13:12 UTC (permalink / raw)
To: yew-devel
The methods `find_node_by_key` and `find_node_by_key_mut` have to
linearly search for the key in the tree. When doing that for a large
number of keys, this becomes very slow.
To speed that up, introduce a `key_cache`, which is just a
`HashMap<Key, uszie>` that points to the node_id in the slab tree.
We have to be careful to update this cache with every insert or remove
operation.
* on insert, add the new entry into the cache
* on removal, remove the entry and do it recursively for all children of
that node
* on bulk append: iterate over the newly added subtree and add the keys
* on tree/root replace: recalculate the cache for the whole tree.
Signed-off-by: Dominik Csapak <d.csapak@proxmox.com>
---
src/state/tree_store/keyed_slab_tree.rs | 94 ++++++++++++++++++-------
1 file changed, 69 insertions(+), 25 deletions(-)
diff --git a/src/state/tree_store/keyed_slab_tree.rs b/src/state/tree_store/keyed_slab_tree.rs
index e26780c..df163a2 100644
--- a/src/state/tree_store/keyed_slab_tree.rs
+++ b/src/state/tree_store/keyed_slab_tree.rs
@@ -1,5 +1,5 @@
-use std::cmp::Ordering;
use std::collections::HashSet;
+use std::{cmp::Ordering, collections::HashMap};
use slab::Slab;
@@ -30,6 +30,8 @@ pub struct KeyedSlabTree<T> {
listeners: Slab<Callback<()>>,
+ key_cache: HashMap<Key, usize>,
+
pub(crate) view_root: bool,
}
@@ -98,7 +100,7 @@ impl<T> KeyedSlabTreeNodeMut<'_, T> {
/// Find a node by key.
pub fn find_node_by_key(&self, key: &Key) -> Option<KeyedSlabTreeNodeRef<T>> {
self.tree
- .find_subnode_by_key(self.node_id, key)
+ .find_subnode_by_key(key)
.map(|node_id| KeyedSlabTreeNodeRef {
node_id,
tree: self.tree,
@@ -108,7 +110,7 @@ impl<T> KeyedSlabTreeNodeMut<'_, T> {
/// Find a node by key (mutable).
pub fn find_node_by_key_mut(&mut self, key: &Key) -> Option<KeyedSlabTreeNodeMut<T>> {
self.tree
- .find_subnode_by_key(self.node_id, key)
+ .find_subnode_by_key(key)
.map(|node_id| KeyedSlabTreeNodeMut {
node_id,
tree: self.tree,
@@ -189,7 +191,7 @@ impl<T> KeyedSlabTreeNodeRef<'_, T> {
/// Find a node by key.
pub fn find_node_by_key(&self, key: &Key) -> Option<KeyedSlabTreeNodeRef<T>> {
self.tree
- .find_subnode_by_key(self.node_id, key)
+ .find_subnode_by_key(key)
.map(|node_id| KeyedSlabTreeNodeRef {
node_id,
tree: self.tree,
@@ -240,6 +242,7 @@ impl<T> KeyedSlabTree<T> {
filter: None,
listeners: Slab::new(),
view_root: true,
+ key_cache: HashMap::new(),
}
}
@@ -374,7 +377,10 @@ impl<T> KeyedSlabTree<T> {
///
/// The current tree (if any) is discarded.
pub fn set_root(&mut self, record: T) -> KeyedSlabTreeNodeMut<T> {
+ self.key_cache.clear();
+ let key = self.extract_key(&record);
let node = self.tree.set_root(record);
+ self.key_cache.insert(key, node.node_id);
KeyedSlabTreeNodeMut {
node_id: node.node_id,
tree: self,
@@ -386,6 +392,7 @@ impl<T> KeyedSlabTree<T> {
/// The current tree (if any) is discarded.
pub fn set_root_tree(&mut self, data: impl Into<SlabTree<T>>) {
self.tree.set_root_tree(data);
+ self.key_cache = self.recalculate_cache();
}
/// Set the whole tree, but safe/restore expanded state
@@ -396,7 +403,7 @@ impl<T> KeyedSlabTree<T> {
Some(root) => root.extract_expanded_state(),
None => HashSet::new(),
};
- self.tree.set_root_tree(data);
+ self.set_root_tree(data);
if let Some(mut root) = self.root_mut() {
root.apply_expanded_state(&expanded_state);
}
@@ -437,15 +444,62 @@ impl<T> KeyedSlabTree<T> {
level: usize,
parent: usize,
) -> usize {
- self.tree
- .append_subtree_node(subtree, subtree_node, level, parent)
+ let node_id = self
+ .tree
+ .append_subtree_node(subtree, subtree_node, level, parent);
+
+ let key_cache = self.calculate_cache(node_id);
+ self.key_cache.extend(key_cache);
+
+ node_id
+ }
+
+ fn remove_subtree_from_cache(&mut self, node_id: usize) {
+ if let Some(entry) = self.tree.get(node_id) {
+ self.key_cache.remove(&self.extract_key(&entry.record));
+ if let Some(children) = entry.children.clone() {
+ for child in children {
+ self.remove_subtree_from_cache(child);
+ }
+ }
+ }
}
fn remove_node_id(&mut self, node_id: usize) -> Option<T> {
+ self.remove_subtree_from_cache(node_id);
self.tree.remove_node_id(node_id)
}
+ fn calculate_cache(&self, node_id: usize) -> HashMap<Key, usize> {
+ let mut map = HashMap::new();
+ if let Some(node) = self.get(node_id) {
+ let key = self.extract_key(&node.record);
+ map.insert(key, node_id);
+ match node.children.clone() {
+ Some(list) => {
+ for child_id in list {
+ map.extend(self.calculate_cache(child_id));
+ }
+ }
+ None => {}
+ }
+ }
+
+ map
+ }
+
+ fn recalculate_cache(&self) -> HashMap<Key, usize> {
+ match self.tree.root_id {
+ Some(root_id) => self.calculate_cache(root_id),
+ None => HashMap::new(),
+ }
+ }
+
fn remove_tree_node_id(&mut self, node_id: usize) -> Option<KeyedSlabTree<T>> {
+ let key_cache = self.calculate_cache(node_id);
+ for key in key_cache.keys() {
+ self.key_cache.remove(key);
+ }
match self.tree.remove_tree_node_id(node_id) {
Some(tree) => Some(KeyedSlabTree {
extract_key: self.extract_key.clone(),
@@ -456,37 +510,27 @@ impl<T> KeyedSlabTree<T> {
filter: None,
listeners: Slab::new(),
view_root: true,
+ key_cache,
}),
None => None,
}
}
fn insert_record(&mut self, record: T, parent_id: Option<usize>) -> usize {
- self.tree.insert_record(record, parent_id)
+ let key = self.extract_key(&record);
+ let node_id = self.tree.insert_record(record, parent_id);
+ self.key_cache.insert(key, node_id);
+ node_id
}
- fn find_subnode_by_key(&self, node_id: usize, key: &Key) -> Option<usize> {
- let entry = self.get(node_id)?;
-
- if key == &self.extract_key(&entry.record) {
- return Some(node_id);
- }
-
- if let Some(children) = &entry.children {
- for child_id in children {
- if let Some(pos) = self.find_subnode_by_key(*child_id, key) {
- return Some(pos);
- }
- }
- }
-
- None
+ fn find_subnode_by_key(&self, key: &Key) -> Option<usize> {
+ self.key_cache.get(key).copied()
}
fn find_node_by_key(&self, key: &Key) -> Option<usize> {
match self.tree.root_id {
None => None,
- Some(root_id) => self.find_subnode_by_key(root_id, key),
+ Some(_root_id) => self.find_subnode_by_key(key),
}
}
--
2.47.3
_______________________________________________
yew-devel mailing list
yew-devel@lists.proxmox.com
https://lists.proxmox.com/cgi-bin/mailman/listinfo/yew-devel
^ permalink raw reply [flat|nested] 4+ messages in thread