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

// Copyright 2019 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

use crate::constants;
use crate::BlockType;
use std::cmp::{max, min};

/// Returns the smallest order such that (MIN_ORDER_SHIFT << order) >= size.
/// Size must be non zero.
pub fn fit_order(size: usize) -> usize {
    // Safety: `leading_zeros` returns a u32, so this is safe promotion
    (std::mem::size_of::<usize>() * 8 - (size - 1).leading_zeros() as usize)
        .checked_sub(constants::MIN_ORDER_SHIFT)
        .unwrap_or(0)
}

/// Get size in bytes of a given |order|.
pub fn order_to_size(order: u8) -> usize {
    constants::MIN_ORDER_SIZE << order
}

/// Get the necessary |block size| to fit the given |payload_size| in range
/// MIN_ORDER_SIZE <= block size <= MAX_ORDER_SIZE
pub fn block_size_for_payload(payload_size: usize) -> usize {
    min(
        constants::MAX_ORDER_SIZE,
        max(payload_size + constants::HEADER_SIZE_BYTES, constants::MIN_ORDER_SIZE),
    )
}

/// Get the size in bytes for the payload section of a block of the given |order|.
pub fn payload_size_for_order(order: u8) -> usize {
    order_to_size(order) - constants::HEADER_SIZE_BYTES
}

/// Get the array capacity size for the given |order|.
pub fn array_capacity(order: u8, entry_type: BlockType) -> Option<usize> {
    entry_type.array_element_size().map(|size| {
        (order_to_size(order)
            - constants::HEADER_SIZE_BYTES
            - constants::ARRAY_PAYLOAD_METADATA_SIZE_BYTES)
            / size
    })
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn fit_order_test() {
        assert_eq!(0, fit_order(1));
        assert_eq!(0, fit_order(16));
        assert_eq!(1, fit_order(17));
        assert_eq!(2, fit_order(33));
        assert_eq!(7, fit_order(2048));
    }

    #[test]
    fn order_to_size_test() {
        assert_eq!(16, order_to_size(0));
        assert_eq!(32, order_to_size(1));
        assert_eq!(64, order_to_size(2));
        assert_eq!(128, order_to_size(3));
        assert_eq!(256, order_to_size(4));
        assert_eq!(512, order_to_size(5));
        assert_eq!(1024, order_to_size(6));
        assert_eq!(2048, order_to_size(7));
    }

    #[test]
    fn fit_payload_test() {
        for payload_size in 0..500 {
            let block_size = block_size_for_payload(payload_size);
            let order = fit_order(block_size) as u8;
            let payload_max = payload_size_for_order(order);
            assert!(
                payload_size <= payload_max,
                "Needed {} bytes for a payload, but only got {}; block size {}, order {}",
                payload_size,
                payload_max,
                block_size,
                order
            );
        }
    }

    #[test]
    fn array_capacity_numeric() {
        assert_eq!(2, array_capacity(1, BlockType::IntValue).expect("get size"));
        assert_eq!(2 + 4, array_capacity(2, BlockType::IntValue).expect("get size"));
        assert_eq!(2 + 4 + 8, array_capacity(3, BlockType::IntValue).expect("get size"));
        assert_eq!(2 + 4 + 8 + 16, array_capacity(4, BlockType::IntValue).expect("get size"));
        assert_eq!(2 + 4 + 8 + 16 + 32, array_capacity(5, BlockType::IntValue).expect("get size"));
        assert_eq!(
            2 + 4 + 8 + 16 + 32 + 64,
            array_capacity(6, BlockType::IntValue).expect("get size")
        );
        assert_eq!(
            2 + 4 + 8 + 16 + 32 + 64 + 128,
            array_capacity(7, BlockType::IntValue).expect("get size")
        );
    }

    #[test]
    fn array_capacity_string_reference() {
        assert_eq!(4, array_capacity(1, BlockType::StringReference).expect("get size"));
        assert_eq!(4 + 8, array_capacity(2, BlockType::StringReference).expect("get size"));
        assert_eq!(4 + 8 + 16, array_capacity(3, BlockType::StringReference).expect("get size"));
        assert_eq!(
            4 + 8 + 16 + 32,
            array_capacity(4, BlockType::StringReference).expect("get size")
        );
        assert_eq!(
            4 + 8 + 16 + 32 + 64,
            array_capacity(5, BlockType::StringReference).expect("get size")
        );
        assert_eq!(
            4 + 8 + 16 + 32 + 64 + 128,
            array_capacity(6, BlockType::StringReference).expect("get size")
        );
        assert_eq!(
            4 + 8 + 16 + 32 + 64 + 128 + 256,
            array_capacity(7, BlockType::StringReference).expect("get size")
        );
    }
}