onion_vm/utils/
fastmap.rs

1
2//! Onion 高性能键池与映射（FastMap）模块。
3//!
4//! 提供高效的键池（OnionKeyPool）与稀疏映射（OnionFastMap）实现，
5//! 支持常量池优化、索引访问、键到索引的高效映射，适用于虚拟机参数、捕获、环境等场景。
6//!
7//! # 主要功能
8//! - 键池的唯一化与索引映射
9//! - 稀疏键值对存储与高效查找
10//! - 支持索引与键的双向访问
11//! - 线性插入、查找与覆盖
12
13use std::{hash::Hash, sync::Arc};
14
15use rustc_hash::FxHashMap;
16
17
18/// Onion 键池。
19///
20/// 提供唯一化的键集合与键到索引的高效映射，适用于常量池、参数池等场景。
21///
22/// # 字段
23/// - `keys`: 键的有序集合
24/// - `key_to_index`: 键到索引的哈希映射
25#[derive(Debug, Clone)]
26pub struct OnionKeyPool<K: PartialEq + Eq + Hash + Clone> {
27    keys: Arc<[K]>,
28    key_to_index: Arc<FxHashMap<K, usize>>,
29}
30
31impl<K: PartialEq + Eq + Hash + Clone> OnionKeyPool<K> {
32    pub fn create(keys: Vec<K>) -> Self {
33        let mut key_to_index = FxHashMap::default();
34        for (i, k) in keys.iter().enumerate() {
35            key_to_index.insert(k.clone(), i);
36        }
37        Self {
38            keys: keys.into(),
39            key_to_index: Arc::new(key_to_index),
40        }
41    }
42
43    pub fn new(k: Arc<[K]>, i: Arc<FxHashMap<K, usize>>) -> Self {
44        Self {
45            keys: k,
46            key_to_index: i,
47        }
48    }
49    pub fn keys(&self) -> &[K] {
50        &self.keys
51    }
52
53    pub fn indices(&self) -> &FxHashMap<K, usize> {
54        &self.key_to_index
55    }
56}
57
58
59/// Onion 高性能稀疏映射。
60///
61/// 基于键池索引实现的稀疏键值对存储，支持高效查找与插入。
62/// 适用于参数绑定、捕获环境等虚拟机场景。
63/// 不保证键的唯一性，后插入的值可能会覆盖先前的值。
64///
65/// # 字段
66/// - `pairs`: (索引, 值) 对列表
67/// - `pool`: 关联的键池
68#[derive(Debug, Clone)]
69pub struct OnionFastMap<K: PartialEq + Eq + Hash + Clone, V> {
70    pairs: Vec<(usize, V)>,
71    pool: OnionKeyPool<K>,
72}
73
74impl<K: PartialEq + Eq + Hash + Clone, V> OnionFastMap<K, V> {
75    pub fn new(pool: OnionKeyPool<K>) -> Self {
76        Self {
77            pairs: Vec::new(),
78            pool,
79        }
80    }
81
82    pub fn pool(&self) -> &OnionKeyPool<K> {
83        &self.pool
84    }
85
86    pub fn new_with_pairs(pairs: Vec<(usize, V)>, pool: OnionKeyPool<K>) -> Self {
87        Self { pairs, pool }
88    }
89
90    #[inline(always)]
91    pub fn push<Q: ?Sized>(&mut self, key: &Q, value: V) -> Option<()>
92    where
93        K: std::borrow::Borrow<Q>,
94        Q: std::hash::Hash + Eq,
95    {
96        if let Some(index) = self.pool.indices().get(key).copied() {
97            self.pairs.push((index, value));
98            Some(())
99        } else {
100            None
101        }
102    }
103
104    #[inline(always)]
105    pub fn push_with_index(&mut self, index: usize, value: V) -> Option<()> {
106        if index < self.pool.keys().len() {
107            self.pairs.push((index, value));
108            Some(())
109        } else {
110            None
111        }
112    }
113
114    #[inline(always)]
115    pub fn pairs(&self) -> &[(usize, V)] {
116        &self.pairs
117    }
118
119    #[inline(always)]
120    pub fn set_pairs(&mut self, pairs: Vec<(usize, V)>) {
121        self.pairs = pairs;
122    }
123
124    #[inline(always)]
125    pub fn clear(&mut self) {
126        self.pairs.clear();
127    }
128
129    #[inline(always)]
130    pub fn to_index<Q: ?Sized>(&self, key: &Q) -> Option<usize>
131    where
132        K: std::borrow::Borrow<Q>,
133        Q: std::hash::Hash + Eq,
134    {
135        self.pool.indices().get(key).copied()
136    }
137
138    #[inline(always)]
139    pub fn from_index(&self, index: usize) -> Option<&K> {
140        self.pool.keys().get(index)
141    }
142
143    #[inline(always)]
144    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
145    where
146        K: std::borrow::Borrow<Q>,
147        Q: std::hash::Hash + Eq,
148    {
149        let target_id = self.to_index(key)?;
150        self.pairs
151            .iter()
152            .rfind(|(id, _)| *id == target_id)
153            .map(|(_, v)| v)
154    }
155    #[inline(always)]
156    pub fn get_by_index(&self, target_index: usize) -> Option<&V> {
157        // 同样，需要线性扫描
158        self.pairs
159            .iter()
160            .rfind(|(id, _)| *id == target_index)
161            .map(|(_, v)| v)
162    }
163}
164
165impl<K: PartialEq + Eq + Hash + Clone, V> Default for OnionFastMap<K, V> {
166    fn default() -> Self {
167        Self::new(OnionKeyPool::create(Vec::new()))
168    }
169}
onion_vm/utils/fastmap.rs

onion_vm/utils/
fastmap.rs
