stack_vec/
lib.rs

1//! # Ad-hoc stack vectors
2//! This crate defines the macro `stack![]`, which can be used to create ad-hoc `Vec<T>` like structs of a specific compile-time size on the stack.
3//! These structs never allocate on the heap, and expose an API similar to `Vec<T>`.
4//! ## Usage
5//! The macro can be used like `vec!`, with optional type inference.
6//!
7//! ```
8//! # use stack_vec::stack;
9//! let mut sv = stack![100]; // Implicitly typed.
10//! sv.push(10usize);
11//! let sv = stack![usize; 100]; // Explicitly typed, circumvents that error.
12//! ```
13//!
14//! To see documentation of the types themselves, see one of the pre-defined `StackVec` types in the crate's root.
15//! # Pre-defined types
16//! `StackVec` types of powers of 2 up until 4096 are defined in this crate too.
17//!
18//! You can use the macro to create your own named non-opaque `StackVec` types as well.
19//! ```
20//! # use stack_vec::stack;
21//! stack!(pub type S10Elements S10IntoIter 10); // A `StackVec` type with a capacity of 10.
22//! ```
23
24
25/// Create an ad-hoc sized `Vec`-like array on the stack.
26///
27/// # Usage
28/// ```
29/// # use stack_vec::stack;
30/// let sv = stack![usize; 100];
31/// assert_eq!(sv.cap(), 100);
32/// ```
33///
34/// Can be used mostly just like `Vec<T>`, except the size must be a literal.
35/// ```
36/// # use stack_vec::stack;
37/// let mut sv = stack![12];
38/// for x in 0..12 {
39///  sv.push(vec![x,x]);
40/// }
41/// assert_eq!(sv.into_iter().map(|x| x.into_iter().product::<i32>()).sum::<i32>(), (0..12).map(|x| x*x).sum::<i32>());
42/// ```
43/// # Defining `StackVec` types
44/// You can also use this macro to define your own transparent `StackVec` types
45/// ```
46/// # use stack_vec::stack;
47/// stack!(pub type StackVec10 StackVec10IntoIter 10);
48///
49/// let sv: StackVec10<_> = [1i32; 10].iter().copied().collect();
50/// let sv: StackVec10IntoIter<_> = sv.into_iter();
51/// assert_eq!(sv.sum::<i32>(), 10);
52/// ```
53///
54/// See one of the `StackVec` structs defined here for more information.
55#[macro_export] macro_rules! stack {
56    ($($q:tt)? type $name:ident $into_iter_name:ident $n:literal) => {
57
58	#[allow(unused_doc_comments)]
59	#[doc="A sized stack vector"]
60	$($q)? struct $name<T>([::std::mem::MaybeUninit<T>; $n], usize);
61
62	impl<T> $name<T>
63	{
64	    #![allow(dead_code)]
65	    
66	    /// The max capacity of this `StackVec` type
67	    pub const CAPACITY: usize = $n;
68
69	    /// The max capacity of this `StackVec`
70	    ///
71	    /// # Note
72	    /// Identical to `Self::CAPACITY`, however more convenient for ad-hoc types created through `stack![n]`.
73	    #[inline] pub const fn cap(&self) -> usize
74	    {
75		Self::CAPACITY
76	    }
77
78	    /// Create a new empty `StackVec`.
79	    #[inline] pub fn new() -> Self
80	    {
81		use std::mem::MaybeUninit;
82		unsafe {
83		    Self(MaybeUninit::uninit().assume_init(), 0) // for now we can't make this `const fn` :(
84		}
85	    }
86
87	    /// Extend from a slice where `T: Copy`.
88	    ///
89	    /// Returns the number of elements copied. If the copy would overflow the capacity the rest is ignored.
90	    #[inline] pub fn extend_from_slice_copy<U: AsRef<[T]>>(&mut self, slice: U) -> usize
91	    where T: Copy
92	    {
93		let rest = unsafe {self.rest_mut()};
94		let slice = slice.as_ref();
95		let len = std::cmp::min(rest.len(),slice.len());
96
97		unsafe {
98		    std::ptr::copy(slice.as_ptr(), rest.as_mut_ptr() as *mut std::mem::MaybeUninit<T> as *mut T, len);
99		}
100		self.1+=len;
101		
102		len
103	    }
104
105	    /// Extend from a slice where `T: Clone`
106	    ///
107	    /// Returns the number of elements copied. If the copy would overflow the capacity the rest is ignored.
108	    pub fn extend_from_slice<U: AsRef<[T]>>(&mut self, slice: U) -> usize
109	    where T: ::std::clone::Clone
110	    {
111		let rest = &mut self.0[self.1..];
112		let slice = slice.as_ref();
113
114		let mut wrote=0;
115		for (d,s) in rest.iter_mut().zip(slice.iter())
116		{
117		    *d = std::mem::MaybeUninit::new(s.clone());
118		    self.1+=1;
119		    wrote+=1;
120		}
121		wrote
122	    }
123
124	    /// Try to push an element on to the end of the `StackVec`.
125	    ///
126	    /// If it is full, return the value as `Err(T)` instead.
127	    #[inline(always)] pub fn try_push(&mut self, value: T) -> Result<(), T>
128	    {
129		if self.1 < Self::CAPACITY {
130		    self.0[self.1] = std::mem::MaybeUninit::new(value);
131		    self.1+=1;
132		    Ok(())
133		} else {
134		    Err(value)
135		}
136	    }
137
138	    /// Push an element on the the end of the `StackVec`.
139	    ///
140	    /// # Panics
141	    /// If the `StackVec` is full.
142	    #[inline] pub fn push(&mut self, value: T)
143	    {
144		#[cold] fn off_end() -> ! {
145		    panic!(concat!("Tried to push off the end of `StackVec", stringify!($n), "`"));
146		}
147		if self.1 < Self::CAPACITY {
148		    self.0[self.1] = std::mem::MaybeUninit::new(value);
149		    self.1+=1;
150		} else {
151		    off_end()
152		}
153	    }
154
155	    /// The number of elements currently in the `StackVec`.
156	    #[inline] pub fn len(&self) -> usize
157	    {
158		self.1
159	    }
160
161	    /// A slice of the elements in the `StackVec`.
162	    #[inline(always)] pub fn as_slice(&self) -> &[T]
163	    {
164		unsafe { &*(&self.0[..self.1] as *const [std::mem::MaybeUninit<T>] as *const [T]) }
165	    }
166	    /// A mutable slice of the elements in the `StackVec`.
167	    #[inline(always)] pub fn as_mut_slice(&mut self) -> &mut [T]
168	    {
169		unsafe { &mut *(&mut self.0[..self.1] as *mut [std::mem::MaybeUninit<T>] as *mut [T]) }
170	    }
171
172	    /// A mutable slice of the initialised part of the buffer.
173	    ///
174	    /// All elements of the returned slice are initialised.
175	    #[inline(always)] pub fn init_buffer_mut(&mut self) -> &mut [std::mem::MaybeUninit<T>]
176	    {
177		&mut self.0[..self.1]
178	    }
179	    
180	    /// The initialised part of the buffer.
181	    ///
182	    /// All elements of the returned slice are initialised.
183	    #[inline(always)] pub fn init_buffer(&self) -> &[std::mem::MaybeUninit<T>]
184	    {
185		&self.0[..self.1]
186	    }
187
188	    /// A mutable reference to the uninitialised part of the instance.
189	    ///
190	    /// No elements of the returned slice are initialised.
191	    /// # Note
192	    /// If you initialise some, you must remember to update the length with `set_len()`.
193	    #[inline(always)] pub unsafe fn rest_mut(&mut self) -> &mut [std::mem::MaybeUninit<T>]
194	    {
195		&mut self.0[self.1..]
196	    }
197	    /// The uninitialised part of the instance.
198	    ///
199	    /// No elements of the returned slice are initialised.
200	    #[inline(always)] pub fn rest(&self) -> &[std::mem::MaybeUninit<T>]
201	    {
202		&self.0[self.1..]
203	    }
204
205	    /// A mutable reference to the whole capacity buffer.
206	    ///
207	    /// `..self.len()` will be initialised, `self.len()..` will be uninitialised.
208	    ///
209	    /// # Note
210	    /// If you initialise or uninitialise some element(s), you must remember to update the length with `set_len()`.
211	    #[inline] pub unsafe fn buffer_mut(&mut self) -> &mut [std::mem::MaybeUninit<T>; $n]
212	    {
213		&mut self.0
214	    }
215	    /// A reference to the whole capacity buffer.
216	    ///
217	    /// `..self.len()` will be initialised, `self.len()..` will be uninitialised.
218	    #[inline] pub fn buffer(&self) -> &[std::mem::MaybeUninit<T>; $n]
219	    {
220		&self.0
221	    }
222	    /// Set the internal fill pointer of the `StackVec`.
223	    ///
224	    /// This changes how much of the buffer is assumed to be initialised.
225	    /// Only use this if you have manually initialised some of the uninitialised buffer, as it does no initialising itself.
226	    #[inline] pub unsafe fn set_len(&mut self, len: usize)
227	    {
228		self.1 = len;
229	    }
230	}
231
232	impl<T> ::std::ops::Drop for $name<T>
233	{
234	    fn drop(&mut self)
235	    {
236		if std::mem::needs_drop::<T>() {
237		    for init in &mut self.0[..self.1]
238		    {
239			unsafe {
240			    drop(std::mem::replace(init, std::mem::MaybeUninit::uninit()).assume_init());
241			}
242		    }
243		}
244	    }
245	}
246
247	
248	impl<T> ::std::ops::DerefMut for $name<T>
249	{
250	    #[inline] fn deref_mut(&mut self) -> &mut Self::Target
251	    {
252		self.as_mut_slice()
253	    }
254	}
255	impl<T> ::std::ops::Deref for $name<T>
256	{
257	    type Target = [T];
258
259	    #[inline] fn deref(&self) -> &Self::Target
260	    {
261		self.as_slice()
262	    }
263	}
264	impl<T> ::std::convert::AsRef<[T]> for $name<T>
265	{
266	    #[inline] fn as_ref(&self) -> &[T]
267	    {
268		self.as_slice()
269	    }
270	}
271	impl<T> ::std::convert::AsMut<[T]> for $name<T>
272	{
273	    #[inline] fn as_mut(&mut self) -> &mut [T]
274	    {
275		self.as_mut_slice()
276	    }
277	}
278	impl<T> ::std::borrow::Borrow<[T]> for $name<T>
279	{
280	    #[inline] fn borrow(&self) -> &[T]
281	    {
282		self.as_slice()
283	    }
284	}
285	impl<T> ::std::borrow::BorrowMut<[T]> for $name<T>
286	{
287	    #[inline] fn borrow_mut(&mut self) -> &mut [T]
288	    {
289		self.as_mut_slice()
290	    }
291	}
292	impl<T> ::std::fmt::Debug for $name<T>
293	where T: ::std::fmt::Debug
294	{
295	    fn fmt(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result
296	    {
297		write!(f, "{:?}", self.as_slice())
298	    }
299	}
300	impl<T> ::std::cmp::Eq for $name<T>
301	where T: ::std::cmp::Eq{}
302	impl<T,U> ::std::cmp::PartialEq<U> for $name<T>
303	where T: ::std::cmp::PartialEq,
304	      U: AsRef<[T]>
305	{
306	    #[inline] 
307	    fn eq(&self, other: &U) -> bool
308	    {
309		self.as_slice() == other.as_ref()
310	    }
311	}
312	
313	impl<T> ::std::cmp::Ord for $name<T>
314	where T: ::std::cmp::Ord
315	{
316	    #[inline]
317	    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
318		std::cmp::Ord::cmp(self.as_slice(), other.as_slice())
319	    }
320	}
321	impl<T, U> ::std::cmp::PartialOrd<U> for $name<T>
322	where T: ::std::cmp::PartialOrd,
323	      U: AsRef<[T]>
324	{
325	    #[inline]
326	    fn partial_cmp(&self, other: &U) -> Option<std::cmp::Ordering> {
327		std::cmp::PartialOrd::partial_cmp(self.as_slice(), other.as_ref())
328	    }
329	}
330
331	impl<T,I: ::std::slice::SliceIndex<[T]>> std::ops::Index<I> for $name<T>
332	{
333	    type Output = I::Output;
334	    
335	    #[inline]
336	    fn index(&self, index: I) -> &Self::Output {
337		std::ops::Index::index(self.as_slice(), index)
338	    }
339	}
340	
341	impl<T,I: ::std::slice::SliceIndex<[T]>> std::ops::IndexMut<I> for $name<T>
342	{	    
343	    #[inline]
344	    fn index_mut(&mut self, index: I) -> &mut Self::Output {
345		std::ops::IndexMut::index_mut(self.as_mut_slice(), index)
346	    }
347	}
348	
349
350	impl<T> ::std::clone::Clone for $name<T>
351	where T: ::std::clone::Clone
352	{
353	    fn clone(&self) -> Self
354	    {
355		let mut emp = Self::new();
356		for (d,s) in emp.0.iter_mut().zip(self.iter())
357		{
358		    *d = std::mem::MaybeUninit::new(s.clone());
359		    emp.1+=1;//increment in case of `clone` panic
360		}
361		emp
362	    }
363	}
364	impl<T> ::std::convert::From<$name<T>> for ::std::vec::Vec<T>
365	{
366	    #[inline] fn from(from: $name<T>) -> Self
367	    {
368		from.into_iter().collect()
369	    }
370	}
371	impl<T> std::default::Default for $name<T>
372	{
373	    #[inline]
374	    fn default() -> Self
375	    {
376		Self::new()
377	    }
378	}
379
380
381
382	impl<T> ::std::iter::IntoIterator for $name<T>
383	{
384	    type Item= T;
385	    type IntoIter = $into_iter_name<T>;
386
387	    fn into_iter(self) -> Self::IntoIter
388	    {
389		$into_iter_name(self, 0)
390	    }
391	}
392
393	impl ::std::io::Write for $name<u8>
394	{
395	    fn write(&mut self, buf: &[u8]) -> ::std::io::Result<usize>
396	    {
397		Ok(self.extend_from_slice_copy(buf))
398	    }
399
400	    #[inline]
401	    fn write_vectored(&mut self, bufs: &[::std::io::IoSlice<'_>]) -> ::std::io::Result<usize> {
402		let mut w = 0;
403		for buf in bufs {
404		    w += self.extend_from_slice_copy(&buf[..]);
405		}
406		Ok(w)
407	    }
408	    
409	    #[inline]
410	    fn write_all(&mut self, buf: &[u8]) -> ::std::io::Result<()> {
411		let w = self.extend_from_slice_copy(buf);
412		if w!=buf.len() {
413		    Err(::std::io::Error::new(::std::io::ErrorKind::Other, "No more space"))
414		} else {
415		    Ok(())
416		}
417	    }
418	    
419	    #[inline] fn flush(&mut self) -> ::std::io::Result<()>
420	    {
421		Ok(())
422	    }
423	}
424
425	impl<T> ::std::convert::From<[T; $n]> for $name<T>
426	{
427	    #[inline] fn from(from: [T; $n]) -> Self
428	    {
429		let mut this = Self::new();
430		unsafe {
431		    std::ptr::copy(&from[0] as *const T, &mut this.0[0] as *mut std::mem::MaybeUninit<T> as *mut T, $n);
432		}
433		this.1=$n;
434		std::mem::forget(from);
435		this
436	    }
437	}
438	impl<T> ::std::iter::FromIterator<T> for $name<T>
439	{
440	    fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self
441	    {
442		let mut output = Self::new();
443		for item in iter
444		{
445		    output.push(item);
446		}
447		output
448	    }
449	}
450	
451	/// Consuming iterator type for a `StackVec`
452	pub struct $into_iter_name<T>($name<T>, usize);
453
454	impl<T> $into_iter_name<T>
455	{
456	    #![allow(dead_code)]
457	    
458	    /// The rest of the initialised buffer that has not been consumed yet.
459	    #[inline] pub fn rest(&self) -> &[T]
460	    {
461		&self.0.as_slice()[self.1..]
462	    }
463	    
464	    #[inline(always)] fn m_rest(&self) -> &[std::mem::MaybeUninit<T>]
465	    {
466		&self.0.init_buffer()[self.1..]
467	    }
468	    /// A mutable reference to the rest of the initialised buffer that has not been consumed yet.
469	    #[inline] pub fn rest_mut(&mut self) -> &mut [T]
470	    {
471		&mut self.0.as_mut_slice()[self.1..]
472	    }
473	    
474	    #[inline(always)] fn m_rest_mut(&mut self) -> &mut [std::mem::MaybeUninit<T>]
475	    {
476		&mut self.0.init_buffer_mut()[self.1..]
477	    }
478	}
479	impl<T> std::iter::Iterator for $into_iter_name<T>
480	{
481	    type Item = T;
482	    fn next(&mut self) -> Option<Self::Item>
483	    {
484		let buf = self.0.init_buffer_mut();
485		if self.1 < buf.len() {
486		    (unsafe {
487			Some(std::mem::replace(&mut buf[self.1], std::mem::MaybeUninit::uninit()).assume_init())
488		    },self.1+=1).0
489		} else {
490		    None
491		}
492	    }
493
494	    fn size_hint(&self) -> (usize, Option<usize>)
495	    {
496		(self.0.len(), Some(self.0.len()))
497	    }
498	}
499	impl<T> std::iter::ExactSizeIterator for $into_iter_name<T>{}
500	impl<T> std::iter::FusedIterator for $into_iter_name<T>{}
501	impl<T> std::ops::Drop for $into_iter_name<T>
502	{
503	    fn drop(&mut self)
504	    {
505		if std::mem::needs_drop::<T>() {
506		    unsafe {
507			for init in self.m_rest_mut() {
508			    
509			    drop(std::mem::replace(init, std::mem::MaybeUninit::uninit()).assume_init());
510			}
511		    }
512		    self.0.1=0; //prevent StackVec$n from trying to drop anything
513		}
514	    }
515	}
516
517    };
518    ($t:ty; $n:literal) => {
519	{		
520	    $crate::stack!({} type StackVecN StackVecNIntoIter $n);
521
522	    StackVecN::<$t>::new()
523	}
524    };
525    ($n:literal) => {
526	{
527	    $crate::stack!({} type StackVecN StackVecNIntoIter $n);
528
529	    StackVecN::new()
530	}
531    };
532}
533
534stack!(pub type StackVec1 StackVec1IntoIter 1);
535stack!(pub type StackVec2 StackVec2IntoIter 2);
536stack!(pub type StackVec4 StackVec4IntoIter 4);
537stack!(pub type StackVec8 StackVec8IntoIter 8);
538stack!(pub type StackVec16 StackVec16IntoIter 16);
539stack!(pub type StackVec32 StackVec32IntoIter 32);
540stack!(pub type StackVec64 StackVec64IntoIter 64);
541stack!(pub type StackVec128 StackVec128IntoIter 128);
542stack!(pub type StackVec256 StackVec256IntoIter 256);
543stack!(pub type StackVec512 StackVec512IntoIter 512);
544stack!(pub type StackVec1024 StackVec1024IntoIter 1024);
545stack!(pub type StackVec2048 StackVec2048IntoIter 2048);
546stack!(pub type StackVec4096 StackVec4096IntoIter 4096);
547
548fn _assert_comp()
549{
550    let _svec: StackVec256<i32> = StackVec256::new();
551}
552
553#[cfg(test)]
554mod tests
555{
556    use super::*;
557    #[test]
558    fn push_and_drop()
559    {
560	let mut sv = StackVec256::new();
561	sv.push(String::from("Hello"));
562	sv.push(String::from(" "));
563	sv.push(String::from("world."));
564	sv.push(String::from("!!!"));
565	sv.push(String::from("owo"));
566
567	assert_eq!(sv.len(), 5);
568	assert_eq!("Hello world.", sv.into_iter().take(3).collect::<String>().as_str());
569    }
570
571    #[test]
572    fn conversions()
573    {
574	let mut sv = StackVec256::new();
575	assert_eq!(sv.extend_from_slice(&[vec![1usize,2],vec![3,4], vec![5,6]]), 3);
576
577	assert_eq!(sv[1].iter().sum::<usize>(), 7);
578	assert_eq!(sv.iter().flat_map(|x| x.iter()).sum::<usize>(), 1+2+3+4+5+6);
579
580	let v = Vec::from(sv.clone());
581	assert_eq!(&v[..], &sv[..]);
582	drop(sv);
583	assert_eq!(v.iter().flat_map(|x| x.iter()).sum::<usize>(), 1+2+3+4+5+6);
584    }
585
586    #[test]
587    fn write()
588    {
589	use std::io::Write;
590	let mut sv = StackVec256::new();
591	let buf1 = [0u8; 128];
592	let buf2 = [1u8; 128];
593	
594	sv.write_all(&buf1[..]).expect("Failed to write buf1");
595	sv.write_all(&buf2[..]).expect("Failed to write buf2");
596	assert!(sv.write_all(&buf1[..]).is_err());
597
598	assert_eq!(&sv[..buf1.len()], &buf1[..]);
599	assert_eq!(&sv[buf1.len()..], &buf2[..]);
600
601	assert_eq!(buf1.iter().chain(buf2.iter()).copied().collect::<Vec<_>>(), sv.into_iter().collect::<Vec<_>>());
602    }
603
604    #[test]
605    fn from_iterator()
606    {
607	let sv: StackVec256<_> = vec![1,2,3,4,5,6].into_iter().collect();
608	assert_eq!(sv.into_iter().sum::<i32>(), 6+5+4+3+2+1i32);
609
610	let nt: StackVec256<_> = vec![
611	    vec![1,2,3],
612	    vec![4,5,6],
613	    vec![7,8,9],
614	].into_iter().collect();
615	assert_eq!(nt.iter().flat_map(|x| x.iter()).copied().sum::<i32>(), 9+8+7+6+5+4+3+2+1);
616    }
617
618    #[test]
619    #[should_panic]
620    fn from_too_big()
621    {
622	let _sv: StackVec256<_> = vec![vec![String::from("hi")]; 257].into_iter().collect();
623    }
624
625    #[test]
626    fn ad_hoc()
627    {
628	let mut sv = stack![23];
629
630	assert_eq!(sv.cap(), 23);
631
632	for x in 0..23
633	{
634	    sv.push(vec![x,x]);
635	}
636	assert_eq!(sv.len(), 23);
637
638	assert_eq!(sv.into_iter().flat_map(|x| x.into_iter()).sum::<i32>(), (0..23).map(|x| x*2).sum::<i32>());
639    }
640}
641
stack_vec/lib.rs

stack_vec/
lib.rs
