everscale_types/dict/
mod.rs

1//! Dictionary implementation.
2
3use std::ops::ControlFlow;
4
5pub use self::aug::*;
6pub use self::ops::*;
7pub use self::raw::*;
8pub use self::typed::*;
9
10use crate::cell::*;
11use crate::error::Error;
12
13mod aug;
14mod raw;
15mod typed;
16
17mod ops {
18    pub use self::build::{build_aug_dict_from_sorted_iter, build_dict_from_sorted_iter};
19    pub use self::find::{
20        aug_dict_find_by_extra, dict_find_bound, dict_find_bound_owned, dict_find_owned,
21    };
22    pub use self::get::{dict_get, dict_get_owned, dict_get_subdict};
23    pub use self::insert::{aug_dict_insert, dict_insert, dict_insert_owned};
24    pub use self::remove::{aug_dict_remove_owned, dict_remove_bound_owned, dict_remove_owned};
25    pub use self::split_merge::{dict_merge, dict_split_by_prefix};
26
27    mod build;
28    mod find;
29    mod get;
30    mod insert;
31    mod remove;
32    mod split_merge;
33}
34
35/// Type which can be used as a dictionary key.
36pub trait DictKey: Sized {
37    /// Length in bits for a dictionary key.
38    const BITS: u16;
39
40    /// Creates a key from a raw builder data.
41    fn from_raw_data(raw_data: &[u8; 128]) -> Option<Self>;
42}
43
44macro_rules! impl_dict_key {
45    ($($ty:ty => $bits:literal => |$raw_data:ident| $expr:expr),*,) => {
46        $(impl DictKey for $ty {
47            const BITS: u16 = $bits;
48
49            #[inline]
50            fn from_raw_data($raw_data: &[u8; 128]) -> Option<Self> {
51                Some($expr)
52            }
53        })*
54    };
55}
56
57impl_dict_key! {
58    bool => 1 => |d| d[0] & 0x80 != 0,
59    u8 => 8 => |d| d[0],
60    i8 => 8 => |d| d[0] as i8,
61    u16 => 16 => |d| u16::from_be_bytes([d[0], d[1]]),
62    i16 => 16 => |d| i16::from_be_bytes([d[0], d[1]]),
63    u32 => 32 => |d| u32::from_be_bytes(d[..4].try_into().unwrap()),
64    i32 => 32 => |d| i32::from_be_bytes(d[..4].try_into().unwrap()),
65    u64 => 64 => |d| u64::from_be_bytes(d[..8].try_into().unwrap()),
66    i64 => 64 => |d| i64::from_be_bytes(d[..8].try_into().unwrap()),
67    u128 => 128 => |d| u128::from_be_bytes(d[..16].try_into().unwrap()),
68    i128 => 128 => |d| i128::from_be_bytes(d[..16].try_into().unwrap()),
69    [u8; 16] => 128 => |d| d[..16].try_into().unwrap(),
70    [u8; 20] => 160 => |d| d[..20].try_into().unwrap(),
71    [u8; 32] => 256 => |d| d[..32].try_into().unwrap(),
72    HashBytes => 256 => |d| HashBytes(d[..32].try_into().unwrap()),
73     (u64, u32) => 96 => |d| {
74        (u64::from_be_bytes(d[..8].try_into().unwrap()), u32::from_be_bytes(d[8..12].try_into().unwrap()))
75    },
76}
77
78/// `AugDict` search control flow.
79pub trait SearchByExtra<A> {
80    /// Returns if the leaf extra satisfies the condition.
81    fn on_leaf(&mut self, leaf_extra: &A) -> bool {
82        _ = leaf_extra;
83        true
84    }
85
86    /// Returns which branch satisfies the condition.
87    fn on_edge(&mut self, left_extra: &A, right_extra: &A) -> ControlFlow<(), Branch>;
88}
89
90impl<A, T: SearchByExtra<A>> SearchByExtra<A> for &mut T {
91    #[inline]
92    fn on_leaf(&mut self, leaf_extra: &A) -> bool {
93        T::on_leaf(self, leaf_extra)
94    }
95
96    #[inline]
97    fn on_edge(&mut self, left_extra: &A, right_extra: &A) -> ControlFlow<(), Branch> {
98        T::on_edge(self, left_extra, right_extra)
99    }
100}
101
102impl<A> SearchByExtra<A> for Branch {
103    #[inline]
104    fn on_edge(&mut self, _: &A, _: &A) -> ControlFlow<(), Branch> {
105        ControlFlow::Continue(*self)
106    }
107}
108
109impl<A: Ord> SearchByExtra<A> for std::cmp::Ordering {
110    #[inline]
111    fn on_edge(&mut self, left_extra: &A, right_extra: &A) -> ControlFlow<(), Branch> {
112        ControlFlow::Continue(if *self == left_extra.cmp(right_extra) {
113            Branch::Left
114        } else {
115            Branch::Right
116        })
117    }
118}
119
120/// Dictionary insertion mode.
121#[derive(Debug, Clone, Copy, Eq, PartialEq)]
122#[repr(u8)]
123pub enum SetMode {
124    /// Sets the value associated with the key in the dictionary.
125    Set = 0b11,
126    /// Sets the value associated with the key in the dictionary
127    /// only if the key was already present in it.
128    Replace = 0b01,
129    /// Sets the value associated with key in dictionary,
130    /// but only if it is not already present.
131    Add = 0b10,
132}
133
134impl SetMode {
135    /// Returns `true` if the new value can replace the old value for the same key.
136    #[inline]
137    pub const fn can_replace(self) -> bool {
138        self as u8 & 0b01 != 0
139    }
140
141    /// Returns `true` if inserting a value can add a new key to the dictionary.
142    #[inline]
143    pub const fn can_add(self) -> bool {
144        self as u8 & 0b10 != 0
145    }
146}
147
148/// A type for a comparator function for [`AugDict`].
149///
150/// ## Args
151/// - `left` - a left branch data.
152/// - `right` - a right branch data.
153/// - `builder` - a builder to write the result.
154/// - `context` - a cell context.
155pub type AugDictFn =
156    fn(&mut CellSlice, &mut CellSlice, &mut CellBuilder, &mut dyn CellContext) -> Result<(), Error>;
157
158/// Creates a leaf node
159fn make_leaf(
160    key: &CellSlice,
161    key_bit_len: u16,
162    value: &dyn Store,
163    context: &mut dyn CellContext,
164) -> Result<Cell, Error> {
165    let mut builder = CellBuilder::new();
166    ok!(write_label(key, key_bit_len, &mut builder));
167    ok!(value.store_into(&mut builder, context));
168    builder.build_ext(context)
169}
170
171/// Creates a leaf node with extra value
172fn make_leaf_with_extra(
173    key: &CellSlice,
174    key_bit_len: u16,
175    extra: &dyn Store,
176    value: &dyn Store,
177    context: &mut dyn CellContext,
178) -> Result<Cell, Error> {
179    let mut builder = CellBuilder::new();
180    ok!(write_label(key, key_bit_len, &mut builder));
181    ok!(extra.store_into(&mut builder, context));
182    ok!(value.store_into(&mut builder, context));
183    builder.build_ext(context)
184}
185
186/// Splits an edge or leaf
187fn split_edge(
188    data: &CellSlice,
189    prefix: &mut CellSlice,
190    lcp: &CellSlice,
191    key: &mut CellSlice,
192    value: &dyn Store,
193    context: &mut dyn CellContext,
194) -> Result<Cell, Error> {
195    // Advance the key
196    let prev_key_bit_len = key.size_bits();
197    ok!(key.skip_first(lcp.size_bits() + 1, 0));
198
199    // Read the next bit from the data
200    prefix.skip_first(lcp.size_bits(), 0).ok();
201    let old_to_right = ok!(prefix.load_bit());
202
203    // Create a leaf for the old value
204    let mut left = ok!(make_leaf(prefix, key.size_bits(), data, context));
205    // Create a leaf for the right value
206    let mut right = ok!(make_leaf(key, key.size_bits(), value, context));
207
208    // The part that starts with 1 goes to the right cell
209    if old_to_right {
210        std::mem::swap(&mut left, &mut right);
211    }
212
213    // Create fork
214    let mut builder = CellBuilder::new();
215    ok!(write_label(lcp, prev_key_bit_len, &mut builder));
216    ok!(builder.store_reference(left));
217    ok!(builder.store_reference(right));
218    builder.build_ext(context)
219}
220
221#[allow(clippy::too_many_arguments)]
222fn split_aug_edge(
223    data: &mut CellSlice,
224    prefix: &mut CellSlice,
225    lcp: &CellSlice,
226    key: &mut CellSlice,
227    extra: &dyn Store,
228    value: &dyn Store,
229    comparator: AugDictFn,
230    context: &mut dyn CellContext,
231) -> Result<Cell, Error> {
232    // Advance the key
233    let prev_key_bit_len = key.size_bits();
234    ok!(key.skip_first(lcp.size_bits() + 1, 0));
235
236    // Read the next bit from the data
237    prefix.skip_first(lcp.size_bits(), 0).ok();
238    let old_to_right = ok!(prefix.load_bit());
239
240    // Create a leaf for the old value
241    let mut left = ok!(make_leaf(prefix, key.size_bits(), data, context));
242    // Create a leaf for the new value
243    let mut right = ok!(make_leaf_with_extra(
244        key,
245        key.size_bits(),
246        extra,
247        value,
248        context
249    ));
250    // The part that starts with 1 goes to the right cell
251    if old_to_right {
252        std::mem::swap(&mut left, &mut right);
253    }
254
255    let left_slice = &mut ok!(left.as_slice());
256    let right_slice = &mut ok!(right.as_slice());
257    ok!(read_label(left_slice, key.size_bits()));
258    ok!(read_label(right_slice, key.size_bits()));
259
260    // Create fork edge
261    let mut builder = CellBuilder::new();
262    ok!(write_label(lcp, prev_key_bit_len, &mut builder));
263    ok!(builder.store_reference(left.clone()));
264    ok!(builder.store_reference(right.clone()));
265    ok!(comparator(left_slice, right_slice, &mut builder, context));
266    builder.build_ext(context)
267}
268
269/// Type alias for a pair of key and value as cell slice parts.
270pub type DictOwnedEntry = (CellBuilder, CellSliceParts);
271
272/// Dictionary bound.
273#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
274pub enum DictBound {
275    /// The lowest dictionary key.
276    Min,
277    /// The largest dictionary key.
278    Max,
279}
280
281impl DictBound {
282    fn update_direction(
283        self,
284        prefix: &CellSlice<'_>,
285        signed: bool,
286        direction: &mut Option<Branch>,
287    ) -> Branch {
288        match direction {
289            // Compute direction by the first part
290            None => {
291                let mut branch = *direction.insert(self.into_branch());
292                // Invert first bit for signed keys if starting from the empty part
293                if signed && prefix.is_data_empty() {
294                    branch = branch.reversed();
295                }
296                branch
297            }
298            // Use the same direction for all remaining parts
299            Some(direction) => *direction,
300        }
301    }
302
303    fn into_branch(self) -> Branch {
304        match self {
305            Self::Min => Branch::Left,
306            Self::Max => Branch::Right,
307        }
308    }
309}
310
311/// Loads a non-empty dictionary from the root cell.
312pub fn dict_load_from_root(
313    slice: &mut CellSlice<'_>,
314    key_bit_len: u16,
315    context: &mut dyn CellContext,
316) -> Result<Cell, Error> {
317    let mut root = *slice;
318
319    let label = ok!(read_label(slice, key_bit_len));
320    if label.size_bits() != key_bit_len {
321        ok!(slice.skip_first(0, 2));
322        let root_bits = root.size_bits() - slice.size_bits();
323        let root_refs = root.size_refs() - slice.size_refs();
324        root = root.get_prefix(root_bits, root_refs)
325    } else {
326        slice.load_remaining();
327    }
328
329    let mut builder = CellBuilder::new();
330    ok!(builder.store_slice(root));
331    builder.build_ext(context)
332}
333
334fn rebuild_dict_from_stack(
335    mut segments: Vec<Segment<'_>>,
336    mut leaf: Cell,
337    context: &mut dyn CellContext,
338) -> Result<Cell, Error> {
339    // Rebuild the tree starting from leaves
340    while let Some(last) = segments.pop() {
341        // Load the opposite branch
342        let (left, right) = match last.next_branch {
343            Branch::Left => match last.data.reference_cloned(1) {
344                Some(cell) => (leaf, cell),
345                None => return Err(Error::CellUnderflow),
346            },
347            Branch::Right => match last.data.reference_cloned(0) {
348                Some(cell) => (cell, leaf),
349                None => return Err(Error::CellUnderflow),
350            },
351        };
352
353        let mut builder = CellBuilder::new();
354        ok!(builder.store_cell_data(last.data));
355        ok!(builder.store_reference(left));
356        ok!(builder.store_reference(right));
357        leaf = ok!(builder.build_ext(context));
358    }
359
360    Ok(leaf)
361}
362
363fn rebuild_aug_dict_from_stack(
364    mut segments: Vec<Segment<'_>>,
365    mut leaf: Cell,
366    comparator: AugDictFn,
367    context: &mut dyn CellContext,
368) -> Result<Cell, Error> {
369    // Rebuild the tree starting from leaves
370    while let Some(last) = segments.pop() {
371        // Load the opposite branch
372        let (left, right) = match last.next_branch {
373            Branch::Left => match last.data.reference_cloned(1) {
374                Some(cell) => (leaf, cell),
375                None => return Err(Error::CellUnderflow),
376            },
377            Branch::Right => match last.data.reference_cloned(0) {
378                Some(cell) => (cell, leaf),
379                None => return Err(Error::CellUnderflow),
380            },
381        };
382
383        let last_data_slice = ok!(last.data.as_slice());
384        let last_label = ok!(read_label(&mut last_data_slice.clone(), last.key_bit_len));
385
386        let child_key_bit_len = last.key_bit_len - last_label.size_bits() - 1;
387
388        let left_slice = &mut left.as_slice()?;
389        let right_slice = &mut right.as_slice()?;
390        ok!(read_label(left_slice, child_key_bit_len));
391        ok!(read_label(right_slice, child_key_bit_len));
392
393        let mut builder = CellBuilder::new();
394        ok!(write_label(&last_label, last.key_bit_len, &mut builder));
395        ok!(builder.store_reference(left.clone()));
396        ok!(builder.store_reference(right.clone()));
397        ok!(comparator(left_slice, right_slice, &mut builder, context));
398        leaf = ok!(builder.build_ext(context));
399    }
400
401    Ok(leaf)
402}
403
404#[derive(Clone, Copy)]
405struct Segment<'a> {
406    data: &'a DynCell,
407    next_branch: Branch,
408    key_bit_len: u16,
409}
410
411impl Segment<'_> {
412    // Returns the new leaf and the removed leaf
413    fn rebuild_as_removed(
414        self,
415        key: &CellSlice<'_>,
416        prev_key_bit_len: u16,
417        context: &mut dyn CellContext,
418    ) -> Result<(Cell, Cell), Error> {
419        let index = self.next_branch as u8;
420
421        // Load value branch
422        let Some(value) = self.data.reference_cloned(index) else {
423            return Err(Error::CellUnderflow);
424        };
425        // NOTE: do not use gas here as it was accounted while loading `child` in previous block.
426        // TODO: change mode to `LoadMode::Noop` if copy-on-write for libraries is not ok.
427        let value = ok!(context.load_cell(value, LoadMode::Resolve));
428
429        // Load parent label
430        let pfx = {
431            // SAFETY: `self.data` was already checked for pruned branch access.
432            let mut parent = unsafe { self.data.as_slice_unchecked() };
433            ok!(read_label(&mut parent, prev_key_bit_len))
434        };
435
436        // Load the opposite branch
437        let mut opposite = match self.data.reference(1 - index) {
438            // TODO: change mode to `LoadMode::UseGas` if copy-on-write for libraries is not ok.
439            Some(cell) => ok!(context
440                .load_dyn_cell(cell, LoadMode::Full)
441                .and_then(CellSlice::new)),
442            None => return Err(Error::CellUnderflow),
443        };
444        let rem = ok!(read_label(&mut opposite, key.size_bits()));
445
446        // Build an edge cell
447        let mut builder = CellBuilder::new();
448        ok!(write_label_parts(
449            &pfx,
450            index == 0,
451            &rem,
452            prev_key_bit_len,
453            &mut builder
454        ));
455        ok!(builder.store_slice(opposite));
456        let leaf = ok!(builder.build_ext(context));
457
458        Ok((leaf, value))
459    }
460}
461
462fn write_label(key: &CellSlice, key_bit_len: u16, label: &mut CellBuilder) -> Result<(), Error> {
463    if key_bit_len == 0 || key.is_data_empty() {
464        return write_hml_empty(label);
465    }
466
467    let bits_for_len = (16 - key_bit_len.leading_zeros()) as u16;
468
469    let remaining_bits = key.size_bits();
470
471    let hml_short_len = 2 + 2 * remaining_bits;
472    let hml_long_len = 2 + bits_for_len + remaining_bits;
473    let hml_same_len = 3 + bits_for_len;
474
475    if hml_same_len < hml_long_len && hml_same_len < hml_short_len {
476        if let Some(bit) = key.test_uniform() {
477            ok!(write_hml_same(bit, remaining_bits, bits_for_len, label));
478            return Ok(());
479        }
480    }
481
482    if hml_short_len <= MAX_BIT_LEN && hml_short_len <= hml_long_len {
483        ok!(write_hml_short_tag(remaining_bits, label));
484    } else if hml_long_len <= MAX_BIT_LEN {
485        ok!(write_hml_long_tag(remaining_bits, bits_for_len, label));
486    } else {
487        return Err(Error::InvalidData);
488    }
489
490    ok!(label.store_slice_data(key));
491    Ok(())
492}
493
494fn write_label_parts(
495    pfx: &CellSlice,
496    bit: bool,
497    rem: &CellSlice,
498    key_bit_len: u16,
499    label: &mut CellBuilder,
500) -> Result<(), Error> {
501    if key_bit_len == 0 {
502        return write_hml_empty(label);
503    }
504
505    let bits_for_len = (16 - key_bit_len.leading_zeros()) as u16;
506
507    let remaining_bits = pfx.size_bits() + 1 + rem.size_bits();
508
509    let hml_short_len = 2 + 2 * remaining_bits;
510    let hml_long_len = 2 + bits_for_len + remaining_bits;
511    let hml_same_len = 3 + bits_for_len;
512
513    if hml_same_len < hml_long_len
514        && hml_same_len < hml_short_len
515        && (pfx.is_data_empty() || matches!(pfx.test_uniform(), Some(p) if p == bit))
516        && (rem.is_data_empty() || matches!(rem.test_uniform(), Some(r) if r == bit))
517    {
518        return write_hml_same(bit, remaining_bits, bits_for_len, label);
519    }
520
521    if hml_short_len <= MAX_BIT_LEN && hml_short_len <= hml_long_len {
522        ok!(write_hml_short_tag(remaining_bits, label));
523    } else if hml_long_len <= MAX_BIT_LEN {
524        ok!(write_hml_long_tag(remaining_bits, bits_for_len, label));
525    } else {
526        return Err(Error::InvalidData);
527    }
528    ok!(label.store_slice_data(pfx));
529    ok!(label.store_bit(bit));
530    label.store_slice_data(rem)
531}
532
533fn read_label<'a>(label: &mut CellSlice<'a>, key_bit_len: u16) -> Result<CellSlice<'a>, Error> {
534    let bits_for_len = (16 - key_bit_len.leading_zeros()) as u16;
535
536    if bits_for_len == 0 && label.is_data_empty() {
537        Ok(label.get_prefix(0, 0))
538    } else if !ok!(label.load_bit()) {
539        read_hml_short(label)
540    } else if !ok!(label.load_bit()) {
541        read_hml_long(label, bits_for_len)
542    } else {
543        read_hml_same(label, bits_for_len)
544    }
545}
546
547fn write_hml_empty(label: &mut CellBuilder) -> Result<(), Error> {
548    label.store_zeros(2)
549}
550
551fn write_hml_short_tag(len: u16, label: &mut CellBuilder) -> Result<(), Error> {
552    ok!(label.store_bit_zero());
553
554    for _ in 0..len / 32 {
555        ok!(label.store_u32(u32::MAX));
556    }
557
558    let rem = len % 32;
559    if rem != 0 {
560        ok!(label.store_uint(u64::MAX, rem));
561    }
562    label.store_bit_zero()
563}
564
565fn read_hml_short<'a>(label: &mut CellSlice<'a>) -> Result<CellSlice<'a>, Error> {
566    let mut len = 0;
567    while ok!(label.load_bit()) {
568        len += 1;
569    }
570    let result = *label;
571    ok!(label.skip_first(len, 0));
572    Ok(result.get_prefix(len, 0))
573}
574
575fn write_hml_long_tag(len: u16, bits_for_len: u16, label: &mut CellBuilder) -> Result<(), Error> {
576    ok!(label.store_bit_one());
577    ok!(label.store_bit_zero());
578    label.store_uint(len as u64, bits_for_len)
579}
580
581fn read_hml_long<'a>(label: &mut CellSlice<'a>, bits_for_len: u16) -> Result<CellSlice<'a>, Error> {
582    let len = ok!(label.load_uint(bits_for_len)) as u16;
583    let result = *label;
584    ok!(label.skip_first(len, 0));
585    Ok(result.get_prefix(len, 0))
586}
587
588fn write_hml_same(
589    bit: bool,
590    len: u16,
591    bits_for_len: u16,
592    label: &mut CellBuilder,
593) -> Result<(), Error> {
594    ok!(label.store_small_uint(0b110 | bit as u8, 3));
595    label.store_uint(len as u64, bits_for_len)
596}
597
598fn read_hml_same<'a>(label: &mut CellSlice<'a>, bits_for_len: u16) -> Result<CellSlice<'a>, Error> {
599    let cell = match ok!(label.load_bit()) {
600        false => Cell::all_zeros_ref(),
601        true => Cell::all_ones_ref(),
602    };
603    let len = ok!(label.load_uint(bits_for_len)) as u16;
604
605    // SAFETY: cell is a static ordinary cell
606    let slice = unsafe { cell.as_slice_unchecked() };
607    Ok(slice.get_prefix(len, 0))
608}
609
610/// Which branch to take when traversing the tree.
611#[derive(Debug, Clone, Copy, Eq, PartialEq)]
612pub enum Branch {
613    /// Branch for a key part that starts with bit 0
614    Left = 0,
615    /// Branch for a key part that starts with bit 1
616    Right = 1,
617}
618
619impl Branch {
620    /// Converts the branch to a boolean value.
621    pub fn into_bit(self) -> bool {
622        self == Self::Right
623    }
624
625    /// Returns the opposite branch.
626    pub fn reversed(self) -> Self {
627        match self {
628            Self::Left => Self::Right,
629            Self::Right => Self::Left,
630        }
631    }
632}
633
634impl From<bool> for Branch {
635    fn from(value: bool) -> Self {
636        if value {
637            Self::Right
638        } else {
639            Self::Left
640        }
641    }
642}
643
644#[cfg(test)]
645mod tests {
646    use super::*;
647
648    fn build_cell<F: FnOnce(&mut CellBuilder) -> Result<(), Error>>(f: F) -> Cell {
649        let mut builder = CellBuilder::new();
650        f(&mut builder).unwrap();
651        builder.build().unwrap()
652    }
653
654    #[test]
655    fn labels() -> anyhow::Result<()> {
656        let key_bit_len = 6;
657
658        // Build key
659        let key = {
660            let mut builder = CellBuilder::new();
661            builder.store_zeros(5)?;
662            builder.store_bit_one()?;
663            builder.build()?
664        };
665
666        // Build label
667        let label = {
668            let mut builder = CellBuilder::new();
669            write_label(&key.as_slice()?, key_bit_len, &mut builder)?;
670            builder.build().unwrap()
671        };
672
673        // Parse label
674        let parsed_key = read_label(&mut label.as_slice()?, key_bit_len)?;
675        let parsed_key = {
676            let mut builder = CellBuilder::new();
677            builder.store_slice(parsed_key)?;
678            builder.build()?
679        };
680
681        // Parsed key should be equal to the original
682        assert_eq!(key.as_ref(), parsed_key.as_ref());
683
684        let label = CellBuilder::from_raw_data(&[0xcc, 0x40], 9)
685            .unwrap()
686            .build()
687            .unwrap();
688        let prefix = read_label(&mut label.as_slice()?, 32).unwrap();
689
690        println!("{}", build_cell(|b| b.store_slice(prefix)).display_tree());
691        assert_eq!(prefix.test_uniform(), Some(false));
692
693        Ok(())
694    }
695
696    #[test]
697    fn build_from_array() {
698        for entries in [
699            &[(0u32, 1u32), (1, 2), (2, 4), (2, 3), (3, 4), (4, 5)][..],
700            &[
701                (534837844, 3117028142),
702                (1421713188, 3155891450),
703                (1526242096, 2789399854),
704                (1971086295, 1228713494),
705                (4258889371, 3256452222),
706            ],
707        ] {
708            let result = build_dict_from_sorted_iter(
709                entries.iter().copied(),
710                32,
711                &mut Cell::empty_context(),
712            )
713            .unwrap();
714
715            let mut dict = Dict::<u32, u32>::new();
716            for (k, v) in entries {
717                dict.add(k, v).unwrap();
718            }
719
720            println!("{}", result.as_ref().unwrap().display_tree());
721            println!(
722                "BOC: {}",
723                crate::boc::BocRepr::encode_base64(&result).unwrap()
724            );
725
726            assert_eq!(result, dict.root);
727        }
728    }
729
730    #[test]
731    fn build_from_any_array() {
732        for _ in 0..100 {
733            let n = 1 + rand::random::<usize>() % 1000;
734            let mut entries = (0..n)
735                .map(|_| (rand::random::<u32>(), rand::random::<u32>()))
736                .collect::<Vec<_>>();
737            entries.sort_by_key(|(k, _)| *k);
738
739            let built_from_dict = build_dict_from_sorted_iter(
740                entries.iter().copied(),
741                32,
742                &mut Cell::empty_context(),
743            )
744            .unwrap();
745
746            let mut dict = Dict::<u32, u32>::new();
747            for (k, v) in entries {
748                dict.add(k, v).unwrap();
749            }
750
751            // println!("{}", built_from_dict.as_ref().unwrap().display_tree());
752
753            assert_eq!(built_from_dict, dict.root);
754        }
755    }
756}
everscale_types/dict/mod.rs

everscale_types/dict/
mod.rs
