diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/lib.rs | 844 | ||||
| -rw-r--r-- | src/util.rs | 62 |
2 files changed, 792 insertions, 114 deletions
@@ -5,10 +5,16 @@ use std::cmp::max; use std::mem::MaybeUninit; use std::ptr::NonNull; -use crate::util::MaybeUninitByteSlice; +use crate::util::{AnonUnique, MaybeUninitByteSlice}; mod util; +const FIELD_COUNT_SIZE: usize = size_of::<usize>(); + +const FIELD_COUNT_OFFSET: usize = 0; +const FIELD_METADATA_ARRAY_OFFSET: usize = FIELD_COUNT_SIZE; + +#[derive(Debug)] pub struct OwnedAnyPtr { ptr: *mut dyn Any, @@ -70,9 +76,9 @@ impl Drop for OwnedAnyPtr } } -/// A list of `ItemT`. This data structure stores a list for every field of `ItemT`, -/// reducing memory usage if `ItemT` contains padding and improves memory cache usage if -/// only certain fields are needed when iterating. +/// A list of runtime defined items. This data structure stores fields contiguously, +/// improving cache efficiency when iterating through items and only specific fields are +/// wanted. /// /// Inspired by Zig's `MultiArrayList`. /// @@ -96,8 +102,6 @@ impl Drop for OwnedAnyPtr pub struct MultiVec { ptr: NonNull<MaybeUninit<u8>>, - field_arr_byte_offsets: Vec<usize>, - field_metadata: Vec<FieldMetadata>, length: usize, capacity: usize, layout: Option<Layout>, @@ -133,8 +137,6 @@ impl MultiVec { Self { ptr: NonNull::dangling(), - field_arr_byte_offsets: Vec::new(), - field_metadata: Vec::new(), length: 0, capacity: 0, layout: None, @@ -161,18 +163,21 @@ impl MultiVec //} /// Pushes a item to the `MultiVec`. - /// - /// ## Note on performance - /// Pushing can be pretty slow. Since all of the field lists are stored in the same - /// allocation, when pushing and the `MultiVec` needs to grow, all lists except the - /// first has to be moved to new locations for them to not overlap. pub fn push( &mut self, fields: impl AsRef<[OwnedAnyPtr]> + IntoIterator<Item = OwnedAnyPtr>, ) { if self.capacity != 0 { - assert_eq!(fields.as_ref().len(), self.field_arr_byte_offsets.len()); + assert_eq!(fields.as_ref().len(), self.field_cnt()); + + assert!(fields + .as_ref() + .iter() + .zip(self.get_field_metadata().unwrap()) + .all(|(item_field, field_metadata)| { + item_field.id() == field_metadata.type_id + })); if self.capacity == self.length { self.grow_amortized(1, &fields); @@ -185,16 +190,6 @@ impl MultiVec return; } - self.field_metadata = fields - .as_ref() - .iter() - .map(|field| FieldMetadata { - size: field.size(), - type_id: field.id(), - drop_in_place: field.drop_in_place, - }) - .collect(); - self.do_first_alloc(1, &fields); self.write_item(0, fields); @@ -202,6 +197,135 @@ impl MultiVec self.length = 1; } + pub fn remove(&mut self, item_index: usize) -> Option<Vec<FieldOwned<'_>>> + { + if item_index >= self.length { + return None; + } + + let prev_length = self.length; + + self.length -= 1; + + let mut item_fields = Vec::<FieldOwned<'_>>::with_capacity(self.field_cnt()); + + for field_index in 0..self.field_cnt() { + let field_metadata = &self.get_field_metadata()?.get(field_index)?; + + let field_arr_ptr = unsafe { self.ptr.byte_add(field_metadata.array_offset) }; + + let bytes = unsafe { + std::slice::from_raw_parts_mut( + field_arr_ptr.as_ptr().cast(), + prev_length * field_metadata.size, + ) + }; + + let field_slice = FieldSliceMut { + bytes, + len: prev_length, + field_metadata, + }; + + let mut item_field_bytes = AnonUnique::new_uninit( + Layout::from_size_align(field_metadata.size, field_metadata.alignment) + .unwrap(), + ); + + item_field_bytes.as_slice_mut().copy_from_slice( + field_slice + .get_item(item_index) + .expect("Not possible") + .bytes, + ); + + let item_field = FieldOwned { + bytes: item_field_bytes, + field_metadata, + }; + + item_fields.push(item_field); + + let item_field_offset = field_slice + .get_item_offset(item_index) + .expect("Not possible"); + + field_slice.bytes.copy_within( + item_field_offset + field_slice.field_metadata.size.., + item_field_offset, + ); + } + + Some(item_fields) + } + + pub fn swap_remove(&mut self, item_index: usize) -> Option<Vec<FieldOwned<'_>>> + { + if item_index >= self.length { + return None; + } + + let prev_length = self.length; + + self.length -= 1; + + let mut item_fields = Vec::<FieldOwned<'_>>::with_capacity(self.field_cnt()); + + for field_index in 0..self.field_cnt() { + let field_metadata = &self.get_field_metadata()?.get(field_index)?; + + let field_arr_ptr = unsafe { self.ptr.byte_add(field_metadata.array_offset) }; + + let bytes = unsafe { + std::slice::from_raw_parts_mut( + field_arr_ptr.as_ptr().cast(), + prev_length * field_metadata.size, + ) + }; + + let field_slice = FieldSliceMut { + bytes, + len: prev_length, + field_metadata, + }; + + let mut item_field_bytes = AnonUnique::new_uninit( + Layout::from_size_align(field_metadata.size, field_metadata.alignment) + .unwrap(), + ); + + item_field_bytes.as_slice_mut().copy_from_slice( + field_slice + .get_item(item_index) + .expect("Not possible") + .bytes, + ); + + let item_field = FieldOwned { + bytes: item_field_bytes, + field_metadata, + }; + + item_fields.push(item_field); + + let item_field_offset = field_slice + .get_item_offset(item_index) + .expect("Not possible"); + + let last_item_field_offset = field_slice + .get_item_offset(prev_length - 1) + .expect("Not possible"); + + field_slice.bytes.copy_within( + last_item_field_offset + ..last_item_field_offset + field_slice.field_metadata.size, + item_field_offset, + ); + } + + Some(item_fields) + } + ///// Returns a field of the item with the given index. ///// ///// This function is equivalant to doing `.get_all().get(index)` @@ -230,13 +354,11 @@ impl MultiVec /// Returns a slice containing the specified field of all items. #[must_use] - pub fn get_field_slice(&self, field_index: usize) -> FieldSlice<'_> + pub fn get_field_slice(&self, field_index: usize) -> Option<FieldSlice<'_>> { - let field_arr_byte_offset = self.field_arr_byte_offsets[field_index]; - - let field_metadata = &self.field_metadata[field_index]; + let field_metadata = &self.get_field_metadata()?.get(field_index)?; - let field_arr_ptr = unsafe { self.ptr.byte_add(field_arr_byte_offset) }; + let field_arr_ptr = unsafe { self.ptr.byte_add(field_metadata.array_offset) }; let bytes = unsafe { std::slice::from_raw_parts( @@ -245,22 +367,21 @@ impl MultiVec ) }; - FieldSlice { + Some(FieldSlice { bytes, len: self.len(), field_metadata, - } + }) } /// Returns a slice containing the specified field of all items. #[must_use] - pub fn get_field_slice_mut(&mut self, field_index: usize) -> FieldSliceMut<'_> + pub fn get_field_slice_mut(&mut self, field_index: usize) + -> Option<FieldSliceMut<'_>> { - let field_arr_byte_offset = self.field_arr_byte_offsets[field_index]; + let field_metadata = &self.get_field_metadata()?.get(field_index)?; - let field_metadata = &self.field_metadata[field_index]; - - let field_arr_ptr = unsafe { self.ptr.byte_add(field_arr_byte_offset) }; + let field_arr_ptr = unsafe { self.ptr.byte_add(field_metadata.array_offset) }; let bytes = unsafe { std::slice::from_raw_parts_mut( @@ -269,11 +390,11 @@ impl MultiVec ) }; - FieldSliceMut { + Some(FieldSliceMut { bytes, len: self.len(), field_metadata, - } + }) } /// Returns the number of items stored in this `MultiVec`. @@ -286,7 +407,11 @@ impl MultiVec /// Returns how many fields each item in this `MultiVec` has. pub fn field_cnt(&self) -> usize { - self.field_arr_byte_offsets.len() + if self.capacity() == 0 { + return 0; + } + + unsafe { self.ptr.byte_add(FIELD_COUNT_OFFSET).cast::<usize>().read() } } /// Returns how many items this `MultiVec` has capacity for. @@ -312,21 +437,37 @@ impl MultiVec let new_capacity = max(self.capacity * 2, required_cap); let new_capacity = max(Self::get_min_non_zero_cap(&fields), new_capacity); - let layout = &self.layout.unwrap(); - let (new_layout, new_field_arr_byte_offsets) = Self::create_layout(new_capacity, &fields); - let Some(new_ptr) = NonNull::new(if layout.size() == 0 { - std::ptr::dangling_mut() - } else { - unsafe { alloc(new_layout) } - }) else { + assert_ne!(new_layout.size(), 0); + + let Some(new_ptr) = NonNull::new(unsafe { alloc(new_layout) }) else { handle_alloc_error(new_layout); }; + unsafe { + new_ptr + .byte_add(FIELD_COUNT_OFFSET) + .cast::<usize>() + .write(self.field_cnt()); + } + + unsafe { + std::ptr::copy_nonoverlapping( + self.get_field_metadata() + .expect("Missing field metadata") + .as_ptr(), + new_ptr + .byte_add(FIELD_METADATA_ARRAY_OFFSET) + .cast::<FieldMetadata>() + .as_ptr(), + self.field_cnt(), + ); + } + for field_index in 0..self.field_cnt() { - let field_slice = self.get_field_slice(field_index); + let field_slice = self.get_field_slice(field_index).unwrap(); let new_byte_offset = new_field_arr_byte_offsets[field_index]; @@ -349,25 +490,50 @@ impl MultiVec self.ptr = new_ptr.cast::<MaybeUninit<u8>>(); self.layout = Some(new_layout); self.capacity = new_capacity; - self.field_arr_byte_offsets = new_field_arr_byte_offsets; + + for (field_metadata, new_field_array_offset) in self + .get_maybe_uninit_field_metadata_mut() + .iter_mut() + .zip(new_field_arr_byte_offsets) + { + let field_metadata = unsafe { field_metadata.assume_init_mut() }; + + field_metadata.array_offset = new_field_array_offset; + } } - fn do_first_alloc(&mut self, capacity: usize, fields: impl AsRef<[OwnedAnyPtr]>) + fn do_first_alloc(&mut self, capacity: usize, item_fields: impl AsRef<[OwnedAnyPtr]>) { - let (layout, field_arr_byte_offsets) = Self::create_layout(capacity, fields); + let (layout, field_arr_byte_offsets) = + Self::create_layout(capacity, item_fields.as_ref()); - let Some(ptr) = NonNull::new(if layout.size() == 0 { - std::ptr::dangling_mut() - } else { - unsafe { alloc(layout) } - }) else { + assert_ne!(layout.size(), 0); + + let Some(ptr) = NonNull::new(unsafe { alloc(layout) }) else { handle_alloc_error(layout); }; self.ptr = ptr.cast::<MaybeUninit<u8>>(); self.capacity = capacity; - self.field_arr_byte_offsets = field_arr_byte_offsets; self.layout = Some(layout); + + self.set_field_cnt(item_fields.as_ref().len()); + + for (field_index, uninit_field_metadata) in self + .get_maybe_uninit_field_metadata_mut() + .iter_mut() + .enumerate() + { + let item_field = &item_fields.as_ref()[field_index]; + + uninit_field_metadata.write(FieldMetadata { + size: item_field.size(), + alignment: item_field.alignment(), + type_id: item_field.id(), + array_offset: field_arr_byte_offsets[field_index], + drop_in_place: item_field.drop_in_place, + }); + } } fn create_layout( @@ -375,18 +541,26 @@ impl MultiVec fields: impl AsRef<[OwnedAnyPtr]>, ) -> (Layout, Vec<usize>) { - let mut field_iter = fields.as_ref().iter(); + let layout = Layout::from_size_align(0, 1).expect("Failed to create base layout"); - let first_field = field_iter.next().unwrap(); + let (layout, field_cnt_offset) = layout + .extend(Layout::new::<usize>()) + .expect("Failed to extend layout with field count layout"); - let mut layout = - array_layout(first_field.size(), first_field.alignment(), length).unwrap(); + assert_eq!(field_cnt_offset, FIELD_COUNT_OFFSET); - let mut field_arr_byte_offsets = Vec::with_capacity(fields.as_ref().len()); + let (mut layout, field_metadata_array_offset) = layout + .extend( + Layout::array::<FieldMetadata>(fields.as_ref().len()) + .expect("Failed to create field metadata array layout"), + ) + .expect("Failed to extend layout with field metadata array layout"); + + assert_eq!(field_metadata_array_offset, FIELD_METADATA_ARRAY_OFFSET); - field_arr_byte_offsets.push(0); + let mut field_arr_byte_offsets = Vec::with_capacity(fields.as_ref().len()); - for field in field_iter { + for field in fields.as_ref().iter() { let (new_layout, array_byte_offset) = layout .extend(array_layout(field.size(), field.alignment(), length).unwrap()) .unwrap(); @@ -401,12 +575,12 @@ impl MultiVec fn write_item(&mut self, index: usize, fields: impl IntoIterator<Item = OwnedAnyPtr>) { - for (field_index, item_field) in fields.into_iter().enumerate() { + for (item_field, field_metadata) in + fields.into_iter().zip(self.get_field_metadata().unwrap()) + { let field_size = item_field.size(); - let field_arr_byte_offset = self.field_arr_byte_offsets[field_index]; - - let field_arr_ptr = unsafe { self.ptr.byte_add(field_arr_byte_offset) }; + let field_arr_ptr = unsafe { self.ptr.byte_add(field_metadata.array_offset) }; let field_dst_ptr = unsafe { field_arr_ptr.add(field_size * index) }; @@ -436,6 +610,47 @@ impl MultiVec std::alloc::dealloc(self.ptr.as_ptr().cast::<u8>(), layout); } } + + fn get_field_metadata(&self) -> Option<&[FieldMetadata]> + { + if self.capacity == 0 { + return None; + } + + Some(unsafe { + std::slice::from_raw_parts( + self.ptr + .as_ptr() + .byte_add(FIELD_METADATA_ARRAY_OFFSET) + .cast::<FieldMetadata>(), + self.field_cnt(), + ) + }) + } + + fn get_maybe_uninit_field_metadata_mut(&mut self) + -> &mut [MaybeUninit<FieldMetadata>] + { + unsafe { + std::slice::from_raw_parts_mut( + self.ptr + .as_ptr() + .byte_add(FIELD_METADATA_ARRAY_OFFSET) + .cast::<MaybeUninit<FieldMetadata>>(), + self.field_cnt(), + ) + } + } + + fn set_field_cnt(&mut self, field_cnt: usize) + { + unsafe { + self.ptr + .byte_add(FIELD_COUNT_OFFSET) + .cast::<usize>() + .write(field_cnt); + } + } } //impl<ItemT> FromIterator<ItemT> for MultiVec<ItemT> @@ -477,10 +692,12 @@ impl Drop for MultiVec { fn drop(&mut self) { - assert_eq!(self.field_metadata.len(), self.field_arr_byte_offsets.len()); - - for field_index in 0..self.field_arr_byte_offsets.len() { - for field in self.get_field_slice_mut(field_index).iter_mut() { + for field_index in 0..self.field_cnt() { + for field in self + .get_field_slice_mut(field_index) + .expect("Not possible") + .iter_mut() + { let field_ptr = field.bytes.as_mut_ptr(); unsafe { @@ -497,6 +714,7 @@ impl Drop for MultiVec } } +#[derive(Debug)] pub struct FieldSlice<'mv> { bytes: &'mv [MaybeUninit<u8>], @@ -513,6 +731,24 @@ impl FieldSlice<'_> unsafe { self.bytes.cast::<Item>() } } + pub fn get_item(&self, item_index: usize) -> Option<Field<'_>> + { + let start_off = self.get_item_offset(item_index)?; + + if item_index >= self.len { + return None; + } + + let field_bytes = self + .bytes + .get(start_off..start_off + self.field_metadata.size)?; + + Some(Field { + bytes: field_bytes, + field_metadata: self.field_metadata, + }) + } + pub fn iter(&self) -> FieldSliceIter<'_> { FieldSliceIter { @@ -522,8 +758,18 @@ impl FieldSlice<'_> field_metadata: self.field_metadata, } } + + fn get_item_offset(&self, item_index: usize) -> Option<usize> + { + if item_index >= self.len { + return None; + } + + Some(item_index * self.field_metadata.size) + } } +#[derive(Debug)] pub struct FieldSliceIter<'mv> { bytes: &'mv [MaybeUninit<u8>], @@ -557,22 +803,67 @@ impl<'mv> Iterator for FieldSliceIter<'mv> } } +#[derive(Debug)] pub struct Field<'mv> { bytes: &'mv [MaybeUninit<u8>], field_metadata: &'mv FieldMetadata, } -impl Field<'_> +impl<'mv> Field<'mv> { - pub fn cast<T: 'static>(&mut self) -> &T + pub fn cast<T: 'static>(&self) -> &T { assert_eq!(TypeId::of::<T>(), self.field_metadata.type_id); - unsafe { &*self.bytes.as_ptr().cast::<T>() } + let ptr: *const MaybeUninit<u8> = self.bytes.as_ptr(); + + unsafe { &*ptr.cast::<T>() } } } +#[derive(Debug)] +pub struct FieldOwned<'mv> +{ + bytes: AnonUnique, + field_metadata: &'mv FieldMetadata, +} + +impl FieldOwned<'_> +{ + pub fn as_ref<T: 'static>(&self) -> &T + { + assert_eq!(TypeId::of::<T>(), self.field_metadata.type_id); + + let ptr: *const MaybeUninit<u8> = self.bytes.as_slice().as_ptr(); + + unsafe { &*ptr.cast::<T>() } + } + + pub fn into_boxed<T: 'static>(mut self) -> Box<T> + { + assert_eq!(TypeId::of::<T>(), self.field_metadata.type_id); + + let layout = self.bytes.layout(); + + assert_eq!(layout.size(), size_of::<T>()); + assert_eq!(layout.align(), align_of::<T>()); + + unsafe { Box::from_raw(self.bytes.as_slice_mut().as_mut_ptr().cast::<T>()) } + } +} + +impl Drop for FieldOwned<'_> +{ + fn drop(&mut self) + { + unsafe { + (self.field_metadata.drop_in_place)(self.bytes.as_ptr()); + } + } +} + +#[derive(Debug)] pub struct FieldSliceMut<'mv> { bytes: &'mv mut [MaybeUninit<u8>], @@ -580,11 +871,31 @@ pub struct FieldSliceMut<'mv> field_metadata: &'mv FieldMetadata, } -impl FieldSliceMut<'_> +impl<'mv> FieldSliceMut<'mv> { + pub fn get_item<'this>(&'this self, item_index: usize) -> Option<Field<'mv>> + where + 'this: 'mv, + { + let start_off = self.get_item_offset(item_index)?; + + if item_index >= self.len { + return None; + } + + let field_bytes = self + .bytes + .get(start_off..start_off + self.field_metadata.size)?; + + Some(Field { + bytes: field_bytes, + field_metadata: self.field_metadata, + }) + } + pub fn get_item_mut(&mut self, item_index: usize) -> Option<FieldMut<'_>> { - let start_off = item_index * self.field_metadata.size; + let start_off = self.get_item_offset(item_index)?; if item_index >= self.len { return None; @@ -609,8 +920,18 @@ impl FieldSliceMut<'_> field_metadata: self.field_metadata, } } + + fn get_item_offset(&self, item_index: usize) -> Option<usize> + { + if item_index >= self.len { + return None; + } + + Some(item_index * self.field_metadata.size) + } } +#[derive(Debug)] pub struct FieldSliceIterMut<'mv> { bytes: &'mv mut [MaybeUninit<u8>], @@ -638,7 +959,6 @@ impl<'mv> Iterator for FieldSliceIterMut<'mv> let field_bytes = unsafe { std::slice::from_raw_parts_mut( field_bytes_a.as_mut_ptr(), - //self.bytes.as_mut_ptr().byte_add(start_off), self.field_metadata.size, ) }; @@ -652,6 +972,7 @@ impl<'mv> Iterator for FieldSliceIterMut<'mv> } } +#[derive(Debug)] pub struct FieldMut<'mv> { bytes: &'mv mut [MaybeUninit<u8>], @@ -672,7 +993,9 @@ impl FieldMut<'_> struct FieldMetadata { size: usize, + alignment: usize, type_id: TypeId, + array_offset: usize, drop_in_place: unsafe fn(NonNull<MaybeUninit<u8>>), } @@ -733,11 +1056,29 @@ struct CoolLayoutError; mod tests { use std::any::TypeId; - use std::mem::offset_of; + use std::mem::{offset_of, ManuallyDrop}; use std::ptr::NonNull; use std::sync::atomic::{AtomicUsize, Ordering}; - use crate::{FieldMetadata, MultiVec, OwnedAnyPtr}; + use crate::{ + FieldMetadata, + MultiVec, + OwnedAnyPtr, + FIELD_COUNT_OFFSET, + FIELD_METADATA_ARRAY_OFFSET, + }; + + macro_rules! replace { + ($tt: tt, $replacement: tt) => { + $replacement + }; + } + + macro_rules! count_rep { + ($($tt: tt,)*) => { + 0 $( + replace!($tt, 1))* + }; + } macro_rules! multi_vec_with_data { ( @@ -750,32 +1091,33 @@ mod tests #[repr(C)] struct Data { + field_cnt: usize, + field_metadata: [FieldMetadata; count_rep!($($field_name,)*)], $($field_name: [$field_type; $length],)* } - $data = Data { + assert_eq!(offset_of!(Data, field_cnt), FIELD_COUNT_OFFSET); + assert_eq!(offset_of!(Data, field_metadata), FIELD_METADATA_ARRAY_OFFSET); + + $data = ManuallyDrop::new(Data { + field_cnt: count_rep!($($field_name,)*), + field_metadata: [$( + FieldMetadata { + size: size_of::<$field_type>(), + alignment: align_of::<$field_type>(), + type_id: TypeId::of::<$field_type>(), + array_offset: offset_of!(Data, $field_name), + drop_in_place: |ptr| unsafe { + std::ptr::drop_in_place(ptr.cast::<$field_type>().as_ptr()); + }, + }, + )*], $($field_name: $field_values.map(|val| val.into()),)* - }; + }); let mut multi_vec = MultiVec::new(); multi_vec.ptr = NonNull::from(&mut $data).cast(); - - std::mem::forget($data); - - multi_vec.field_arr_byte_offsets = - vec![$(offset_of!(Data, $field_name),)*]; - - multi_vec.field_metadata = vec![$( - FieldMetadata { - size: size_of::<$field_type>(), - type_id: TypeId::of::<$field_type>(), - drop_in_place: |ptr| unsafe { - std::ptr::drop_in_place(ptr.cast::<$field_type>().as_ptr()); - }, - }, - )*]; - multi_vec.length = $length; multi_vec.capacity = multi_vec.length; @@ -788,16 +1130,38 @@ mod tests { let mut multi_vec = MultiVec::new(); - multi_vec.push([OwnedAnyPtr::new(123), OwnedAnyPtr::new(654)]); + multi_vec.push([OwnedAnyPtr::new(123u32), OwnedAnyPtr::new(654u16)]); assert_eq!(multi_vec.capacity, 1); assert_eq!(multi_vec.length, 1); + assert_eq!(multi_vec.field_cnt(), 2); + + let field_metadata_arr_size = FIELD_METADATA_ARRAY_OFFSET + + size_of::<FieldMetadata>() * multi_vec.field_cnt(); - assert_eq!(multi_vec.field_arr_byte_offsets, [0, size_of::<u32>()]); + let field_metadata = multi_vec.get_field_metadata().expect("Should be Some"); + + assert_eq!(field_metadata[0].size, size_of::<u32>()); + assert_eq!(field_metadata[0].type_id, TypeId::of::<u32>()); + assert_eq!(field_metadata[0].array_offset, field_metadata_arr_size + 0); + + assert_eq!(field_metadata[1].size, size_of::<u16>()); + assert_eq!(field_metadata[1].type_id, TypeId::of::<u16>()); + assert_eq!( + field_metadata[1].array_offset, + field_metadata_arr_size + size_of::<u32>() + ); assert_eq!( unsafe { - std::slice::from_raw_parts::<u32>(multi_vec.ptr.as_ptr().cast(), 1) + std::slice::from_raw_parts::<u32>( + multi_vec + .ptr + .as_ptr() + .byte_add(field_metadata[0].array_offset) + .cast(), + 1, + ) }, [123] ); @@ -805,7 +1169,11 @@ mod tests assert_eq!( unsafe { std::slice::from_raw_parts::<u16>( - multi_vec.ptr.as_ptr().byte_add(size_of::<u32>()).cast(), + multi_vec + .ptr + .as_ptr() + .byte_add(field_metadata[1].array_offset) + .cast(), 1, ) }, @@ -818,18 +1186,49 @@ mod tests { let mut multi_vec = MultiVec::new(); - multi_vec.push([OwnedAnyPtr::new(u32::MAX / 2), OwnedAnyPtr::new::<u16>(654)]); - multi_vec.push([OwnedAnyPtr::new(765), OwnedAnyPtr::new::<u16>(u16::MAX / 3)]); - multi_vec.push([OwnedAnyPtr::new(u32::MAX / 5), OwnedAnyPtr::new::<u16>(337)]); + multi_vec.push([ + OwnedAnyPtr::new::<u32>(u32::MAX / 2), + OwnedAnyPtr::new::<u16>(654), + ]); + multi_vec.push([ + OwnedAnyPtr::new::<u32>(765), + OwnedAnyPtr::new::<u16>(u16::MAX / 3), + ]); + multi_vec.push([ + OwnedAnyPtr::new::<u32>(u32::MAX / 5), + OwnedAnyPtr::new::<u16>(337), + ]); assert_eq!(multi_vec.capacity, 4); assert_eq!(multi_vec.length, 3); + assert_eq!(multi_vec.field_cnt(), 2); + + let field_metadata_arr_size = FIELD_METADATA_ARRAY_OFFSET + + size_of::<FieldMetadata>() * multi_vec.field_cnt(); + + let field_metadata = multi_vec.get_field_metadata().expect("Should be Some"); - assert_eq!(multi_vec.field_arr_byte_offsets, [0, size_of::<u32>() * 4]); + assert_eq!(field_metadata[0].size, size_of::<u32>()); + assert_eq!(field_metadata[0].type_id, TypeId::of::<u32>()); + assert_eq!(field_metadata[0].array_offset, field_metadata_arr_size + 0); + + assert_eq!(field_metadata[1].size, size_of::<u16>()); + assert_eq!(field_metadata[1].type_id, TypeId::of::<u16>()); + assert_eq!( + field_metadata[1].array_offset, + field_metadata_arr_size + size_of::<u32>() * multi_vec.capacity + ); assert_eq!( unsafe { - std::slice::from_raw_parts::<u32>(multi_vec.ptr.as_ptr().cast(), 3) + std::slice::from_raw_parts::<u32>( + multi_vec + .ptr + .as_ptr() + .byte_add(field_metadata[0].array_offset) + .cast(), + multi_vec.length, + ) }, [u32::MAX / 2, 765, u32::MAX / 5] ); @@ -837,8 +1236,12 @@ mod tests assert_eq!( unsafe { std::slice::from_raw_parts::<u16>( - multi_vec.ptr.as_ptr().byte_add(size_of::<u32>() * 4).cast(), - 3, + multi_vec + .ptr + .as_ptr() + .byte_add(field_metadata[1].array_offset) + .cast(), + multi_vec.length, ) }, [654, u16::MAX / 3, 337] @@ -846,7 +1249,7 @@ mod tests } #[test] - fn push_all_unsized_fields_work() + fn push_with_all_unsized_fields_works() { struct UnsizedThing; @@ -854,6 +1257,108 @@ mod tests multi_vec.push([OwnedAnyPtr::new(()), OwnedAnyPtr::new(UnsizedThing)]); multi_vec.push([OwnedAnyPtr::new(()), OwnedAnyPtr::new(UnsizedThing)]); + + let field_metadata_arr_size = FIELD_METADATA_ARRAY_OFFSET + + size_of::<FieldMetadata>() * multi_vec.field_cnt(); + + let field_metadata = multi_vec.get_field_metadata().expect("Should be Some"); + + assert_eq!(field_metadata[0].size, size_of::<()>()); + assert_eq!(field_metadata[0].type_id, TypeId::of::<()>()); + assert_eq!(field_metadata[0].array_offset, field_metadata_arr_size + 0); + + assert_eq!(field_metadata[1].size, size_of::<UnsizedThing>()); + assert_eq!(field_metadata[1].type_id, TypeId::of::<UnsizedThing>()); + assert_eq!(field_metadata[1].array_offset, field_metadata_arr_size + 0); + } + + #[test] + fn push_with_some_unsized_fields_works() + { + struct UnsizedThing; + + #[derive(Debug, PartialEq, Eq)] + struct CustomerName + { + name: &'static str, + } + + #[derive(Debug, PartialEq, Eq)] + struct CustomerAge + { + age: u8, + } + + let mut multi_vec = MultiVec::new(); + + multi_vec.push([ + OwnedAnyPtr::new(CustomerName { name: "Bob Vance" }), + OwnedAnyPtr::new(UnsizedThing), + OwnedAnyPtr::new(CustomerAge { age: 54 }), + ]); + + multi_vec.push([ + OwnedAnyPtr::new(CustomerName { name: "Andy Bernard" }), + OwnedAnyPtr::new(UnsizedThing), + OwnedAnyPtr::new(CustomerAge { age: 40 }), + ]); + + assert_eq!(multi_vec.capacity, 4); + assert_eq!(multi_vec.length, 2); + + let field_metadata_arr_size = FIELD_METADATA_ARRAY_OFFSET + + size_of::<FieldMetadata>() * multi_vec.field_cnt(); + + let field_metadata = multi_vec.get_field_metadata().expect("Should be Some"); + + assert_eq!(field_metadata[0].size, size_of::<CustomerName>()); + assert_eq!(field_metadata[0].type_id, TypeId::of::<CustomerName>()); + assert_eq!(field_metadata[0].array_offset, field_metadata_arr_size + 0); + + assert_eq!(field_metadata[1].size, size_of::<UnsizedThing>()); + assert_eq!(field_metadata[1].type_id, TypeId::of::<UnsizedThing>()); + assert_eq!( + field_metadata[1].array_offset, + field_metadata_arr_size + size_of::<CustomerName>() * multi_vec.capacity + ); + + assert_eq!(field_metadata[2].size, size_of::<CustomerAge>()); + assert_eq!(field_metadata[2].type_id, TypeId::of::<CustomerAge>()); + assert_eq!( + field_metadata[2].array_offset, + field_metadata_arr_size + size_of::<CustomerName>() * multi_vec.capacity + ); + + assert_eq!( + unsafe { + std::slice::from_raw_parts::<CustomerName>( + multi_vec + .ptr + .as_ptr() + .byte_add(field_metadata[0].array_offset) + .cast(), + multi_vec.length, + ) + }, + [ + CustomerName { name: "Bob Vance" }, + CustomerName { name: "Andy Bernard" } + ] + ); + + assert_eq!( + unsafe { + std::slice::from_raw_parts::<CustomerAge>( + multi_vec + .ptr + .as_ptr() + .byte_add(field_metadata[2].array_offset) + .cast(), + multi_vec.length, + ) + }, + [CustomerAge { age: 54 }, CustomerAge { age: 40 }] + ); } //#[test] @@ -970,12 +1475,18 @@ mod tests ); assert_eq!( - multi_vec.get_field_slice(0).as_slice::<u32>(), + multi_vec + .get_field_slice(0) + .expect("Should be Some") + .as_slice::<u32>(), [u32::MAX - 3000, 901, 5560000] ); assert_eq!( - multi_vec.get_field_slice(1).as_slice::<u16>(), + multi_vec + .get_field_slice(1) + .expect("Should be Some") + .as_slice::<u16>(), [20210, 7120, 1010] ); } @@ -995,22 +1506,127 @@ mod tests ); assert_eq!( - multi_vec.get_field_slice(0).as_slice::<u32>(), + multi_vec + .get_field_slice(0) + .expect("Should be Some") + .as_slice::<u32>(), [123, 888, 1910, 11144, 770077] ); assert_eq!( - multi_vec.get_field_slice(1).as_slice::<String>(), + multi_vec + .get_field_slice(1) + .expect("Should be Some") + .as_slice::<String>(), ["No,", "I", "am", "your", "father",] ); assert_eq!( - multi_vec.get_field_slice(2).as_slice::<u8>(), + multi_vec + .get_field_slice(2) + .expect("Should be Some") + .as_slice::<u8>(), [120, 88, 54, 3, 7] ); } #[test] + fn remove_in_middle_works() + { + let mut data; + let mut multi_vec = multi_vec_with_data!( + data = &mut data, + { + _a: u32 = [u32::MAX - 3000, 901, 5560000, 123123], + _b: u16 = [20210u16, 7120, 1010, 9009], + }, + length = 4 + ); + + let removed = multi_vec.remove(1).expect("Should be Some"); + + assert_eq!(&data._a[0..3], [u32::MAX - 3000, 5560000, 123123]); + assert_eq!(&data._b[0..3], [20210u16, 1010, 9009]); + + assert_eq!(removed.len(), 2); + + assert_eq!(*removed[0].as_ref::<u32>(), 901); + assert_eq!(*removed[1].as_ref::<u16>(), 7120); + } + + #[test] + fn remove_at_end_works() + { + let mut data; + let mut multi_vec = multi_vec_with_data!( + data = &mut data, + { + _a: u32 = [u32::MAX - 3000, 901, 5560000, 123123], + _b: u16 = [20210u16, 7120, 1010, 9009], + }, + length = 4 + ); + + let removed = multi_vec.remove(3).expect("Should be Some"); + + assert_eq!(&data._a[0..3], [u32::MAX - 3000, 901, 5560000]); + assert_eq!(&data._b[0..3], [20210u16, 7120, 1010]); + + assert_eq!(removed.len(), 2); + + assert_eq!(*removed[0].as_ref::<u32>(), 123123); + assert_eq!(*removed[1].as_ref::<u16>(), 9009); + } + + #[test] + fn swap_remove_in_middle_works() + { + let mut data; + let mut multi_vec = multi_vec_with_data!( + data = &mut data, + { + _a: u32 = [u32::MAX - 3000, 901, 5560000, 123123], + _b: u16 = [20210u16, 7120, 1010, 9009], + }, + length = 4 + ); + + let removed = multi_vec.swap_remove(1).expect("Should be Some"); + + assert_eq!(&data._a[0..3], [u32::MAX - 3000, 123123, 5560000]); + assert_eq!(&data._b[0..3], [20210u16, 9009, 1010]); + + assert_eq!(removed.len(), 2); + + assert_eq!(*removed[0].as_ref::<u32>(), 901); + assert_eq!(*removed[1].as_ref::<u16>(), 7120); + } + + #[test] + fn swap_remove_at_end_works() + { + let mut data; + let mut multi_vec = multi_vec_with_data!( + data = &mut data, + { + _a: u32 = [u32::MAX - 3000, 901, 5560000, 123123], + _b: u16 = [20210u16, 7120, 1010, 9009], + }, + length = 4 + ); + + let removed = multi_vec.swap_remove(3).expect("Should be Some"); + + assert_eq!(&data._a[0..3], [u32::MAX - 3000, 901, 5560000]); + assert_eq!(&data._b[0..3], [20210u16, 7120, 1010]); + + assert_eq!(removed.len(), 2); + + assert_eq!(*removed[0].as_ref::<u32>(), 123123); + assert_eq!(*removed[1].as_ref::<u16>(), 9009); + } + + #[test] fn fields_are_dropped() { static THING_DROPPED_CNT: AtomicUsize = AtomicUsize::new(0); diff --git a/src/util.rs b/src/util.rs index 70e114b..ba60395 100644 --- a/src/util.rs +++ b/src/util.rs @@ -1,4 +1,6 @@ +use std::alloc::{alloc, dealloc, handle_alloc_error, Layout}; use std::mem::MaybeUninit; +use std::ptr::NonNull; pub trait MaybeUninitByteSlice { @@ -26,3 +28,63 @@ impl MaybeUninitByteSlice for &[MaybeUninit<u8>] unsafe { std::slice::from_raw_parts(self.as_ptr().cast::<Item>(), new_len) } } } + +#[derive(Debug)] +pub struct AnonUnique +{ + ptr: NonNull<MaybeUninit<u8>>, + layout: Layout, +} + +impl AnonUnique +{ + pub fn new_uninit(layout: Layout) -> Self + { + if layout.size() == 0 { + return Self { ptr: NonNull::dangling(), layout }; + } + + let Some(ptr) = NonNull::new(unsafe { alloc(layout) }) else { + handle_alloc_error(layout); + }; + + Self { + ptr: ptr.cast::<MaybeUninit<u8>>(), + layout, + } + } + + pub fn layout(&self) -> &Layout + { + &self.layout + } + + pub fn as_slice_mut(&mut self) -> &mut [MaybeUninit<u8>] + { + unsafe { std::slice::from_raw_parts_mut(self.ptr.as_ptr(), self.layout.size()) } + } + + pub fn as_slice(&self) -> &[MaybeUninit<u8>] + { + unsafe { std::slice::from_raw_parts(self.ptr.as_ptr(), self.layout.size()) } + } + + pub fn as_ptr(&self) -> NonNull<MaybeUninit<u8>> + { + self.ptr + } +} + +impl Drop for AnonUnique +{ + fn drop(&mut self) + { + if self.layout.size() == 0 { + return; + } + + unsafe { + dealloc(self.ptr.as_ptr().cast(), self.layout); + } + } +} |