stack_buf/vec.rs
1use std::borrow::{Borrow, BorrowMut};
2use std::cmp::Ordering;
3use std::hash::{Hash, Hasher};
4use std::iter::FromIterator;
5use std::mem::{ManuallyDrop, MaybeUninit};
6use std::ops::{
7 Bound, Deref, DerefMut, Index, IndexMut, Range, RangeBounds, RangeFrom, RangeFull,
8 RangeInclusive, RangeTo, RangeToInclusive,
9};
10use std::ptr::NonNull;
11use std::{fmt, ptr, slice};
12
13type Size = u32;
14
15macro_rules! assert_capacity {
16 ($cap: expr) => {
17 if std::mem::size_of::<usize>() > std::mem::size_of::<Size>() {
18 // largest supported capacity is Size::MAX
19 if $cap > Size::MAX as usize {
20 [][$cap]
21 }
22 }
23 };
24}
25
26/// Set the length of the vec when the `SetLenOnDrop` value goes out of scope.
27///
28/// Copied from https://github.com/rust-lang/rust/pull/36355
29struct SetLenOnDrop<'a> {
30 len: &'a mut Size,
31 local_len: Size,
32}
33
34impl<'a> SetLenOnDrop<'a> {
35 #[inline]
36 fn new(len: &'a mut Size) -> Self {
37 SetLenOnDrop {
38 local_len: *len,
39 len,
40 }
41 }
42
43 #[inline(always)]
44 fn increment_len(&mut self, increment: Size) {
45 self.local_len += increment;
46 }
47}
48
49impl<'a> Drop for SetLenOnDrop<'a> {
50 #[inline]
51 fn drop(&mut self) {
52 *self.len = self.local_len;
53 }
54}
55
56/// A draining iterator for `StackVec<T, N>`.
57///
58/// This `struct` is created by [`StackVec::drain()`].
59pub struct Drain<'a, T: 'a, const N: usize> {
60 /// Index of tail to preserve
61 tail_start: usize,
62 /// Length of tail
63 tail_len: usize,
64 /// Current remaining range to remove
65 iter: slice::Iter<'a, T>,
66 vec: NonNull<StackVec<T, N>>,
67}
68
69unsafe impl<'a, T: Sync, const N: usize> Sync for Drain<'a, T, N> {}
70unsafe impl<'a, T: Send, const N: usize> Send for Drain<'a, T, N> {}
71
72impl<'a, T: 'a, const N: usize> Iterator for Drain<'a, T, N> {
73 type Item = T;
74
75 #[inline]
76 fn next(&mut self) -> Option<Self::Item> {
77 self.iter
78 .next()
79 .map(|elt| unsafe { ptr::read(elt as *const _) })
80 }
81
82 #[inline]
83 fn size_hint(&self) -> (usize, Option<usize>) {
84 self.iter.size_hint()
85 }
86}
87
88impl<'a, T: 'a, const N: usize> DoubleEndedIterator for Drain<'a, T, N> {
89 #[inline]
90 fn next_back(&mut self) -> Option<Self::Item> {
91 self.iter
92 .next_back()
93 .map(|elt| unsafe { ptr::read(elt as *const _) })
94 }
95}
96
97impl<'a, T: 'a, const N: usize> ExactSizeIterator for Drain<'a, T, N> {}
98
99impl<'a, T: 'a, const N: usize> Drop for Drain<'a, T, N> {
100 fn drop(&mut self) {
101 // len is currently 0 so panicking while dropping will not cause a double drop.
102
103 // exhaust self first
104 while let Some(_) = self.next() {}
105
106 if self.tail_len > 0 {
107 unsafe {
108 let source_vec = self.vec.as_mut();
109 // memmove back untouched tail, update to new length
110 let start = source_vec.len();
111 let tail = self.tail_start;
112 let src = source_vec.as_ptr().add(tail);
113 let dst = source_vec.as_mut_ptr().add(start);
114 ptr::copy(src, dst, self.tail_len);
115 source_vec.set_len(start + self.tail_len);
116 }
117 }
118 }
119}
120
121/// A `Vec`-like container that stores elements on the stack.
122///
123/// The `StackVec` is a vector backed by a fixed size array. It keeps track of
124/// the number of initialized elements. The `StackVec<T, N>` is parameterized
125/// by `T` for the element type and `N` for the maximum capacity.
126///
127/// `N` is of type `usize` but is range limited to `u32::MAX`; attempting to create larger
128/// `StackVec` with larger capacity will panic.
129///
130/// The vector is a contiguous value (storing the elements inline) that you can store directly on
131/// the stack.
132///
133/// It offers a simple API but also dereferences to a slice, so that the full slice API is
134/// available.
135pub struct StackVec<T, const N: usize> {
136 vec: [MaybeUninit<T>; N],
137 len: Size,
138}
139
140impl<T, const N: usize> StackVec<T, N> {
141 const VALUE: MaybeUninit<T> = MaybeUninit::uninit();
142 const VEC: [MaybeUninit<T>; N] = [Self::VALUE; N];
143
144 /// Creates a new empty `StackVec`.
145 ///
146 /// The maximum capacity is given by the generic parameter `N`.
147 ///
148 /// # Examples
149 ///
150 /// ```
151 /// use stack_buf::StackVec;
152 ///
153 /// let mut vec = StackVec::<_, 16>::new();
154 /// vec.push(1);
155 /// vec.push(2);
156 /// assert_eq!(&vec[..], &[1, 2]);
157 /// assert_eq!(vec.capacity(), 16);
158 /// ```
159 #[inline]
160 pub const fn new() -> Self {
161 assert_capacity!(N);
162 StackVec {
163 vec: Self::VEC,
164 len: 0,
165 }
166 }
167
168 /// Returns the number of elements stored in the `StackVec`.
169 ///
170 /// # Examples
171 ///
172 /// ```
173 /// use stack_buf::StackVec;
174 ///
175 /// let mut vec = StackVec::from([1, 2, 3]);
176 /// vec.pop();
177 /// assert_eq!(vec.len(), 2);
178 /// ```
179 #[inline(always)]
180 pub const fn len(&self) -> usize {
181 self.len as usize
182 }
183
184 /// Returns `true` if the `StackVec` is empty, false otherwise.
185 ///
186 /// # Examples
187 ///
188 /// ```
189 /// use stack_buf::StackVec;
190 ///
191 /// let mut vec = StackVec::from([1]);
192 /// vec.pop();
193 /// assert_eq!(vec.is_empty(), true);
194 /// ```
195 #[inline(always)]
196 pub const fn is_empty(&self) -> bool {
197 self.len() == 0
198 }
199
200 /// Returns `true` if the `StackVec` is completely filled to its capacity, false otherwise.
201 ///
202 /// # Examples
203 ///
204 /// ```
205 /// use stack_buf::StackVec;
206 ///
207 /// let mut vec = StackVec::<_, 1>::new();
208 /// assert!(!vec.is_full());
209 /// vec.push(1);
210 /// assert!(vec.is_full());
211 /// ```
212 #[inline]
213 pub const fn is_full(&self) -> bool {
214 self.len() == self.capacity()
215 }
216
217 /// Returns the capacity of the `StackVec`.
218 ///
219 /// # Examples
220 ///
221 /// ```
222 /// use stack_buf::StackVec;
223 ///
224 /// let vec = StackVec::from([1, 2, 3]);
225 /// assert_eq!(vec.capacity(), 3);
226 /// ```
227 #[inline(always)]
228 pub const fn capacity(&self) -> usize {
229 N
230 }
231
232 /// Returns the capacity left in the `StackVec`.
233 ///
234 /// # Examples
235 ///
236 /// ```
237 /// use stack_buf::StackVec;
238 ///
239 /// let mut vec = StackVec::from([1, 2, 3]);
240 /// vec.pop();
241 /// assert_eq!(vec.remaining_capacity(), 1);
242 /// ```
243 #[inline]
244 pub const fn remaining_capacity(&self) -> usize {
245 self.capacity() - self.len()
246 }
247
248 /// Returns a raw pointer to the `StackVec`'s buffer.
249 #[inline(always)]
250 pub const fn as_ptr(&self) -> *const T {
251 self.vec.as_ptr() as _
252 }
253
254 /// Returns a raw mutable pointer to the `StackVec`'s buffer.
255 #[inline(always)]
256 pub fn as_mut_ptr(&mut self) -> *mut T {
257 self.vec.as_mut_ptr() as _
258 }
259
260 /// Returns a slice containing all elements of the `StackVec`.
261 #[inline]
262 pub fn as_slice(&self) -> &[T] {
263 unsafe { slice::from_raw_parts(self.as_ptr(), self.len()) }
264 }
265
266 /// Returns a mutable slice containing all elements of the `StackVec`.
267 #[inline]
268 pub fn as_mut_slice(&mut self) -> &mut [T] {
269 unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len()) }
270 }
271
272 /// Sets the `StackVec`’s length without dropping or moving out elements
273 ///
274 /// # Safety
275 /// This method is `unsafe` because it changes the notion of the
276 /// number of “valid” elements in the vector.
277 ///
278 /// This method uses *debug assertions* to check that `length` is
279 /// not greater than the capacity.
280 #[inline]
281 pub unsafe fn set_len(&mut self, length: usize) {
282 debug_assert!(length <= self.capacity());
283 self.len = length as Size;
284 }
285
286 /// Appends an `value` to the end of the `StackVec`.
287 ///
288 /// # Panics
289 ///
290 /// This function will panic if the `StackVec` is already full.
291 ///
292 /// # Examples
293 ///
294 /// ```
295 /// use stack_buf::StackVec;
296 ///
297 /// let mut vec = StackVec::<_, 2>::new();
298 ///
299 /// vec.push(1);
300 /// vec.push(2);
301 ///
302 /// assert_eq!(&vec[..], &[1, 2]);
303 /// ```
304 #[inline]
305 pub fn push(&mut self, value: T) {
306 self.vec[self.len()] = MaybeUninit::new(value);
307 self.len += 1;
308 }
309
310 /// Removes the last element of the vector and return it, or None if empty.
311 ///
312 /// # Examples
313 ///
314 /// ```
315 /// use stack_buf::StackVec;
316 ///
317 /// let mut vec = StackVec::<_, 2>::new();
318 ///
319 /// vec.push(1);
320 ///
321 /// assert_eq!(vec.pop(), Some(1));
322 /// assert_eq!(vec.pop(), None);
323 /// ```
324 #[inline]
325 pub fn pop(&mut self) -> Option<T> {
326 if self.is_empty() {
327 return None;
328 }
329 unsafe {
330 self.len -= 1;
331 Some(ptr::read(self.as_ptr().add(self.len())))
332 }
333 }
334
335 /// Shortens the vector, keeping the first `len` elements and dropping
336 /// the rest.
337 ///
338 /// If `len` is greater than the vector’s current length this has no
339 /// effect.
340 ///
341 /// # Examples
342 ///
343 /// ```
344 /// use stack_buf::StackVec;
345 ///
346 /// let mut vec = StackVec::from([1, 2, 3, 4, 5]);
347 /// vec.truncate(3);
348 /// assert_eq!(&vec[..], &[1, 2, 3]);
349 /// vec.truncate(4);
350 /// assert_eq!(&vec[..], &[1, 2, 3]);
351 /// ```
352 #[inline]
353 pub fn truncate(&mut self, len: usize) {
354 if len > self.len() {
355 return;
356 }
357
358 unsafe {
359 let remaining_len = self.len() - len;
360 let s = ptr::slice_from_raw_parts_mut(self.as_mut_ptr().add(len), remaining_len);
361 self.set_len(len);
362 ptr::drop_in_place(s);
363 }
364 }
365
366 /// Clears the vector, removing all values.
367 ///
368 /// Note that this method has no effect on the allocated capacity
369 /// of the vector.
370 ///
371 /// # Examples
372 ///
373 /// ```
374 /// use stack_buf::StackVec;
375 ///
376 /// let mut vec = StackVec::from([1, 2, 3]);
377 ///
378 /// vec.clear();
379 ///
380 /// assert!(vec.is_empty());
381 /// ```
382 #[inline]
383 pub fn clear(&mut self) {
384 self.truncate(0)
385 }
386
387 /// Inserts an element at position `index` within the vector, shifting all
388 /// elements after it to the right.
389 ///
390 /// # Panics
391 ///
392 /// Panics if `index > len` or the vector is full.
393 ///
394 /// # Examples
395 ///
396 /// ```
397 /// use stack_buf::{StackVec, stack_vec};
398 ///
399 /// let mut vec = stack_vec![5#1, 2, 3];
400 /// vec.insert(1, 4);
401 /// assert_eq!(&vec[..], [1, 4, 2, 3]);
402 /// vec.insert(4, 5);
403 /// assert_eq!(&vec[..], [1, 4, 2, 3, 5]);
404 /// ```
405 #[inline]
406 pub fn insert(&mut self, index: usize, element: T) {
407 #[cold]
408 #[inline(never)]
409 fn assert_failed(index: usize, len: usize) -> ! {
410 panic!(
411 "insertion index (is {}) should be <= len (is {})",
412 index, len
413 );
414 }
415
416 let len = self.len();
417 if index > len {
418 assert_failed(index, len);
419 }
420 assert!(len < self.capacity());
421 unsafe {
422 let ptr = self.as_mut_ptr().add(index);
423 ptr::copy(ptr, ptr.offset(1), len - index);
424 ptr::write(ptr, element);
425 self.set_len(len + 1);
426 }
427 }
428
429 /// Removes and returns the element at position `index` within the vector,
430 /// shifting all elements after it to the left.
431 ///
432 /// # Panics
433 ///
434 /// Panics if `index` is out of bounds.
435 ///
436 /// # Examples
437 ///
438 /// ```
439 /// use stack_buf::StackVec;
440 ///
441 /// let mut vec = StackVec::from([1, 2, 3]);
442 /// assert_eq!(vec.remove(1), 2);
443 /// assert_eq!(&vec[..], [1, 3]);
444 /// ```
445 #[inline]
446 pub fn remove(&mut self, index: usize) -> T {
447 #[cold]
448 #[inline(never)]
449 fn assert_failed(index: usize, len: usize) -> ! {
450 panic!("removal index (is {}) should be < len (is {})", index, len);
451 }
452
453 let len = self.len();
454 if index >= len {
455 assert_failed(index, len);
456 }
457 unsafe {
458 let ret;
459 {
460 let ptr = self.as_mut_ptr().add(index);
461 ret = ptr::read(ptr);
462 ptr::copy(ptr.offset(1), ptr, len - index - 1);
463 }
464 self.set_len(len - 1);
465 ret
466 }
467 }
468
469 /// Removes an element from the vector and returns it.
470 ///
471 /// The removed element is replaced by the last element of the vector.
472 ///
473 /// This does not preserve ordering, but is O(1).
474 ///
475 /// # Panics
476 ///
477 /// Panics if `index` is out of bounds.
478 ///
479 /// # Examples
480 ///
481 /// ```
482 /// use stack_buf::StackVec;
483 ///
484 /// let mut v = StackVec::from(["foo", "bar", "baz", "qux"]);
485 ///
486 /// assert_eq!(v.swap_remove(1), "bar");
487 /// assert_eq!(&v[..], ["foo", "qux", "baz"]);
488 ///
489 /// assert_eq!(v.swap_remove(0), "foo");
490 /// assert_eq!(&v[..], ["baz", "qux"]);
491 /// ```
492 #[inline]
493 pub fn swap_remove(&mut self, index: usize) -> T {
494 #[cold]
495 #[inline(never)]
496 fn assert_failed(index: usize, len: usize) -> ! {
497 panic!(
498 "swap_remove index (is {}) should be < len (is {})",
499 index, len
500 );
501 }
502
503 let len = self.len();
504 if index >= len {
505 assert_failed(index, len);
506 }
507 unsafe {
508 // We replace self[index] with the last element. Note that if the
509 // bounds check above succeeds there must be a last element (which
510 // can be self[index] itself).
511 let last = ptr::read(self.as_ptr().add(len - 1));
512 let hole = self.as_mut_ptr().add(index);
513 self.set_len(len - 1);
514 ptr::replace(hole, last)
515 }
516 }
517
518 /// Create a draining iterator that removes the specified range in the vector
519 /// and yields the removed items from start to end. The element range is
520 /// removed even if the iterator is not consumed until the end.
521 ///
522 /// Note: It is unspecified how many elements are removed from the vector,
523 /// if the `Drain` value is leaked.
524 ///
525 /// # Panics
526 /// If the starting point is greater than the end point or if
527 /// the end point is greater than the length of the vector.
528 ///
529 /// # Examples
530 ///
531 /// ```
532 /// use stack_buf::StackVec;
533 ///
534 /// let mut v1 = StackVec::from([1, 2, 3]);
535 /// let v2: StackVec<_, 3> = v1.drain(0..2).collect();
536 /// assert_eq!(&v1[..], &[3]);
537 /// assert_eq!(&v2[..], &[1, 2]);
538 /// ```
539 #[inline]
540 pub fn drain<R>(&mut self, range: R) -> Drain<T, N>
541 where
542 R: RangeBounds<usize>,
543 {
544 // Memory safety
545 //
546 // When the Drain is first created, it shortens the length of
547 // the source vector to make sure no uninitialized or moved-from elements
548 // are accessible at all if the Drain's destructor never gets to run.
549 //
550 // Drain will ptr::read out the values to remove.
551 // When finished, remaining tail of the vec is copied back to cover
552 // the hole, and the vector length is restored to the new length.
553 //
554 let len = self.len();
555 let start = match range.start_bound() {
556 Bound::Unbounded => 0,
557 Bound::Included(&i) => i,
558 Bound::Excluded(&i) => i.saturating_add(1),
559 };
560 let end = match range.end_bound() {
561 Bound::Excluded(&j) => j,
562 Bound::Included(&j) => j.saturating_add(1),
563 Bound::Unbounded => len,
564 };
565
566 // bounds check happens here (before length is changed!)
567 let range_slice: *const _ = &self[start..end];
568
569 // Calling `set_len` creates a fresh and thus unique mutable references, making all
570 // older aliases we created invalid. So we cannot call that function.
571 self.len = start as Size;
572
573 unsafe {
574 Drain {
575 tail_start: end,
576 tail_len: len - end,
577 iter: (*range_slice).iter(),
578 vec: NonNull::new_unchecked(self as *mut _),
579 }
580 }
581 }
582
583 /// Retains only the elements specified by the predicate.
584 ///
585 /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
586 /// This method operates in place and preserves the order of the retained
587 /// elements.
588 ///
589 /// # Examples
590 ///
591 /// ```
592 /// use stack_buf::StackVec;
593 ///
594 /// let mut vec = StackVec::from([1, 2, 3, 4]);
595 /// vec.retain(|x| *x & 1 != 0 );
596 /// assert_eq!(&vec[..], &[1, 3]);
597 /// ```
598 #[inline]
599 pub fn retain<F>(&mut self, mut f: F)
600 where
601 F: FnMut(&mut T) -> bool,
602 {
603 let mut del = 0;
604 let len = self.len();
605 for i in 0..len {
606 if !f(&mut self[i]) {
607 del += 1;
608 } else if del > 0 {
609 self.swap(i - del, i);
610 }
611 }
612 self.truncate(len - del);
613 }
614
615 /// Removes all but the first of consecutive elements in the vector satisfying a given equality
616 /// relation.
617 ///
618 /// The `same_bucket` function is passed references to two elements from the vector and
619 /// must determine if the elements compare equal. The elements are passed in opposite order
620 /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is removed.
621 ///
622 /// If the vector is sorted, this removes all duplicates.
623 ///
624 /// # Examples
625 ///
626 /// ```
627 /// use stack_buf::stack_vec;
628 ///
629 /// let mut vec = stack_vec!["foo", "bar", "Bar", "baz", "bar"];
630 ///
631 /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
632 ///
633 /// assert_eq!(&vec[..], ["foo", "bar", "baz", "bar"]);
634 /// ```
635 pub fn dedup_by<F>(&mut self, mut same_bucket: F)
636 where
637 F: FnMut(&mut T, &mut T) -> bool,
638 {
639 // See the implementation of Vec::dedup_by in the
640 // standard library for an explanation of this algorithm.
641 let len = self.len();
642 if len <= 1 {
643 return;
644 }
645
646 let ptr = self.as_mut_ptr();
647 let mut w: usize = 1;
648
649 unsafe {
650 for r in 1..len {
651 let p_r = ptr.add(r);
652 let p_wm1 = ptr.add(w - 1);
653 if !same_bucket(&mut *p_r, &mut *p_wm1) {
654 if r != w {
655 let p_w = p_wm1.add(1);
656 std::mem::swap(&mut *p_r, &mut *p_w);
657 }
658 w += 1;
659 }
660 }
661 }
662
663 self.truncate(w);
664 }
665
666 /// Removes all but the first of consecutive elements in the vector that resolve to the same
667 /// key.
668 ///
669 /// If the vector is sorted, this removes all duplicates.
670 ///
671 /// # Examples
672 ///
673 /// ```
674 /// use stack_buf::stack_vec;
675 ///
676 /// let mut vec = stack_vec![10, 20, 21, 30, 20];
677 ///
678 /// vec.dedup_by_key(|i| *i / 10);
679 ///
680 /// assert_eq!(&vec[..], [10, 20, 30, 20]);
681 /// ```
682 #[inline]
683 pub fn dedup_by_key<F, K>(&mut self, mut key: F)
684 where
685 F: FnMut(&mut T) -> K,
686 K: PartialEq,
687 {
688 self.dedup_by(|a, b| key(a) == key(b))
689 }
690}
691
692impl<T: Clone, const N: usize> StackVec<T, N> {
693 /// Creates a `StackVec` with `n` copies of `elem`.
694 ///
695 /// # Panics
696 ///
697 /// This function will panic if the `n > N`.
698 ///
699 /// # Examples
700 ///
701 /// ```
702 /// use stack_buf::StackVec;
703 ///
704 /// let vec = StackVec::<char, 128>::from_elem('d', 2);
705 /// assert_eq!(&vec[..], ['d', 'd']);
706 /// ```
707 #[inline]
708 pub fn from_elem(elem: T, n: usize) -> Self {
709 let mut vec = StackVec::<T, N>::new();
710 vec.push_elem(elem, n);
711 vec
712 }
713
714 /// Appends `n` copies of `elem` to the `StackVec`.
715 ///
716 /// # Panics
717 ///
718 /// This function will panic if the `self.remaining_capacity() < n`.
719 ///
720 /// # Examples
721 ///
722 /// ```
723 /// use stack_buf::StackVec;
724 ///
725 /// let mut vec = StackVec::<char, 10>::new();
726 /// vec.push('a');
727 /// vec.push_elem('d', 2);
728 /// assert_eq!(&vec[..], ['a', 'd', 'd']);
729 /// ```
730 #[inline]
731 pub fn push_elem(&mut self, elem: T, n: usize) {
732 assert!(self.remaining_capacity() >= n);
733 unsafe {
734 let ptr = self.as_mut_ptr();
735 let mut local_len = SetLenOnDrop::new(&mut self.len);
736 for _ in 0..n {
737 ptr::write(ptr.offset(local_len.local_len as isize), elem.clone());
738 local_len.increment_len(1);
739 }
740 }
741 }
742
743 /// Clones and appends all elements in a slice to the `StackVec`.
744 ///
745 /// Iterates over the slice `other`, clones each element, and then appends
746 /// it to this `StackVec`. The `other` vector is traversed in-order.
747 ///
748 /// # Panics
749 ///
750 /// This function will panic if `self.remaining_capacity() < other.len()`.
751 ///
752 /// # Examples
753 ///
754 /// ```
755 /// use stack_buf::{StackVec, stack_vec};
756 /// let mut vec = stack_vec![10#1];
757 /// vec.extend_from_slice(&[2, 3, 4]);
758 /// assert_eq!(&vec[..], [1, 2, 3, 4]);
759 /// ```
760 #[inline]
761 pub fn extend_from_slice(&mut self, other: &[T]) {
762 assert!(self.remaining_capacity() >= other.len());
763 unsafe {
764 let ptr = self.as_mut_ptr();
765 let mut local_len = SetLenOnDrop::new(&mut self.len);
766 for elem in other {
767 ptr::write(ptr.offset(local_len.local_len as isize), elem.clone());
768 local_len.increment_len(1);
769 }
770 }
771 }
772
773 /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
774 ///
775 /// If `new_len` is greater than `len`, the `Vec` is extended by the
776 /// difference, with each additional slot filled with `value`.
777 /// If `new_len` is less than `len`, the `Vec` is simply truncated.
778 ///
779 /// This method requires `T` to implement [`Clone`],
780 /// in order to be able to clone the passed value.
781 ///
782 /// # Panics
783 ///
784 /// This function will be panic if `new_len > self.capacity()`.
785 ///
786 /// # Examples
787 ///
788 /// ```
789 /// use stack_buf::{StackVec, stack_vec};
790 ///
791 /// let mut vec = stack_vec![5#"hello"];
792 /// vec.resize(3, "world");
793 /// assert_eq!(&vec[..], ["hello", "world", "world"]);
794 ///
795 /// let mut vec = stack_vec![1, 2, 3, 4];
796 /// vec.resize(2, 0);
797 /// assert_eq!(&vec[..], [1, 2]);
798 /// ```
799 #[inline]
800 pub fn resize(&mut self, new_len: usize, value: T) {
801 assert!(new_len <= self.capacity());
802 let len = self.len();
803
804 if new_len > len {
805 self.push_elem(value, new_len - len);
806 } else {
807 self.truncate(new_len);
808 }
809 }
810}
811
812impl<T: Copy, const N: usize> StackVec<T, N> {
813 /// Copies all elements from `src` into `self`, using a memcpy.
814 ///
815 /// The length of `src` must be less than or equals `self`'s remaining capacity.
816 ///
817 /// If `T` does not implement `Copy`, use [`StackVec::extend_from_slice()`].
818 ///
819 /// # Panics
820 ///
821 /// This function will panic if the length of `self.remaining_capacity() < src.len()`.
822 ///
823 /// # Examples
824 ///
825 /// Copying two elements from a slice into a `StackVec`:
826 ///
827 /// ```
828 /// use stack_buf::StackVec;
829 ///
830 /// let src = [1, 2, 3, 4];
831 /// let mut dst = StackVec::<_, 8>::new();
832 ///
833 /// dst.copy_from_slice(&src[2..]);
834 ///
835 /// assert_eq!(src, [1, 2, 3, 4]);
836 /// assert_eq!(&dst[..], [3, 4]);
837 /// ```
838 #[inline]
839 pub fn copy_from_slice(&mut self, src: &[T]) {
840 assert!(self.remaining_capacity() >= src.len());
841
842 unsafe {
843 let dest = self.as_mut_ptr().add(self.len());
844 ptr::copy_nonoverlapping(src.as_ptr(), dest, src.len());
845 self.set_len(self.len() + src.len());
846 }
847 }
848}
849
850impl<T, const N: usize> Drop for StackVec<T, N> {
851 #[inline]
852 fn drop(&mut self) {
853 unsafe { ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.as_mut_ptr(), self.len())) }
854 }
855}
856
857/// Creates a `StackVec` from an array.
858///
859/// # Examples
860///
861/// ```
862/// use stack_buf::StackVec;
863///
864/// let mut vec = StackVec::from([1, 2, 3]);
865/// assert_eq!(vec.len(), 3);
866/// assert_eq!(vec.capacity(), 3);
867/// ```
868impl<T, const N: usize> From<[T; N]> for StackVec<T, N> {
869 #[inline]
870 fn from(array: [T; N]) -> Self {
871 let array = ManuallyDrop::new(array);
872 let mut vec = StackVec::<T, N>::new();
873 unsafe {
874 (&*array as *const [T; N] as *const [MaybeUninit<T>; N])
875 .copy_to_nonoverlapping(&mut vec.vec as *mut [MaybeUninit<T>; N], 1);
876 vec.set_len(N);
877 }
878 vec
879 }
880}
881
882impl<T, const N: usize> Clone for StackVec<T, N>
883where
884 T: Clone,
885{
886 #[inline]
887 fn clone(&self) -> Self {
888 self.iter().cloned().collect()
889 }
890
891 #[inline]
892 fn clone_from(&mut self, source: &Self) {
893 self.clear();
894 self.extend_from_slice(source);
895 }
896}
897
898impl<T, const N: usize> Deref for StackVec<T, N> {
899 type Target = [T];
900
901 #[inline(always)]
902 fn deref(&self) -> &[T] {
903 self.as_slice()
904 }
905}
906
907impl<T, const N: usize> DerefMut for StackVec<T, N> {
908 #[inline(always)]
909 fn deref_mut(&mut self) -> &mut [T] {
910 self.as_mut_slice()
911 }
912}
913
914impl<T, const N: usize> AsRef<[T]> for StackVec<T, N> {
915 #[inline(always)]
916 fn as_ref(&self) -> &[T] {
917 self.as_slice()
918 }
919}
920
921impl<T, const N: usize> AsMut<[T]> for StackVec<T, N> {
922 #[inline(always)]
923 fn as_mut(&mut self) -> &mut [T] {
924 self.as_mut_slice()
925 }
926}
927
928impl<T, const N: usize> Borrow<[T]> for StackVec<T, N> {
929 #[inline(always)]
930 fn borrow(&self) -> &[T] {
931 self.as_slice()
932 }
933}
934
935impl<T, const N: usize> BorrowMut<[T]> for StackVec<T, N> {
936 #[inline(always)]
937 fn borrow_mut(&mut self) -> &mut [T] {
938 self.as_mut_slice()
939 }
940}
941
942impl<T, const N: usize> Default for StackVec<T, N> {
943 /// Creates an empty `StackVec<T, N>`.
944 #[inline(always)]
945 fn default() -> StackVec<T, N> {
946 StackVec::new()
947 }
948}
949
950impl<T: fmt::Debug, const N: usize> fmt::Debug for StackVec<T, N> {
951 #[inline]
952 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
953 fmt::Debug::fmt(&**self, f)
954 }
955}
956
957impl<T, const N: usize> Hash for StackVec<T, N>
958where
959 T: Hash,
960{
961 #[inline]
962 fn hash<H: Hasher>(&self, state: &mut H) {
963 Hash::hash(&**self, state)
964 }
965}
966
967impl<T, const N1: usize, const N2: usize> PartialEq<StackVec<T, N2>> for StackVec<T, N1>
968where
969 T: PartialEq,
970{
971 #[inline]
972 fn eq(&self, other: &StackVec<T, N2>) -> bool {
973 **self == **other
974 }
975}
976
977impl<T, const N: usize> PartialEq<[T]> for StackVec<T, N>
978where
979 T: PartialEq,
980{
981 #[inline]
982 fn eq(&self, other: &[T]) -> bool {
983 **self == *other
984 }
985}
986
987impl<T, const N: usize> Eq for StackVec<T, N> where T: Eq {}
988
989impl<T: PartialOrd, const N1: usize, const N2: usize> PartialOrd<StackVec<T, N2>>
990 for StackVec<T, N1>
991{
992 #[inline]
993 fn partial_cmp(&self, other: &StackVec<T, N2>) -> Option<Ordering> {
994 PartialOrd::partial_cmp(&**self, &**other)
995 }
996}
997
998impl<T: Ord, const N: usize> Ord for StackVec<T, N> {
999 #[inline]
1000 fn cmp(&self, other: &Self) -> Ordering {
1001 Ord::cmp(&**self, &**other)
1002 }
1003}
1004
1005#[cfg(feature = "std")]
1006#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
1007impl<const N: usize> std::io::Write for StackVec<u8, N> {
1008 #[inline]
1009 fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
1010 self.copy_from_slice(buf);
1011 Ok(buf.len())
1012 }
1013
1014 #[inline]
1015 fn flush(&mut self) -> std::io::Result<()> {
1016 Ok(())
1017 }
1018}
1019
1020impl<const N: usize> fmt::Write for StackVec<u8, N> {
1021 #[inline]
1022 fn write_str(&mut self, s: &str) -> fmt::Result {
1023 self.copy_from_slice(s.as_bytes());
1024 Ok(())
1025 }
1026}
1027
1028impl<T, const N: usize> Index<usize> for StackVec<T, N> {
1029 type Output = T;
1030
1031 #[inline]
1032 fn index(&self, index: usize) -> &Self::Output {
1033 &self.as_slice()[index]
1034 }
1035}
1036
1037impl<T, const N: usize> IndexMut<usize> for StackVec<T, N> {
1038 #[inline]
1039 fn index_mut(&mut self, index: usize) -> &mut Self::Output {
1040 &mut self.as_mut_slice()[index]
1041 }
1042}
1043
1044impl<T, const N: usize> Index<RangeFull> for StackVec<T, N> {
1045 type Output = [T];
1046
1047 #[inline]
1048 fn index(&self, _index: RangeFull) -> &Self::Output {
1049 self.as_slice()
1050 }
1051}
1052
1053impl<T, const N: usize> IndexMut<RangeFull> for StackVec<T, N> {
1054 #[inline]
1055 fn index_mut(&mut self, _index: RangeFull) -> &mut Self::Output {
1056 self.as_mut_slice()
1057 }
1058}
1059
1060macro_rules! impl_range_index {
1061 ($idx_ty: ty) => {
1062 impl<T, const N: usize> Index<$idx_ty> for StackVec<T, N> {
1063 type Output = [T];
1064
1065 #[inline]
1066 fn index(&self, index: $idx_ty) -> &Self::Output {
1067 &self.as_slice()[index]
1068 }
1069 }
1070
1071 impl<T, const N: usize> IndexMut<$idx_ty> for StackVec<T, N> {
1072 #[inline]
1073 fn index_mut(&mut self, index: $idx_ty) -> &mut Self::Output {
1074 &mut self.as_mut_slice()[index]
1075 }
1076 }
1077 };
1078 ($($idx_ty: ty),+ $(,)?) => {
1079 $(impl_range_index!($idx_ty);)+
1080 }
1081}
1082
1083impl_range_index!(
1084 Range<usize>,
1085 RangeFrom<usize>,
1086 RangeInclusive<usize>,
1087 RangeTo<usize>,
1088 RangeToInclusive<usize>,
1089);
1090
1091impl<T, const N: usize> Extend<T> for StackVec<T, N> {
1092 #[inline]
1093 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1094 for elem in iter.into_iter() {
1095 self.push(elem);
1096 }
1097 }
1098}
1099
1100impl<T, const N: usize> FromIterator<T> for StackVec<T, N> {
1101 #[inline]
1102 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1103 let mut vec = StackVec::new();
1104 vec.extend(iter);
1105 vec
1106 }
1107}
1108
1109/// Iterate the `StackVec` with references to each element.
1110///
1111/// ```
1112/// use stack_buf::StackVec;
1113///
1114/// let vec = StackVec::from([1, 2, 3]);
1115///
1116/// for ele in &vec {
1117/// // ...
1118/// }
1119/// ```
1120impl<'a, T, const N: usize> IntoIterator for &'a StackVec<T, N> {
1121 type Item = &'a T;
1122 type IntoIter = slice::Iter<'a, T>;
1123
1124 #[inline]
1125 fn into_iter(self) -> Self::IntoIter {
1126 self.iter()
1127 }
1128}
1129
1130/// Iterate the `StackVec` with mutable references to each element.
1131///
1132/// ```
1133/// use stack_buf::StackVec;
1134///
1135/// let mut vec = StackVec::from([1, 2, 3]);
1136///
1137/// for ele in &mut vec {
1138/// // ...
1139/// }
1140/// ```
1141impl<'a, T, const N: usize> IntoIterator for &'a mut StackVec<T, N> {
1142 type Item = &'a mut T;
1143 type IntoIter = slice::IterMut<'a, T>;
1144
1145 #[inline]
1146 fn into_iter(self) -> Self::IntoIter {
1147 self.iter_mut()
1148 }
1149}
1150
1151/// Iterate the `StackVec` with each element by value.
1152///
1153/// The vector is consumed by this operation.
1154///
1155/// ```
1156/// use stack_buf::StackVec;
1157///
1158/// for ele in StackVec::from([1, 2, 3]) {
1159/// // ...
1160/// }
1161/// ```
1162impl<T, const N: usize> IntoIterator for StackVec<T, N> {
1163 type Item = T;
1164 type IntoIter = IntoIter<T, N>;
1165
1166 #[inline]
1167 fn into_iter(self) -> Self::IntoIter {
1168 IntoIter {
1169 vec: self,
1170 index: 0,
1171 }
1172 }
1173}
1174
1175/// An iterator that consumes a `StackVec` and yields its items by value.
1176///
1177/// Returned from [`StackVec::into_iter()`].
1178pub struct IntoIter<T, const N: usize> {
1179 vec: StackVec<T, N>,
1180 index: usize,
1181}
1182
1183impl<T, const N: usize> Iterator for IntoIter<T, N> {
1184 type Item = T;
1185
1186 #[inline]
1187 fn next(&mut self) -> Option<Self::Item> {
1188 if self.index == self.vec.len() {
1189 None
1190 } else {
1191 unsafe {
1192 let index = self.index;
1193 self.index = index + 1;
1194 Some(ptr::read(self.vec.as_mut_ptr().add(index)))
1195 }
1196 }
1197 }
1198
1199 #[inline]
1200 fn size_hint(&self) -> (usize, Option<usize>) {
1201 let len = self.vec.len() - self.index;
1202 (len, Some(len))
1203 }
1204}
1205
1206impl<T, const N: usize> DoubleEndedIterator for IntoIter<T, N> {
1207 #[inline]
1208 fn next_back(&mut self) -> Option<Self::Item> {
1209 if self.index == self.vec.len() {
1210 None
1211 } else {
1212 unsafe {
1213 let new_len = self.vec.len() - 1;
1214 self.vec.set_len(new_len);
1215 Some(ptr::read(self.vec.as_mut_ptr().add(new_len)))
1216 }
1217 }
1218 }
1219}
1220
1221impl<T, const N: usize> ExactSizeIterator for IntoIter<T, N> {}
1222
1223impl<T, const N: usize> Drop for IntoIter<T, N> {
1224 #[inline]
1225 fn drop(&mut self) {
1226 let index = self.index;
1227 let len = self.vec.len();
1228 unsafe {
1229 self.vec.set_len(0);
1230 let elements = slice::from_raw_parts_mut(self.vec.as_mut_ptr().add(index), len - index);
1231 ptr::drop_in_place(elements);
1232 }
1233 }
1234}
1235
1236impl<T: fmt::Debug, const N: usize> fmt::Debug for IntoIter<T, N> {
1237 #[inline]
1238 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1239 f.debug_list().entries(&self.vec[self.index..]).finish()
1240 }
1241}
1242
1243#[cfg(feature = "serde")]
1244mod impl_serde {
1245 use super::*;
1246 use serde::de::{Error, SeqAccess, Visitor};
1247 use serde::{Deserialize, Deserializer, Serialize, Serializer};
1248 use std::marker::PhantomData;
1249
1250 #[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1251 impl<T: Serialize, const N: usize> Serialize for StackVec<T, N> {
1252 #[inline]
1253 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1254 where
1255 S: Serializer,
1256 {
1257 serializer.collect_seq(self.as_slice())
1258 }
1259 }
1260
1261 #[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1262 impl<'de, T: Deserialize<'de>, const N: usize> Deserialize<'de> for StackVec<T, N> {
1263 #[inline]
1264 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1265 where
1266 D: Deserializer<'de>,
1267 {
1268 struct StackVecVisitor<'de, T: Deserialize<'de>, const N: usize>(
1269 PhantomData<(&'de (), [T; N])>,
1270 );
1271
1272 impl<'de, T: Deserialize<'de>, const N: usize> Visitor<'de> for StackVecVisitor<'de, T, N> {
1273 type Value = StackVec<T, N>;
1274
1275 fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
1276 write!(formatter, "an array with no more than {} items", N)
1277 }
1278
1279 #[inline]
1280 fn visit_seq<SA>(self, mut seq: SA) -> Result<Self::Value, SA::Error>
1281 where
1282 SA: SeqAccess<'de>,
1283 {
1284 let mut values = StackVec::<T, N>::new();
1285
1286 while let Some(value) = seq.next_element()? {
1287 if values.is_full() {
1288 return Err(SA::Error::invalid_length(N + 1, &self));
1289 }
1290
1291 values.push(value);
1292 }
1293
1294 Ok(values)
1295 }
1296 }
1297
1298 deserializer.deserialize_seq(StackVecVisitor::<T, N>(PhantomData))
1299 }
1300 }
1301}
1302
1303/// Creates a [`StackVec`] containing the arguments.
1304///
1305/// `stack_vec!` allows `StackVec`s to be defined with the same syntax as array expressions.
1306/// There are two forms of this macro:
1307///
1308/// - Creates a empty [`StackVec`]:
1309///
1310/// ```
1311/// use stack_buf::{StackVec, stack_vec};
1312///
1313/// let vec: StackVec<i32, 8> = stack_vec![];
1314/// assert!(vec.is_empty());
1315/// assert_eq!(vec.capacity(), 8);
1316///
1317/// let vec = stack_vec![i32; 16];
1318/// assert!(vec.is_empty());
1319/// assert_eq!(vec.capacity(), 16);
1320/// ```
1321///
1322/// - Creates a [`StackVec`] containing a given list of elements:
1323///
1324/// ```
1325/// use stack_buf::{StackVec, stack_vec};
1326///
1327/// let vec = stack_vec![128#1, 2, 3];
1328/// assert_eq!(vec.capacity(), 128);
1329/// assert_eq!(vec[0], 1);
1330/// assert_eq!(vec[1], 2);
1331/// assert_eq!(vec[2], 3);
1332///
1333/// let vec = stack_vec![1, 2, 3];
1334/// assert_eq!(vec.capacity(), 3);
1335///
1336/// ```
1337///
1338/// - Creates a [`StackVec`] from a given element and size:
1339///
1340/// ```
1341/// use stack_buf::{StackVec, stack_vec};
1342///
1343/// let v = stack_vec![0x8000#1; 3];
1344/// assert_eq!(v.as_slice(), [1, 1, 1]);
1345/// assert_eq!(v.capacity(), 0x8000);
1346///
1347/// let v = stack_vec![1; 3];
1348/// assert_eq!(v.capacity(), 3);
1349/// ```
1350///
1351/// Note that unlike array expressions this syntax supports all elements
1352/// which implement [`Clone`] and the number of elements doesn't have to be
1353/// a constant.
1354///
1355/// This will use `clone` to duplicate an expression, so one should be careful
1356/// using this with types having a nonstandard `Clone` implementation. For
1357/// example, `stack_vec![Rc::new(1); 5]` will create a vector of five references
1358/// to the same boxed integer value, not five references pointing to independently
1359/// boxed integers.
1360#[macro_export]
1361macro_rules! stack_vec {
1362 () => ($crate::StackVec::new());
1363 ($ty: ty; $cap: literal) => ($crate::StackVec::<$ty, $cap>::new());
1364 ($elem:expr; $n:expr) => ({
1365 $crate::StackVec::<_, $n>::from_elem($elem, $n)
1366 });
1367 ($cap:literal# $elem:expr; $n:expr) => ({
1368 $crate::StackVec::<_, $cap>::from_elem($elem, $n)
1369 });
1370 ($($x:expr),+ $(,)?) => ({
1371 $crate::StackVec::from([$($x),+])
1372 });
1373 ($cap:literal# $($x:expr),+ $(,)?) => ({
1374 let mut vec = $crate::StackVec::<_, $cap>::new();
1375 $(vec.push($x);)+
1376 vec
1377 });
1378}