commonlibsse_ng\re\b\BSTArray/heap.rs
1use core::{
2 alloc::Layout,
3 marker::PhantomData,
4 ops::{Index, IndexMut, Range, RangeBounds},
5 ptr::{self, NonNull},
6};
7use std::alloc::handle_alloc_error;
8
9use crate::re::MemoryManager::TESGlobalAlloc;
10use std_fork::alloc::SelflessAllocator;
11use stdx::ptr::{ConstNonNull, Unique};
12
13/// A binary-compatible, growable array.
14///
15/// `BSTArray<T, A>` is a contiguous, heap-allocated collection of elements of type `T`
16/// with memory layout designed to match Havok's native `BSTArray`. This type is similar
17/// to [`Vec<T>`] in usage but may differ in layout due to alignment, padding, or
18/// platform-specific serialization constraints.
19///
20/// This array uses a custom allocator `A` (which implements [`Allocator`]) to control
21/// memory allocation. In contexts where allocation is fixed (e.g., read-only arrays or
22/// statically-sized blocks), capacity may be fixed or omitted entirely.
23///
24/// Internally, the array stores:
25/// - a pointer to the data buffer
26/// - the number of elements (`len`)
27/// - the capacity of the allocation (`cap`)
28///
29/// # Features
30///
31/// - Compatible with Havok's binary layout for `BSTArray<T>`
32/// - Supports growable or fixed-capacity semantics
33/// - Custom allocator support (`A: Allocator`)
34/// - Methods similar to `Vec<T>`
35///
36/// # Panics
37///
38/// Most methods panic under the following conditions:
39///
40/// - Indexing out of bounds (`array[index]`)
41/// - Reserving more capacity than is possible
42/// - Pushing to a full fixed-capacity array (if applicable)
43///
44/// # Example
45///
46/// ```rust
47/// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
48/// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
49///
50/// let mut array = BSTArray::<i32>::new();
51/// array.push(1);
52/// array.push(2);
53/// assert_eq!(array.len(), 2);
54/// assert_eq!(array[1], 2);
55/// ```
56///
57/// # See also
58///
59/// - [`Vec<T>`]
60/// - [`Box<[T]>`]
61#[repr(C)]
62pub struct BSTArray<T, A = TESGlobalAlloc>
63where
64 A: SelflessAllocator,
65{
66 // BSTArrayHeapAllocator
67 /// null check safe `*mut T`.
68 data: Option<Unique<T>>, // 0x000
69 capacity: u32, // 0x004,
70
71 // Unlike the C++ implementation, the pad must be manually inserted
72 // because BSTArrayHeapAllocator was inlined.
73 pad08: u32, // 0x008,
74
75 // BSTArrayBase
76 // length of elements
77 size: u32, // 0x010
78
79 // Assumed Zero size type.
80 alloc: PhantomData<A>,
81}
82const _: () = assert!(core::mem::size_of::<BSTArray<()>>() == 0x18);
83
84impl<T, A> BSTArray<T, A>
85where
86 A: SelflessAllocator,
87{
88 /// Creates a new, empty `BSTArray<T, A>` with the specified allocator.
89 ///
90 /// The array will not allocate until elements are pushed.
91 ///
92 /// # Example
93 /// ```
94 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
95 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
96 ///
97 /// let array = BSTArray::<i32>::new();
98 /// assert!(array.is_empty());
99 /// ```
100 #[inline]
101 pub const fn new() -> Self {
102 Self { data: None, capacity: 0, pad08: 0, size: 0, alloc: PhantomData }
103 }
104
105 /// Creates a new, empty `BSTArray<T, A>` with the capacity.
106 ///
107 /// # Example
108 /// ```
109 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
110 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
111 ///
112 /// let array = BSTArray::<i32>::with_capacity(5);
113 /// assert_eq!(array.capacity(), 5);
114 /// ```
115 pub fn with_capacity(capacity: usize) -> Self {
116 let new_data = A::allocate(Self::new_layout(capacity)).ok();
117 let data = new_data.map(|p| unsafe { Unique::new_unchecked(p.cast::<T>().as_ptr()) });
118 let capacity = capacity as u32;
119
120 Self { data, capacity, pad08: 0, size: 0, alloc: PhantomData }
121 }
122
123 /// Returns the number of elements in the array.
124 ///
125 /// This is also referred to as the array’s "length".
126 ///
127 /// # Example
128 /// ```
129 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
130 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
131 ///
132 /// let array = BSTArray::<i32>::new();
133 /// assert_eq!(array.len(), 0);
134 /// ```
135 #[inline]
136 pub const fn len(&self) -> usize {
137 self.size as usize
138 }
139
140 /// Returns `true` if the array contains no elements.
141 ///
142 /// # Example
143 /// ```
144 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
145 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
146 ///
147 /// let array = BSTArray::<i32>::new();
148 /// assert!(array.is_empty());
149 /// ```
150 #[inline]
151 pub const fn is_empty(&self) -> bool {
152 self.len() == 0
153 }
154
155 /// Returns the total number of elements the array can hold without reallocating.
156 ///
157 /// This is the allocated capacity, which may be larger than the current length.
158 ///
159 /// # Example
160 /// ```
161 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
162 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
163 ///
164 /// let mut array = BSTArray::<i32>::with_capacity(10);
165 /// assert!(array.capacity() >= 10);
166 /// ```
167 #[inline]
168 pub const fn capacity(&self) -> usize {
169 self.capacity as usize
170 }
171
172 /// Shrinks the capacity of the array as much as possible.
173 ///
174 /// It will drop any excess capacity not used by the current elements.
175 ///
176 /// # Examples
177 ///
178 /// ```
179 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
180 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
181 ///
182 /// let mut array = BSTArray::<i32>::with_capacity(10);
183 /// array.push(1);
184 /// assert_eq!(array.len(), 1);
185 /// array.shrink_to_fit();
186 /// assert!(array.capacity() >= array.len());
187 /// ```
188 #[inline]
189 pub fn shrink_to_fit(&mut self) {
190 let len = self.len();
191 self.change_capacity(len);
192 }
193
194 /// Appends an element to the back of the array.
195 ///
196 /// # Panics
197 /// Panics if the array is at fixed capacity and cannot grow.
198 ///
199 /// # Example
200 /// ```
201 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
202 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
203 ///
204 /// let mut array = BSTArray::<i32>::new();
205 /// array.push(5);
206 /// assert_eq!(array[0], 5);
207 /// ```
208 #[inline]
209 pub fn push(&mut self, value: T) {
210 let size = self.size;
211 if size == self.capacity {
212 self.grow();
213 }
214 unsafe {
215 if let Some(ptr) = self.as_non_null_ptr() {
216 ptr.add(size as usize).write(value);
217 }
218 }
219
220 self.size += 1;
221 }
222
223 /// Removes the last element from the array and returns it, or `None` if it's empty.
224 ///
225 /// # Example
226 /// ```
227 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
228 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
229 ///
230 /// let mut array = BSTArray::<i32>::new();
231 /// array.push(1);
232 /// assert_eq!(array.pop(), Some(1));
233 /// assert_eq!(array.pop(), None);
234 /// ```
235 #[inline]
236 pub fn pop(&mut self) -> Option<T> {
237 let len = self.len();
238 if len == 0 {
239 None
240 } else {
241 self.size -= 1;
242 unsafe { Some(ptr::read(self.as_non_null_ptr()?.add(len - 1).as_ptr())) }
243 }
244 }
245
246 /// Returns a reference to the element at the given index, if it exists.
247 ///
248 /// # Example
249 /// ```
250 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
251 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
252 ///
253 /// let mut array = BSTArray::<i32>::new();
254 /// array.push(42);
255 /// assert_eq!(array.get(0), Some(&42));
256 /// assert_eq!(array.get(1), None);
257 /// ```
258 #[inline]
259 pub fn get(&self, index: usize) -> Option<&T> {
260 if index < self.len() {
261 return unsafe { Some(self.as_const_non_null_ptr()?.add(index).as_ref()) };
262 }
263 None
264 }
265
266 /// Returns a mutable reference to the element at the given index, if it exists.
267 ///
268 /// # Example
269 /// ```
270 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
271 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
272 ///
273 /// let mut array = BSTArray::<i32>::new();
274 /// array.push(10);
275 /// if let Some(x) = array.get_mut(0) {
276 /// *x += 1;
277 /// }
278 /// assert_eq!(array[0], 11);
279 /// ```
280 #[inline]
281 pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
282 if index < self.len() {
283 return unsafe { Some(self.as_non_null_ptr()?.add(index).as_mut()) };
284 }
285 None
286 }
287
288 /// Clears the array, removing all elements but preserving the capacity.
289 ///
290 /// # Examples
291 /// ```
292 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
293 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
294 ///
295 /// let mut array = BSTArray::<i32>::with_capacity(10);
296 /// array.push(1);
297 /// array.push(2);
298 /// assert_eq!(array.len(), 2);
299 /// array.clear();
300 /// assert_eq!(array.len(), 0);
301 /// assert_eq!(array.capacity(), 10); // Capacity is preserved
302 /// ```
303 #[inline]
304 pub fn clear(&mut self) {
305 // Drop all elements in the array without changing capacity
306 if let Some(non_null) = self.as_non_null_ptr() {
307 for i in 0..self.len() {
308 unsafe {
309 // SAFETY: we're dropping each element in place
310 ptr::drop_in_place(non_null.add(i).as_ptr());
311 }
312 }
313 }
314
315 self.size = 0; // Reset the length, but keep the allocated capacity
316 }
317
318 /// Returns a non null pointer of the array’s buffer.
319 #[inline]
320 pub const fn as_non_null_ptr(&mut self) -> Option<NonNull<T>> {
321 match self.data {
322 Some(p) => Some(p.as_non_null_ptr()),
323 None => None,
324 }
325 }
326
327 /// Returns a non null pointer of the array’s buffer.
328 #[inline]
329 pub const fn as_const_non_null_ptr(&self) -> Option<ConstNonNull<T>> {
330 match self.data {
331 Some(p) => Some(ConstNonNull::from_unique(p)),
332 None => None,
333 }
334 }
335
336 /// Checks if the array contains the given element.
337 ///
338 /// Returns `true` if the element is present in the array, and `false` otherwise.
339 ///
340 /// # Examples
341 ///
342 /// ```
343 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
344 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
345 ///
346 /// let mut array = BSTArray::<i32>::with_capacity(10);
347 /// array.push(1);
348 /// array.push(2);
349 /// assert!(array.contains(&1));
350 /// assert!(!array.contains(&3));
351 /// ```
352 #[inline]
353 pub fn contains(&self, value: &T) -> bool
354 where
355 T: PartialEq,
356 {
357 for i in 0..self.len() {
358 if let Some(item) = self.get(i) {
359 if item == value {
360 return true;
361 }
362 }
363 }
364 false
365 }
366
367 /// Retains only the elements that satisfy the predicate.
368 ///
369 /// This method takes a closure that accepts an element of the array and returns a boolean.
370 /// Elements for which the closure returns `true` will be kept, while elements for which
371 /// it returns `false` will be removed.
372 ///
373 /// # Examples
374 ///
375 /// ```
376 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
377 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
378 ///
379 /// let mut array = BSTArray::<i32>::with_capacity(10);
380 /// array.push(1);
381 /// array.push(2);
382 /// array.push(3);
383 /// array.retain(|&x| x > 1);
384 /// assert_eq!(array.len(), 2);
385 /// assert!(array.contains(&2));
386 /// assert!(array.contains(&3));
387 /// ```
388 ///
389 /// # Panics
390 /// array ptr is null
391 #[inline]
392 pub fn retain<F>(&mut self, mut f: F)
393 where
394 F: FnMut(&T) -> bool,
395 {
396 let mut retained = 0;
397
398 for i in 0..self.len() {
399 let src = match self.as_non_null_ptr() {
400 Some(elem) => unsafe { elem.add(i) },
401 None => continue,
402 };
403
404 if f(unsafe { src.as_ref() }) {
405 if retained != i {
406 unsafe {
407 let dst = self.as_non_null_ptr().unwrap().add(retained).as_ptr();
408 ptr::copy_nonoverlapping(src.as_ptr(), dst, 1);
409 }
410 }
411 retained += 1;
412 } else {
413 unsafe { ptr::drop_in_place(src.as_ptr()) }; // Drop elements that do not match the predicate
414 }
415 }
416
417 self.size = retained as u32;
418 }
419
420 /// Resizes the array to the specified length.
421 ///
422 /// If the list is shorter, it will be extended with cloning the value given as the argument.
423 ///
424 /// # Examples
425 ///
426 /// ```
427 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
428 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
429 ///
430 /// let mut array = BSTArray::<i32>::with_capacity(10);
431 /// array.push(1);
432 /// array.push(2);
433 /// array.resize(5, 0);
434 /// assert_eq!(array.len(), 5);
435 /// assert_eq!(array[3], 0);
436 /// ```
437 #[inline]
438 pub fn resize(&mut self, new_size: usize, value: T)
439 where
440 T: Clone,
441 {
442 let prev_size = self.len();
443 if new_size > prev_size {
444 for _ in prev_size..new_size {
445 self.push(value.clone());
446 }
447 } else {
448 for i in new_size..prev_size {
449 if let Some(src) = self.as_non_null_ptr() {
450 unsafe { ptr::drop_in_place(src.add(i).as_ptr()) };
451 }
452 }
453 }
454 self.size = new_size as u32;
455 }
456
457 /// Removes a range of elements from the array, returning them as a vector.
458 ///
459 /// This method removes the elements within the specified range and returns them as
460 /// a `Vec<T>`. The range must be within the bounds of the array.
461 ///
462 /// # Examples
463 ///
464 /// ```
465 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
466 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
467 ///
468 /// let mut array = BSTArray::<i32>::with_capacity(10);
469 /// array.push(1);
470 /// array.push(2);
471 /// array.push(3);
472 /// array.push(4);
473 /// array.push(5);
474 /// let drained = array.drain(0..2);
475 /// assert_eq!(drained.collect::<Vec<_>>(), vec![1, 2]);
476 /// assert_eq!(array.len(), 3);
477 /// assert_eq!(array[0], 3);
478 /// assert_eq!(array[1], 4);
479 /// assert_eq!(array[2], 5);
480 /// ```
481 ///
482 /// # Panics
483 /// Panics if the range is out of bounds.
484 #[inline]
485 pub fn drain<R>(&mut self, range: R) -> BSTDrain<'_, T, A>
486 where
487 R: RangeBounds<usize>,
488 {
489 let len = self.len();
490 let Range { start, end } = stdx::slice::range(range, ..len);
491 debug_assert!(start <= end);
492 debug_assert!(end <= len);
493
494 // Need this.
495 // If the size is not changed before creating iter for Drain, inconsistencies will occur.
496 self.size = start as u32;
497
498 let iter = match self.as_non_null_ptr() {
499 Some(src) => unsafe {
500 core::slice::from_raw_parts(src.add(start).as_ptr(), end - start)
501 },
502 None => &[],
503 }
504 .iter();
505
506 BSTDrain {
507 iter,
508 tail_start: end,
509 tail_len: len - end,
510 array: unsafe { NonNull::new_unchecked(self as *mut Self) },
511 }
512 }
513
514 /// Returns a slice of all elements in the array.
515 #[inline]
516 pub const fn as_slice(&self) -> &[T] {
517 let ptr = self.as_const_non_null_ptr();
518 let len = self.len();
519
520 if ptr.is_none() || (len == 0) {
521 return &[];
522 }
523
524 if let Some(src) = self.as_const_non_null_ptr() {
525 unsafe { core::slice::from_raw_parts(src.as_ptr(), len) }
526 } else {
527 &[]
528 }
529 }
530
531 /// Returns a mutable slice of all elements in the array.
532 #[inline]
533 #[allow(clippy::needless_pass_by_ref_mut)]
534 pub const fn as_mut_slice(&mut self) -> &mut [T] {
535 let ptr = self.as_non_null_ptr();
536 let len = self.len();
537
538 if ptr.is_none() || (len == 0) {
539 return &mut [];
540 }
541
542 if let Some(src) = self.as_non_null_ptr() {
543 unsafe { core::slice::from_raw_parts_mut(src.as_ptr(), len) }
544 } else {
545 &mut []
546 }
547 }
548
549 /// Returns an iterator over the elements of the array.
550 ///
551 /// This iterator yields references to the elements in the array.
552 ///
553 /// # Examples
554 ///
555 /// ```
556 /// # use commonlibsse_ng::re::BSTArray::BSTArray as BSTArray_;
557 /// # type BSTArray<T> = BSTArray_<T, stdx::alloc::Global>;
558 ///
559 /// let mut array = BSTArray::<i32>::with_capacity(10);
560 /// array.push(1);
561 /// array.push(2);
562 /// let sum: i32 = array.iter().sum();
563 /// assert_eq!(sum, 3);
564 /// ```
565 #[inline]
566 pub const fn iter(&self) -> BSTArrayIterator<'_, T, A> {
567 BSTArrayIterator { array: self, index: 0 }
568 }
569
570 fn grow(&mut self) {
571 const MIN_CAPACITY: usize = 4;
572 const GROWTH_FACTOR: usize = 2;
573
574 let old_capacity = self.capacity();
575 let new_capacity =
576 if old_capacity == 0 { MIN_CAPACITY } else { old_capacity * GROWTH_FACTOR };
577 self.change_capacity(new_capacity);
578 }
579
580 fn change_capacity(&mut self, new_capacity: usize) {
581 if new_capacity == 0 {
582 return;
583 }
584 let new_data = {
585 let layout = Self::new_layout(new_capacity);
586 A::allocate(layout).map_or_else(|_| handle_alloc_error(layout), |data| data.cast::<T>())
587 };
588
589 if let Some(old_data) = self.as_non_null_ptr() {
590 let old_capacity = self.capacity();
591 let copy_count = core::cmp::min(old_capacity, new_capacity);
592
593 unsafe { ptr::copy_nonoverlapping(old_data.as_ptr(), new_data.as_ptr(), copy_count) };
594
595 let old_layout = self.layout();
596 unsafe { A::deallocate(old_data.cast(), old_layout) };
597 }
598
599 self.data = Some(Unique::from(new_data));
600 self.capacity = new_capacity as u32;
601 }
602
603 /// Creates a layout describing the record for a `[T; n]`.
604 ///
605 /// # Panics
606 /// On arithmetic overflow or when the total size would exceed
607 /// `isize::MAX`, panic.
608 fn new_layout(n: usize) -> Layout {
609 Layout::array::<T>(n).expect("BSTArray need: alloc size < isize::MAX")
610 }
611
612 /// Gets a layout self.
613 ///
614 /// # Panics
615 /// On arithmetic overflow or when the total size would exceed
616 /// `isize::MAX`, panic.
617 fn layout(&self) -> Layout {
618 Self::new_layout(self.capacity())
619 }
620}
621
622impl<T, A> Drop for BSTArray<T, A>
623where
624 A: SelflessAllocator,
625{
626 fn drop(&mut self) {
627 unsafe {
628 if let Some(ptr) = self.data {
629 // Drop each element
630 let ptr = ptr.as_non_null_ptr();
631 for i in 0..self.size as usize {
632 ptr::drop_in_place(ptr.add(i).as_ptr());
633 }
634 A::deallocate(ptr.cast(), self.layout());
635 }
636 }
637 }
638}
639
640impl<T, A> Index<usize> for BSTArray<T, A>
641where
642 A: SelflessAllocator,
643{
644 type Output = T;
645
646 #[inline]
647 fn index(&self, index: usize) -> &Self::Output {
648 assert!(index < self.len(), "Index out of bounds");
649 unsafe { self.as_const_non_null_ptr().unwrap().add(index).as_ref() }
650 }
651}
652
653impl<T, A> IndexMut<usize> for BSTArray<T, A>
654where
655 A: SelflessAllocator,
656{
657 #[inline]
658 fn index_mut(&mut self, index: usize) -> &mut Self::Output {
659 assert!(index < self.len(), "Index out of bounds");
660 unsafe { self.as_non_null_ptr().unwrap().add(index).as_mut() }
661 }
662}
663
664////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
665// Iterator
666
667/// Iterator returned by `BSTArray::drain()`
668pub struct BSTDrain<'a, T, A>
669where
670 A: SelflessAllocator,
671{
672 tail_start: usize, // = range.end
673 tail_len: usize, // = original_len - range.end
674 iter: core::slice::Iter<'a, T>,
675 array: NonNull<BSTArray<T, A>>,
676}
677
678impl<T, A> Iterator for BSTDrain<'_, T, A>
679where
680 A: SelflessAllocator,
681{
682 type Item = T;
683
684 #[inline]
685 fn next(&mut self) -> Option<Self::Item> {
686 self.iter.next().map(|item| unsafe { ptr::read(item) })
687 }
688
689 #[inline]
690 fn size_hint(&self) -> (usize, Option<usize>) {
691 self.iter.size_hint()
692 }
693}
694
695impl<T, A> DoubleEndedIterator for BSTDrain<'_, T, A>
696where
697 A: SelflessAllocator,
698{
699 #[inline]
700 fn next_back(&mut self) -> Option<Self::Item> {
701 self.iter.next_back().map(|item| unsafe { ptr::read(item) })
702 }
703}
704
705impl<T, A> ExactSizeIterator for BSTDrain<'_, T, A>
706where
707 A: SelflessAllocator,
708{
709 #[inline]
710 fn len(&self) -> usize {
711 self.iter.len()
712 }
713}
714
715impl<T, A: SelflessAllocator> Drop for BSTDrain<'_, T, A> {
716 fn drop(&mut self) {
717 // Copyright (c) 2018 The Servo Project Developers
718 // SPDX-License-Identifier: Apache-2.0 OR MIT
719 // https://github.com/servo/rust-smallvec/blob/v2/src/lib.rs#L3
720
721 if core::mem::needs_drop::<T>() {
722 self.for_each(drop);
723 }
724
725 // Copy backward data not subject to drain to the drained start location
726 if self.tail_len > 0 {
727 unsafe {
728 let array = self.array.as_mut();
729
730 let start = array.len();
731 let tail = self.tail_start;
732 if let Some(ptr) = array.as_non_null_ptr() {
733 if tail != start {
734 let src = ptr.add(tail).as_ptr();
735 let dst = ptr.add(start).as_ptr();
736 ptr::copy(src, dst, self.tail_len);
737 }
738 }
739 array.size = (start + self.tail_len) as u32;
740 }
741 }
742 }
743}
744
745////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
746
747pub struct BSTArrayIterator<'a, T, A>
748where
749 A: SelflessAllocator,
750{
751 array: &'a BSTArray<T, A>,
752 index: usize,
753}
754
755impl<'a, T, A> Iterator for BSTArrayIterator<'a, T, A>
756where
757 A: SelflessAllocator,
758{
759 type Item = &'a T;
760
761 #[inline]
762 fn next(&mut self) -> Option<Self::Item> {
763 if self.index < self.array.len() {
764 let item = unsafe { self.array.as_const_non_null_ptr()?.add(self.index).as_ref() };
765 self.index += 1;
766 Some(item)
767 } else {
768 None
769 }
770 }
771}
772
773pub struct BSTArrayIntoIterator<T, A>
774where
775 A: SelflessAllocator,
776{
777 array: BSTArray<T, A>,
778 index: usize,
779}
780
781impl<T, A> Iterator for BSTArrayIntoIterator<T, A>
782where
783 A: SelflessAllocator,
784{
785 type Item = T;
786
787 #[inline]
788 fn next(&mut self) -> Option<Self::Item> {
789 if self.index < self.array.len() {
790 let item = unsafe { ptr::read(self.array.as_non_null_ptr()?.add(self.index).as_ptr()) };
791 self.index += 1;
792 Some(item)
793 } else {
794 None
795 }
796 }
797}
798
799impl<T, A> IntoIterator for BSTArray<T, A>
800where
801 A: SelflessAllocator,
802{
803 type Item = T;
804 type IntoIter = BSTArrayIntoIterator<T, A>;
805
806 #[inline]
807 fn into_iter(self) -> Self::IntoIter {
808 BSTArrayIntoIterator { array: self, index: 0 }
809 }
810}
811
812impl<'a, T, A> IntoIterator for &'a BSTArray<T, A>
813where
814 A: SelflessAllocator,
815{
816 type Item = &'a T;
817 type IntoIter = BSTArrayIterator<'a, T, A>;
818
819 #[inline]
820 fn into_iter(self) -> Self::IntoIter {
821 BSTArrayIterator { array: self, index: 0 }
822 }
823}
824
825pub struct BSTArrayIterMut<'a, T, A>
826where
827 A: SelflessAllocator,
828{
829 array: &'a mut BSTArray<T, A>,
830 index: usize,
831}
832
833impl<'a, T, A> Iterator for BSTArrayIterMut<'a, T, A>
834where
835 A: SelflessAllocator,
836{
837 type Item = &'a mut T;
838
839 #[inline]
840 fn next(&mut self) -> Option<Self::Item> {
841 if self.index < self.array.len() {
842 unsafe {
843 let mut ptr = self.array.as_non_null_ptr()?.add(self.index);
844 self.index += 1;
845 Some(ptr.as_mut())
846 }
847 } else {
848 None
849 }
850 }
851
852 #[inline]
853 fn size_hint(&self) -> (usize, Option<usize>) {
854 let len = self.array.len();
855 (len, Some(len))
856 }
857}
858
859impl<'a, T, A> IntoIterator for &'a mut BSTArray<T, A>
860where
861 A: SelflessAllocator,
862{
863 type Item = &'a mut T;
864 type IntoIter = BSTArrayIterMut<'a, T, A>;
865
866 #[inline]
867 fn into_iter(self) -> Self::IntoIter {
868 BSTArrayIterMut { array: self, index: 0 }
869 }
870}
871
872impl<T, A> Extend<T> for BSTArray<T, A>
873where
874 A: SelflessAllocator,
875{
876 #[inline]
877 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
878 for elem in iter {
879 self.push(elem);
880 }
881 }
882}
883
884////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
885// Standard derive
886
887impl<T, A> core::fmt::Debug for BSTArray<T, A>
888where
889 T: core::fmt::Debug,
890 A: SelflessAllocator,
891{
892 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
893 f.debug_list().entries(self.as_slice()).finish()
894 }
895}
896
897impl<T> Default for BSTArray<T> {
898 #[inline]
899 fn default() -> Self {
900 Self::new()
901 }
902}
903
904impl<T, A> Clone for BSTArray<T, A>
905where
906 A: SelflessAllocator + Clone,
907{
908 #[inline]
909 fn clone(&self) -> Self {
910 // heap clone
911 let data = self.as_const_non_null_ptr().map(|src_ptr| {
912 let layout = self.layout();
913 let Ok(dst_ptr) = A::allocate(layout) else { handle_alloc_error(layout) };
914 let dst_ptr = dst_ptr.cast::<T>();
915 unsafe { ptr::copy_nonoverlapping(src_ptr.as_ptr(), dst_ptr.as_ptr(), layout.size()) };
916
917 Unique::from(dst_ptr)
918 });
919
920 Self { data, capacity: self.capacity, pad08: 0, size: self.size, alloc: PhantomData }
921 }
922}
923
924impl<T, A> PartialEq for BSTArray<T, A>
925where
926 T: PartialEq,
927 A: SelflessAllocator,
928{
929 #[inline]
930 fn eq(&self, other: &Self) -> bool {
931 self.as_slice() == other.as_slice()
932 }
933}
934impl<T, A> PartialEq<Vec<T>> for BSTArray<T, A>
935where
936 T: PartialEq,
937 A: SelflessAllocator,
938{
939 #[inline]
940 fn eq(&self, other: &Vec<T>) -> bool {
941 self.as_slice() == *other
942 }
943}
944
945impl<T, A> PartialEq<&[T]> for BSTArray<T, A>
946where
947 T: PartialEq,
948 A: SelflessAllocator,
949{
950 #[inline]
951 fn eq(&self, other: &&[T]) -> bool {
952 self.as_slice() == *other
953 }
954}
955
956impl<T, A> Eq for BSTArray<T, A>
957where
958 T: Eq,
959 A: SelflessAllocator,
960{
961}
962
963impl<T, A> PartialOrd for BSTArray<T, A>
964where
965 T: PartialOrd,
966 A: SelflessAllocator,
967{
968 #[inline]
969 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
970 self.as_slice().partial_cmp(other.as_slice())
971 }
972}
973
974impl<T, A> Ord for BSTArray<T, A>
975where
976 T: Ord,
977 A: SelflessAllocator,
978{
979 #[inline]
980 fn cmp(&self, other: &Self) -> core::cmp::Ordering {
981 self.as_slice().cmp(other.as_slice())
982 }
983}
984
985impl<T, A> core::hash::Hash for BSTArray<T, A>
986where
987 T: core::hash::Hash,
988 A: SelflessAllocator,
989{
990 #[inline]
991 fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
992 self.as_slice().hash(state);
993 }
994}
995
996////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
997
998#[cfg(test)]
999mod tests {
1000 use stdx::alloc::Global;
1001
1002 use super::BSTArray as BSTArray_;
1003
1004 type BSTArray<T> = BSTArray_<T, Global>;
1005
1006 #[test]
1007 fn test_drain() {
1008 let mut array = BSTArray::with_capacity(10);
1009 array.push(1);
1010 array.push(2);
1011 array.push(3);
1012 array.push(4);
1013 array.push(5);
1014
1015 let drained = array.drain(1..3);
1016 // for i in drained {
1017 // println!("{:?}", i);
1018 // }
1019 assert_eq!(drained.collect::<Vec<_>>(), vec![2, 3]);
1020 assert_eq!(array.len(), 3);
1021 assert_eq!(array[0], 1);
1022 assert_eq!(array[1], 4);
1023 assert_eq!(array[2], 5);
1024 }
1025}