revm_state/bal/
writes.rs

1//! BAL containing writes.
2
3use crate::bal::BalIndex;
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 BalIndex.
13    pub writes: Vec<(BalIndex, T)>,
14}
15
16impl<T: PartialEq + Clone> BalWrites<T> {
17    /// Create a new BalWrites.
18    pub fn new(mut writes: Vec<(BalIndex, 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: BalIndex) -> 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: BalIndex) -> 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 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: BalIndex, 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 BalIndex is same as last it will override the value.
85    pub fn update(&mut self, index: BalIndex, 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 BalIndex 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: BalIndex,
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    #[test]
144    fn test_get() {
145        let bal_writes = BalWrites::new(vec![(0, 1), (1, 2), (2, 3)]);
146        assert_eq!(bal_writes.get(0), None);
147        assert_eq!(bal_writes.get(1), Some(1));
148        assert_eq!(bal_writes.get(2), Some(2));
149        assert_eq!(bal_writes.get(3), Some(3));
150        assert_eq!(bal_writes.get(4), Some(3));
151    }
152
153    fn get_binary_search(threshold: BalIndex) {
154        // Construct test data up to (threshold - 1), skipping one key to simulate a gap.
155        let entries: Vec<_> = (0..threshold - 1)
156            .map(|i| (i, i + 1))
157            .chain(std::iter::once((threshold, threshold + 1)))
158            .collect();
159
160        let bal_writes = BalWrites::new(entries);
161
162        // Case 1: lookup before any entries
163        assert_eq!(bal_writes.get(0), None);
164
165        // Case 2: lookups for existing keys before the gap
166        for i in 1..threshold - 1 {
167            assert_eq!(bal_writes.get(i), Some(i));
168        }
169
170        // Case 3: lookup at the skipped key — should return the previous value
171        assert_eq!(bal_writes.get(threshold), Some(threshold - 1));
172
173        // Case 4: lookup after the skipped key — should return the next valid value
174        assert_eq!(bal_writes.get(threshold + 1), Some(threshold + 1));
175    }
176
177    #[test]
178    fn test_get_binary_search() {
179        get_binary_search(4);
180        get_binary_search(5);
181        get_binary_search(6);
182        get_binary_search(7);
183    }
184}
revm_state/bal/writes.rs

revm_state/bal/
writes.rs
