revm_state/bal/
writes.rs

1//! BAL containing writes.
2
3use crate::bal::BlockAccessIndex;
4use std::vec::Vec;
5
6/// Use to store values
7///
8/// If empty it means that this item was read from database.
9#[derive(Debug, Default, Clone, PartialEq, Eq)]
10#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
11pub struct BalWrites<T: PartialEq + Clone> {
12    /// List of writes with [`BlockAccessIndex`].
13    pub writes: Vec<(BlockAccessIndex, T)>,
14}
15
16impl<T: PartialEq + Clone> BalWrites<T> {
17    /// Create a new BalWrites.
18    pub fn new(mut writes: Vec<(BlockAccessIndex, T)>) -> Self {
19        writes.sort_by_key(|(index, _)| *index);
20        Self { writes }
21    }
22
23    /// Linear search is used for small number of writes. It is faster than binary search.
24    #[inline(never)]
25    pub fn get_linear_search(&self, bal_index: BlockAccessIndex) -> Option<T> {
26        let mut last_item = None;
27        for (index, item) in self.writes.iter() {
28            // if index is greater than bal_index we return the last item.
29            if index >= &bal_index {
30                return last_item;
31            }
32            last_item = Some(item.clone());
33        }
34        last_item
35    }
36
37    /// Get value from BAL.
38    pub fn get(&self, bal_index: BlockAccessIndex) -> Option<T> {
39        if self.writes.len() < 5 {
40            return self.get_linear_search(bal_index);
41        }
42        // else do binary search.
43        let i = match self
44            .writes
45            .binary_search_by_key(&bal_index, |(index, _)| *index)
46        {
47            Ok(i) => i,
48            Err(i) => i,
49        };
50        // only if i is not zero, we return the previous value.
51        (i != 0).then(|| self.writes[i - 1].1.clone())
52    }
53
54    /// Extend the builder with another builder.
55    pub fn extend(&mut self, other: BalWrites<T>) {
56        self.writes.extend(other.writes);
57    }
58
59    /// Returns true if the builder is empty.
60    pub const fn is_empty(&self) -> bool {
61        self.writes.is_empty()
62    }
63
64    /// Force insert a value into the BalWrites.
65    ///
66    /// Check if last index is same as the index to insert.
67    /// If it is, we override the value.
68    /// If it is not, we push the value to the end of the vector.
69    ///
70    /// No checks for original value is done. This is useful when we know that value is different.
71    #[inline]
72    pub fn force_update(&mut self, index: BlockAccessIndex, value: T) {
73        if let Some(last) = self.writes.last_mut() {
74            if index == last.0 {
75                last.1 = value;
76                return;
77            }
78        }
79        self.writes.push((index, value));
80    }
81
82    /// Insert a value into the builder.
83    ///
84    /// If [`BlockAccessIndex`] is same as last it will override the value.
85    pub fn update(&mut self, index: BlockAccessIndex, original_value: &T, value: T) {
86        self.update_with_key(index, original_value, value, |i| i);
87    }
88
89    /// Insert a value into the builder.
90    ///
91    /// If [`BlockAccessIndex`] is same as last it will override the value.
92    ///
93    /// Assumes that index is always greater than last one and that Writes are updated in proper order.
94    #[inline]
95    pub fn update_with_key<K: PartialEq, F>(
96        &mut self,
97        index: BlockAccessIndex,
98        original_subvalue: &K,
99        value: T,
100        f: F,
101    ) where
102        F: Fn(&T) -> &K,
103    {
104        // if index is different, we push the new value.
105        if let Some(last) = self.writes.last_mut() {
106            if last.0 != index {
107                // we push the new value only if it is changed.
108                if f(&last.1) != f(&value) {
109                    self.writes.push((index, value));
110                }
111                return;
112            }
113        }
114
115        // extract previous (Can be original_subvalue or previous value) and last value.
116        let (previous, last) = match self.writes.as_mut_slice() {
117            [.., previous, last] => (f(&previous.1), last),
118            [last] => (original_subvalue, last),
119            [] => {
120                // if writes are empty check if original value is same as newly set value.
121                if original_subvalue != f(&value) {
122                    self.writes.push((index, value));
123                }
124                return;
125            }
126        };
127
128        // if previous value is same, we pop the last value.
129        if previous == f(&value) {
130            self.writes.pop();
131            return;
132        }
133
134        // if it is different, we update the last value.
135        last.1 = value;
136    }
137}
138
139#[cfg(test)]
140mod tests {
141    use super::*;
142
143    const fn idx(index: u64) -> BlockAccessIndex {
144        BlockAccessIndex::new(index)
145    }
146
147    #[test]
148    fn test_get() {
149        let bal_writes = BalWrites::new(vec![(idx(0), 1), (idx(1), 2), (idx(2), 3)]);
150        assert_eq!(bal_writes.get(idx(0)), None);
151        assert_eq!(bal_writes.get(idx(1)), Some(1));
152        assert_eq!(bal_writes.get(idx(2)), Some(2));
153        assert_eq!(bal_writes.get(idx(3)), Some(3));
154        assert_eq!(bal_writes.get(idx(4)), Some(3));
155    }
156
157    fn get_binary_search(threshold: u64) {
158        // Construct test data up to (threshold - 1), skipping one key to simulate a gap.
159        let entries: Vec<_> = (0..threshold - 1)
160            .map(|i| (idx(i), i + 1))
161            .chain(std::iter::once((idx(threshold), threshold + 1)))
162            .collect();
163
164        let bal_writes = BalWrites::new(entries);
165
166        // Case 1: lookup before any entries
167        assert_eq!(bal_writes.get(idx(0)), None);
168
169        // Case 2: lookups for existing keys before the gap
170        for i in 1..threshold - 1 {
171            assert_eq!(bal_writes.get(idx(i)), Some(i));
172        }
173
174        // Case 3: lookup at the skipped key — should return the previous value
175        assert_eq!(bal_writes.get(idx(threshold)), Some(threshold - 1));
176
177        // Case 4: lookup after the skipped key — should return the next valid value
178        assert_eq!(bal_writes.get(idx(threshold + 1)), Some(threshold + 1));
179    }
180
181    #[test]
182    fn test_get_binary_search() {
183        get_binary_search(4);
184        get_binary_search(5);
185        get_binary_search(6);
186        get_binary_search(7);
187    }
188}
revm_state/bal/writes.rs

revm_state/bal/
writes.rs
