use std::mem::size_of;
pub(crate) const fn vec_slot<T>() -> usize {
2 * size_of::<T>()
}
pub(crate) const fn vec_first<T>() -> usize {
4 * size_of::<T>()
}
const fn btree_leaf<K, V>() -> usize {
16 + 11 * (size_of::<K>() + size_of::<V>()) + 8
}
const fn btree_internal<K, V>() -> usize {
btree_leaf::<K, V>() + 12 * size_of::<usize>()
}
pub(crate) const fn btree_entry<K, V>() -> usize {
btree_leaf::<K, V>().div_ceil(5) + btree_internal::<K, V>().div_ceil(8)
}
pub(crate) const fn btree_map<K, V>() -> usize {
btree_leaf::<K, V>()
}
pub(crate) const fn hash_entry<T>() -> usize {
3 * (size_of::<T>() + 1)
}
pub(crate) const fn hash_map<T>() -> usize {
8 * (size_of::<T>() + 1) + 16 + 8
}
pub(crate) const fn shared_text(len: usize) -> usize {
(len + 2 * size_of::<usize>()).next_multiple_of(align_of::<usize>())
}
#[cfg(test)]
mod tests {
use std::collections::BTreeMap;
use super::*;
#[test]
fn a_shared_string_is_charged_its_padded_allocation() {
assert_eq!(shared_text(0), 2 * size_of::<usize>());
assert_eq!(shared_text(1), 2 * size_of::<usize>() + align_of::<usize>());
assert_eq!(shared_text(8), 3 * size_of::<usize>());
assert_eq!(shared_text(9) % align_of::<usize>(), 0);
}
#[test]
fn a_map_of_one_entry_is_covered_by_what_a_map_costs_once() {
assert_eq!(btree_leaf::<u64, u64>(), 16 + 11 * 16 + 8);
assert!(btree_map::<u64, u64>() >= btree_leaf::<u64, u64>());
for n in [1_usize, 5, 11, 12, 13, 24, 25, 100, 10_000] {
let (leaves, internals) = if n <= 11 { (1, 0) } else { (n / 5, 1 + n / 25) };
let held = leaves * btree_leaf::<u64, u64>() + internals * btree_internal::<u64, u64>();
let charged = btree_map::<u64, u64>() + n * btree_entry::<u64, u64>();
assert!(charged >= held, "{n}: {charged} < {held}");
}
let map: BTreeMap<u64, u64> = (0..12).map(|k| (k, k)).collect();
assert_eq!(map.len(), 12);
}
#[test]
fn a_list_is_charged_at_least_its_room() {
for n in 1_usize..200 {
let mut list: Vec<u64> = Vec::new();
for k in 0..n {
list.push(k as u64);
}
let held = list.capacity() * size_of::<u64>();
let charged = vec_first::<u64>() + n * vec_slot::<u64>();
assert!(charged >= held, "{n}: {charged} < {held}");
}
}
#[test]
fn a_hash_table_is_charged_at_least_its_buckets() {
use std::collections::HashSet;
for n in 1_usize..5000 {
let set: HashSet<u64> = (0..n as u64).collect();
let capacity = set.capacity();
let buckets = match capacity {
0..4 => 4,
4..8 => 8,
_ => (capacity * 8 / 7).next_power_of_two(),
};
let held = buckets * (size_of::<u64>() + 1) + 16;
let charged = hash_map::<u64>() + n * hash_entry::<u64>();
assert!(charged >= held, "{n}: {charged} < {held}");
}
}
}