Compiler Explorer

Source code

const std = @import("std");
const BITS_TO_PRESERVE = @as(comptime_int, (@typeInfo(usize).Int.bits - 1) - @clz(@as(usize, 20)));

// Kinda an approximation of 16 log2(x). Will be divided by 8 to approximate 2 log2(x).
fn log_approx_helper(x: usize) usize {
    const fls = @intCast(std.math.Log2Int(usize), (@typeInfo(usize).Int.bits - 1) - @clz(x)); // [4, 63]
    const x_with_msb_unset = x ^ @as(usize, 1) << fls;
    const pack_bits_under_old_msb = x_with_msb_unset >> fls - BITS_TO_PRESERVE;
    return @as(usize, fls) << BITS_TO_PRESERVE | pack_bits_under_old_msb; // [16, 1023] on 64-bit
}

/// Modify the array so that it can hold at least `new_capacity` items.
/// Invalidates pointers if additional memory is needed.
export fn ensureTotalCapacity(capacity: usize, new_capacity: usize) usize {
    const power = 1 + (log_approx_helper(new_capacity +| 20) -| log_approx_helper(capacity +| 20)) / 8;
    const shift = @intCast(std.math.Log2Int(usize), power >> 1);
    const approx_sqrt_2_power = (@as(usize, 1) << shift) | (@as(usize, power & 1) << (shift -| 1));
    return @max(capacity +| (capacity / 2 + 8), (capacity +| 20) *| approx_sqrt_2_power - 20);
}