--- a/rust/hwphysics/src/data.rs Wed Aug 28 18:35:36 2019 +0200
+++ b/rust/hwphysics/src/data.rs Wed Aug 28 18:36:37 2019 +0200
@@ -1,6 +1,8 @@
use super::common::GearId;
use std::{
any::TypeId,
+ fmt::{Debug, Error, Formatter},
+ io::Write,
mem::{size_of, MaybeUninit},
num::NonZeroU16,
ptr::{copy_nonoverlapping, null_mut, NonNull},
@@ -8,24 +10,18 @@
};
pub trait TypeTuple: Sized {
- fn len() -> usize;
- fn get_types(dest: &mut Vec<TypeId>);
+ fn get_types(types: &mut Vec<TypeId>);
unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F);
}
macro_rules! type_tuple_impl {
($($n: literal: $t: ident),+) => {
impl<$($t: 'static),+> TypeTuple for ($(&$t),+,) {
- fn len() -> usize {
- [$({TypeId::of::<$t>(); 1}),+].iter().sum()
- }
-
fn get_types(types: &mut Vec<TypeId>) {
$(types.push(TypeId::of::<$t>()));+
}
- unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F)
- {
+ unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F) {
for i in 0..count {
unsafe {
f(($(&*(*slices.get_unchecked($n) as *mut $t).add(i)),+,));
@@ -35,16 +31,11 @@
}
impl<$($t: 'static),+> TypeTuple for ($(&mut $t),+,) {
- fn len() -> usize {
- [$({TypeId::of::<$t>(); 1}),+].iter().sum()
- }
-
fn get_types(types: &mut Vec<TypeId>) {
$(types.push(TypeId::of::<$t>()));+
}
- unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F)
- {
+ unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F) {
for i in 0..count {
unsafe {
f(($(&mut *(*slices.get_unchecked($n) as *mut $t).add(i)),+,));
@@ -68,27 +59,65 @@
elements_count: u16,
data: Box<[u8; BLOCK_SIZE]>,
component_blocks: [Option<NonNull<u8>>; 64],
+ element_sizes: Box<[u16]>,
}
impl Unpin for DataBlock {}
+impl Debug for DataBlock {
+ fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
+ write!(
+ f,
+ "Block ({}/{}) {{\n",
+ self.elements_count, self.max_elements
+ )?;
+ write!(f, "\tIDs: [")?;
+ let id_slice = unsafe {
+ slice::from_raw_parts(
+ self.data.as_ptr() as *const GearId,
+ self.elements_count as usize,
+ )
+ };
+ for gear_id in id_slice {
+ write!(f, "{}, ", gear_id)?;
+ }
+ write!(f, "]\n")?;
+ for type_index in 0..self.element_sizes.len() {
+ if let Some(ptr) = self.component_blocks[type_index] {
+ write!(f, "\tC{}: [", type_index)?;
+ let slice = unsafe {
+ slice::from_raw_parts(
+ ptr.as_ptr(),
+ (self.elements_count * self.element_sizes[type_index]) as usize,
+ )
+ };
+ for byte in slice {
+ write!(f, "{}, ", byte)?;
+ }
+ write!(f, "]\n")?;
+ }
+ }
+ write!(f, "}}\n")
+ }
+}
+
impl DataBlock {
- fn new(mask: u64, element_sizes: &[u16; 64]) -> Self {
+ fn new(mask: u64, element_sizes: &[u16]) -> Self {
let total_size: u16 = element_sizes
.iter()
.enumerate()
.filter(|(i, _)| mask & (1 << *i as u64) != 0)
.map(|(_, size)| *size)
.sum();
- let max_elements = (BLOCK_SIZE / total_size as usize) as u16;
+ let max_elements = (BLOCK_SIZE / (total_size as usize + size_of::<GearId>())) as u16;
let mut data: Box<[u8; BLOCK_SIZE]> =
Box::new(unsafe { MaybeUninit::uninit().assume_init() });
let mut blocks = [None; 64];
- let mut offset = 0;
+ let mut offset = size_of::<GearId>() * max_elements as usize;
- for i in 0..64 {
- if mask & (1 << i) != 0 {
+ for i in 0..element_sizes.len() {
+ if mask & (1 << i as u64) != 0 {
blocks[i] = Some(NonNull::new(data[offset..].as_mut_ptr()).unwrap());
offset += element_sizes[i] as usize * max_elements as usize;
}
@@ -98,6 +127,25 @@
max_elements,
data,
component_blocks: blocks,
+ element_sizes: Box::from(element_sizes),
+ }
+ }
+
+ fn gear_ids(&self) -> &[GearId] {
+ unsafe {
+ slice::from_raw_parts(
+ self.data.as_ptr() as *const GearId,
+ self.max_elements as usize,
+ )
+ }
+ }
+
+ fn gear_ids_mut(&mut self) -> &mut [GearId] {
+ unsafe {
+ slice::from_raw_parts_mut(
+ self.data.as_mut_ptr() as *mut GearId,
+ self.max_elements as usize,
+ )
}
}
@@ -112,6 +160,15 @@
block_index: u16,
}
+impl LookupEntry {
+ fn new(block_index: u16, index: u16) -> Self {
+ Self {
+ index: unsafe { Some(NonZeroU16::new_unchecked(index + 1)) },
+ block_index,
+ }
+ }
+}
+
pub struct GearDataManager {
types: Vec<TypeId>,
blocks: Vec<DataBlock>,
@@ -137,33 +194,63 @@
self.types.iter().position(|id| *id == type_id)
}
- fn move_between_blocks(&mut self, from_block_index: u16, from_index: u16, to_block_index: u16) {
- debug_assert!(from_block_index != to_block_index);
- let source_mask = self.block_masks[from_block_index as usize];
- let destination_mask = self.block_masks[to_block_index as usize];
- debug_assert!(source_mask & destination_mask == source_mask);
+ fn move_between_blocks(&mut self, src_block_index: u16, src_index: u16, dest_block_index: u16) {
+ debug_assert!(src_block_index != dest_block_index);
+ let src_mask = self.block_masks[src_block_index as usize];
+ let dest_mask = self.block_masks[dest_block_index as usize];
+ debug_assert!(src_mask & dest_mask == src_mask);
- let source = &self.blocks[from_block_index as usize];
- let destination = &self.blocks[to_block_index as usize];
- debug_assert!(from_index < source.elements_count);
- debug_assert!(!destination.is_full());
+ let src_block = &self.blocks[src_block_index as usize];
+ let dest_block = &self.blocks[dest_block_index as usize];
+ debug_assert!(src_index < src_block.elements_count);
+ debug_assert!(!dest_block.is_full());
- for i in 0..64 {
- if source_mask & 1 << i != 0 {
+ let dest_index = dest_block.elements_count;
+ for i in 0..self.types.len() {
+ if src_mask & (1 << i as u64) != 0 {
+ let size = self.element_sizes[i];
+ let src_ptr = src_block.component_blocks[i].unwrap().as_ptr();
+ let dest_ptr = dest_block.component_blocks[i].unwrap().as_ptr();
unsafe {
copy_nonoverlapping(
- source.component_blocks[i].unwrap().as_ptr(),
- destination.component_blocks[i].unwrap().as_ptr(),
- self.element_sizes[i] as usize,
+ src_ptr.add((src_index * size) as usize),
+ dest_ptr.add((dest_index * size) as usize),
+ size as usize,
);
+ if src_index < src_block.elements_count - 1 {
+ copy_nonoverlapping(
+ src_ptr.add((size * (src_block.elements_count - 1)) as usize),
+ src_ptr.add((size * src_index) as usize),
+ size as usize,
+ );
+ }
}
}
}
- self.blocks[from_block_index as usize].elements_count -= 1;
- self.blocks[to_block_index as usize].elements_count += 1;
+
+ let src_block = &mut self.blocks[src_block_index as usize];
+ let gear_id = src_block.gear_ids()[src_index as usize];
+
+ if src_index < src_block.elements_count - 1 {
+ let relocated_index = src_block.elements_count as usize - 1;
+ let gear_ids = src_block.gear_ids_mut();
+ let relocated_id = gear_ids[relocated_index];
+
+ gear_ids[src_index as usize] = relocated_id;
+ self.lookup[relocated_id.get() as usize - 1] =
+ LookupEntry::new(src_block_index, src_index);
+ }
+ src_block.elements_count -= 1;
+
+ let dest_block = &mut self.blocks[dest_block_index as usize];
+ let dest_index = dest_block.elements_count;
+
+ dest_block.gear_ids_mut()[dest_index as usize] = gear_id;
+ self.lookup[gear_id.get() as usize - 1] = LookupEntry::new(dest_block_index, dest_index);
+ dest_block.elements_count += 1;
}
- fn add_to_block<T: Clone>(&mut self, block_index: u16, value: &T) {
+ fn add_to_block<T: Clone>(&mut self, gear_id: GearId, block_index: u16, value: &T) {
debug_assert!(self.block_masks[block_index as usize].count_ones() == 1);
let block = &mut self.blocks[block_index as usize];
@@ -171,11 +258,15 @@
unsafe {
let slice = slice::from_raw_parts_mut(
- block.data.as_mut_ptr() as *mut T,
+ block.component_blocks[0].unwrap().as_ptr() as *mut T,
block.max_elements as usize,
);
*slice.get_unchecked_mut(block.elements_count as usize) = value.clone();
};
+
+ let index = block.elements_count;
+ self.lookup[gear_id.get() as usize - 1] = LookupEntry::new(block_index, index);
+ block.gear_ids_mut()[index as usize] = gear_id;
block.elements_count += 1;
}
@@ -197,6 +288,16 @@
}
}
}
+
+ self.lookup[block.gear_ids()[index as usize].get() as usize - 1] = LookupEntry::default();
+ if index < block.elements_count - 1 {
+ let relocated_index = block.elements_count as usize - 1;
+ let gear_ids = block.gear_ids_mut();
+
+ gear_ids[index as usize] = gear_ids[relocated_index];
+ self.lookup[gear_ids[relocated_index].get() as usize - 1] =
+ LookupEntry::new(block_index, index);
+ }
block.elements_count -= 1;
}
@@ -210,7 +311,10 @@
{
index as u16
} else {
- self.blocks.push(DataBlock::new(mask, &self.element_sizes));
+ self.blocks.push(DataBlock::new(
+ mask,
+ &self.element_sizes[0..self.types.len()],
+ ));
self.block_masks.push(mask);
(self.blocks.len() - 1) as u16
}
@@ -231,7 +335,7 @@
}
} else {
let dest_block_index = self.ensure_block(type_bit);
- self.add_to_block(dest_block_index, value);
+ self.add_to_block(gear_id, dest_block_index, value);
}
} else {
panic!("Unregistered type")
@@ -242,18 +346,14 @@
if let Some(type_index) = self.get_type_index::<T>() {
let entry = self.lookup[gear_id.get() as usize - 1];
if let Some(index) = entry.index {
- let destination_mask =
+ let dest_mask =
self.block_masks[entry.block_index as usize] & !(1 << type_index as u64);
- if destination_mask == 0 {
+ if dest_mask == 0 {
self.remove_all(gear_id)
} else {
- let destination_block_index = self.ensure_block(destination_mask);
- self.move_between_blocks(
- entry.block_index,
- index.get() - 1,
- destination_block_index,
- );
+ let dest_block_index = self.ensure_block(dest_mask);
+ self.move_between_blocks(entry.block_index, index.get() - 1, dest_block_index);
}
}
} else {
@@ -289,21 +389,20 @@
for (arg_index, type_id) in arg_types.iter().enumerate() {
match self.types.iter().position(|t| t == type_id) {
- Some(i) if selector & 1 << i as u64 != 0 => panic!("Duplicate type"),
+ Some(i) if selector & (1 << i as u64) != 0 => panic!("Duplicate type"),
Some(i) => {
type_indices[arg_index] = i as i8;
- selector &= 1 << i as u64;
+ selector |= 1 << i as u64;
}
None => panic!("Unregistered type"),
}
}
-
let mut slices = vec![null_mut(); arg_types.len()];
for (block_index, mask) in self.block_masks.iter().enumerate() {
if mask & selector == selector {
let block = &self.blocks[block_index];
-
+ block.elements_count;
for (arg_index, type_index) in type_indices.iter().cloned().enumerate() {
slices[arg_index as usize] = block.component_blocks[type_index as usize]
.unwrap()
@@ -327,10 +426,13 @@
value: u32,
}
+ #[derive(Clone)]
+ struct Tag {
+ nothing: u8,
+ }
+
#[test]
fn single_component_iteration() {
- assert!(std::mem::size_of::<Datum>() > 0);
-
let mut manager = GearDataManager::new();
manager.register::<Datum>();
for i in 1..=5 {
@@ -345,4 +447,33 @@
manager.iter(|(d,): (&Datum,)| sum += d.value);
assert_eq!(sum, 35);
}
+
+ #[test]
+ fn multiple_component_iteration() {
+ let mut manager = GearDataManager::new();
+ manager.register::<Datum>();
+ manager.register::<Tag>();
+ for i in 1..=10 {
+ let gear_id = GearId::new(i as u16).unwrap();
+ manager.add(gear_id, &Datum { value: i });
+ }
+
+ for i in 1..=10 {
+ let gear_id = GearId::new(i as u16).unwrap();
+ if i & 1 == 0 {
+ manager.add(GearId::new(i as u16).unwrap(), &Tag { nothing: 0 });
+ }
+ }
+
+ let mut sum = 0;
+ manager.iter(|(d,): (&Datum,)| sum += d.value);
+ assert_eq!(sum, 55);
+
+ let mut tag_sum1 = 0;
+ let mut tag_sum2 = 0;
+ manager.iter(|(d, _): (&Datum, &Tag)| tag_sum1 += d.value);
+ manager.iter(|(_, d): (&Tag, &Datum)| tag_sum2 += d.value);
+ assert_eq!(tag_sum1, 30);
+ assert_eq!(tag_sum2, tag_sum1);
+ }
}