]>
Commit | Line | Data |
---|---|---|
9fa01778 XL |
1 | //! This crate implements a structure that can be used as a generic array type.use |
2 | //! Core Rust array types `[T; N]` can't be used generically with | |
3 | //! respect to `N`, so for example this: | |
4 | //! | |
5 | //! ```{should_fail} | |
6 | //! struct Foo<T, N> { | |
7 | //! data: [T; N] | |
8 | //! } | |
9 | //! ``` | |
10 | //! | |
11 | //! won't work. | |
12 | //! | |
13 | //! **generic-array** exports a `GenericArray<T,N>` type, which lets | |
14 | //! the above be implemented as: | |
15 | //! | |
16 | //! ``` | |
17 | //! # use generic_array::{ArrayLength, GenericArray}; | |
18 | //! struct Foo<T, N: ArrayLength<T>> { | |
19 | //! data: GenericArray<T,N> | |
20 | //! } | |
21 | //! ``` | |
22 | //! | |
23 | //! The `ArrayLength<T>` trait is implemented by default for | |
24 | //! [unsigned integer types](../typenum/uint/index.html) from | |
25 | //! [typenum](../typenum/index.html). | |
26 | //! | |
27 | //! For ease of use, an `arr!` macro is provided - example below: | |
28 | //! | |
29 | //! ``` | |
30 | //! # #[macro_use] | |
31 | //! # extern crate generic_array; | |
32 | //! # extern crate typenum; | |
33 | //! # fn main() { | |
34 | //! let array = arr![u32; 1, 2, 3]; | |
35 | //! assert_eq!(array[2], 3); | |
36 | //! # } | |
37 | //! ``` | |
38 | ||
39 | //#![deny(missing_docs)] | |
40 | #![no_std] | |
41 | ||
42 | pub extern crate typenum; | |
43 | #[cfg(feature = "serde")] | |
44 | extern crate serde; | |
45 | ||
46 | mod hex; | |
47 | mod impls; | |
48 | ||
49 | #[cfg(feature = "serde")] | |
50 | pub mod impl_serde; | |
51 | ||
52 | use core::{mem, ptr, slice}; | |
53 | ||
54 | use core::marker::PhantomData; | |
55 | use core::mem::ManuallyDrop; | |
56 | pub use core::mem::transmute; | |
57 | use core::ops::{Deref, DerefMut}; | |
58 | ||
59 | use typenum::bit::{B0, B1}; | |
60 | use typenum::uint::{UInt, UTerm, Unsigned}; | |
61 | ||
62 | #[cfg_attr(test, macro_use)] | |
63 | pub mod arr; | |
64 | pub mod iter; | |
65 | pub use iter::GenericArrayIter; | |
66 | ||
67 | /// Trait making `GenericArray` work, marking types to be used as length of an array | |
68 | pub unsafe trait ArrayLength<T>: Unsigned { | |
69 | /// Associated type representing the array type for the number | |
70 | type ArrayType; | |
71 | } | |
72 | ||
73 | unsafe impl<T> ArrayLength<T> for UTerm { | |
74 | #[doc(hidden)] | |
75 | type ArrayType = (); | |
76 | } | |
77 | ||
78 | /// Internal type used to generate a struct of appropriate size | |
79 | #[allow(dead_code)] | |
80 | #[repr(C)] | |
81 | #[doc(hidden)] | |
82 | pub struct GenericArrayImplEven<T, U> { | |
83 | parent1: U, | |
84 | parent2: U, | |
85 | _marker: PhantomData<T>, | |
86 | } | |
87 | ||
88 | impl<T: Clone, U: Clone> Clone for GenericArrayImplEven<T, U> { | |
89 | fn clone(&self) -> GenericArrayImplEven<T, U> { | |
90 | GenericArrayImplEven { | |
91 | parent1: self.parent1.clone(), | |
92 | parent2: self.parent2.clone(), | |
93 | _marker: PhantomData, | |
94 | } | |
95 | } | |
96 | } | |
97 | ||
98 | impl<T: Copy, U: Copy> Copy for GenericArrayImplEven<T, U> {} | |
99 | ||
100 | /// Internal type used to generate a struct of appropriate size | |
101 | #[allow(dead_code)] | |
102 | #[repr(C)] | |
103 | #[doc(hidden)] | |
104 | pub struct GenericArrayImplOdd<T, U> { | |
105 | parent1: U, | |
106 | parent2: U, | |
107 | data: T, | |
108 | } | |
109 | ||
110 | impl<T: Clone, U: Clone> Clone for GenericArrayImplOdd<T, U> { | |
111 | fn clone(&self) -> GenericArrayImplOdd<T, U> { | |
112 | GenericArrayImplOdd { | |
113 | parent1: self.parent1.clone(), | |
114 | parent2: self.parent2.clone(), | |
115 | data: self.data.clone(), | |
116 | } | |
117 | } | |
118 | } | |
119 | ||
120 | impl<T: Copy, U: Copy> Copy for GenericArrayImplOdd<T, U> {} | |
121 | ||
122 | unsafe impl<T, N: ArrayLength<T>> ArrayLength<T> for UInt<N, B0> { | |
123 | #[doc(hidden)] | |
124 | type ArrayType = GenericArrayImplEven<T, N::ArrayType>; | |
125 | } | |
126 | ||
127 | unsafe impl<T, N: ArrayLength<T>> ArrayLength<T> for UInt<N, B1> { | |
128 | #[doc(hidden)] | |
129 | type ArrayType = GenericArrayImplOdd<T, N::ArrayType>; | |
130 | } | |
131 | ||
132 | /// Struct representing a generic array - `GenericArray<T, N>` works like [T; N] | |
133 | #[allow(dead_code)] | |
134 | pub struct GenericArray<T, U: ArrayLength<T>> { | |
135 | data: U::ArrayType, | |
136 | } | |
137 | ||
138 | impl<T, N> Deref for GenericArray<T, N> | |
139 | where | |
140 | N: ArrayLength<T>, | |
141 | { | |
142 | type Target = [T]; | |
143 | ||
144 | fn deref(&self) -> &[T] { | |
145 | unsafe { slice::from_raw_parts(self as *const Self as *const T, N::to_usize()) } | |
146 | } | |
147 | } | |
148 | ||
149 | impl<T, N> DerefMut for GenericArray<T, N> | |
150 | where | |
151 | N: ArrayLength<T>, | |
152 | { | |
153 | fn deref_mut(&mut self) -> &mut [T] { | |
154 | unsafe { slice::from_raw_parts_mut(self as *mut Self as *mut T, N::to_usize()) } | |
155 | } | |
156 | } | |
157 | ||
158 | struct ArrayBuilder<T, N: ArrayLength<T>> { | |
159 | array: ManuallyDrop<GenericArray<T, N>>, | |
160 | position: usize, | |
161 | } | |
162 | ||
163 | impl<T, N: ArrayLength<T>> ArrayBuilder<T, N> { | |
164 | fn new() -> ArrayBuilder<T, N> { | |
165 | ArrayBuilder { | |
166 | array: ManuallyDrop::new(unsafe { mem::uninitialized() }), | |
167 | position: 0, | |
168 | } | |
169 | } | |
170 | ||
171 | fn into_inner(self) -> GenericArray<T, N> { | |
172 | let array = unsafe { ptr::read(&self.array) }; | |
173 | ||
174 | mem::forget(self); | |
175 | ||
176 | ManuallyDrop::into_inner(array) | |
177 | } | |
178 | } | |
179 | ||
180 | impl<T, N: ArrayLength<T>> Drop for ArrayBuilder<T, N> { | |
181 | fn drop(&mut self) { | |
182 | for value in self.array.iter_mut().take(self.position) { | |
183 | unsafe { | |
184 | ptr::drop_in_place(value); | |
185 | } | |
186 | } | |
187 | } | |
188 | } | |
189 | ||
190 | struct ArrayConsumer<T, N: ArrayLength<T>> { | |
191 | array: ManuallyDrop<GenericArray<T, N>>, | |
192 | position: usize, | |
193 | } | |
194 | ||
195 | impl<T, N: ArrayLength<T>> ArrayConsumer<T, N> { | |
196 | fn new(array: GenericArray<T, N>) -> ArrayConsumer<T, N> { | |
197 | ArrayConsumer { | |
198 | array: ManuallyDrop::new(array), | |
199 | position: 0, | |
200 | } | |
201 | } | |
202 | } | |
203 | ||
204 | impl<T, N: ArrayLength<T>> Drop for ArrayConsumer<T, N> { | |
205 | fn drop(&mut self) { | |
206 | for i in self.position..N::to_usize() { | |
207 | unsafe { | |
208 | ptr::drop_in_place(self.array.get_unchecked_mut(i)); | |
209 | } | |
210 | } | |
211 | } | |
212 | } | |
213 | ||
214 | impl<T, N> GenericArray<T, N> | |
215 | where | |
216 | N: ArrayLength<T>, | |
217 | { | |
218 | /// Initializes a new `GenericArray` instance using the given function. | |
219 | /// | |
220 | /// If the generator function panics while initializing the array, | |
221 | /// any already initialized elements will be dropped. | |
222 | pub fn generate<F>(f: F) -> GenericArray<T, N> | |
223 | where | |
224 | F: Fn(usize) -> T, | |
225 | { | |
226 | let mut destination = ArrayBuilder::new(); | |
227 | ||
228 | for (i, dst) in destination.array.iter_mut().enumerate() { | |
229 | unsafe { | |
230 | ptr::write(dst, f(i)); | |
231 | } | |
232 | ||
233 | destination.position += 1; | |
234 | } | |
235 | ||
236 | destination.into_inner() | |
237 | } | |
238 | ||
239 | /// Map a function over a slice to a `GenericArray`. | |
240 | /// | |
241 | /// The length of the slice *must* be equal to the length of the array. | |
242 | #[inline] | |
243 | pub fn map_slice<S, F: Fn(&S) -> T>(s: &[S], f: F) -> GenericArray<T, N> { | |
244 | assert_eq!(s.len(), N::to_usize()); | |
245 | ||
246 | Self::generate(|i| f(unsafe { s.get_unchecked(i) })) | |
247 | } | |
248 | ||
249 | /// Maps a `GenericArray` to another `GenericArray`. | |
250 | /// | |
251 | /// If the mapping function panics, any already initialized elements in the new array | |
252 | /// will be dropped, AND any unused elements in the source array will also be dropped. | |
253 | pub fn map<U, F>(self, f: F) -> GenericArray<U, N> | |
254 | where | |
255 | F: Fn(T) -> U, | |
256 | N: ArrayLength<U>, | |
257 | { | |
258 | let mut source = ArrayConsumer::new(self); | |
259 | let mut destination = ArrayBuilder::new(); | |
260 | ||
261 | for (dst, src) in destination.array.iter_mut().zip(source.array.iter()) { | |
262 | unsafe { | |
263 | ptr::write(dst, f(ptr::read(src))); | |
264 | } | |
265 | ||
266 | source.position += 1; | |
267 | destination.position += 1; | |
268 | } | |
269 | ||
270 | destination.into_inner() | |
271 | } | |
272 | ||
273 | /// Maps a `GenericArray` to another `GenericArray` by reference. | |
274 | /// | |
275 | /// If the mapping function panics, any already initialized elements will be dropped. | |
276 | #[inline] | |
277 | pub fn map_ref<U, F>(&self, f: F) -> GenericArray<U, N> | |
278 | where | |
279 | F: Fn(&T) -> U, | |
280 | N: ArrayLength<U>, | |
281 | { | |
282 | GenericArray::generate(|i| f(unsafe { self.get_unchecked(i) })) | |
283 | } | |
284 | ||
285 | /// Combines two `GenericArray` instances and iterates through both of them, | |
286 | /// initializing a new `GenericArray` with the result of the zipped mapping function. | |
287 | /// | |
288 | /// If the mapping function panics, any already initialized elements in the new array | |
289 | /// will be dropped, AND any unused elements in the source arrays will also be dropped. | |
290 | pub fn zip<B, U, F>(self, rhs: GenericArray<B, N>, f: F) -> GenericArray<U, N> | |
291 | where | |
292 | F: Fn(T, B) -> U, | |
293 | N: ArrayLength<B> + ArrayLength<U>, | |
294 | { | |
295 | let mut left = ArrayConsumer::new(self); | |
296 | let mut right = ArrayConsumer::new(rhs); | |
297 | ||
298 | let mut destination = ArrayBuilder::new(); | |
299 | ||
300 | for (dst, (lhs, rhs)) in | |
301 | destination.array.iter_mut().zip(left.array.iter().zip( | |
302 | right.array.iter(), | |
303 | )) | |
304 | { | |
305 | unsafe { | |
306 | ptr::write(dst, f(ptr::read(lhs), ptr::read(rhs))); | |
307 | } | |
308 | ||
309 | destination.position += 1; | |
310 | left.position += 1; | |
311 | right.position += 1; | |
312 | } | |
313 | ||
314 | destination.into_inner() | |
315 | } | |
316 | ||
317 | /// Combines two `GenericArray` instances and iterates through both of them by reference, | |
318 | /// initializing a new `GenericArray` with the result of the zipped mapping function. | |
319 | /// | |
320 | /// If the mapping function panics, any already initialized elements will be dropped. | |
321 | pub fn zip_ref<B, U, F>(&self, rhs: &GenericArray<B, N>, f: F) -> GenericArray<U, N> | |
322 | where | |
323 | F: Fn(&T, &B) -> U, | |
324 | N: ArrayLength<B> + ArrayLength<U>, | |
325 | { | |
326 | GenericArray::generate(|i| unsafe { | |
327 | f(self.get_unchecked(i), rhs.get_unchecked(i)) | |
328 | }) | |
329 | } | |
330 | ||
331 | /// Extracts a slice containing the entire array. | |
332 | #[inline] | |
333 | pub fn as_slice(&self) -> &[T] { | |
334 | self.deref() | |
335 | } | |
336 | ||
337 | /// Extracts a mutable slice containing the entire array. | |
338 | #[inline] | |
339 | pub fn as_mut_slice(&mut self) -> &mut [T] { | |
340 | self.deref_mut() | |
341 | } | |
342 | ||
343 | /// Converts slice to a generic array reference with inferred length; | |
344 | /// | |
345 | /// Length of the slice must be equal to the length of the array. | |
346 | #[inline] | |
347 | pub fn from_slice(slice: &[T]) -> &GenericArray<T, N> { | |
348 | assert_eq!(slice.len(), N::to_usize()); | |
349 | ||
350 | unsafe { &*(slice.as_ptr() as *const GenericArray<T, N>) } | |
351 | } | |
352 | ||
353 | /// Converts mutable slice to a mutable generic array reference | |
354 | /// | |
355 | /// Length of the slice must be equal to the length of the array. | |
356 | #[inline] | |
357 | pub fn from_mut_slice(slice: &mut [T]) -> &mut GenericArray<T, N> { | |
358 | assert_eq!(slice.len(), N::to_usize()); | |
359 | ||
360 | unsafe { &mut *(slice.as_mut_ptr() as *mut GenericArray<T, N>) } | |
361 | } | |
362 | } | |
363 | ||
364 | impl<T: Clone, N> GenericArray<T, N> | |
365 | where | |
366 | N: ArrayLength<T>, | |
367 | { | |
368 | /// Construct a `GenericArray` from a slice by cloning its content | |
369 | /// | |
370 | /// Length of the slice must be equal to the length of the array | |
371 | #[inline] | |
372 | pub fn clone_from_slice(list: &[T]) -> GenericArray<T, N> { | |
373 | Self::from_exact_iter(list.iter().cloned()).expect( | |
374 | "Slice must be the same length as the array", | |
375 | ) | |
376 | } | |
377 | } | |
378 | ||
379 | impl<T, N> GenericArray<T, N> | |
380 | where | |
381 | N: ArrayLength<T>, | |
382 | { | |
383 | pub fn from_exact_iter<I>(iter: I) -> Option<Self> | |
384 | where | |
385 | I: IntoIterator<Item = T>, | |
386 | <I as IntoIterator>::IntoIter: ExactSizeIterator, | |
387 | { | |
388 | let iter = iter.into_iter(); | |
389 | ||
390 | if iter.len() == N::to_usize() { | |
391 | let mut destination = ArrayBuilder::new(); | |
392 | ||
393 | for (dst, src) in destination.array.iter_mut().zip(iter.into_iter()) { | |
394 | unsafe { | |
395 | ptr::write(dst, src); | |
396 | } | |
397 | ||
398 | destination.position += 1; | |
399 | } | |
400 | ||
401 | let array = unsafe { ptr::read(&destination.array) }; | |
402 | ||
403 | mem::forget(destination); | |
404 | ||
405 | Some(ManuallyDrop::into_inner(array)) | |
406 | } else { | |
407 | None | |
408 | } | |
409 | } | |
410 | } | |
411 | ||
412 | impl<T, N> ::core::iter::FromIterator<T> for GenericArray<T, N> | |
413 | where | |
414 | N: ArrayLength<T>, | |
415 | T: Default, | |
416 | { | |
417 | fn from_iter<I>(iter: I) -> GenericArray<T, N> | |
418 | where | |
419 | I: IntoIterator<Item = T>, | |
420 | { | |
421 | let mut destination = ArrayBuilder::new(); | |
422 | ||
423 | let defaults = ::core::iter::repeat(()).map(|_| T::default()); | |
424 | ||
425 | for (dst, src) in destination.array.iter_mut().zip( | |
426 | iter.into_iter().chain(defaults), | |
427 | ) | |
428 | { | |
429 | unsafe { | |
430 | ptr::write(dst, src); | |
431 | } | |
432 | } | |
433 | ||
434 | destination.into_inner() | |
435 | } | |
436 | } | |
437 | ||
438 | #[cfg(test)] | |
439 | mod test { | |
440 | // Compile with: | |
441 | // cargo rustc --lib --profile test --release -- | |
442 | // -C target-cpu=native -C opt-level=3 --emit asm | |
443 | // and view the assembly to make sure test_assembly generates | |
444 | // SIMD instructions instead of a niave loop. | |
445 | ||
446 | #[inline(never)] | |
447 | pub fn black_box<T>(val: T) -> T { | |
448 | use core::{mem, ptr}; | |
449 | ||
450 | let ret = unsafe { ptr::read_volatile(&val) }; | |
451 | mem::forget(val); | |
452 | ret | |
453 | } | |
454 | ||
455 | #[test] | |
456 | fn test_assembly() { | |
457 | let a = black_box(arr![i32; 1, 3, 5, 7]); | |
458 | let b = black_box(arr![i32; 2, 4, 6, 8]); | |
459 | ||
460 | let c = a.zip_ref(&b, |l, r| l + r); | |
461 | ||
462 | assert_eq!(c, arr![i32; 3, 7, 11, 15]); | |
463 | } | |
464 | } |