my_ecs/ds/vec/chunk_any_vec.rs
1use super::{
2 super::{
3 raw::{
4 AsRawIter, FlatIter, FlatIterMut, FlatRawIter, ParFlatIter, ParFlatIterMut, RawIter,
5 },
6 types::{FnCloneRaw, FnDropRaw, TypeInfo},
7 },
8 AnyVec,
9};
10use crate::{ds::raw::AsFlatRawIter, util::prelude::*};
11use std::{
12 any::{self, TypeId},
13 cmp::{Ord, Ordering},
14 mem,
15 ptr::{self, NonNull},
16};
17
18/// A type-erased vector containing values of the same type.
19///
20/// This is very similar to [`AnyVec`] except memory management. As the name
21/// says, this vector is based on chunks. When you put values and the vector
22/// doesn't have sufficient capacity for them, the vector appends chunks and
23/// then put the values in the chunks. Therefore, the vector will be more
24/// efficient than `AnyVec` when frequent insertion/removal are expected.
25/// Note, however, that the iteration performance would be worse than `AnyVec`
26/// due to the split chunks in memory.
27#[derive(Debug, Clone)]
28pub struct ChunkAnyVec {
29 /// Chunks.
30 ///
31 /// The very first chunk plays a role of giving type information without
32 /// storing values. Use [`ChunkAnyVec::index_2d`] to convert an index into
33 /// chunk and item indices.
34 chunks: Vec<AnyVec>,
35
36 /// Maximum length and initial capacity of each chunk.
37 ///
38 /// The length is limited to be a power of two.
39 /// Zero length is considered as `usize::MAX + 1`.
40 chunk_cap: PowerOfTwo,
41
42 /// Number of items.
43 len: usize,
44
45 /// Offset to the first chunk that contains values.
46 ///
47 /// If the type is not ZST, the offset is 1 due to the first special chunk.
48 /// Otherwise, the offset is 0.
49 chunk_offset: usize,
50
51 /// Maximum capacity the vector can grow.
52 ///
53 /// If the type is not ZST, the maximum is `isize::MAX / self.item_size`.
54 /// Otherwise, the maximum is `usize::MAX`.
55 max_cap: usize,
56}
57
58impl ChunkAnyVec {
59 /// Creates a new empty vector.
60 ///
61 /// The vector will create and append chunks that can contain items as many
62 /// as the given chunk capacity. But the type is ZST, chunk capacity is
63 /// ignored.
64 ///
65 /// # Panics
66 ///
67 /// Panics if the given chunk capacity is not a power of two.
68 ///
69 /// # Examples
70 ///
71 /// ```
72 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
73 ///
74 /// let chunk_cap = 2;
75 /// let mut v = ChunkAnyVec::new(tinfo!(i32), chunk_cap);
76 /// assert_eq!(v.capacity(), 0);
77 ///
78 /// unsafe {
79 /// for _ in 0..chunk_cap {
80 /// v.push(0_i32);
81 /// assert_eq!(v.capacity(), chunk_cap);
82 /// }
83 /// v.push(0_i32);
84 /// assert_eq!(v.capacity(), chunk_cap * 2);
85 /// }
86 /// ```
87 pub fn new(tinfo: TypeInfo, chunk_cap: usize) -> Self {
88 let mut v = Self {
89 chunks: vec![AnyVec::new(tinfo)],
90 chunk_cap: PowerOfTwo::new(chunk_cap).unwrap(),
91 len: 0,
92 max_cap: 0,
93 chunk_offset: 1,
94 };
95
96 // If ZST, we won't allocate any memory for the vector.
97 // But, adjust capacity like `Vec`.
98 if v.is_zst() {
99 v.chunk_cap = PowerOfTwo::new(0).unwrap();
100 v.max_cap = usize::MAX;
101 v.chunk_offset = 0;
102 } else if v.default_chunk_capacity() > isize::MAX as usize {
103 // We need to restrict isize::MAX + 1.
104 panic!("`chunk_cap` must be less than isize::MAX");
105 } else {
106 // Same limitation with `Vec` or `AnyVec`.
107 v.max_cap = isize::MAX as usize / v.chunks[0].item_size();
108 }
109
110 v
111 }
112
113 /// Returns [`TypeInfo`] of the item.
114 ///
115 /// # Examples
116 ///
117 /// ```
118 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
119 ///
120 /// let v = ChunkAnyVec::new(tinfo!(i32), 2);
121 /// assert_eq!(v.type_info(), &tinfo!(i32));
122 /// ```
123 pub fn type_info(&self) -> &TypeInfo {
124 self.chunks[0].type_info()
125 }
126
127 /// Returns [`TypeId`] of the item.
128 ///
129 /// # Examples
130 ///
131 /// ```
132 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
133 ///
134 /// let v = ChunkAnyVec::new(tinfo!(i32), 2);
135 /// assert_eq!(v.type_id(), std::any::TypeId::of::<i32>());
136 /// ```
137 pub fn type_id(&self) -> TypeId {
138 self.chunks[0].type_id()
139 }
140
141 /// Returns name of the item based on [`type_name`](any::type_name).
142 ///
143 /// # Examples
144 ///
145 /// ```
146 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
147 ///
148 /// let v = ChunkAnyVec::new(tinfo!(i32), 2);
149 /// println!("{}", v.type_name());
150 /// ```
151 pub fn type_name(&self) -> &'static str {
152 self.chunks[0].type_name()
153 }
154
155 /// Returns size in bytes of the item.
156 ///
157 /// # Examples
158 ///
159 /// ```
160 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
161 ///
162 /// let v = ChunkAnyVec::new(tinfo!(i32), 2);
163 /// assert_eq!(v.item_size(), std::mem::size_of::<i32>());
164 /// ```
165 pub fn item_size(&self) -> usize {
166 self.chunks[0].item_size()
167 }
168
169 /// Returns whether the item is zero-sized type or not.
170 ///
171 /// # Examples
172 ///
173 /// ```
174 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
175 ///
176 /// let v = ChunkAnyVec::new(tinfo!(i32), 2);
177 /// assert!(!v.is_zst());
178 /// let v = ChunkAnyVec::new(tinfo!(()), 2);
179 /// assert!(v.is_zst());
180 /// ```
181 pub fn is_zst(&self) -> bool {
182 self.chunks[0].is_zst()
183 }
184
185 /// Returns alignment in bytes of the item.
186 ///
187 /// # Examples
188 ///
189 /// ```
190 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
191 ///
192 /// let v = ChunkAnyVec::new(tinfo!(i32), 2);
193 /// assert_eq!(v.align(), std::mem::align_of::<i32>());
194 /// ```
195 pub fn align(&self) -> usize {
196 self.chunks[0].align()
197 }
198
199 /// Returns raw drop function pointer.
200 pub fn fn_drop(&self) -> FnDropRaw {
201 self.chunks[0].fn_drop()
202 }
203
204 /// Returns raw clone function pointer.
205 pub fn fn_clone(&self) -> FnCloneRaw {
206 self.chunks[0].fn_clone()
207 }
208
209 /// Returns whether the item is [`Clone`] or not.
210 ///
211 /// # Examples
212 ///
213 /// ```
214 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
215 ///
216 /// let v = ChunkAnyVec::new(tinfo!(i32), 2);
217 /// assert!(v.is_clone());
218 ///
219 /// struct S;
220 /// let v = ChunkAnyVec::new(tinfo!(S), 2);
221 /// assert!(!v.is_clone());
222 /// ```
223 pub fn is_clone(&self) -> bool {
224 self.chunks[0].is_clone()
225 }
226
227 /// Returns whether the item is [`Send`] or not.
228 ///
229 /// # Examples
230 ///
231 /// ```
232 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
233 ///
234 /// let v = ChunkAnyVec::new(tinfo!(i32), 2);
235 /// assert!(v.is_send());
236 /// // let v = ChunkAnyVec::new(tinfo!(*mut u8), 2); // Disallowed for now.
237 /// ```
238 pub fn is_send(&self) -> bool {
239 self.chunks[0].is_send()
240 }
241
242 /// Returns whether the item is [`Sync`] or not.
243 ///
244 /// # Examples
245 ///
246 /// ```
247 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
248 ///
249 /// let v = ChunkAnyVec::new(tinfo!(i32), 2);
250 /// assert!(v.is_sync());
251 /// // let v = ChunkAnyVec::new(tinfo!(*mut u8), 2); // Disallowed for now.
252 /// ```
253 pub fn is_sync(&self) -> bool {
254 self.chunks[0].is_sync()
255 }
256
257 /// Returns true if the given [`TypeId`] is the same as item of the vector.
258 ///
259 /// # Examples
260 ///
261 /// ```
262 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
263 ///
264 /// let v = ChunkAnyVec::new(tinfo!(i32), 2);
265 /// assert!(v.is_type_of::<i32>());
266 /// ```
267 pub fn is_type_of<T: 'static>(&self) -> bool {
268 self.chunks[0].is_type_of::<T>()
269 }
270
271 /// Returns number of item.
272 ///
273 /// # Examples
274 ///
275 /// ```
276 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
277 ///
278 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
279 /// unsafe { v.push(0_i32) };
280 /// assert_eq!(v.len(), 1);
281 /// ```
282 pub const fn len(&self) -> usize {
283 self.len
284 }
285
286 /// Returns true if the vector is empty.
287 ///
288 /// # Examples
289 ///
290 /// ```
291 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
292 ///
293 /// let v = ChunkAnyVec::new(tinfo!(i32), 2);
294 /// assert!(v.is_empty());
295 /// ```
296 pub const fn is_empty(&self) -> bool {
297 self.len() == 0
298 }
299
300 /// Returns capacity in bytes of the vector.
301 ///
302 /// # Examples
303 ///
304 /// ```
305 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
306 ///
307 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
308 /// v.reserve(10);
309 /// assert!(v.capacity() >= 10);
310 /// ```
311 pub fn capacity(&self) -> usize {
312 if self.is_zst() {
313 self.max_cap
314 } else {
315 // Chunk always has the fixed capacity.
316 self.num_chunks() * self.default_chunk_capacity()
317 }
318 }
319
320 /// Returns default chunk capacity, which is a power of two.
321 ///
322 /// # Examples
323 ///
324 /// ```
325 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
326 ///
327 /// let chunk_cap = 2;
328 /// let mut v = ChunkAnyVec::new(tinfo!(i32), chunk_cap);
329 /// assert_eq!(v.default_chunk_capacity(), chunk_cap);
330 /// ```
331 pub const fn default_chunk_capacity(&self) -> usize {
332 self.chunk_cap.get()
333 }
334
335 /// Returns number of chunks.
336 ///
337 /// # Examples
338 ///
339 /// ```
340 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
341 ///
342 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
343 /// assert_eq!(v.num_chunks(), 0);
344 ///
345 /// unsafe {
346 /// v.push(0_i32);
347 /// v.push(1_i32);
348 /// assert_eq!(v.num_chunks(), 1);
349 /// v.push(2_i32);
350 /// assert_eq!(v.num_chunks(), 2);
351 /// }
352 /// ```
353 pub fn num_chunks(&self) -> usize {
354 self.chunks.len() - self.chunk_offset
355 }
356
357 /// Returns shared reference to a chunk at the given chunk index.
358 ///
359 /// # Examples
360 ///
361 /// ```
362 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
363 ///
364 /// let chunk_cap = 2;
365 /// let mut v = ChunkAnyVec::new(tinfo!(i32), chunk_cap);
366 ///
367 /// unsafe {
368 /// v.push(0_i32);
369 /// v.push(1_i32);
370 /// v.push(2_i32);
371 /// }
372 ///
373 /// let first_chunk = v.get_chunk(0).unwrap();
374 /// let first_slice = unsafe { first_chunk.as_slice::<i32>() };
375 /// assert_eq!(first_slice, &[0, 1]);
376 /// ```
377 pub fn get_chunk(&self, chunk_index: usize) -> Option<&AnyVec> {
378 self.chunks.get(chunk_index + self.chunk_offset)
379 }
380
381 /// Returns iterator visiting all items.
382 ///
383 /// # Panics
384 ///
385 /// Panics if the given type is not the same as the one vector contains.
386 ///
387 /// # Examples
388 ///
389 /// ```
390 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
391 ///
392 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
393 /// unsafe {
394 /// v.push(0_i32);
395 /// v.push(1_i32);
396 /// }
397 /// for x in v.iter_of::<i32>() {
398 /// println!("{x}");
399 /// }
400 /// ```
401 pub fn iter_of<T: 'static>(&self) -> FlatIter<'_, T> {
402 assert!(
403 self.is_type_of::<T>(),
404 "expected `{}`, but received `{}`",
405 self.type_name(),
406 any::type_name::<T>()
407 );
408
409 // Safety: Vector contains type `T` data in it.
410 unsafe { AsFlatRawIter::iter_of(self) }
411 }
412
413 /// Returns mutable iterator visiting all items.
414 ///
415 /// # Panics
416 ///
417 /// Panics if the given type is not the same as the vector contains.
418 ///
419 /// # Examples
420 ///
421 /// ```
422 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
423 ///
424 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
425 /// unsafe {
426 /// v.push(0_i32);
427 /// v.push(1_i32);
428 /// }
429 /// for x in v.iter_mut_of::<i32>() {
430 /// *x += 10;
431 /// }
432 /// ```
433 pub fn iter_mut_of<T: 'static>(&mut self) -> FlatIterMut<'_, T> {
434 assert!(
435 self.is_type_of::<T>(),
436 "expected `{}`, but received `{}`",
437 self.type_name(),
438 any::type_name::<T>()
439 );
440
441 // Safety: Vector contains type `T` data in it.
442 unsafe { AsFlatRawIter::iter_mut_of(self) }
443 }
444
445 /// Returns parallel iterator visiting all items.
446 ///
447 /// Parallel iterator implements [`rayon`]'s parallel iterator traits, so
448 /// that it can be split into multiple CPU cores then consumed at the same
449 /// time.
450 ///
451 /// # Panics
452 ///
453 /// Panics if the given type is not the same as the vector contains.
454 ///
455 /// # Examples
456 ///
457 /// ```
458 /// use my_ecs::prelude::*;
459 /// use my_ecs::ds::ChunkAnyVec;
460 ///
461 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
462 /// unsafe {
463 /// v.push(1_i32);
464 /// v.push(2_i32);
465 /// v.push(3_i32);
466 /// }
467 /// let sum: i32 = v.par_iter_of::<i32>().sum();
468 /// assert_eq!(sum, 6);
469 /// ```
470 pub fn par_iter_of<T: 'static>(&self) -> ParFlatIter<'_, T> {
471 assert!(
472 self.is_type_of::<T>(),
473 "expected `{}`, but received `{}`",
474 self.type_name(),
475 any::type_name::<T>()
476 );
477
478 // Safety: Vector contains type `T` data in it.
479 unsafe { AsFlatRawIter::par_iter_of(self) }
480 }
481
482 /// Returns mutable parallel iterator visiting all items.
483 ///
484 /// Parallel iterator implements [`rayon`]'s parallel iterator traits, so
485 /// that it can be split into multiple CPU cores then consumed at the same
486 /// time.
487 ///
488 /// # Panics
489 ///
490 /// Panics if the given type is not the same as the vector contains.
491 ///
492 /// # Examples
493 ///
494 /// ```
495 /// use my_ecs::prelude::*;
496 /// use my_ecs::ds::ChunkAnyVec;
497 ///
498 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
499 /// unsafe {
500 /// v.push(1_i32);
501 /// v.push(2_i32);
502 /// v.push(3_i32);
503 /// }
504 /// let sum: i32 = v.par_iter_mut_of::<i32>().map(|x| *x + 1).sum();
505 /// assert_eq!(sum, 9);
506 /// ```
507 pub fn par_iter_mut_of<T: 'static>(&mut self) -> ParFlatIterMut<'_, T> {
508 assert!(
509 self.is_type_of::<T>(),
510 "expected `{}`, but received `{}`",
511 self.type_name(),
512 any::type_name::<T>()
513 );
514
515 // Safety: Vector contains type `T` data in it.
516 unsafe { AsFlatRawIter::par_iter_mut_of(self) }
517 }
518
519 /// Reserves additional capacity more than or equal to the given value.
520 ///
521 /// If capacity of the vector is already sufficient, nothing takes place.
522 /// Otherwise, allocates chunks and append them to the vector so that the
523 /// capacity will be greater than or equal to `self.len() + additional`.
524 /// Unlike [`AnyVec::reserve`], this method appends chunks as little as
525 /// possible.
526 ///
527 /// # Panics
528 ///
529 /// Panics if total memory in bytes after calling this method will exceed
530 /// [`isize::MAX`].
531 ///
532 /// # Examples
533 ///
534 /// ```
535 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
536 ///
537 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
538 /// v.reserve(10);
539 /// assert!(v.capacity() >= 10);
540 /// ```
541 pub fn reserve(&mut self, additional: usize) {
542 self.reserve_exact(additional);
543 }
544
545 /// This method is the same as [`ChunkAnyVec::reserve`].
546 //
547 // For consistency.
548 pub fn reserve_exact(&mut self, additional: usize) {
549 let new_cap = self.len.saturating_add(additional);
550
551 if self.capacity() >= new_cap {
552 return;
553 }
554 if new_cap > self.max_capacity() {
555 panic!("can't allocate {new_cap} x {} bytes", self.item_size());
556 }
557
558 // Rounds up the target capacity to be a multiple of chunk length.
559 // This operation doesn't overflow because cap and len are restricted.
560 let new_cap =
561 (new_cap + self.default_chunk_capacity() - 1) & !(self.default_chunk_capacity() - 1);
562
563 // If the new_cap is clamped by this operation,
564 // the last chunk length will be the same as the others' - 1.
565 let new_cap = new_cap.min(self.max_capacity());
566
567 let mut remain = (new_cap - self.capacity()) as isize;
568 while remain > 0 {
569 self.chunks.push(self.create_chunk());
570 remain -= self.default_chunk_capacity() as isize; // Fixed cap
571 }
572 }
573
574 /// Shrinks capacity of the vector as much as possible.
575 ///
576 /// # Examples
577 ///
578 /// ```
579 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
580 ///
581 /// let chunk_cap = 4;
582 /// let mut v = ChunkAnyVec::new(tinfo!(i32), chunk_cap);
583 /// assert_eq!(v.capacity(), 0);
584 ///
585 /// unsafe { v.push(1_i32) };
586 /// assert_eq!(v.capacity(), chunk_cap);
587 ///
588 /// v.reserve(chunk_cap);
589 /// assert_eq!(v.capacity(), chunk_cap * 2);
590 ///
591 /// v.shrink_to_fit();
592 /// assert_eq!(v.capacity(), chunk_cap);
593 ///
594 /// v.pop_drop();
595 /// v.shrink_to_fit();
596 /// assert_eq!(v.capacity(), 0);
597 /// ```
598 pub fn shrink_to_fit(&mut self) {
599 if self.is_zst() {
600 return;
601 }
602
603 let redundant_cap = self.capacity() - self.len();
604 let redundant_chunks = redundant_cap / self.default_chunk_capacity();
605 self.chunks.truncate(self.chunks.len() - redundant_chunks);
606 }
607
608 /// Sets length of the vector to the given value without any additional
609 /// operations.
610 ///
611 /// # Safety
612 ///
613 /// - `new_len` must be less than or equal to `self.capacity()`.
614 /// - If `new_len` is greater than the previous length, caller must
615 /// initialize the extended range with proper values.
616 /// - If `new_len` is less than the previous length, caller must drop
617 /// abandoned values from the vector properly.
618 pub unsafe fn set_len(&mut self, new_len: usize) {
619 debug_assert!(new_len <= self.capacity());
620
621 self.len = new_len;
622 }
623
624 /// Copies data as much as `self.item_size()` from `src` address to the end
625 /// of the vector.
626 ///
627 /// If the vector doesn't have sufficient capacity for the appended value,
628 /// then the vector increases its capacity first by calling
629 /// [`ChunkAnyVec::reserve`] which allocates memory more than just one value,
630 /// then does the copy.
631 ///
632 /// # Safety
633 ///
634 /// - `src` must point to a valid type that the vector contains.
635 /// - `src` must not be dropped after calling this method because it is
636 /// moved into the vector.
637 ///
638 /// # Examples
639 ///
640 /// ```
641 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
642 /// use std::ptr::NonNull;
643 ///
644 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
645 ///
646 /// let value = 0x01020304_i32;
647 /// unsafe {
648 /// let ptr = (&value as *const i32 as *const u8).cast_mut();
649 /// v.push_raw(NonNull::new(ptr).unwrap());
650 /// assert_eq!(v.pop(), Some(value));
651 /// }
652 /// ```
653 pub unsafe fn push_raw(&mut self, ptr: NonNull<u8>) {
654 self.reserve(1);
655
656 let (ci, _) = self.index_2d(self.len());
657
658 unsafe {
659 self.chunks[ci].push_raw(ptr);
660 // If ZST, new length can overflow.
661 let new_len = self.len().checked_add(1).unwrap();
662 self.set_len(new_len);
663 }
664 }
665
666 /// Writes a value to the end of the vector by calling the given function.
667 ///
668 /// If the vector doesn't have sufficient capacity for the appended value,
669 /// then the vector increases its capacity first by calling
670 /// [`ChunkAnyVec::reserve`] which allocates a chunk, then does the write
671 /// operation.
672 ///
673 /// # Safety
674 ///
675 /// - `write` must write a valid type that the vector contains.
676 ///
677 /// # Examples
678 ///
679 /// ```
680 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
681 /// use std::ptr::{self, NonNull};
682 ///
683 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
684 ///
685 /// let value = 0x01020304_i32;
686 /// unsafe {
687 /// v.push_with(|dst| {
688 /// ptr::write(dst as *mut i32, value);
689 /// });
690 /// assert_eq!(v.pop(), Some(value));
691 /// }
692 /// ```
693 pub unsafe fn push_with<F>(&mut self, write: F)
694 where
695 F: FnOnce(*mut u8),
696 {
697 self.reserve(1);
698
699 let (ci, _) = self.index_2d(self.len());
700
701 unsafe {
702 self.chunks[ci].push_with(write);
703 // If ZST, new length can overflow.
704 let new_len = self.len().checked_add(1).unwrap();
705 self.set_len(new_len);
706 }
707 }
708
709 /// Appends the given value to the end of the vector.
710 ///
711 /// # Safety
712 ///
713 /// - `value` must be the same type as the vector contains.
714 ///
715 /// # Examples
716 ///
717 /// ```
718 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
719 ///
720 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
721 /// unsafe {
722 /// v.push(0_i32);
723 /// assert_eq!(v.pop(), Some(0_i32));
724 /// }
725 /// ```
726 pub unsafe fn push<T: 'static>(&mut self, mut value: T) {
727 debug_assert!(
728 self.is_type_of::<T>(),
729 "expected `{}`, but received `{}`",
730 self.type_name(),
731 any::type_name::<T>()
732 );
733
734 unsafe {
735 let ptr = NonNull::new_unchecked(&mut value as *mut T as *mut u8);
736 self.push_raw(ptr);
737 }
738 mem::forget(value);
739 }
740
741 /// Removes the last item from the vector and writes it to the given
742 /// buffer, then returns `Some`.
743 ///
744 /// If removing is successful, caller becomes to own the item in the
745 /// buffer, so that caller must call `drop()` on it correctly.
746 /// Otherwise, returns `None` without change to the buffer.
747 ///
748 /// # Safety
749 ///
750 /// Undefined behavior if conditions below are not met.
751 /// - `buf` must have enough size to be copied an item.
752 /// - When `Some` is returned, `buf` must be correctly handled as an item.
753 /// For example, if an item should be dropped, caller must call drop() on
754 /// it.
755 /// - When `None` is returned, `buf` must be correctly handled as it was.
756 ///
757 /// # Examples
758 ///
759 /// ```
760 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
761 ///
762 /// let chunk_cap = 4;
763 /// let mut v = ChunkAnyVec::new(tinfo!(i32), chunk_cap);
764 /// unsafe { v.push(42_i32) };
765 /// assert_eq!(v.len(), 1);
766 ///
767 /// let mut buf = 0_i32;
768 /// let res = unsafe { v.pop_raw(&mut buf as *mut i32 as *mut u8) };
769 /// assert!(res.is_some());
770 /// assert!(v.is_empty());
771 /// assert_eq!(buf, 42);
772 /// ```
773 pub unsafe fn pop_raw(&mut self, buf: *mut u8) -> Option<()> {
774 if self.is_empty() {
775 return None;
776 }
777
778 // Safety:
779 // - The vector must not be empty: Ok.
780 // - After calling `reduce_len_then_get_last_chunk`, caller must remove
781 // an item from the returned chunk: Ok.
782 unsafe {
783 let last_chunk = self.reduce_len_then_get_last_chunk();
784 last_chunk.pop_raw(buf);
785 }
786 Some(())
787 }
788
789 /// Removes the last item from the vector.
790 ///
791 /// # Safety
792 ///
793 /// - `T` must be the same type as the vector contains.
794 ///
795 /// # Examples
796 ///
797 /// ```
798 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
799 ///
800 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
801 ///
802 /// unsafe {
803 /// v.push(0_i32);
804 /// let value = v.pop::<i32>().unwrap();
805 /// assert_eq!(value, 0_i32);
806 /// }
807 /// ```
808 pub unsafe fn pop<T: 'static>(&mut self) -> Option<T> {
809 if self.is_empty() {
810 return None;
811 }
812
813 // Safety:
814 // - The vector must not be empty: Ok.
815 // - After calling `reduce_len_then_get_last_chunk`, caller must remove
816 // an item from the returned chunk: Ok.
817 unsafe {
818 let last_chunk = self.reduce_len_then_get_last_chunk();
819 last_chunk.pop()
820 }
821 }
822
823 /// Removes the last item from the vector then drops it immediately.
824 ///
825 /// # Examples
826 ///
827 /// ```
828 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
829 ///
830 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
831 ///
832 /// unsafe {
833 /// v.push(0_i32);
834 /// assert_eq!(v.pop_drop(), Some(()));
835 /// }
836 /// ```
837 pub fn pop_drop(&mut self) -> Option<()> {
838 if self.is_empty() {
839 return None;
840 }
841
842 // Safety:
843 // - The vector must not be empty: Ok.
844 // - After calling `reduce_len_then_get_last_chunk`, caller must remove
845 // an item from the returned chunk: Ok.
846 let last_chunk = unsafe { self.reduce_len_then_get_last_chunk() };
847 last_chunk.pop_drop()
848 }
849
850 /// Removes the last item from the vector without calling drop function on
851 /// it.
852 ///
853 /// # Safety
854 ///
855 /// Rust safety doesn't include calling drop function. See
856 /// [`forget`](mem::forget) for more information. However, caller must
857 /// guarantee that not calling drop function is fine for the item.
858 ///
859 /// # Examples
860 ///
861 /// ```
862 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
863 ///
864 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
865 ///
866 /// unsafe {
867 /// v.push(0_i32);
868 /// assert_eq!(v.pop_forget(), Some(()));
869 /// }
870 /// ```
871 pub fn pop_forget(&mut self) -> Option<()> {
872 if self.is_empty() {
873 return None;
874 }
875
876 // Safety:
877 // - The vector must not be empty: Ok.
878 // - After calling `reduce_len_then_get_last_chunk`, caller must remove
879 // an item from the returned chunk: Ok.
880 let last_chunk = unsafe { self.reduce_len_then_get_last_chunk() };
881 last_chunk.pop_forget()
882 }
883
884 /// Reduces length by 1 and returns mutable reference to the last chunk.
885 ///
886 /// # Safety
887 ///
888 /// - The vector must not be empty.
889 /// - Caller must remove an item from the returned chunk.
890 unsafe fn reduce_len_then_get_last_chunk(&mut self) -> &mut AnyVec {
891 // Safety: Decreasing is safe.
892 unsafe { self.set_len(self.len() - 1) };
893
894 let (ci, _) = self.index_2d(self.len());
895
896 // Safety: `r` is valid.
897 unsafe { self.chunks.get_unchecked_mut(ci) }
898 }
899
900 /// Removes an item at the given index from the vector and writes it to the
901 /// given buffer.
902 ///
903 /// Therefore, the item is actually moved from the vector to the given
904 /// buffer. So caller must take care of calling drop on it.
905 ///
906 /// # Panics
907 ///
908 /// Panics if the given index is out of bounds.
909 ///
910 /// # Safety
911 ///
912 /// Undefined behavior if conditions below are not met.
913 /// - `buf` must have enough size to be copied an item.
914 /// - When `Some` is returned, `buf` must be correctly handled as an item.
915 /// For example, if an item should be dropped, caller must call drop() on
916 /// it.
917 /// - When `None` is returned, `buf` must be correctly handled as it was.
918 ///
919 /// # Examples
920 ///
921 /// ```
922 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
923 ///
924 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
925 /// unsafe {
926 /// v.push(0_i32);
927 /// v.push(1_i32);
928 /// v.push(2_i32);
929 /// }
930 /// assert_eq!(v.len(), 3);
931 ///
932 /// let mut buf = 3_i32;
933 /// unsafe { v.swap_remove_raw(0, &mut buf as *mut i32 as *mut u8) };
934 /// assert_eq!(buf, 0);
935 ///
936 /// unsafe {
937 /// assert_eq!(v.pop::<i32>(), Some(1));
938 /// assert_eq!(v.pop::<i32>(), Some(2));
939 /// }
940 /// ```
941 pub unsafe fn swap_remove_raw(&mut self, index: usize, buf: *mut u8) {
942 // If index is out of bounds or len() - 1 overflows, swap() panics.
943 self.swap(index, self.len().wrapping_sub(1));
944 unsafe { self.pop_raw(buf) };
945 }
946
947 /// Removes an item at the given index from the vector and returns it.
948 ///
949 /// Then the last item of the vector is moved to the vacant slot.
950 ///
951 /// # Panics
952 ///
953 /// Panics if the given index is out of bounds.
954 ///
955 /// # Safety
956 ///
957 /// - `T` must be the same type as the vector contains.
958 ///
959 /// # Examples
960 ///
961 /// ```
962 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
963 ///
964 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
965 ///
966 /// unsafe {
967 /// v.push(0_i32);
968 /// v.push(1_i32);
969 /// v.push(2_i32);
970 /// assert_eq!(v.swap_remove::<i32>(0), 0);
971 /// assert_eq!(v.swap_remove::<i32>(0), 2);
972 /// assert_eq!(v.swap_remove::<i32>(0), 1);
973 /// }
974 /// ```
975 pub unsafe fn swap_remove<T: 'static>(&mut self, index: usize) -> T {
976 // If index is out of bounds or len() - 1 overflows, swap() panics.
977 self.swap(index, self.len().wrapping_sub(1));
978 unsafe { self.pop().unwrap() }
979 }
980
981 /// Removes an item at the given index from the vector and drops it
982 /// immediately.
983 ///
984 /// Then the last item of the vector is moved to the vacant slot.
985 ///
986 /// # Panics
987 ///
988 /// Panics if the given index is out of bounds.
989 ///
990 /// # Examples
991 ///
992 /// ```
993 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
994 ///
995 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
996 ///
997 /// unsafe {
998 /// v.push(0_i32);
999 /// v.swap_remove_drop(0);
1000 /// assert!(v.is_empty());
1001 /// }
1002 /// ```
1003 pub fn swap_remove_drop(&mut self, index: usize) {
1004 // If index is out of bounds or len() - 1 overflows, swap() panics.
1005 self.swap(index, self.len().wrapping_sub(1));
1006 self.pop_drop();
1007 }
1008
1009 /// Removes an item at the given index from the vector without calling drop
1010 /// function on it.
1011 ///
1012 /// Then the last item of the vector is moved to the vacant slot.
1013 ///
1014 /// # Panics
1015 ///
1016 /// Panics if given index is out of bounds.
1017 ///
1018 /// # Safety
1019 ///
1020 /// Rust safety doesn't include calling drop function. See
1021 /// [`forget`](mem::forget) for more information. However, caller must
1022 /// guarantee that not calling drop function is fine for the item.
1023 ///
1024 /// # Examples
1025 ///
1026 /// ```
1027 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
1028 ///
1029 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
1030 ///
1031 /// unsafe {
1032 /// v.push(0_i32);
1033 /// v.swap_remove_forget(0);
1034 /// assert!(v.is_empty());
1035 /// }
1036 /// ```
1037 pub fn swap_remove_forget(&mut self, index: usize) {
1038 // If index is out of bounds or len() - 1 overflows, swap() panics.
1039 self.swap(index, self.len().wrapping_sub(1));
1040 self.pop_forget();
1041 }
1042
1043 /// Replaces an item with another item in the vector.
1044 ///
1045 /// # Panics
1046 ///
1047 /// Panics if any given indices is out of bounds.
1048 ///
1049 /// # Examples
1050 ///
1051 /// ```
1052 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
1053 ///
1054 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
1055 ///
1056 /// unsafe {
1057 /// v.push(0_i32);
1058 /// v.push(1_i32);
1059 /// v.swap(0, 1);
1060 /// assert_eq!(v.pop(), Some(0));
1061 /// assert_eq!(v.pop(), Some(1));
1062 /// }
1063 /// ```
1064 pub fn swap(&mut self, index0: usize, index1: usize) {
1065 assert!(index0 < self.len(), "{index0} is out of bounds");
1066 assert!(index1 < self.len(), "{index1} is out of bounds");
1067
1068 unsafe {
1069 let (ci0, ii0) = self.index_2d(index0);
1070 let (ci1, ii1) = self.index_2d(index1);
1071 let ptr0 = self.chunks[ci0].get_ptr(ii0);
1072 let ptr1 = self.chunks[ci1].get_ptr(ii1);
1073 if ptr0 != ptr1 {
1074 ptr::swap_nonoverlapping(ptr0, ptr1, self.item_size());
1075 }
1076 }
1077 }
1078
1079 /// Returns a pointer to an item at the given index.
1080 ///
1081 /// # Examples
1082 ///
1083 /// ```
1084 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
1085 ///
1086 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
1087 ///
1088 /// let value = 0x01020304_i32;
1089 /// unsafe { v.push(value) };
1090 ///
1091 /// let ptr = v.get_raw(0).unwrap().cast::<i32>().as_ptr().cast_const();
1092 /// unsafe {
1093 /// assert_eq!(std::ptr::read(ptr), value);
1094 /// }
1095 /// ```
1096 pub fn get_raw(&self, index: usize) -> Option<NonNull<u8>> {
1097 if index < self.len() {
1098 unsafe { Some(self.get_raw_unchecked(index)) }
1099 } else {
1100 None
1101 }
1102 }
1103
1104 /// Returns a pointer to an item at the given index.
1105 ///
1106 /// # Safety
1107 ///
1108 /// - Index must be in bounds.
1109 ///
1110 /// # Examples
1111 ///
1112 /// ```
1113 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
1114 ///
1115 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
1116 ///
1117 /// let value = 0x01020304_i32;
1118 /// unsafe {
1119 /// v.push(value);
1120 /// let ptr = v.get_raw_unchecked(0)
1121 /// .cast::<i32>()
1122 /// .as_ptr()
1123 /// .cast_const();
1124 /// assert_eq!(std::ptr::read(ptr), value);
1125 /// }
1126 /// ```
1127 pub unsafe fn get_raw_unchecked(&self, index: usize) -> NonNull<u8> {
1128 let (ci, ii) = self.index_2d(index);
1129 unsafe { self.chunks[ci].get_raw_unchecked(ii) }
1130 }
1131
1132 /// Returns shared reference to an item at the given index.
1133 ///
1134 /// # Safety
1135 ///
1136 /// - `T` must be the same type as the vector contains.
1137 ///
1138 /// # Examples
1139 ///
1140 /// ```
1141 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
1142 ///
1143 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
1144 ///
1145 /// unsafe {
1146 /// v.push(0_i32);
1147 /// assert_eq!(v.get(0), Some(&0_i32));
1148 /// }
1149 /// ```
1150 pub unsafe fn get<T: 'static>(&self, index: usize) -> Option<&T> {
1151 if index < self.len() {
1152 let (ci, ii) = self.index_2d(index);
1153 // Type is checked here.
1154 unsafe { self.chunks[ci].get(ii) }
1155 } else {
1156 None
1157 }
1158 }
1159
1160 /// Returns mutable reference to an item at the given index.
1161 ///
1162 /// # Safety
1163 ///
1164 /// - `T` must be the same type as the vector contains.
1165 ///
1166 /// # Examples
1167 ///
1168 /// ```
1169 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
1170 ///
1171 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
1172 ///
1173 /// unsafe {
1174 /// v.push(0_i32);
1175 /// *v.get_mut(0).unwrap() = 1_i32;
1176 /// assert_eq!(v.get(0), Some(&1_i32));
1177 /// }
1178 /// ```
1179 pub unsafe fn get_mut<T: 'static>(&mut self, index: usize) -> Option<&mut T> {
1180 if index < self.len() {
1181 let (ci, ii) = self.index_2d(index);
1182 // Type is checked here.
1183 unsafe { self.chunks[ci].get_mut(ii) }
1184 } else {
1185 None
1186 }
1187 }
1188
1189 /// Resizes the vector to the given length.
1190 ///
1191 /// If the new length is greater than previous length of the vector, then
1192 /// the vector is extended with the given value. Otherwise, the vector is
1193 /// shrunk.
1194 ///
1195 /// # Panics
1196 ///
1197 /// Panics if `T` is not the same type as the vector contains.
1198 ///
1199 /// # Examples
1200 ///
1201 /// ```
1202 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
1203 ///
1204 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
1205 ///
1206 /// unsafe {
1207 /// v.resize(2, 0_i32);
1208 /// assert_eq!(v.pop(), Some(0_i32));
1209 /// assert_eq!(v.pop(), Some(0_i32));
1210 /// assert!(v.is_empty());
1211 /// }
1212 /// ```
1213 pub fn resize<T>(&mut self, new_len: usize, value: T)
1214 where
1215 T: Clone + 'static,
1216 {
1217 // Panic: `self.resize_with` panics if the given type `T` is incorrect.
1218 self.resize_with(new_len, || value.clone())
1219 }
1220
1221 /// Resizes the vector to the given length.
1222 ///
1223 /// If the new length is greater than previous length of the vector, then
1224 /// the vector is extended with clones of a value pointed by the given
1225 /// pointer. Otherwise, the vector is shrunk.
1226 ///
1227 /// # Panics
1228 ///
1229 /// Panics if vector item is not [`Clone`].
1230 ///
1231 /// # Safety
1232 ///
1233 /// - `val_ptr` must point to a valid type that the vector contains.
1234 ///
1235 /// # Examples
1236 ///
1237 /// ```
1238 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
1239 /// use std::ptr::NonNull;
1240 ///
1241 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
1242 ///
1243 /// let value = 0x01020304_i32;
1244 /// unsafe {
1245 /// let ptr = (&value as *const i32 as *const u8).cast_mut();
1246 /// v.resize_raw(2, NonNull::new(ptr).unwrap());
1247 /// assert_eq!(v.pop(), Some(value));
1248 /// assert_eq!(v.pop(), Some(value));
1249 /// assert!(v.is_empty());
1250 /// }
1251 /// ```
1252 pub unsafe fn resize_raw(&mut self, new_len: usize, val_ptr: NonNull<u8>) {
1253 assert!(self.is_clone(), "expected `Clone` type");
1254
1255 self._resize(new_len, |last_chunk, new_last_chunk_len| unsafe {
1256 last_chunk.resize_raw(new_last_chunk_len, val_ptr);
1257 });
1258 }
1259
1260 /// Resizes the vector to the given length.
1261 ///
1262 /// If the new length is greater than previous length of the vector, then
1263 /// the vector is extended with values the given function generates. In this
1264 /// case, generated values are appended in order. Otherwise, the vector is
1265 /// shrunk.
1266 ///
1267 /// # Panics
1268 ///
1269 /// Panics if `T` is not the same type as the vector contains.
1270 ///
1271 /// # Examples
1272 ///
1273 /// ```
1274 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
1275 ///
1276 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
1277 ///
1278 /// unsafe {
1279 /// v.resize_with(2, || 0_i32);
1280 /// assert_eq!(v.pop(), Some(0_i32));
1281 /// assert_eq!(v.pop(), Some(0_i32));
1282 /// assert!(v.is_empty());
1283 /// }
1284 /// ```
1285 pub fn resize_with<T, F>(&mut self, new_len: usize, mut f: F)
1286 where
1287 T: 'static,
1288 F: FnMut() -> T,
1289 {
1290 assert!(
1291 self.is_type_of::<T>(),
1292 "expected `{}`, but received `{}`",
1293 self.type_name(),
1294 any::type_name::<T>()
1295 );
1296
1297 // Safety: Closure must fill the chunk as much as the given length: Ok.
1298 unsafe {
1299 self._resize(new_len, move |last_chunk, new_last_chunk_len| {
1300 last_chunk.resize_with(new_last_chunk_len, &mut f)
1301 });
1302 }
1303 }
1304
1305 /// # Safety
1306 ///
1307 /// `fill_chunk` function must make the given chunk to be the given length.
1308 unsafe fn _resize<F>(&mut self, new_len: usize, mut fill_chunk: F)
1309 where
1310 F: FnMut(&mut AnyVec, usize), // Last chunk, New last chunk length
1311 {
1312 match new_len.cmp(&self.len()) {
1313 Ordering::Less => self.truncate(new_len),
1314 Ordering::Equal => {}
1315 Ordering::Greater => {
1316 let mut remain = new_len - self.len();
1317
1318 self.reserve(remain);
1319
1320 let last_index = self.len().saturating_sub(1);
1321 let (mut ci, _) = self.index_2d(last_index);
1322 let chunk_cap = self.default_chunk_capacity();
1323
1324 while remain > 0 {
1325 let last_chunk = &mut self.chunks[ci];
1326 let partial = remain.min(chunk_cap - last_chunk.len());
1327 let new_last_chunk_len = last_chunk.len() + partial;
1328
1329 fill_chunk(last_chunk, new_last_chunk_len);
1330 debug_assert_eq!(last_chunk.len(), new_last_chunk_len);
1331
1332 remain -= partial;
1333 ci += 1;
1334 }
1335
1336 unsafe { self.set_len(new_len) };
1337 }
1338 }
1339 }
1340
1341 /// Shrinks the vector to the given length, and drops abandoned items.
1342 ///
1343 /// If the given length is greater than or equal to the current length of
1344 /// the vector, nothing takes place.
1345 ///
1346 /// # Examples
1347 ///
1348 /// ```
1349 /// use my_ecs::{tinfo, ds::ChunkAnyVec};
1350 ///
1351 /// let mut v = ChunkAnyVec::new(tinfo!(i32), 2);
1352 ///
1353 /// unsafe { v.resize(10, 0_i32) };
1354 /// v.truncate(5);
1355 /// assert_eq!(v.len(), 5);
1356 /// ```
1357 pub fn truncate(&mut self, len: usize) {
1358 if len >= self.len() {
1359 return;
1360 }
1361
1362 let mut cur_len = self.len();
1363
1364 while cur_len > len {
1365 // `len > 0` because of early exit above, so `cur_len > 1`.
1366 let (ci, _) = self.index_2d(cur_len - 1);
1367 let last_chunk_len = self.chunks[ci].len();
1368 let partial = last_chunk_len.min(cur_len - len);
1369
1370 // We do not drop chunk itself to avoid frequent allocations. Just
1371 // eliminates items in the chunk only.
1372 self.chunks[ci].truncate(last_chunk_len - partial);
1373
1374 cur_len -= partial;
1375 }
1376
1377 unsafe { self.set_len(cur_len) };
1378 }
1379
1380 /// Creates a new chunk.
1381 ///
1382 /// Note that chunk always has the fixed capacity.
1383 fn create_chunk(&self) -> AnyVec {
1384 let mut chunk = self.chunks[0].clone();
1385 chunk.reserve_exact(self.default_chunk_capacity());
1386 chunk
1387 }
1388
1389 /// Converts 1D index into 2D index.
1390 const fn index_2d(&self, index: usize) -> (usize, usize) {
1391 (
1392 self.chunk_cap.quotient(index) + self.chunk_offset,
1393 self.chunk_cap.remainder(index),
1394 )
1395 }
1396
1397 const fn max_capacity(&self) -> usize {
1398 self.max_cap
1399 }
1400
1401 #[inline]
1402 unsafe fn fn_iter(this: NonNull<u8>, chunk_idx: usize) -> RawIter {
1403 let this = unsafe { this.cast::<ChunkAnyVec>().as_ref() };
1404 if let Some(chunk) = this.get_chunk(chunk_idx) {
1405 chunk.iter()
1406 } else {
1407 RawIter::empty()
1408 }
1409 }
1410
1411 #[inline]
1412 unsafe fn fn_find(this: NonNull<u8>, item_idx: usize) -> (RawIter, usize, usize) {
1413 let this = unsafe { this.cast::<ChunkAnyVec>().as_ref() };
1414 let (ci, ii) = this.index_2d(item_idx);
1415 let iter = if let Some(chunk) = this.chunks.get(ci) {
1416 chunk.iter()
1417 } else {
1418 RawIter::empty()
1419 };
1420 (iter, ci - this.chunk_offset, ii)
1421 }
1422}
1423
1424impl AsFlatRawIter for ChunkAnyVec {
1425 /// # Safety
1426 ///
1427 /// Returned iterator is not bounded by lifetime.
1428 /// But it actually relies on `&self`, so it must be used as if
1429 /// it's borrowed.
1430 unsafe fn iter(&self) -> FlatRawIter {
1431 // Safety: Infallible.
1432 let this = unsafe {
1433 let ptr = self as *const _ as *const u8;
1434 NonNull::new_unchecked(ptr.cast_mut())
1435 };
1436
1437 let chunks = self.num_chunks();
1438 let stride = self.item_size().max(self.align());
1439
1440 unsafe {
1441 FlatRawIter::new(
1442 this,
1443 chunks,
1444 Self::fn_iter,
1445 Self::fn_find,
1446 stride,
1447 self.len(),
1448 )
1449 }
1450 }
1451}
1452
1453#[cfg(test)]
1454mod tests {
1455 use super::*;
1456 use crate::tinfo;
1457
1458 #[test]
1459 fn test_chunk_any_vec_push_pop() {
1460 // Safety: Type is correct.
1461 unsafe {
1462 let chunk_num = 4 * 4;
1463 let chunk_cap = 2;
1464 let mut v = ChunkAnyVec::new(tinfo!(usize), chunk_cap);
1465 for r in 0..chunk_num {
1466 for c in 0..chunk_cap {
1467 let index = r * chunk_cap + c;
1468 let value = r * chunk_cap + c;
1469
1470 v.push::<usize>(value);
1471
1472 assert_eq!(index + 1, v.len());
1473 assert_eq!(Some(&value), v.get(index));
1474 assert_eq!((r + 1) * chunk_cap, v.capacity());
1475 }
1476 }
1477
1478 assert_eq!(chunk_num * chunk_cap, v.capacity());
1479 assert_eq!(
1480 v.capacity(),
1481 v.chunks.iter().map(|chunk| chunk.capacity()).sum::<usize>()
1482 );
1483
1484 for r in (chunk_num / 4..chunk_num).rev() {
1485 for c in (0..chunk_cap).rev() {
1486 let value = r * chunk_cap + c;
1487 assert_eq!(Some(value), v.pop());
1488 }
1489 }
1490
1491 assert_eq!(chunk_num / 4 * chunk_cap, v.len());
1492 }
1493 }
1494
1495 #[test]
1496 fn test_chunk_any_vec_swap_remove() {
1497 // Safety: Type is correct.
1498 unsafe {
1499 let chunk_size = 8;
1500 let item_num = 13;
1501 let chunk_num = (item_num as f32 / chunk_size as f32).ceil() as usize;
1502 let mut v = ChunkAnyVec::new(tinfo!(i32), chunk_size);
1503 let mut expect = vec![];
1504 for i in 0..item_num {
1505 v.push(i);
1506 expect.push(i);
1507 }
1508
1509 enum Pos {
1510 Start,
1511 Middle,
1512 End,
1513 }
1514
1515 let mut pos = Pos::Start;
1516 for _i in 0..item_num {
1517 let index = match pos {
1518 Pos::Start => {
1519 pos = Pos::Middle;
1520 0
1521 }
1522 Pos::Middle => {
1523 pos = Pos::End;
1524 v.len() / 2
1525 }
1526 Pos::End => {
1527 pos = Pos::Start;
1528 v.len() - 1
1529 }
1530 };
1531 let expect_val = expect.swap_remove(index);
1532 let popped_val: i32 = v.swap_remove(index);
1533
1534 assert_eq!(expect_val, popped_val);
1535 assert_eq!(expect.len(), v.len());
1536 for j in 0..v.len() {
1537 assert_eq!(expect.get(j), v.get(j));
1538 }
1539 }
1540
1541 assert!(v.is_empty());
1542 assert_eq!(chunk_num * chunk_size, v.capacity());
1543 }
1544 }
1545
1546 #[test]
1547 fn test_chunk_any_vec_resize() {
1548 // Safety: Type is correct.
1549 unsafe {
1550 // Tests resize().
1551 let mut v = ChunkAnyVec::new(tinfo!(i32), 8);
1552 assert!(v.is_empty());
1553
1554 // Resizes the vector.
1555 v.resize(20, 42);
1556 assert_eq!(v.len(), 20);
1557 for val in v.iter_of::<i32>() {
1558 assert_eq!(*val, 42);
1559 }
1560
1561 // Tests resize_raw().
1562 #[derive(Clone)]
1563 struct Val(String);
1564
1565 let mut v = ChunkAnyVec::new(tinfo!(Val), 8);
1566
1567 let val = Val("42".to_owned());
1568 let val_ptr = NonNull::new(&val as *const Val as *mut Val as *mut u8).unwrap();
1569 v.resize_raw(20, val_ptr);
1570 assert_eq!(v.len(), 20);
1571
1572 for val in v.iter_of::<Val>() {
1573 assert_eq!(val.0.as_str(), "42");
1574 }
1575 }
1576 }
1577
1578 #[test]
1579 fn test_chunk_any_vec_iter() {
1580 // Safety: Type is correct.
1581 unsafe {
1582 const CHUNK_SIZES: &[usize] = &[1, 2, 4, 8];
1583 const CHUNK_COUNTS: &[usize] = &[1, 2, 3];
1584
1585 for chunk_size in CHUNK_SIZES {
1586 for chunk_count in CHUNK_COUNTS {
1587 let mut v = ChunkAnyVec::new(tinfo!(i32), *chunk_size);
1588 let num = (chunk_size * chunk_count) as i32;
1589 for i in 0..num {
1590 v.push(i);
1591 }
1592
1593 test_iter(
1594 v.iter_of::<i32>(),
1595 (0..num).into_iter(),
1596 |l: &i32, r: i32| *l == r,
1597 );
1598 }
1599 }
1600 }
1601 }
1602
1603 #[test]
1604 fn test_chunk_any_vec_iter_split() {
1605 use rayon::iter::plumbing::Producer;
1606 use std::collections::VecDeque;
1607 use std::ops::Range;
1608
1609 // Safety: Type is correct.
1610 unsafe {
1611 const CHUNK_COUNTS: &[usize] = &[1, 2, 3];
1612 const CHUNK_SIZES: &[usize] = &[1, 2, 4, 8];
1613 const TARGET_CHUNK_LENS: &[usize] = &[1, 2, 3, 4];
1614
1615 for chunk_size in CHUNK_SIZES {
1616 for chunk_count in CHUNK_COUNTS {
1617 let mut v = ChunkAnyVec::new(tinfo!(i32), *chunk_size);
1618 let num = (chunk_size * chunk_count) as i32;
1619 for i in 0..num {
1620 v.push(i);
1621 }
1622
1623 let iter = v.par_iter_of::<i32>();
1624 let mut pieces = VecDeque::new();
1625 pieces.push_front((iter, 0..num));
1626
1627 for target_chunk_len in TARGET_CHUNK_LENS {
1628 inner(pieces.clone(), *target_chunk_len);
1629 }
1630 }
1631 }
1632 }
1633
1634 fn inner(mut pieces: VecDeque<(ParFlatIter<i32>, Range<i32>)>, target_chunk_len: usize) {
1635 loop {
1636 let (piece, range) = pieces.pop_front().unwrap();
1637 if piece.len() <= target_chunk_len {
1638 break;
1639 }
1640
1641 let mid = piece.len() / 2;
1642 let (l_piece, r_piece) = piece.split_at(mid);
1643
1644 let mid = (range.start + range.end) / 2;
1645 let l_range = range.start..mid;
1646 let r_range = mid..range.end;
1647
1648 if l_piece.len() <= target_chunk_len {
1649 pieces.push_back((l_piece, l_range))
1650 } else {
1651 pieces.push_front((l_piece, l_range));
1652 }
1653 if r_piece.len() <= target_chunk_len {
1654 pieces.push_back((r_piece, r_range));
1655 } else {
1656 pieces.push_front((r_piece, r_range));
1657 }
1658 }
1659
1660 for (piece, range) in pieces {
1661 test_iter(piece.into_seq(), range, |l: &i32, r: i32| *l == r)
1662 }
1663 }
1664 }
1665
1666 #[test]
1667 fn test_chunk_any_vec_zst() {
1668 // Safety: Type is correct.
1669 unsafe {
1670 let chunk_size = 8; // no effect.
1671 let mut v = ChunkAnyVec::new(tinfo!(()), chunk_size);
1672 assert!(v.is_empty());
1673 for i in 1..=chunk_size {
1674 v.push(());
1675 assert_eq!(v.len(), i);
1676 }
1677
1678 // Not allocated.
1679 assert_eq!(
1680 v.get_chunk(0).unwrap().get_ptr(0),
1681 AnyVec::aligned_dangling(tinfo!(()).align).as_ptr()
1682 );
1683
1684 for i in (1..=chunk_size).rev() {
1685 v.pop_drop();
1686 assert_eq!(v.len(), i - 1);
1687 }
1688 }
1689 }
1690
1691 fn test_iter<I, J, II, JI, F>(iter: I, expect: J, eq: F)
1692 where
1693 I: Iterator<Item = II> + ExactSizeIterator + DoubleEndedIterator + Clone,
1694 J: Iterator<Item = JI> + ExactSizeIterator + DoubleEndedIterator + Clone,
1695 II: PartialEq + std::fmt::Debug,
1696 JI: PartialEq + std::fmt::Debug,
1697 F: Fn(II, JI) -> bool,
1698 {
1699 // `iter` and `expect` must have the same number of items.
1700 assert_eq!(iter.len(), expect.len());
1701
1702 // Traverses forward.
1703 let mut zipped = iter.clone().zip(expect.clone());
1704 assert!(zipped.all(|(l, r)| eq(l, r)));
1705
1706 // Traverses backward.
1707 let mut zipped = iter.clone().rev().zip(expect.clone().rev());
1708 assert!(zipped.all(|(l, r)| eq(l, r)));
1709
1710 // Traverses forward and backward alternately.
1711 let mut zipped = iter.zip(expect);
1712 let mut forward = true;
1713 let n = zipped.len();
1714 for _ in 0..n {
1715 let pair = if forward {
1716 zipped.next()
1717 } else {
1718 zipped.next_back()
1719 };
1720 let (l, r) = pair.unwrap();
1721 assert!(eq(l, r));
1722 forward = !forward;
1723 }
1724 }
1725}