author | alfadur |
Wed, 28 Aug 2019 01:27:34 +0300 | |
changeset 15372 | 7a3ed957cee9 |
parent 15371 | 24a9afbf33c6 |
child 15373 | 5e2b9740086f |
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; |
12 |
fn get_types(dest: &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, |
|
140 |
from_block_index: u16, |
|
141 |
from_index: u16, |
|
142 |
to_block_index: u16, |
|
143 |
) -> u16 { |
|
15357 | 144 |
debug_assert!(from_block_index != to_block_index); |
15354 | 145 |
let source_mask = self.block_masks[from_block_index as usize]; |
146 |
let destination_mask = self.block_masks[to_block_index as usize]; |
|
147 |
debug_assert!(source_mask & destination_mask == source_mask); |
|
148 |
||
149 |
let source = &self.blocks[from_block_index as usize]; |
|
150 |
let destination = &self.blocks[to_block_index as usize]; |
|
15357 | 151 |
debug_assert!(from_index < source.elements_count); |
152 |
debug_assert!(!destination.is_full()); |
|
153 |
||
15372 | 154 |
let to_index = destination.elements_count; |
155 |
for i in 0..self.types.len() { |
|
156 |
if source_mask & 1 << i as u64 != 0 { |
|
15357 | 157 |
unsafe { |
158 |
copy_nonoverlapping( |
|
15372 | 159 |
source.component_blocks[i] |
160 |
.unwrap() |
|
161 |
.as_ptr() |
|
162 |
.add((from_index * self.element_sizes[i]) as usize), |
|
163 |
destination.component_blocks[i] |
|
164 |
.unwrap() |
|
165 |
.as_ptr() |
|
166 |
.add((to_index * self.element_sizes[i]) as usize), |
|
15357 | 167 |
self.element_sizes[i] as usize, |
168 |
); |
|
169 |
} |
|
170 |
} |
|
15354 | 171 |
} |
15357 | 172 |
self.blocks[from_block_index as usize].elements_count -= 1; |
15372 | 173 |
let destination = &mut self.blocks[to_block_index as usize]; |
174 |
destination.elements_count += 1; |
|
175 |
destination.elements_count - 1 |
|
15354 | 176 |
} |
177 |
||
15372 | 178 |
fn add_to_block<T: Clone>(&mut self, block_index: u16, value: &T) -> u16 { |
15356 | 179 |
debug_assert!(self.block_masks[block_index as usize].count_ones() == 1); |
180 |
||
181 |
let block = &mut self.blocks[block_index as usize]; |
|
182 |
debug_assert!(block.elements_count < block.max_elements); |
|
183 |
||
184 |
unsafe { |
|
185 |
let slice = slice::from_raw_parts_mut( |
|
186 |
block.data.as_mut_ptr() as *mut T, |
|
187 |
block.max_elements as usize, |
|
188 |
); |
|
189 |
*slice.get_unchecked_mut(block.elements_count as usize) = value.clone(); |
|
190 |
}; |
|
191 |
block.elements_count += 1; |
|
15372 | 192 |
block.elements_count - 1 |
15354 | 193 |
} |
194 |
||
195 |
fn remove_from_block(&mut self, block_index: u16, index: u16) { |
|
15356 | 196 |
let block = &mut self.blocks[block_index as usize]; |
197 |
debug_assert!(index < block.elements_count); |
|
198 |
||
199 |
for (i, size) in self.element_sizes.iter().cloned().enumerate() { |
|
200 |
if index < block.elements_count - 1 { |
|
15358 | 201 |
if let Some(ptr) = block.component_blocks[i] { |
15356 | 202 |
unsafe { |
15357 | 203 |
copy_nonoverlapping( |
15356 | 204 |
ptr.as_ptr() |
205 |
.add((size * (block.elements_count - 1)) as usize), |
|
206 |
ptr.as_ptr().add((size * index) as usize), |
|
207 |
size as usize, |
|
208 |
); |
|
209 |
} |
|
210 |
} |
|
211 |
} |
|
212 |
} |
|
213 |
block.elements_count -= 1; |
|
15354 | 214 |
} |
215 |
||
216 |
#[inline] |
|
15358 | 217 |
fn ensure_block(&mut self, mask: u64) -> u16 { |
15354 | 218 |
if let Some(index) = self |
219 |
.block_masks |
|
220 |
.iter() |
|
221 |
.enumerate() |
|
222 |
.position(|(i, m)| *m == mask && !self.blocks[i].is_full()) |
|
223 |
{ |
|
224 |
index as u16 |
|
225 |
} else { |
|
226 |
self.blocks.push(DataBlock::new(mask, &self.element_sizes)); |
|
15358 | 227 |
self.block_masks.push(mask); |
15354 | 228 |
(self.blocks.len() - 1) as u16 |
229 |
} |
|
230 |
} |
|
231 |
||
232 |
pub fn add<T: Clone + 'static>(&mut self, gear_id: GearId, value: &T) { |
|
233 |
if let Some(type_index) = self.get_type_index::<T>() { |
|
15358 | 234 |
let type_bit = 1 << type_index as u64; |
15354 | 235 |
let entry = self.lookup[gear_id.get() as usize - 1]; |
236 |
||
237 |
if let Some(index) = entry.index { |
|
238 |
let mask = self.block_masks[entry.block_index as usize]; |
|
239 |
let new_mask = mask | type_bit; |
|
240 |
||
241 |
if new_mask != mask { |
|
15358 | 242 |
let dest_block_index = self.ensure_block(new_mask); |
15372 | 243 |
let dest_index = self.move_between_blocks( |
244 |
entry.block_index, |
|
245 |
index.get() - 1, |
|
246 |
dest_block_index, |
|
247 |
); |
|
248 |
self.lookup[gear_id.get() as usize - 1] = LookupEntry { |
|
249 |
index: unsafe { |
|
250 |
Some(NonZeroU16::new_unchecked(dest_index.saturating_add(1))) |
|
251 |
}, |
|
252 |
block_index: dest_block_index, |
|
253 |
} |
|
15354 | 254 |
} |
255 |
} else { |
|
15358 | 256 |
let dest_block_index = self.ensure_block(type_bit); |
15372 | 257 |
let index = self.add_to_block(dest_block_index, value); |
258 |
self.lookup[gear_id.get() as usize - 1] = LookupEntry { |
|
259 |
index: unsafe { Some(NonZeroU16::new_unchecked(index.saturating_add(1))) }, |
|
260 |
block_index: dest_block_index, |
|
261 |
} |
|
15354 | 262 |
} |
263 |
} else { |
|
264 |
panic!("Unregistered type") |
|
265 |
} |
|
266 |
} |
|
267 |
||
268 |
pub fn remove<T: 'static>(&mut self, gear_id: GearId) { |
|
269 |
if let Some(type_index) = self.get_type_index::<T>() { |
|
270 |
let entry = self.lookup[gear_id.get() as usize - 1]; |
|
271 |
if let Some(index) = entry.index { |
|
15357 | 272 |
let destination_mask = |
15358 | 273 |
self.block_masks[entry.block_index as usize] & !(1 << type_index as u64); |
15357 | 274 |
|
275 |
if destination_mask == 0 { |
|
276 |
self.remove_all(gear_id) |
|
277 |
} else { |
|
15358 | 278 |
let destination_block_index = self.ensure_block(destination_mask); |
15357 | 279 |
self.move_between_blocks( |
280 |
entry.block_index, |
|
281 |
index.get() - 1, |
|
282 |
destination_block_index, |
|
283 |
); |
|
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) { |
d6b4586b271f
make sure component slice order corresponds to the type args
alfadur
parents:
15358
diff
changeset
|
323 |
Some(i) if selector & 1 << i as u64 != 0 => panic!("Duplicate type"), |
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 |
} |