bitcoin_internals/
array_vec.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! A simplified `Copy` version of `arrayvec::ArrayVec`.
4
5use core::fmt;
6
7pub use safety_boundary::ArrayVec;
8
9/// Limits the scope of `unsafe` auditing.
10// New trait impls and fns that don't need to access internals should go below the module, not
11// inside it!
12mod safety_boundary {
13    use core::mem::MaybeUninit;
14
15    use crate::const_tools::cond_const;
16
17    /// A growable contiguous collection backed by array.
18    #[derive(Copy)]
19    pub struct ArrayVec<T: Copy, const CAP: usize> {
20        len: usize,
21        data: [MaybeUninit<T>; CAP],
22    }
23
24    impl<T: Copy, const CAP: usize> ArrayVec<T, CAP> {
25        // The bounds are const-unstable until 1.61
26        cond_const! {
27            /// Creates an empty `ArrayVec`.
28            pub const(in rust_v_1_61 = "1.61") fn new() -> Self {
29                Self {
30                    len: 0,
31                    data: [MaybeUninit::uninit(); CAP],
32                }
33            }
34
35            /// Creates an `ArrayVec` initialized with the contets of `slice`.
36            ///
37            /// # Panics
38            ///
39            /// If the slice is longer than `CAP`.
40            pub const(in rust_v_1_61 = "1.61") fn from_slice(slice: &[T]) -> Self {
41                assert!(slice.len() <= CAP);
42                let mut data = [MaybeUninit::uninit(); CAP];
43                let mut i = 0;
44                // can't use mutable references and operators in const
45                while i < slice.len() {
46                    data[i] = MaybeUninit::new(slice[i]);
47                    i += 1;
48                }
49
50                Self {
51                    len: slice.len(),
52                    data,
53                }
54            }
55        }
56
57        // from_raw_parts is const-unstable until 1.64
58        cond_const! {
59            /// Returns a reference to the underlying data.
60            pub const(in rust_v_1_64 = "1.64") fn as_slice(&self) -> &[T] {
61                let ptr = &self.data as *const _ as *const T;
62                unsafe { core::slice::from_raw_parts(ptr, self.len) }
63            }
64        }
65
66        /// Returns a mutable reference to the underlying data.
67        pub fn as_mut_slice(&mut self) -> &mut [T] {
68            unsafe { &mut *(&mut self.data[..self.len] as *mut _ as *mut [T]) }
69        }
70
71        /// Adds an element into `self`.
72        ///
73        /// # Panics
74        ///
75        /// If the length would increase past CAP.
76        pub fn push(&mut self, element: T) {
77            assert!(self.len < CAP);
78            self.data[self.len] = MaybeUninit::new(element);
79            self.len += 1;
80        }
81
82        /// Copies and appends all elements from `slice` into `self`.
83        ///
84        /// # Panics
85        ///
86        /// If the length would increase past CAP.
87        pub fn extend_from_slice(&mut self, slice: &[T]) {
88            let new_len = self.len.checked_add(slice.len()).expect("integer/buffer overflow");
89            assert!(new_len <= CAP, "buffer overflow");
90            // SAFETY: MaybeUninit<T> has the same layout as T
91            let slice = unsafe { &*(slice as *const _ as *const [MaybeUninit<T>]) };
92            self.data[self.len..].copy_from_slice(slice);
93            self.len = new_len;
94        }
95    }
96}
97
98impl<T: Copy, const CAP: usize> Default for ArrayVec<T, CAP> {
99    fn default() -> Self { Self::new() }
100}
101
102/// Clones the value *faster* than using `Copy`.
103///
104/// Because we avoid copying the uninitialized part of the array this copies the value faster than
105/// memcpy.
106#[allow(clippy::non_canonical_clone_impl)]
107impl<T: Copy, const CAP: usize> Clone for ArrayVec<T, CAP> {
108    fn clone(&self) -> Self { Self::from_slice(self) }
109}
110
111impl<T: Copy, const CAP: usize> core::ops::Deref for ArrayVec<T, CAP> {
112    type Target = [T];
113
114    fn deref(&self) -> &Self::Target { self.as_slice() }
115}
116
117impl<T: Copy, const CAP: usize> core::ops::DerefMut for ArrayVec<T, CAP> {
118    fn deref_mut(&mut self) -> &mut Self::Target { self.as_mut_slice() }
119}
120
121impl<T: Copy + Eq, const CAP: usize> Eq for ArrayVec<T, CAP> {}
122
123impl<T: Copy + PartialEq, const CAP1: usize, const CAP2: usize> PartialEq<ArrayVec<T, CAP2>>
124    for ArrayVec<T, CAP1>
125{
126    fn eq(&self, other: &ArrayVec<T, CAP2>) -> bool { **self == **other }
127}
128
129impl<T: Copy + PartialEq, const CAP: usize> PartialEq<[T]> for ArrayVec<T, CAP> {
130    fn eq(&self, other: &[T]) -> bool { **self == *other }
131}
132
133impl<T: Copy + PartialEq, const CAP: usize> PartialEq<ArrayVec<T, CAP>> for [T] {
134    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
135}
136
137impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<[T; LEN]>
138    for ArrayVec<T, CAP>
139{
140    fn eq(&self, other: &[T; LEN]) -> bool { **self == *other }
141}
142
143impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<ArrayVec<T, CAP>>
144    for [T; LEN]
145{
146    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
147}
148
149impl<T: Copy + Ord, const CAP: usize> Ord for ArrayVec<T, CAP> {
150    fn cmp(&self, other: &ArrayVec<T, CAP>) -> core::cmp::Ordering { (**self).cmp(&**other) }
151}
152
153impl<T: Copy + PartialOrd, const CAP1: usize, const CAP2: usize> PartialOrd<ArrayVec<T, CAP2>>
154    for ArrayVec<T, CAP1>
155{
156    fn partial_cmp(&self, other: &ArrayVec<T, CAP2>) -> Option<core::cmp::Ordering> {
157        (**self).partial_cmp(&**other)
158    }
159}
160
161impl<T: Copy + fmt::Debug, const CAP: usize> fmt::Debug for ArrayVec<T, CAP> {
162    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { fmt::Debug::fmt(&**self, f) }
163}
164
165impl<T: Copy + core::hash::Hash, const CAP: usize> core::hash::Hash for ArrayVec<T, CAP> {
166    fn hash<H: core::hash::Hasher>(&self, state: &mut H) { core::hash::Hash::hash(&**self, state) }
167}
168
169#[cfg(test)]
170mod tests {
171    use super::ArrayVec;
172
173    #[test]
174    fn arrayvec_ops() {
175        let mut av = ArrayVec::<_, 1>::new();
176        assert!(av.is_empty());
177        av.push(42);
178        assert_eq!(av.len(), 1);
179        assert_eq!(av, [42]);
180    }
181
182    #[test]
183    #[should_panic]
184    fn overflow_push() {
185        let mut av = ArrayVec::<_, 0>::new();
186        av.push(42);
187    }
188
189    #[test]
190    #[should_panic]
191    fn overflow_extend() {
192        let mut av = ArrayVec::<_, 0>::new();
193        av.extend_from_slice(&[42]);
194    }
195}
bitcoin_internals/array_vec.rs

bitcoin_internals/
array_vec.rs
