pipecircuit 0.0.23

Correct. Robust. Fast. Portable. Pick four.
Documentation 
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

use super::{RangeIndex, RangeIndexInconsistency, RangeIndexKey};
use crate::storage::warp_table::secondary_index::StableSlot;

const SLOTS_PER_BLOCK: usize = u64::BITS as usize;

pub(super) struct SlotLocation<'index> {
    members: &'index mut u64,
    planes: &'index mut [u64],
    mask: u64,
}

impl SlotLocation<'_> {
    pub(super) fn member(&self) -> bool {
        *self.members & self.mask != 0
    }

    pub(super) fn word(&self) -> u64 {
        self.planes
            .iter()
            .zip(0_u32..)
            .fold(0, |word, (plane, bit)| {
                if *plane & self.mask == 0 {
                    word
                } else {
                    word | 1_u64.rotate_left(bit)
                }
            })
    }

    pub(super) fn write(&mut self, present: bool, word: u64) {
        if present {
            *self.members |= self.mask;
        } else {
            *self.members &= !self.mask;
        }
        for (plane, bit) in self.planes.iter_mut().zip(0_u32..) {
            if word & 1_u64.rotate_left(bit) == 0 {
                *plane &= !self.mask;
            } else {
                *plane |= self.mask;
            }
        }
    }
}

pub(super) fn storage_dimensions(maximum_rows: usize, bits: u32) -> Option<(usize, usize)> {
    let bit_count = usize::try_from(bits).ok()?;
    let words_per_block = bit_count.checked_add(1)?;
    let block_count = maximum_rows.div_ceil(SLOTS_PER_BLOCK);
    let storage_words = block_count.checked_mul(words_per_block)?;
    Some((words_per_block, storage_words))
}

impl<Key: RangeIndexKey> RangeIndex<Key> {
    pub(super) fn validated_words_per_block(&self) -> Result<usize, RangeIndexInconsistency> {
        let (words_per_block, expected) = storage_dimensions(self.maximum_rows, Key::BITS).ok_or(
            RangeIndexInconsistency::StorageCapacityOverflow {
                maximum_rows: self.maximum_rows,
                bits: Key::BITS,
            },
        )?;
        if self.blocks.len() != expected {
            return Err(RangeIndexInconsistency::BlockStorageLengthMismatch {
                expected,
                actual: self.blocks.len(),
            });
        }
        Ok(words_per_block)
    }

    pub(super) fn locate_slot(
        &mut self,
        slot: StableSlot,
        words_per_block: usize,
    ) -> Result<(SlotLocation<'_>, &mut u64), RangeIndexInconsistency> {
        let slot_index = usize::try_from(slot.value())
            .ok()
            .filter(|index| *index < self.maximum_rows)
            .ok_or(RangeIndexInconsistency::SlotOutsideCapacity {
                maximum_rows: self.maximum_rows,
            })?;
        let actual = self.blocks.len();
        let (members, planes) = self
            .blocks
            .chunks_exact_mut(words_per_block)
            .nth(slot_index / SLOTS_PER_BLOCK)
            .and_then(|block| block.split_first_mut())
            .ok_or(RangeIndexInconsistency::BlockStorageLengthMismatch {
                expected: actual.saturating_add(words_per_block),
                actual,
            })?;
        Ok((
            SlotLocation {
                members,
                planes,
                mask: 1_u64.rotate_left(slot.value()),
            },
            &mut self.member_count,
        ))
    }
}