The crate docs give a quick overview of the memory layout. As for implementation, it's simplest to explain by starting with the T: ?Aligned
case (when T
's alignment isn't known at compile time; for example, T = dyn Debug
). In this case, the UnsizedVec
looks more or less like this:
// Following is somewhat simplified
pub struct UnsizedVec<T: ?Sized> {
// Pointer to start of heap allocation
// (dangling if `cap` is 0)
ptr: NonNull<()>,
// length of heap allocation (0 if we haven't allocated)
cap: usize,
// See later explanation for why this is needed.
// `alloc::vec::Vec` is the standard library's `Vec`.
// This is distinct from the heap allocation
// used to store the elements of the` UnsizedVec`.
metadata_list: alloc::vec::Vec<MetadataStorage<T>>,
// See later explanation for why this is needed.
align: usize,
}
struct MetadataStorage<T: ?Sized> {
metadata: <T as Pointee>::Metadata,
offset_next: usize,
}
The elements of the UnsizedVec
are laid out sequentially in memory, just as with normal Vec
. The one caveat is that every element is padded so that the size it takes up in the vec, in bytes, is a multiple of the number in the align
field. align
is equal to the largest alignment (as returned by core::mem::align_of_val
) out of all the elements in the vec. It can increase when a new element is added, which triggers re-padding and reallocation. The UnsizedVec
's backing allocation is itself aligned to align
.
The metadata
field stores a list of MetadataStorage
structs, one for each element of the vec, and laid out in the same order. This MetadataStorage
struct has two fields. For the element at index i
of vec v
, v.metadata_list[i].metadata
stores the pointer metadata of the element, needed to reconstruct a wide pointer to it. The offset_next
field stores the offset of the byte one past the end of the element, compared to the start of the vec (but not padded to a multiple of align
). For example, if the third element occupies bytes 4 to 7 of the UnsizedVec
's heap allocation, v.metadata_list[i].offset_next
will equal 8.
This allows indexing into the UnsizedVec
in O(1) time. To get the offset of the start of the element at index index
of vec myvec
, we do index.checked_sub(1).map_or(0, |prev_index| myvec.metadata_list[prev_index].offset_next.next_multiple_of(myvec.align))
. And to get the offset of one past the end of the element, we do unsized_vec.metadata_list[index].offset_next
. This gives us enough information to find our element in the unsized_vec
's heap allocation, and copy it out or return a reference to it.
To get the length of myvec
, we just do myvec.metadata_list.len()
.
Now, when T: ?Sized + Aligned
(for example, T = [u32]
), we do mostly the same thing, except we don't need to worry about storing an align
field or padding to it. So we use specialization to store a ()
in that field instead, and skip all the extra padding logic.
When T: Sized
, we use more specialization so that MetadataStorage
's two fields both become ()
. This makes MetadataStorage
a ZST, so metadata_list
never allocates and is basically just a usize
length field. This allows UnsizedVec
to behave basically identically to the standard library Vec
, and to be trivially convertible to and from it.