everscale_types/dict/ops/
insert.rs

1use crate::cell::*;
2use crate::dict::{
3    make_leaf, make_leaf_with_extra, read_label, rebuild_aug_dict_from_stack,
4    rebuild_dict_from_stack, split_aug_edge, split_edge, AugDictFn, Branch, Segment, SetMode,
5};
6use crate::error::Error;
7
8/// Inserts the value associated with key in dictionary
9/// in accordance with the logic of the specified [`SetMode`].
10pub fn dict_insert(
11    dict: &mut Option<Cell>,
12    key: &mut CellSlice,
13    key_bit_len: u16,
14    value: &dyn Store,
15    mode: SetMode,
16    context: &mut dyn CellContext,
17) -> Result<bool, Error> {
18    if key.size_bits() != key_bit_len {
19        return Err(Error::CellUnderflow);
20    }
21
22    let mut data = match dict.as_ref() {
23        // TODO: change mode to `LoadMode::UseGas` if copy-on-write for libraries is not ok.
24        Some(data) => ok!(context.load_dyn_cell(data.as_ref(), LoadMode::Full)),
25        None if mode.can_add() => {
26            *dict = Some(ok!(make_leaf(key, key_bit_len, value, context)));
27            return Ok(true);
28        }
29        None => return Ok(false),
30    };
31
32    let mut stack = Vec::<Segment>::new();
33
34    let leaf = loop {
35        let mut remaining_data = ok!(data.as_slice());
36
37        // Read the next part of the key from the current data
38        let prefix = &mut ok!(read_label(&mut remaining_data, key.size_bits()));
39
40        // Match the prefix with the key
41        let lcp = key.longest_common_data_prefix(prefix);
42        match lcp.size_bits().cmp(&key.size_bits()) {
43            // If all bits match, an existing value was found
44            std::cmp::Ordering::Equal => {
45                // Check if we can replace the value
46                if !mode.can_replace() {
47                    // TODO: what is the desired behavior for root as a library?
48                    return Ok(false);
49                }
50                // Replace the existing value
51                break ok!(make_leaf(prefix, key.size_bits(), value, context));
52            }
53            // LCP is less than prefix, an edge to slice was found
54            std::cmp::Ordering::Less if lcp.size_bits() < prefix.size_bits() => {
55                // Check if we can add a new value
56                if !mode.can_add() {
57                    // TODO: what is the desired behavior for root as a library?
58                    return Ok(false);
59                }
60                break ok!(split_edge(
61                    &remaining_data,
62                    prefix,
63                    &lcp,
64                    key,
65                    value,
66                    context
67                ));
68            }
69            // The key contains the entire prefix, but there are still some bits left
70            std::cmp::Ordering::Less => {
71                // Fail fast if there are not enough references in the fork
72                if data.reference_count() != 2 {
73                    return Err(Error::CellUnderflow);
74                }
75
76                // Remove the LCP from the key
77                let key_bit_len = key.size_bits();
78                key.skip_first(lcp.size_bits(), 0).ok();
79
80                // Load the next branch
81                let next_branch = match key.load_bit() {
82                    Ok(bit) => Branch::from(bit),
83                    Err(e) => return Err(e),
84                };
85
86                let child = match data.reference(next_branch as u8) {
87                    // TODO: change mode to `LoadMode::UseGas` if copy-on-write for libraries is not ok
88                    Some(cell) => ok!(context.load_dyn_cell(cell, LoadMode::Full)),
89                    None => return Err(Error::CellUnderflow),
90                };
91
92                // Push an intermediate edge to the stack
93                stack.push(Segment {
94                    data,
95                    next_branch,
96                    key_bit_len,
97                });
98                data = child;
99            }
100            std::cmp::Ordering::Greater => {
101                debug_assert!(false, "LCP of prefix and key can't be greater than key");
102                unsafe { std::hint::unreachable_unchecked() };
103            }
104        }
105    };
106
107    *dict = Some(ok!(rebuild_dict_from_stack(stack, leaf, context)));
108    Ok(true)
109}
110
111/// Inserts the value associated with key in aug dictionary
112/// in accordance with the logic of the specified [`SetMode`] and comparator for extra
113#[allow(clippy::too_many_arguments)]
114pub fn aug_dict_insert(
115    dict: &mut Option<Cell>,
116    key: &mut CellSlice,
117    key_bit_len: u16,
118    extra: &dyn Store,
119    value: &dyn Store,
120    mode: SetMode,
121    comparator: AugDictFn,
122    context: &mut dyn CellContext,
123) -> Result<bool, Error> {
124    if key.size_bits() != key_bit_len {
125        return Err(Error::CellUnderflow);
126    }
127
128    let mut data = match dict.as_ref() {
129        // TODO: change mode to `LoadMode::UseGas` if copy-on-write for libraries is not ok.
130        Some(data) => {
131            ok!(context.load_dyn_cell(data.as_ref(), LoadMode::Full))
132        }
133        None if mode.can_add() => {
134            let cell = ok!(make_leaf_with_extra(
135                key,
136                key_bit_len,
137                extra,
138                value,
139                context
140            ));
141            *dict = Some(cell);
142            return Ok(true);
143        }
144        None => return Ok(false),
145    };
146
147    let mut stack = Vec::<Segment>::new();
148
149    let leaf = loop {
150        let mut remaining_data = ok!(data.as_slice());
151        // Read the next part of the key from the current data
152        let prefix = &mut ok!(read_label(&mut remaining_data, key.size_bits()));
153        // Match the prefix with the key
154        let lcp = key.longest_common_data_prefix(prefix);
155        match lcp.size_bits().cmp(&key.size_bits()) {
156            // If all bits match, an existing value was found
157            std::cmp::Ordering::Equal => {
158                // Check if we can replace the value
159                if !mode.can_replace() {
160                    // TODO: what is the desired behavior for root as a library?
161                    return Ok(false);
162                }
163                // Replace the existing value
164                break ok!(make_leaf_with_extra(
165                    prefix,
166                    key.size_bits(),
167                    extra,
168                    value,
169                    context
170                ));
171            }
172            // LCP is less than prefix, an edge to slice was found
173            std::cmp::Ordering::Less if lcp.size_bits() < prefix.size_bits() => {
174                // Check if we can add a new value
175                if !mode.can_add() {
176                    // TODO: what is the desired behavior for root as a library?
177                    return Ok(false);
178                }
179                break ok!(split_aug_edge(
180                    &mut remaining_data,
181                    prefix,
182                    &lcp,
183                    key,
184                    extra,
185                    value,
186                    comparator,
187                    context,
188                ));
189            }
190            // The key contains the entire prefix, but there are still some bits left
191            std::cmp::Ordering::Less => {
192                // Fail fast if there are not enough references in the fork
193                if data.reference_count() != 2 {
194                    return Err(Error::CellUnderflow);
195                }
196
197                // Remove the LCP from the key
198                let key_bit_len = key.size_bits();
199                key.skip_first(lcp.size_bits(), 0).ok();
200                // Load the next branch
201                let next_branch = match key.load_bit() {
202                    Ok(bit) => Branch::from(bit),
203                    Err(e) => return Err(e),
204                };
205                let child = match data.reference(next_branch as u8) {
206                    // TODO: change mode to `LoadMode::UseGas` if copy-on-write for libraries is not ok
207                    Some(cell) => ok!(context.load_dyn_cell(cell, LoadMode::Full)),
208                    None => return Err(Error::CellUnderflow),
209                };
210
211                // Push an intermediate edge to the stack
212                stack.push(Segment {
213                    data,
214                    next_branch,
215                    key_bit_len,
216                });
217                data = child;
218            }
219            std::cmp::Ordering::Greater => {
220                debug_assert!(false, "LCP of prefix and key can't be greater than key");
221                unsafe { std::hint::unreachable_unchecked() };
222            }
223        }
224    };
225
226    *dict = Some(ok!(rebuild_aug_dict_from_stack(
227        stack, leaf, comparator, context,
228    )));
229
230    Ok(true)
231}
232
233/// Inserts the value associated with key in dictionary
234/// in accordance with the logic of the specified [`SetMode`].
235///
236/// Returns a tuple with a new dict root, changed flag and the previous value.
237pub fn dict_insert_owned(
238    dict: &mut Option<Cell>,
239    key: &mut CellSlice,
240    key_bit_len: u16,
241    value: &dyn Store,
242    mode: SetMode,
243    context: &mut dyn CellContext,
244) -> Result<(bool, Option<CellSliceParts>), Error> {
245    fn last(
246        stack: &[Segment],
247        context: &mut dyn CellContext,
248        mode: LoadMode,
249    ) -> Result<Option<Cell>, Error> {
250        match stack.last() {
251            Some(Segment {
252                data, next_branch, ..
253            }) => match data.reference_cloned(*next_branch as u8) {
254                Some(cell) => context.load_cell(cell, mode).map(Some),
255                None => Err(Error::CellUnderflow),
256            },
257            None => Ok(None),
258        }
259    }
260
261    if key.size_bits() != key_bit_len {
262        return Err(Error::CellUnderflow);
263    }
264
265    let root = match &dict {
266        // TODO: change mode to `LoadMode::UseGas` if copy-on-write for libraries is not ok.
267        Some(data) => ok!(context.load_cell(data.clone(), LoadMode::Full)),
268        None if mode.can_add() => {
269            *dict = Some(ok!(make_leaf(key, key_bit_len, value, context)));
270            return Ok((true, None));
271        }
272        None => return Ok((false, None)),
273    };
274    let mut data = root.as_ref();
275    let mut stack = Vec::<Segment>::new();
276
277    let (mut leaf, value_range) = loop {
278        let mut remaining_data = ok!(data.as_slice());
279
280        // Read the next part of the key from the current data
281        let prefix = &mut ok!(read_label(&mut remaining_data, key.size_bits()));
282
283        // Match the prefix with the key
284        let lcp = key.longest_common_data_prefix(prefix);
285        match lcp.size_bits().cmp(&key.size_bits()) {
286            // If all bits match, an existing value was found
287            std::cmp::Ordering::Equal => {
288                // Check if we can replace the value
289                if !mode.can_replace() {
290                    // TODO: change mode to `LoadMode::Noop` if copy-on-write for libraries is not ok.
291                    let value = (
292                        ok!(last(&stack, context, LoadMode::Resolve))
293                            .unwrap_or_else(|| root.clone()),
294                        remaining_data.range(),
295                    );
296                    // TODO: what is the desired behavior for root as a library?
297                    return Ok((false, Some(value)));
298                }
299                // Replace the existing value
300                break (
301                    ok!(make_leaf(prefix, key.size_bits(), value, context)),
302                    Some(remaining_data.range()),
303                );
304            }
305            // LCP is less than prefix, an edge to slice was found
306            std::cmp::Ordering::Less if lcp.size_bits() < prefix.size_bits() => {
307                // Check if we can add a new value
308                if !mode.can_add() {
309                    // TODO: what is the desired behavior for root as a library?
310                    return Ok((false, None));
311                }
312                break (
313                    ok!(split_edge(
314                        &remaining_data,
315                        prefix,
316                        &lcp,
317                        key,
318                        value,
319                        context
320                    )),
321                    None,
322                );
323            }
324            // The key contains the entire prefix, but there are still some bits left
325            std::cmp::Ordering::Less => {
326                // Fail fast if there are not enough references in the fork
327                if data.reference_count() != 2 {
328                    return Err(Error::CellUnderflow);
329                }
330
331                // Remove the LCP from the key
332                let key_bit_len = key.size_bits();
333                key.skip_first(lcp.size_bits(), 0).ok();
334
335                // Load the next branch
336                let next_branch = match key.load_bit() {
337                    Ok(bit) => Branch::from(bit),
338                    Err(e) => return Err(e),
339                };
340
341                let child = match data.reference(next_branch as u8) {
342                    // TODO: change mode to `LoadMode::UseGas` if copy-on-write for libraries is not ok
343                    Some(cell) => ok!(context.load_dyn_cell(cell, LoadMode::Full)),
344                    None => return Err(Error::CellUnderflow),
345                };
346
347                // Push an intermediate edge to the stack
348                stack.push(Segment {
349                    data,
350                    next_branch,
351                    key_bit_len,
352                });
353                data = child;
354            }
355            std::cmp::Ordering::Greater => {
356                debug_assert!(false, "LCP of prefix and key can't be greater than key");
357                unsafe { std::hint::unreachable_unchecked() };
358            }
359        }
360    };
361
362    let value = match value_range {
363        Some(range) => {
364            // TODO: change mode to `LoadMode::Noop` if copy-on-write for libraries is not ok
365            let last = ok!(last(&stack, context, LoadMode::Resolve));
366            leaf = ok!(rebuild_dict_from_stack(stack, leaf, context));
367            Some((last.unwrap_or(root), range))
368        }
369        None => {
370            leaf = ok!(rebuild_dict_from_stack(stack, leaf, context));
371            None
372        }
373    };
374
375    *dict = Some(leaf);
376    Ok((true, value))
377}
everscale_types/dict/ops/insert.rs

everscale_types/dict/ops/
insert.rs
