author | alfadur |
Wed, 28 Aug 2019 13:20:10 +0300 | |
changeset 15373 | 5e2b9740086f |
parent 15372 | 7a3ed957cee9 |
child 15375 | 37b632d38f14 |
permissions | -rw-r--r-- |
15354 | 1 |
use super::common::GearId; |
2 |
use std::{ |
|
3 |
any::TypeId, |
|
4 |
mem::{size_of, MaybeUninit}, |
|
5 |
num::NonZeroU16, |
|
15368 | 6 |
ptr::{copy_nonoverlapping, null_mut, NonNull}, |
15354 | 7 |
slice, |
8 |
}; |
|
15305 | 9 |
|
15368 | 10 |
pub trait TypeTuple: Sized { |
15305 | 11 |
fn len() -> usize; |
15373 | 12 |
fn get_types(types: &mut Vec<TypeId>); |
15368 | 13 |
unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F); |
15305 | 14 |
} |
15 |
||
15369 | 16 |
macro_rules! type_tuple_impl { |
17 |
($($n: literal: $t: ident),+) => { |
|
18 |
impl<$($t: 'static),+> TypeTuple for ($(&$t),+,) { |
|
15368 | 19 |
fn len() -> usize { |
15369 | 20 |
[$({TypeId::of::<$t>(); 1}),+].iter().sum() |
15368 | 21 |
} |
22 |
||
23 |
fn get_types(types: &mut Vec<TypeId>) { |
|
15369 | 24 |
$(types.push(TypeId::of::<$t>()));+ |
15368 | 25 |
} |
15305 | 26 |
|
15371 | 27 |
unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F) { |
15368 | 28 |
for i in 0..count { |
29 |
unsafe { |
|
15369 | 30 |
f(($(&*(*slices.get_unchecked($n) as *mut $t).add(i)),+,)); |
15368 | 31 |
} |
32 |
} |
|
33 |
} |
|
34 |
} |
|
15354 | 35 |
|
15369 | 36 |
impl<$($t: 'static),+> TypeTuple for ($(&mut $t),+,) { |
15368 | 37 |
fn len() -> usize { |
15369 | 38 |
[$({TypeId::of::<$t>(); 1}),+].iter().sum() |
15368 | 39 |
} |
40 |
||
41 |
fn get_types(types: &mut Vec<TypeId>) { |
|
15369 | 42 |
$(types.push(TypeId::of::<$t>()));+ |
15368 | 43 |
} |
44 |
||
15371 | 45 |
unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F) { |
15368 | 46 |
for i in 0..count { |
47 |
unsafe { |
|
15369 | 48 |
f(($(&mut *(*slices.get_unchecked($n) as *mut $t).add(i)),+,)); |
15368 | 49 |
} |
50 |
} |
|
51 |
} |
|
15354 | 52 |
} |
53 |
} |
|
15305 | 54 |
} |
55 |
||
15369 | 56 |
type_tuple_impl!(0: A); |
57 |
type_tuple_impl!(0: A, 1: B); |
|
58 |
type_tuple_impl!(0: A, 1: B, 2: C); |
|
59 |
type_tuple_impl!(0: A, 1: B, 2: C, 3: D); |
|
60 |
type_tuple_impl!(0: A, 1: B, 2: C, 3: D, 4: E); |
|
15368 | 61 |
|
15354 | 62 |
const BLOCK_SIZE: usize = 32768; |
63 |
||
64 |
struct DataBlock { |
|
65 |
max_elements: u16, |
|
66 |
elements_count: u16, |
|
67 |
data: Box<[u8; BLOCK_SIZE]>, |
|
15358 | 68 |
component_blocks: [Option<NonNull<u8>>; 64], |
15305 | 69 |
} |
70 |
||
15354 | 71 |
impl Unpin for DataBlock {} |
72 |
||
73 |
impl DataBlock { |
|
74 |
fn new(mask: u64, element_sizes: &[u16; 64]) -> Self { |
|
75 |
let total_size: u16 = element_sizes |
|
76 |
.iter() |
|
77 |
.enumerate() |
|
15358 | 78 |
.filter(|(i, _)| mask & (1 << *i as u64) != 0) |
15354 | 79 |
.map(|(_, size)| *size) |
80 |
.sum(); |
|
81 |
let max_elements = (BLOCK_SIZE / total_size as usize) as u16; |
|
82 |
||
83 |
let mut data: Box<[u8; BLOCK_SIZE]> = |
|
15357 | 84 |
Box::new(unsafe { MaybeUninit::uninit().assume_init() }); |
15354 | 85 |
let mut blocks = [None; 64]; |
86 |
let mut offset = 0; |
|
87 |
||
15372 | 88 |
for i in 0..element_sizes.len() { |
89 |
if mask & (1 << i as u64) != 0 { |
|
15354 | 90 |
blocks[i] = Some(NonNull::new(data[offset..].as_mut_ptr()).unwrap()); |
91 |
offset += element_sizes[i] as usize * max_elements as usize; |
|
92 |
} |
|
93 |
} |
|
15305 | 94 |
Self { |
15354 | 95 |
elements_count: 0, |
96 |
max_elements, |
|
97 |
data, |
|
15358 | 98 |
component_blocks: blocks, |
15305 | 99 |
} |
100 |
} |
|
101 |
||
15354 | 102 |
fn is_full(&self) -> bool { |
103 |
self.elements_count == self.max_elements |
|
104 |
} |
|
15305 | 105 |
} |
106 |
||
15354 | 107 |
#[derive(Clone, Copy, Debug, Default)] |
108 |
pub struct LookupEntry { |
|
109 |
index: Option<NonZeroU16>, |
|
110 |
block_index: u16, |
|
15305 | 111 |
} |
112 |
||
113 |
pub struct GearDataManager { |
|
114 |
types: Vec<TypeId>, |
|
15354 | 115 |
blocks: Vec<DataBlock>, |
116 |
block_masks: Vec<u64>, |
|
117 |
element_sizes: Box<[u16; 64]>, |
|
118 |
lookup: Box<[LookupEntry]>, |
|
15305 | 119 |
} |
120 |
||
121 |
impl GearDataManager { |
|
122 |
pub fn new() -> Self { |
|
123 |
Self { |
|
124 |
types: vec![], |
|
15354 | 125 |
blocks: vec![], |
126 |
block_masks: vec![], |
|
127 |
element_sizes: Box::new([0; 64]), |
|
128 |
lookup: vec![LookupEntry::default(); u16::max_value() as usize].into_boxed_slice(), |
|
129 |
} |
|
130 |
} |
|
131 |
||
132 |
#[inline] |
|
133 |
fn get_type_index<T: 'static>(&self) -> Option<usize> { |
|
134 |
let type_id = TypeId::of::<T>(); |
|
135 |
self.types.iter().position(|id| *id == type_id) |
|
136 |
} |
|
137 |
||
15372 | 138 |
fn move_between_blocks( |
139 |
&mut self, |
|
15373 | 140 |
src_block_index: u16, |
141 |
src_index: u16, |
|
142 |
dest_block_index: u16, |
|
15372 | 143 |
) -> u16 { |
15373 | 144 |
debug_assert!(src_block_index != dest_block_index); |
145 |
let src_mask = self.block_masks[src_block_index as usize]; |
|
146 |
let dest_mask = self.block_masks[dest_block_index as usize]; |
|
147 |
debug_assert!(src_mask & dest_mask == src_mask); |
|
15354 | 148 |
|
15373 | 149 |
let src_block = &self.blocks[src_block_index as usize]; |
150 |
let dest_block = &self.blocks[dest_block_index as usize]; |
|
151 |
debug_assert!(src_index < src_block.elements_count); |
|
152 |
debug_assert!(!dest_block.is_full()); |
|
15357 | 153 |
|
15373 | 154 |
let dest_index = dest_block.elements_count; |
15372 | 155 |
for i in 0..self.types.len() { |
15373 | 156 |
if src_mask & (1 << i as u64) != 0 { |
157 |
let size = self.element_sizes[i]; |
|
158 |
let src_ptr = src_block.component_blocks[i].unwrap().as_ptr(); |
|
159 |
let dest_ptr = dest_block.component_blocks[i].unwrap().as_ptr(); |
|
15357 | 160 |
unsafe { |
161 |
copy_nonoverlapping( |
|
15373 | 162 |
src_ptr.add((src_index * size) as usize), |
163 |
dest_ptr.add((dest_index * size) as usize), |
|
164 |
size as usize, |
|
15357 | 165 |
); |
15373 | 166 |
if src_index < src_block.elements_count - 1 { |
167 |
copy_nonoverlapping( |
|
168 |
src_ptr.add((size * (src_block.elements_count - 1)) as usize), |
|
169 |
src_ptr.add((size * src_index) as usize), |
|
170 |
size as usize, |
|
171 |
); |
|
172 |
} |
|
15357 | 173 |
} |
174 |
} |
|
15354 | 175 |
} |
15373 | 176 |
self.blocks[src_block_index as usize].elements_count -= 1; |
177 |
let dest_block = &mut self.blocks[dest_block_index as usize]; |
|
178 |
dest_block.elements_count += 1; |
|
179 |
dest_block.elements_count - 1 |
|
15354 | 180 |
} |
181 |
||
15372 | 182 |
fn add_to_block<T: Clone>(&mut self, block_index: u16, value: &T) -> u16 { |
15356 | 183 |
debug_assert!(self.block_masks[block_index as usize].count_ones() == 1); |
184 |
||
185 |
let block = &mut self.blocks[block_index as usize]; |
|
186 |
debug_assert!(block.elements_count < block.max_elements); |
|
187 |
||
188 |
unsafe { |
|
189 |
let slice = slice::from_raw_parts_mut( |
|
190 |
block.data.as_mut_ptr() as *mut T, |
|
191 |
block.max_elements as usize, |
|
192 |
); |
|
193 |
*slice.get_unchecked_mut(block.elements_count as usize) = value.clone(); |
|
194 |
}; |
|
195 |
block.elements_count += 1; |
|
15372 | 196 |
block.elements_count - 1 |
15354 | 197 |
} |
198 |
||
199 |
fn remove_from_block(&mut self, block_index: u16, index: u16) { |
|
15356 | 200 |
let block = &mut self.blocks[block_index as usize]; |
201 |
debug_assert!(index < block.elements_count); |
|
202 |
||
203 |
for (i, size) in self.element_sizes.iter().cloned().enumerate() { |
|
204 |
if index < block.elements_count - 1 { |
|
15358 | 205 |
if let Some(ptr) = block.component_blocks[i] { |
15356 | 206 |
unsafe { |
15357 | 207 |
copy_nonoverlapping( |
15356 | 208 |
ptr.as_ptr() |
209 |
.add((size * (block.elements_count - 1)) as usize), |
|
210 |
ptr.as_ptr().add((size * index) as usize), |
|
211 |
size as usize, |
|
212 |
); |
|
213 |
} |
|
214 |
} |
|
215 |
} |
|
216 |
} |
|
217 |
block.elements_count -= 1; |
|
15354 | 218 |
} |
219 |
||
220 |
#[inline] |
|
15358 | 221 |
fn ensure_block(&mut self, mask: u64) -> u16 { |
15354 | 222 |
if let Some(index) = self |
223 |
.block_masks |
|
224 |
.iter() |
|
225 |
.enumerate() |
|
226 |
.position(|(i, m)| *m == mask && !self.blocks[i].is_full()) |
|
227 |
{ |
|
228 |
index as u16 |
|
229 |
} else { |
|
230 |
self.blocks.push(DataBlock::new(mask, &self.element_sizes)); |
|
15358 | 231 |
self.block_masks.push(mask); |
15354 | 232 |
(self.blocks.len() - 1) as u16 |
233 |
} |
|
234 |
} |
|
235 |
||
236 |
pub fn add<T: Clone + 'static>(&mut self, gear_id: GearId, value: &T) { |
|
237 |
if let Some(type_index) = self.get_type_index::<T>() { |
|
15358 | 238 |
let type_bit = 1 << type_index as u64; |
15354 | 239 |
let entry = self.lookup[gear_id.get() as usize - 1]; |
240 |
||
241 |
if let Some(index) = entry.index { |
|
242 |
let mask = self.block_masks[entry.block_index as usize]; |
|
243 |
let new_mask = mask | type_bit; |
|
244 |
||
245 |
if new_mask != mask { |
|
15358 | 246 |
let dest_block_index = self.ensure_block(new_mask); |
15372 | 247 |
let dest_index = self.move_between_blocks( |
248 |
entry.block_index, |
|
249 |
index.get() - 1, |
|
250 |
dest_block_index, |
|
251 |
); |
|
252 |
self.lookup[gear_id.get() as usize - 1] = LookupEntry { |
|
253 |
index: unsafe { |
|
254 |
Some(NonZeroU16::new_unchecked(dest_index.saturating_add(1))) |
|
255 |
}, |
|
256 |
block_index: dest_block_index, |
|
257 |
} |
|
15354 | 258 |
} |
259 |
} else { |
|
15358 | 260 |
let dest_block_index = self.ensure_block(type_bit); |
15372 | 261 |
let index = self.add_to_block(dest_block_index, value); |
262 |
self.lookup[gear_id.get() as usize - 1] = LookupEntry { |
|
263 |
index: unsafe { Some(NonZeroU16::new_unchecked(index.saturating_add(1))) }, |
|
264 |
block_index: dest_block_index, |
|
265 |
} |
|
15354 | 266 |
} |
267 |
} else { |
|
268 |
panic!("Unregistered type") |
|
269 |
} |
|
270 |
} |
|
271 |
||
272 |
pub fn remove<T: 'static>(&mut self, gear_id: GearId) { |
|
273 |
if let Some(type_index) = self.get_type_index::<T>() { |
|
274 |
let entry = self.lookup[gear_id.get() as usize - 1]; |
|
275 |
if let Some(index) = entry.index { |
|
15373 | 276 |
let dest_mask = |
15358 | 277 |
self.block_masks[entry.block_index as usize] & !(1 << type_index as u64); |
15357 | 278 |
|
15373 | 279 |
if dest_mask == 0 { |
15357 | 280 |
self.remove_all(gear_id) |
281 |
} else { |
|
15373 | 282 |
let dest_block_index = self.ensure_block(dest_mask); |
283 |
self.move_between_blocks(entry.block_index, index.get() - 1, dest_block_index); |
|
15357 | 284 |
} |
15354 | 285 |
} |
15357 | 286 |
} else { |
287 |
panic!("Unregistered type") |
|
288 |
} |
|
289 |
} |
|
290 |
||
291 |
pub fn remove_all(&mut self, gear_id: GearId) { |
|
292 |
let entry = self.lookup[gear_id.get() as usize - 1]; |
|
293 |
if let Some(index) = entry.index { |
|
294 |
self.remove_from_block(entry.block_index, index.get() - 1); |
|
15305 | 295 |
} |
15372 | 296 |
self.lookup[gear_id.get() as usize - 1] = LookupEntry { |
297 |
index: None, |
|
298 |
block_index: 0, |
|
299 |
} |
|
15305 | 300 |
} |
301 |
||
302 |
pub fn register<T: 'static>(&mut self) { |
|
15356 | 303 |
debug_assert!(!std::mem::needs_drop::<T>()); |
304 |
debug_assert!(self.types.len() <= 64); |
|
305 |
debug_assert!(size_of::<T>() <= u16::max_value() as usize); |
|
15354 | 306 |
|
15305 | 307 |
let id = TypeId::of::<T>(); |
308 |
if !self.types.contains(&id) { |
|
15354 | 309 |
self.element_sizes[self.types.len()] = size_of::<T>() as u16; |
15305 | 310 |
self.types.push(id); |
311 |
} |
|
312 |
} |
|
313 |
||
15367
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
314 |
pub fn iter<T: TypeTuple + 'static, F: FnMut(T)>(&self, mut f: F) { |
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
315 |
let mut arg_types = Vec::with_capacity(64); |
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
316 |
T::get_types(&mut arg_types); |
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
317 |
|
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
318 |
let mut type_indices = vec![-1i8; arg_types.len()]; |
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
319 |
let mut selector = 0u64; |
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
320 |
|
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
321 |
for (arg_index, type_id) in arg_types.iter().enumerate() { |
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
322 |
match self.types.iter().position(|t| t == type_id) { |
15373 | 323 |
Some(i) if selector & (1 << i as u64) != 0 => panic!("Duplicate type"), |
15367
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
324 |
Some(i) => { |
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
325 |
type_indices[arg_index] = i as i8; |
15372 | 326 |
selector |= 1 << i as u64; |
15368 | 327 |
} |
328 |
None => panic!("Unregistered type"), |
|
15305 | 329 |
} |
330 |
} |
|
15367
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
331 |
let mut slices = vec![null_mut(); arg_types.len()]; |
15358 | 332 |
|
15354 | 333 |
for (block_index, mask) in self.block_masks.iter().enumerate() { |
334 |
if mask & selector == selector { |
|
335 |
let block = &self.blocks[block_index]; |
|
15372 | 336 |
block.elements_count; |
15367
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
337 |
for (arg_index, type_index) in type_indices.iter().cloned().enumerate() { |
15368 | 338 |
slices[arg_index as usize] = block.component_blocks[type_index as usize] |
339 |
.unwrap() |
|
340 |
.as_ptr() |
|
15354 | 341 |
} |
15358 | 342 |
|
343 |
unsafe { |
|
344 |
T::iter(&slices[..], block.elements_count as usize, |x| f(x)); |
|
345 |
} |
|
15305 | 346 |
} |
347 |
} |
|
348 |
} |
|
349 |
} |
|
15354 | 350 |
|
351 |
#[cfg(test)] |
|
352 |
mod test { |
|
15358 | 353 |
use super::{super::common::GearId, GearDataManager}; |
15354 | 354 |
|
15358 | 355 |
#[derive(Clone)] |
15354 | 356 |
struct Datum { |
357 |
value: u32, |
|
358 |
} |
|
359 |
||
15371 | 360 |
#[derive(Clone)] |
361 |
struct Tag { |
|
362 |
nothing: u8, |
|
363 |
} |
|
364 |
||
15354 | 365 |
#[test] |
15358 | 366 |
fn single_component_iteration() { |
15354 | 367 |
let mut manager = GearDataManager::new(); |
368 |
manager.register::<Datum>(); |
|
15358 | 369 |
for i in 1..=5 { |
370 |
manager.add(GearId::new(i as u16).unwrap(), &Datum { value: i }); |
|
371 |
} |
|
372 |
||
373 |
let mut sum = 0; |
|
374 |
manager.iter(|(d,): (&Datum,)| sum += d.value); |
|
15368 | 375 |
assert_eq!(sum, 15); |
15358 | 376 |
|
15368 | 377 |
manager.iter(|(d,): (&mut Datum,)| d.value += 1); |
378 |
manager.iter(|(d,): (&Datum,)| sum += d.value); |
|
379 |
assert_eq!(sum, 35); |
|
15354 | 380 |
} |
15371 | 381 |
|
382 |
#[test] |
|
383 |
fn multiple_component_iteration() { |
|
384 |
let mut manager = GearDataManager::new(); |
|
385 |
manager.register::<Datum>(); |
|
386 |
manager.register::<Tag>(); |
|
387 |
for i in 1..=10 { |
|
388 |
let gear_id = GearId::new(i as u16).unwrap(); |
|
389 |
manager.add(gear_id, &Datum { value: i }); |
|
390 |
if i & 1 == 0 { |
|
391 |
manager.add(gear_id, &Tag { nothing: 0 }); |
|
392 |
} |
|
393 |
} |
|
394 |
||
395 |
let mut sum1 = 0; |
|
396 |
let mut sum2 = 0; |
|
397 |
manager.iter(|(d, _): (&Datum, &Tag)| sum1 += d.value); |
|
398 |
manager.iter(|(_, d): (&Tag, &Datum)| sum2 += d.value); |
|
399 |
assert_eq!(sum1, 30); |
|
400 |
assert_eq!(sum2, sum1); |
|
401 |
} |
|
15354 | 402 |
} |