turbocow 0.3.0-beta.2

Compact, clone-on-write vectors, strings, maps and sets with inline + referenced storage — a superset of ecow.
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

use core::mem;

use crate::allocator::Global;

/// Compute the per-allocator inline limit from the allocator's size.
///
/// The maximum amount of inline storage. Typically, this is 15 bytes.
///
/// This computes `size_of::<EcoVec<u8, A>>()` manually from the allocator
/// size to avoid circular const evaluation when used in `generic_const_exprs`
/// bounds. `EcoVec<u8, A>` is `repr(C)` with fields:
///   `ptr: NonNull<u8>` + `len: usize` + `alloc: A` + `phantom: PhantomData<u8>`
///
/// Special cases for exotic systems:
/// - For big endian, increase the limit so the tagged length of the inline
///   variant doesn't overlap with the EcoVec.
/// - In case EcoVec is very large (128-bit pointers), increase the limit too.
pub(crate) const fn inline_limit<A>() -> usize {
    // EcoVec<u8, A> is repr(C): NonNull<u8> (ptr-sized) + usize + A + PhantomData (0)
    let ecovec_size =
        mem::size_of::<usize>() + mem::size_of::<usize>() + mem::size_of::<A>();
    // The inline buffer must exactly fill the space occupied by EcoVec so
    // that the tagged_len byte sits at the high byte of EcoVec::len.
    // On 64-bit this is 15, on 32-bit this is 7.
    let mut limit = ecovec_size - 1;
    if cfg!(target_endian = "big") {
        limit += mem::size_of::<usize>();
    }
    limit
}

/// Backward-compatible LIMIT constant for the default (Global) allocator.
pub(crate) const LIMIT: usize = inline_limit::<Global>();

// ---------------------------------------------------------------------------
// Tag encoding (2-bit scheme in the byte at offset N of the union)
//
// The `tagged_len` byte (offset N in InlineVec) doubles as a variant
// discriminant.  We use the two highest bits:
//
//   0b10xx_xxxx  →  Inline   (bit 7 set, bit 6 clear)
//   0b11xx_xxxx  →  Referenced (both bits set)
//   0b0xxx_xxxx  →  Spilled  (bit 7 clear — guaranteed because EcoVec's
//                              `len` never exceeds `isize::MAX`)
//
// The remaining 6 bits hold the inline / referenced length (max 63).
// ---------------------------------------------------------------------------

/// Bit 7 — set for both Inline and Referenced variants.
pub(crate) const LEN_INLINE_TAG: u8 = 0b1000_0000;

/// Bit 6 — set *only* for the Referenced variant (together with bit 7).
pub(crate) const LEN_REFERENCED_TAG: u8 = 0b0100_0000;

/// Both tag bits combined.
pub(crate) const LEN_TAGS: u8 = LEN_INLINE_TAG | LEN_REFERENCED_TAG;

/// Mask that extracts the length value from a tagged byte.
pub(crate) const LEN_VALUE_MASK: u8 = !LEN_TAGS;

/// `usize`-level mask for embedding the *referenced* tag in
/// `Referenced::len`.  On little-endian 64-bit the high byte of `len`
/// overlaps with `tagged_len`, so the tag is naturally visible.  On other
/// layouts we write the tag byte explicitly as well.
pub(crate) const LEN_TAGS_USIZE: usize =
    (LEN_TAGS as usize) << (usize::BITS as usize - 8);

/// Mask that extracts the actual length from a `Referenced::len` field.
pub(crate) const LEN_VALUE_MASK_USIZE: usize = !LEN_TAGS_USIZE;

/// Whether the high byte of `Referenced::len` naturally overlaps with the
/// `tagged_len` byte at offset `LIMIT` in `InlineVec`.
///
/// On 64-bit little-endian with a ZST allocator this is true:
///   - `Referenced::len` starts at offset `size_of::<usize>()` (after `ptr`)
///   - Its highest byte (LE) is at offset `2 * size_of::<usize>() - 1` = 15 = LIMIT
///
/// When true, writing the tag bits into `Referenced::len` is sufficient and
/// the explicit tag-byte write in `from_referenced` can be skipped.
pub(crate) const TAG_OVERLAPS_LEN: bool = {
    let ptr_size = mem::size_of::<usize>();
    // High byte of `len` field in Referenced (repr(C): ptr then len)
    let len_high_byte_offset = if cfg!(target_endian = "little") {
        // LE: high byte is at the end of the word
        ptr_size + ptr_size - 1
    } else {
        // BE: high byte is at the start of the word
        ptr_size
    };
    len_high_byte_offset == inline_limit::<Global>()
};