1 use super::common::GearId; |
1 use super::common::GearId; |
2 use std::{ |
2 use std::{ |
3 any::TypeId, |
3 any::TypeId, |
|
4 fmt::{Debug, Error, Formatter}, |
|
5 io::Write, |
4 mem::{size_of, MaybeUninit}, |
6 mem::{size_of, MaybeUninit}, |
5 num::NonZeroU16, |
7 num::NonZeroU16, |
6 ptr::{copy_nonoverlapping, null_mut, NonNull}, |
8 ptr::{copy_nonoverlapping, null_mut, NonNull}, |
7 slice, |
9 slice, |
8 }; |
10 }; |
9 |
11 |
10 pub trait TypeTuple: Sized { |
12 pub trait TypeTuple: Sized { |
11 fn len() -> usize; |
|
12 fn get_types(types: &mut Vec<TypeId>); |
13 fn get_types(types: &mut Vec<TypeId>); |
13 unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F); |
14 unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F); |
14 } |
15 } |
15 |
16 |
16 macro_rules! type_tuple_impl { |
17 macro_rules! type_tuple_impl { |
17 ($($n: literal: $t: ident),+) => { |
18 ($($n: literal: $t: ident),+) => { |
18 impl<$($t: 'static),+> TypeTuple for ($(&$t),+,) { |
19 impl<$($t: 'static),+> TypeTuple for ($(&$t),+,) { |
19 fn len() -> usize { |
|
20 [$({TypeId::of::<$t>(); 1}),+].iter().sum() |
|
21 } |
|
22 |
|
23 fn get_types(types: &mut Vec<TypeId>) { |
20 fn get_types(types: &mut Vec<TypeId>) { |
24 $(types.push(TypeId::of::<$t>()));+ |
21 $(types.push(TypeId::of::<$t>()));+ |
25 } |
22 } |
26 |
23 |
27 unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F) { |
24 unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F) { |
32 } |
29 } |
33 } |
30 } |
34 } |
31 } |
35 |
32 |
36 impl<$($t: 'static),+> TypeTuple for ($(&mut $t),+,) { |
33 impl<$($t: 'static),+> TypeTuple for ($(&mut $t),+,) { |
37 fn len() -> usize { |
|
38 [$({TypeId::of::<$t>(); 1}),+].iter().sum() |
|
39 } |
|
40 |
|
41 fn get_types(types: &mut Vec<TypeId>) { |
34 fn get_types(types: &mut Vec<TypeId>) { |
42 $(types.push(TypeId::of::<$t>()));+ |
35 $(types.push(TypeId::of::<$t>()));+ |
43 } |
36 } |
44 |
37 |
45 unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F) { |
38 unsafe fn iter<F: FnMut(Self)>(slices: &[*mut u8], count: usize, mut f: F) { |
64 struct DataBlock { |
57 struct DataBlock { |
65 max_elements: u16, |
58 max_elements: u16, |
66 elements_count: u16, |
59 elements_count: u16, |
67 data: Box<[u8; BLOCK_SIZE]>, |
60 data: Box<[u8; BLOCK_SIZE]>, |
68 component_blocks: [Option<NonNull<u8>>; 64], |
61 component_blocks: [Option<NonNull<u8>>; 64], |
|
62 element_sizes: Box<[u16]>, |
69 } |
63 } |
70 |
64 |
71 impl Unpin for DataBlock {} |
65 impl Unpin for DataBlock {} |
72 |
66 |
|
67 impl Debug for DataBlock { |
|
68 fn fmt(&self, f: &mut Formatter) -> Result<(), Error> { |
|
69 write!( |
|
70 f, |
|
71 "Block ({}/{}) {{\n", |
|
72 self.elements_count, self.max_elements |
|
73 )?; |
|
74 write!(f, "\tIDs: [")?; |
|
75 let id_slice = unsafe { |
|
76 slice::from_raw_parts( |
|
77 self.data.as_ptr() as *const GearId, |
|
78 self.elements_count as usize, |
|
79 ) |
|
80 }; |
|
81 for gear_id in id_slice { |
|
82 write!(f, "{}, ", gear_id)?; |
|
83 } |
|
84 write!(f, "]\n")?; |
|
85 for type_index in 0..self.element_sizes.len() { |
|
86 if let Some(ptr) = self.component_blocks[type_index] { |
|
87 write!(f, "\tC{}: [", type_index)?; |
|
88 let slice = unsafe { |
|
89 slice::from_raw_parts( |
|
90 ptr.as_ptr(), |
|
91 (self.elements_count * self.element_sizes[type_index]) as usize, |
|
92 ) |
|
93 }; |
|
94 for byte in slice { |
|
95 write!(f, "{}, ", byte)?; |
|
96 } |
|
97 write!(f, "]\n")?; |
|
98 } |
|
99 } |
|
100 write!(f, "}}\n") |
|
101 } |
|
102 } |
|
103 |
73 impl DataBlock { |
104 impl DataBlock { |
74 fn new(mask: u64, element_sizes: &[u16; 64]) -> Self { |
105 fn new(mask: u64, element_sizes: &[u16]) -> Self { |
75 let total_size: u16 = element_sizes |
106 let total_size: u16 = element_sizes |
76 .iter() |
107 .iter() |
77 .enumerate() |
108 .enumerate() |
78 .filter(|(i, _)| mask & (1 << *i as u64) != 0) |
109 .filter(|(i, _)| mask & (1 << *i as u64) != 0) |
79 .map(|(_, size)| *size) |
110 .map(|(_, size)| *size) |
80 .sum(); |
111 .sum(); |
81 let max_elements = (BLOCK_SIZE / total_size as usize) as u16; |
112 let max_elements = (BLOCK_SIZE / (total_size as usize + size_of::<GearId>())) as u16; |
82 |
113 |
83 let mut data: Box<[u8; BLOCK_SIZE]> = |
114 let mut data: Box<[u8; BLOCK_SIZE]> = |
84 Box::new(unsafe { MaybeUninit::uninit().assume_init() }); |
115 Box::new(unsafe { MaybeUninit::uninit().assume_init() }); |
85 let mut blocks = [None; 64]; |
116 let mut blocks = [None; 64]; |
86 let mut offset = 0; |
117 let mut offset = size_of::<GearId>() * max_elements as usize; |
87 |
118 |
88 for i in 0..element_sizes.len() { |
119 for i in 0..element_sizes.len() { |
89 if mask & (1 << i as u64) != 0 { |
120 if mask & (1 << i as u64) != 0 { |
90 blocks[i] = Some(NonNull::new(data[offset..].as_mut_ptr()).unwrap()); |
121 blocks[i] = Some(NonNull::new(data[offset..].as_mut_ptr()).unwrap()); |
91 offset += element_sizes[i] as usize * max_elements as usize; |
122 offset += element_sizes[i] as usize * max_elements as usize; |
94 Self { |
125 Self { |
95 elements_count: 0, |
126 elements_count: 0, |
96 max_elements, |
127 max_elements, |
97 data, |
128 data, |
98 component_blocks: blocks, |
129 component_blocks: blocks, |
|
130 element_sizes: Box::from(element_sizes), |
|
131 } |
|
132 } |
|
133 |
|
134 fn gear_ids(&self) -> &[GearId] { |
|
135 unsafe { |
|
136 slice::from_raw_parts( |
|
137 self.data.as_ptr() as *const GearId, |
|
138 self.max_elements as usize, |
|
139 ) |
|
140 } |
|
141 } |
|
142 |
|
143 fn gear_ids_mut(&mut self) -> &mut [GearId] { |
|
144 unsafe { |
|
145 slice::from_raw_parts_mut( |
|
146 self.data.as_mut_ptr() as *mut GearId, |
|
147 self.max_elements as usize, |
|
148 ) |
99 } |
149 } |
100 } |
150 } |
101 |
151 |
102 fn is_full(&self) -> bool { |
152 fn is_full(&self) -> bool { |
103 self.elements_count == self.max_elements |
153 self.elements_count == self.max_elements |
106 |
156 |
107 #[derive(Clone, Copy, Debug, Default)] |
157 #[derive(Clone, Copy, Debug, Default)] |
108 pub struct LookupEntry { |
158 pub struct LookupEntry { |
109 index: Option<NonZeroU16>, |
159 index: Option<NonZeroU16>, |
110 block_index: u16, |
160 block_index: u16, |
|
161 } |
|
162 |
|
163 impl LookupEntry { |
|
164 fn new(block_index: u16, index: u16) -> Self { |
|
165 Self { |
|
166 index: unsafe { Some(NonZeroU16::new_unchecked(index + 1)) }, |
|
167 block_index, |
|
168 } |
|
169 } |
111 } |
170 } |
112 |
171 |
113 pub struct GearDataManager { |
172 pub struct GearDataManager { |
114 types: Vec<TypeId>, |
173 types: Vec<TypeId>, |
115 blocks: Vec<DataBlock>, |
174 blocks: Vec<DataBlock>, |
133 fn get_type_index<T: 'static>(&self) -> Option<usize> { |
192 fn get_type_index<T: 'static>(&self) -> Option<usize> { |
134 let type_id = TypeId::of::<T>(); |
193 let type_id = TypeId::of::<T>(); |
135 self.types.iter().position(|id| *id == type_id) |
194 self.types.iter().position(|id| *id == type_id) |
136 } |
195 } |
137 |
196 |
138 fn move_between_blocks( |
197 fn move_between_blocks(&mut self, src_block_index: u16, src_index: u16, dest_block_index: u16) { |
139 &mut self, |
|
140 src_block_index: u16, |
|
141 src_index: u16, |
|
142 dest_block_index: u16, |
|
143 ) -> u16 { |
|
144 debug_assert!(src_block_index != dest_block_index); |
198 debug_assert!(src_block_index != dest_block_index); |
145 let src_mask = self.block_masks[src_block_index as usize]; |
199 let src_mask = self.block_masks[src_block_index as usize]; |
146 let dest_mask = self.block_masks[dest_block_index as usize]; |
200 let dest_mask = self.block_masks[dest_block_index as usize]; |
147 debug_assert!(src_mask & dest_mask == src_mask); |
201 debug_assert!(src_mask & dest_mask == src_mask); |
148 |
202 |
171 ); |
225 ); |
172 } |
226 } |
173 } |
227 } |
174 } |
228 } |
175 } |
229 } |
176 self.blocks[src_block_index as usize].elements_count -= 1; |
230 |
|
231 let src_block = &mut self.blocks[src_block_index as usize]; |
|
232 let gear_id = src_block.gear_ids()[src_index as usize]; |
|
233 |
|
234 if src_index < src_block.elements_count - 1 { |
|
235 let relocated_index = src_block.elements_count as usize - 1; |
|
236 let gear_ids = src_block.gear_ids_mut(); |
|
237 let relocated_id = gear_ids[relocated_index]; |
|
238 |
|
239 gear_ids[src_index as usize] = relocated_id; |
|
240 self.lookup[relocated_id.get() as usize - 1] = |
|
241 LookupEntry::new(src_block_index, src_index); |
|
242 } |
|
243 src_block.elements_count -= 1; |
|
244 |
177 let dest_block = &mut self.blocks[dest_block_index as usize]; |
245 let dest_block = &mut self.blocks[dest_block_index as usize]; |
|
246 let dest_index = dest_block.elements_count; |
|
247 |
|
248 dest_block.gear_ids_mut()[dest_index as usize] = gear_id; |
|
249 self.lookup[gear_id.get() as usize - 1] = LookupEntry::new(dest_block_index, dest_index); |
178 dest_block.elements_count += 1; |
250 dest_block.elements_count += 1; |
179 dest_block.elements_count - 1 |
251 } |
180 } |
252 |
181 |
253 fn add_to_block<T: Clone>(&mut self, gear_id: GearId, block_index: u16, value: &T) { |
182 fn add_to_block<T: Clone>(&mut self, block_index: u16, value: &T) -> u16 { |
|
183 debug_assert!(self.block_masks[block_index as usize].count_ones() == 1); |
254 debug_assert!(self.block_masks[block_index as usize].count_ones() == 1); |
184 |
255 |
185 let block = &mut self.blocks[block_index as usize]; |
256 let block = &mut self.blocks[block_index as usize]; |
186 debug_assert!(block.elements_count < block.max_elements); |
257 debug_assert!(block.elements_count < block.max_elements); |
187 |
258 |
188 unsafe { |
259 unsafe { |
189 let slice = slice::from_raw_parts_mut( |
260 let slice = slice::from_raw_parts_mut( |
190 block.data.as_mut_ptr() as *mut T, |
261 block.component_blocks[0].unwrap().as_ptr() as *mut T, |
191 block.max_elements as usize, |
262 block.max_elements as usize, |
192 ); |
263 ); |
193 *slice.get_unchecked_mut(block.elements_count as usize) = value.clone(); |
264 *slice.get_unchecked_mut(block.elements_count as usize) = value.clone(); |
194 }; |
265 }; |
|
266 |
|
267 let index = block.elements_count; |
|
268 self.lookup[gear_id.get() as usize - 1] = LookupEntry::new(block_index, index); |
|
269 block.gear_ids_mut()[index as usize] = gear_id; |
195 block.elements_count += 1; |
270 block.elements_count += 1; |
196 block.elements_count - 1 |
|
197 } |
271 } |
198 |
272 |
199 fn remove_from_block(&mut self, block_index: u16, index: u16) { |
273 fn remove_from_block(&mut self, block_index: u16, index: u16) { |
200 let block = &mut self.blocks[block_index as usize]; |
274 let block = &mut self.blocks[block_index as usize]; |
201 debug_assert!(index < block.elements_count); |
275 debug_assert!(index < block.elements_count); |
212 ); |
286 ); |
213 } |
287 } |
214 } |
288 } |
215 } |
289 } |
216 } |
290 } |
|
291 |
|
292 self.lookup[block.gear_ids()[index as usize].get() as usize - 1] = LookupEntry::default(); |
|
293 if index < block.elements_count - 1 { |
|
294 let relocated_index = block.elements_count as usize - 1; |
|
295 let gear_ids = block.gear_ids_mut(); |
|
296 |
|
297 gear_ids[index as usize] = gear_ids[relocated_index]; |
|
298 self.lookup[gear_ids[relocated_index].get() as usize - 1] = |
|
299 LookupEntry::new(block_index, index); |
|
300 } |
217 block.elements_count -= 1; |
301 block.elements_count -= 1; |
218 } |
302 } |
219 |
303 |
220 #[inline] |
304 #[inline] |
221 fn ensure_block(&mut self, mask: u64) -> u16 { |
305 fn ensure_block(&mut self, mask: u64) -> u16 { |
242 let mask = self.block_masks[entry.block_index as usize]; |
329 let mask = self.block_masks[entry.block_index as usize]; |
243 let new_mask = mask | type_bit; |
330 let new_mask = mask | type_bit; |
244 |
331 |
245 if new_mask != mask { |
332 if new_mask != mask { |
246 let dest_block_index = self.ensure_block(new_mask); |
333 let dest_block_index = self.ensure_block(new_mask); |
247 let dest_index = self.move_between_blocks( |
334 self.move_between_blocks(entry.block_index, index.get() - 1, dest_block_index); |
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 } |
|
258 } |
335 } |
259 } else { |
336 } else { |
260 let dest_block_index = self.ensure_block(type_bit); |
337 let dest_block_index = self.ensure_block(type_bit); |
261 let index = self.add_to_block(dest_block_index, value); |
338 self.add_to_block(gear_id, 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 } |
|
266 } |
339 } |
267 } else { |
340 } else { |
268 panic!("Unregistered type") |
341 panic!("Unregistered type") |
269 } |
342 } |
270 } |
343 } |
290 |
363 |
291 pub fn remove_all(&mut self, gear_id: GearId) { |
364 pub fn remove_all(&mut self, gear_id: GearId) { |
292 let entry = self.lookup[gear_id.get() as usize - 1]; |
365 let entry = self.lookup[gear_id.get() as usize - 1]; |
293 if let Some(index) = entry.index { |
366 if let Some(index) = entry.index { |
294 self.remove_from_block(entry.block_index, index.get() - 1); |
367 self.remove_from_block(entry.block_index, index.get() - 1); |
295 } |
|
296 self.lookup[gear_id.get() as usize - 1] = LookupEntry { |
|
297 index: None, |
|
298 block_index: 0, |
|
299 } |
368 } |
300 } |
369 } |
301 |
370 |
302 pub fn register<T: 'static>(&mut self) { |
371 pub fn register<T: 'static>(&mut self) { |
303 debug_assert!(!std::mem::needs_drop::<T>()); |
372 debug_assert!(!std::mem::needs_drop::<T>()); |
385 manager.register::<Datum>(); |
454 manager.register::<Datum>(); |
386 manager.register::<Tag>(); |
455 manager.register::<Tag>(); |
387 for i in 1..=10 { |
456 for i in 1..=10 { |
388 let gear_id = GearId::new(i as u16).unwrap(); |
457 let gear_id = GearId::new(i as u16).unwrap(); |
389 manager.add(gear_id, &Datum { value: i }); |
458 manager.add(gear_id, &Datum { value: i }); |
|
459 } |
|
460 |
|
461 for i in 1..=10 { |
|
462 let gear_id = GearId::new(i as u16).unwrap(); |
390 if i & 1 == 0 { |
463 if i & 1 == 0 { |
391 manager.add(gear_id, &Tag { nothing: 0 }); |
464 manager.add(GearId::new(i as u16).unwrap(), &Tag { nothing: 0 }); |
392 } |
465 } |
393 } |
466 } |
394 |
467 |
395 let mut sum1 = 0; |
468 let mut sum = 0; |
396 let mut sum2 = 0; |
469 manager.iter(|(d,): (&Datum,)| sum += d.value); |
397 manager.iter(|(d, _): (&Datum, &Tag)| sum1 += d.value); |
470 assert_eq!(sum, 55); |
398 manager.iter(|(_, d): (&Tag, &Datum)| sum2 += d.value); |
471 |
399 assert_eq!(sum1, 30); |
472 let mut tag_sum1 = 0; |
400 assert_eq!(sum2, sum1); |
473 let mut tag_sum2 = 0; |
401 } |
474 manager.iter(|(d, _): (&Datum, &Tag)| tag_sum1 += d.value); |
402 } |
475 manager.iter(|(_, d): (&Tag, &Datum)| tag_sum2 += d.value); |
|
476 assert_eq!(tag_sum1, 30); |
|
477 assert_eq!(tag_sum2, tag_sum1); |
|
478 } |
|
479 } |