prns-core 0.3.4

Pure Reticulum engine and wire contract for Personal Reticulum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

use super::core::{buckets_for_two_thirds_load, exceeds_two_thirds_load};
use super::{IndexKey, LemireIndex};
use crate::interfaces::InterfaceId;
use crate::wire::DestinationHash;

#[test]
fn bucket_sizing_preserves_two_thirds_headroom_without_overflow() {
    assert_eq!(buckets_for_two_thirds_load(0), 1);
    assert_eq!(buckets_for_two_thirds_load(1), 2);
    assert_eq!(buckets_for_two_thirds_load(2), 3);
    assert_eq!(buckets_for_two_thirds_load(3), 5);
    assert_eq!(buckets_for_two_thirds_load(1_024), 1_536);
    assert_eq!(buckets_for_two_thirds_load(usize::MAX), usize::MAX);
    assert!(!exceeds_two_thirds_load(5, 8));
    assert!(exceeds_two_thirds_load(6, 8));
    assert!(!exceeds_two_thirds_load(usize::MAX / 2, usize::MAX));
}

#[test]
fn interface_ids_sharing_a_kind_byte_still_spread_across_buckets() {
    let a = InterfaceId::new([0x07, 0, 0, 0, 0, 0, 0, 0x11]);
    let b = InterfaceId::new([0x07, 0, 0, 0, 0, 0, 0, 0x22]);
    assert_eq!(a.lemire_key() & 0xff, 0x07);
    assert_ne!(a.lemire_key() >> 56, b.lemire_key() >> 56);
}

#[test]
fn fixed_slot_removal_preserves_a_newer_duplicate_key() {
    let duplicate = DestinationHash::new([7; 16]);
    let other = DestinationHash::new([8; 16]);
    let keys = [duplicate, other, duplicate];
    let mut index = LemireIndex::<8>::default();
    for slot in 0..keys.len() {
        index.insert(slot, &keys);
    }

    index.remove_slot(0, &keys);

    assert_eq!(index.get(&duplicate, &keys), Some(2));
    assert_eq!(index.get(&other, &keys), Some(1));

    index.remove_slot(2, &keys);

    assert_eq!(index.get(&duplicate, &keys), None);
    assert_eq!(index.get(&other, &keys), Some(1));
}

#[cfg(feature = "alloc")]
mod heap {
    use super::super::HeapLemireIndex;
    use crate::wire::DestinationHash;

    fn dest_n(n: u32) -> DestinationHash {
        let key = (n as u64).wrapping_mul(0x9E37_79B9_7F4A_7C15);
        let mut b = [0u8; 16];
        b[..8].copy_from_slice(&key.to_be_bytes());
        b[8..12].copy_from_slice(&n.to_be_bytes());
        DestinationHash::new(b)
    }

    #[test]
    fn every_key_stays_findable_across_rebuilds_and_absent_keys_miss() {
        let mut index = HeapLemireIndex::default();
        let mut keys = std::vec::Vec::new();
        for n in 0..1_000u32 {
            keys.push(dest_n(n));
            index.insert(keys.len() - 1, &keys);
        }
        for (slot, key) in keys.iter().enumerate() {
            assert_eq!(index.get(key, &keys), Some(slot));
        }
        assert_eq!(index.get(&dest_n(1_000), &keys), None);
    }

    #[test]
    fn removal_re_packs_so_later_keys_survive_and_repoint_follows_a_swap() {
        let mut index = HeapLemireIndex::default();
        let mut keys = std::vec::Vec::new();
        for n in 0..100u32 {
            keys.push(dest_n(n));
            index.insert(keys.len() - 1, &keys);
        }

        let removed = keys[10];
        index.remove(&removed, &keys);
        let moved = keys[keys.len() - 1];
        index.repoint(&moved, 10, &keys);
        keys.swap_remove(10);

        assert_eq!(index.get(&removed, &keys), None);
        for (slot, key) in keys.iter().enumerate() {
            assert_eq!(index.get(key, &keys), Some(slot));
        }
    }

    #[test]
    fn slot_removal_and_repoint_preserve_duplicate_keys() {
        let duplicate = dest_n(7);
        let mut keys = std::vec![duplicate, dest_n(8), duplicate];
        let mut index = HeapLemireIndex::default();
        for slot in 0..keys.len() {
            index.insert(slot, &keys);
        }

        index.remove_slot(0, &keys);
        index.repoint_slot(2, 0, &keys);
        keys.swap_remove(0);

        assert_eq!(index.get(&duplicate, &keys), Some(0));
        assert_eq!(index.get(&dest_n(8), &keys), Some(1));
        index.remove_slot(0, &keys);
        index.repoint_slot(1, 0, &keys);
        keys.swap_remove(0);
        assert_eq!(index.get(&duplicate, &keys), None);
        assert_eq!(index.get(&dest_n(8), &keys), Some(0));
    }

    #[test]
    fn clear_empties_every_bucket_without_shrinking() {
        let mut index = HeapLemireIndex::default();
        let mut keys = std::vec::Vec::new();
        for n in 0..100u32 {
            keys.push(dest_n(n));
            index.insert(keys.len() - 1, &keys);
        }
        index.clear();
        assert_eq!(index.get(&dest_n(0), &keys), None);

        keys.clear();
        keys.push(dest_n(7));
        index.insert(0, &keys);
        assert_eq!(index.get(&dest_n(7), &keys), Some(0));
    }
}