/home/ubuntu/.cargo/registry/src/index.crates.io-6f17d22bba15001f/arrayvec-0.7.4/src/arrayvec.rs
Line | Count | Source (jump to first uncovered line) |
1 | | |
2 | | use std::cmp; |
3 | | use std::iter; |
4 | | use std::mem; |
5 | | use std::ops::{Bound, Deref, DerefMut, RangeBounds}; |
6 | | use std::ptr; |
7 | | use std::slice; |
8 | | |
9 | | // extra traits |
10 | | use std::borrow::{Borrow, BorrowMut}; |
11 | | use std::hash::{Hash, Hasher}; |
12 | | use std::fmt; |
13 | | |
14 | | #[cfg(feature="std")] |
15 | | use std::io; |
16 | | |
17 | | use std::mem::ManuallyDrop; |
18 | | use std::mem::MaybeUninit; |
19 | | |
20 | | #[cfg(feature="serde")] |
21 | | use serde::{Serialize, Deserialize, Serializer, Deserializer}; |
22 | | |
23 | | use crate::LenUint; |
24 | | use crate::errors::CapacityError; |
25 | | use crate::arrayvec_impl::ArrayVecImpl; |
26 | | use crate::utils::MakeMaybeUninit; |
27 | | |
28 | | /// A vector with a fixed capacity. |
29 | | /// |
30 | | /// The `ArrayVec` is a vector backed by a fixed size array. It keeps track of |
31 | | /// the number of initialized elements. The `ArrayVec<T, CAP>` is parameterized |
32 | | /// by `T` for the element type and `CAP` for the maximum capacity. |
33 | | /// |
34 | | /// `CAP` is of type `usize` but is range limited to `u32::MAX`; attempting to create larger |
35 | | /// arrayvecs with larger capacity will panic. |
36 | | /// |
37 | | /// The vector is a contiguous value (storing the elements inline) that you can store directly on |
38 | | /// the stack if needed. |
39 | | /// |
40 | | /// It offers a simple API but also dereferences to a slice, so that the full slice API is |
41 | | /// available. The ArrayVec can be converted into a by value iterator. |
42 | | pub struct ArrayVec<T, const CAP: usize> { |
43 | | // the `len` first elements of the array are initialized |
44 | | xs: [MaybeUninit<T>; CAP], |
45 | | len: LenUint, |
46 | | } |
47 | | |
48 | | impl<T, const CAP: usize> Drop for ArrayVec<T, CAP> { |
49 | 2.25k | fn drop(&mut self) { |
50 | 2.25k | self.clear(); |
51 | 2.25k | |
52 | 2.25k | // MaybeUninit inhibits array's drop |
53 | 2.25k | } _RNvXNtCskQaAGJdWXwX_8arrayvec8arrayvecINtB2_8ArrayVechKj1000_ENtNtNtCs6xNykbTfrCs_4core3ops4drop4Drop4dropCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 49 | 1.12k | fn drop(&mut self) { | 50 | 1.12k | self.clear(); | 51 | 1.12k | | 52 | 1.12k | // MaybeUninit inhibits array's drop | 53 | 1.12k | } |
_RNvXNtCskQaAGJdWXwX_8arrayvec8arrayvecINtB2_8ArrayVecjKj10_ENtNtNtCs6xNykbTfrCs_4core3ops4drop4Drop4dropCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 49 | 1.12k | fn drop(&mut self) { | 50 | 1.12k | self.clear(); | 51 | 1.12k | | 52 | 1.12k | // MaybeUninit inhibits array's drop | 53 | 1.12k | } |
Unexecuted instantiation: _RNvXNtCskQaAGJdWXwX_8arrayvec8arrayvecINtB2_8ArrayVecjKj80_ENtNtNtCs6xNykbTfrCs_4core3ops4drop4Drop4dropCslLTLXfmDngu_8flex_dns |
54 | | } |
55 | | |
56 | | macro_rules! panic_oob { |
57 | | ($method_name:expr, $index:expr, $len:expr) => { |
58 | | panic!(concat!("ArrayVec::", $method_name, ": index {} is out of bounds in vector of length {}"), |
59 | | $index, $len) |
60 | | } |
61 | | } |
62 | | |
63 | | impl<T, const CAP: usize> ArrayVec<T, CAP> { |
64 | | /// Capacity |
65 | | const CAPACITY: usize = CAP; |
66 | | |
67 | | /// Create a new empty `ArrayVec`. |
68 | | /// |
69 | | /// The maximum capacity is given by the generic parameter `CAP`. |
70 | | /// |
71 | | /// ``` |
72 | | /// use arrayvec::ArrayVec; |
73 | | /// |
74 | | /// let mut array = ArrayVec::<_, 16>::new(); |
75 | | /// array.push(1); |
76 | | /// array.push(2); |
77 | | /// assert_eq!(&array[..], &[1, 2]); |
78 | | /// assert_eq!(array.capacity(), 16); |
79 | | /// ``` |
80 | | #[inline] |
81 | | #[track_caller] |
82 | 2.25k | pub fn new() -> ArrayVec<T, CAP> { |
83 | 2.25k | assert_capacity_limit!(CAP); |
84 | | unsafe { |
85 | 2.25k | ArrayVec { xs: MaybeUninit::uninit().assume_init(), len: 0 } |
86 | 2.25k | } |
87 | 2.25k | } _RNvMs_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB4_8ArrayVechKj1000_E3newCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 82 | 1.12k | pub fn new() -> ArrayVec<T, CAP> { | 83 | 1.12k | assert_capacity_limit!(CAP); | 84 | | unsafe { | 85 | 1.12k | ArrayVec { xs: MaybeUninit::uninit().assume_init(), len: 0 } | 86 | 1.12k | } | 87 | 1.12k | } |
_RNvMs_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB4_8ArrayVecjKj10_E3newCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 82 | 1.12k | pub fn new() -> ArrayVec<T, CAP> { | 83 | 1.12k | assert_capacity_limit!(CAP); | 84 | | unsafe { | 85 | 1.12k | ArrayVec { xs: MaybeUninit::uninit().assume_init(), len: 0 } | 86 | 1.12k | } | 87 | 1.12k | } |
Unexecuted instantiation: _RNvMs_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB4_8ArrayVecjKj80_E3newCslLTLXfmDngu_8flex_dns |
88 | | |
89 | | /// Create a new empty `ArrayVec` (const fn). |
90 | | /// |
91 | | /// The maximum capacity is given by the generic parameter `CAP`. |
92 | | /// |
93 | | /// ``` |
94 | | /// use arrayvec::ArrayVec; |
95 | | /// |
96 | | /// static ARRAY: ArrayVec<u8, 1024> = ArrayVec::new_const(); |
97 | | /// ``` |
98 | | pub const fn new_const() -> ArrayVec<T, CAP> { |
99 | | assert_capacity_limit_const!(CAP); |
100 | | ArrayVec { xs: MakeMaybeUninit::ARRAY, len: 0 } |
101 | | } |
102 | | |
103 | | /// Return the number of elements in the `ArrayVec`. |
104 | | /// |
105 | | /// ``` |
106 | | /// use arrayvec::ArrayVec; |
107 | | /// |
108 | | /// let mut array = ArrayVec::from([1, 2, 3]); |
109 | | /// array.pop(); |
110 | | /// assert_eq!(array.len(), 2); |
111 | | /// ``` |
112 | | #[inline(always)] |
113 | 30.5k | pub const fn len(&self) -> usize { self.len as usize } _RNvMs_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB4_8ArrayVechKj1000_E3lenCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 113 | 29.4k | pub const fn len(&self) -> usize { self.len as usize } |
_RNvMs_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB4_8ArrayVecjKj10_E3lenCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 113 | 1.12k | pub const fn len(&self) -> usize { self.len as usize } |
Unexecuted instantiation: _RNvMs_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB4_8ArrayVecjKj80_E3lenCslLTLXfmDngu_8flex_dns |
114 | | |
115 | | /// Returns whether the `ArrayVec` is empty. |
116 | | /// |
117 | | /// ``` |
118 | | /// use arrayvec::ArrayVec; |
119 | | /// |
120 | | /// let mut array = ArrayVec::from([1]); |
121 | | /// array.pop(); |
122 | | /// assert_eq!(array.is_empty(), true); |
123 | | /// ``` |
124 | | #[inline] |
125 | | pub const fn is_empty(&self) -> bool { self.len() == 0 } |
126 | | |
127 | | /// Return the capacity of the `ArrayVec`. |
128 | | /// |
129 | | /// ``` |
130 | | /// use arrayvec::ArrayVec; |
131 | | /// |
132 | | /// let array = ArrayVec::from([1, 2, 3]); |
133 | | /// assert_eq!(array.capacity(), 3); |
134 | | /// ``` |
135 | | #[inline(always)] |
136 | 2.29k | pub const fn capacity(&self) -> usize { CAP } |
137 | | |
138 | | /// Return true if the `ArrayVec` is completely filled to its capacity, false otherwise. |
139 | | /// |
140 | | /// ``` |
141 | | /// use arrayvec::ArrayVec; |
142 | | /// |
143 | | /// let mut array = ArrayVec::<_, 1>::new(); |
144 | | /// assert!(!array.is_full()); |
145 | | /// array.push(1); |
146 | | /// assert!(array.is_full()); |
147 | | /// ``` |
148 | | pub const fn is_full(&self) -> bool { self.len() == self.capacity() } |
149 | | |
150 | | /// Returns the capacity left in the `ArrayVec`. |
151 | | /// |
152 | | /// ``` |
153 | | /// use arrayvec::ArrayVec; |
154 | | /// |
155 | | /// let mut array = ArrayVec::from([1, 2, 3]); |
156 | | /// array.pop(); |
157 | | /// assert_eq!(array.remaining_capacity(), 1); |
158 | | /// ``` |
159 | 1.16k | pub const fn remaining_capacity(&self) -> usize { |
160 | 1.16k | self.capacity() - self.len() |
161 | 1.16k | } |
162 | | |
163 | | /// Push `element` to the end of the vector. |
164 | | /// |
165 | | /// ***Panics*** if the vector is already full. |
166 | | /// |
167 | | /// ``` |
168 | | /// use arrayvec::ArrayVec; |
169 | | /// |
170 | | /// let mut array = ArrayVec::<_, 2>::new(); |
171 | | /// |
172 | | /// array.push(1); |
173 | | /// array.push(2); |
174 | | /// |
175 | | /// assert_eq!(&array[..], &[1, 2]); |
176 | | /// ``` |
177 | | #[track_caller] |
178 | 0 | pub fn push(&mut self, element: T) { |
179 | 0 | ArrayVecImpl::push(self, element) |
180 | 0 | } |
181 | | |
182 | | /// Push `element` to the end of the vector. |
183 | | /// |
184 | | /// Return `Ok` if the push succeeds, or return an error if the vector |
185 | | /// is already full. |
186 | | /// |
187 | | /// ``` |
188 | | /// use arrayvec::ArrayVec; |
189 | | /// |
190 | | /// let mut array = ArrayVec::<_, 2>::new(); |
191 | | /// |
192 | | /// let push1 = array.try_push(1); |
193 | | /// let push2 = array.try_push(2); |
194 | | /// |
195 | | /// assert!(push1.is_ok()); |
196 | | /// assert!(push2.is_ok()); |
197 | | /// |
198 | | /// assert_eq!(&array[..], &[1, 2]); |
199 | | /// |
200 | | /// let overflow = array.try_push(3); |
201 | | /// |
202 | | /// assert!(overflow.is_err()); |
203 | | /// ``` |
204 | | pub fn try_push(&mut self, element: T) -> Result<(), CapacityError<T>> { |
205 | | ArrayVecImpl::try_push(self, element) |
206 | | } |
207 | | |
208 | | /// Push `element` to the end of the vector without checking the capacity. |
209 | | /// |
210 | | /// It is up to the caller to ensure the capacity of the vector is |
211 | | /// sufficiently large. |
212 | | /// |
213 | | /// This method uses *debug assertions* to check that the arrayvec is not full. |
214 | | /// |
215 | | /// ``` |
216 | | /// use arrayvec::ArrayVec; |
217 | | /// |
218 | | /// let mut array = ArrayVec::<_, 2>::new(); |
219 | | /// |
220 | | /// if array.len() + 2 <= array.capacity() { |
221 | | /// unsafe { |
222 | | /// array.push_unchecked(1); |
223 | | /// array.push_unchecked(2); |
224 | | /// } |
225 | | /// } |
226 | | /// |
227 | | /// assert_eq!(&array[..], &[1, 2]); |
228 | | /// ``` |
229 | | pub unsafe fn push_unchecked(&mut self, element: T) { |
230 | | ArrayVecImpl::push_unchecked(self, element) |
231 | | } |
232 | | |
233 | | /// Shortens the vector, keeping the first `len` elements and dropping |
234 | | /// the rest. |
235 | | /// |
236 | | /// If `len` is greater than the vector’s current length this has no |
237 | | /// effect. |
238 | | /// |
239 | | /// ``` |
240 | | /// use arrayvec::ArrayVec; |
241 | | /// |
242 | | /// let mut array = ArrayVec::from([1, 2, 3, 4, 5]); |
243 | | /// array.truncate(3); |
244 | | /// assert_eq!(&array[..], &[1, 2, 3]); |
245 | | /// array.truncate(4); |
246 | | /// assert_eq!(&array[..], &[1, 2, 3]); |
247 | | /// ``` |
248 | | pub fn truncate(&mut self, new_len: usize) { |
249 | | ArrayVecImpl::truncate(self, new_len) |
250 | | } |
251 | | |
252 | | /// Remove all elements in the vector. |
253 | 2.25k | pub fn clear(&mut self) { |
254 | 2.25k | ArrayVecImpl::clear(self) |
255 | 2.25k | } _RNvMs_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB4_8ArrayVechKj1000_E5clearCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 253 | 1.12k | pub fn clear(&mut self) { | 254 | 1.12k | ArrayVecImpl::clear(self) | 255 | 1.12k | } |
_RNvMs_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB4_8ArrayVecjKj10_E5clearCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 253 | 1.12k | pub fn clear(&mut self) { | 254 | 1.12k | ArrayVecImpl::clear(self) | 255 | 1.12k | } |
Unexecuted instantiation: _RNvMs_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB4_8ArrayVecjKj80_E5clearCslLTLXfmDngu_8flex_dns |
256 | | |
257 | | |
258 | | /// Get pointer to where element at `index` would be |
259 | 1.16k | unsafe fn get_unchecked_ptr(&mut self, index: usize) -> *mut T { |
260 | 1.16k | self.as_mut_ptr().add(index) |
261 | 1.16k | } |
262 | | |
263 | | /// Insert `element` at position `index`. |
264 | | /// |
265 | | /// Shift up all elements after `index`. |
266 | | /// |
267 | | /// It is an error if the index is greater than the length or if the |
268 | | /// arrayvec is full. |
269 | | /// |
270 | | /// ***Panics*** if the array is full or the `index` is out of bounds. See |
271 | | /// `try_insert` for fallible version. |
272 | | /// |
273 | | /// ``` |
274 | | /// use arrayvec::ArrayVec; |
275 | | /// |
276 | | /// let mut array = ArrayVec::<_, 2>::new(); |
277 | | /// |
278 | | /// array.insert(0, "x"); |
279 | | /// array.insert(0, "y"); |
280 | | /// assert_eq!(&array[..], &["y", "x"]); |
281 | | /// |
282 | | /// ``` |
283 | | #[track_caller] |
284 | | pub fn insert(&mut self, index: usize, element: T) { |
285 | | self.try_insert(index, element).unwrap() |
286 | | } |
287 | | |
288 | | /// Insert `element` at position `index`. |
289 | | /// |
290 | | /// Shift up all elements after `index`; the `index` must be less than |
291 | | /// or equal to the length. |
292 | | /// |
293 | | /// Returns an error if vector is already at full capacity. |
294 | | /// |
295 | | /// ***Panics*** `index` is out of bounds. |
296 | | /// |
297 | | /// ``` |
298 | | /// use arrayvec::ArrayVec; |
299 | | /// |
300 | | /// let mut array = ArrayVec::<_, 2>::new(); |
301 | | /// |
302 | | /// assert!(array.try_insert(0, "x").is_ok()); |
303 | | /// assert!(array.try_insert(0, "y").is_ok()); |
304 | | /// assert!(array.try_insert(0, "z").is_err()); |
305 | | /// assert_eq!(&array[..], &["y", "x"]); |
306 | | /// |
307 | | /// ``` |
308 | | pub fn try_insert(&mut self, index: usize, element: T) -> Result<(), CapacityError<T>> { |
309 | | if index > self.len() { |
310 | | panic_oob!("try_insert", index, self.len()) |
311 | | } |
312 | | if self.len() == self.capacity() { |
313 | | return Err(CapacityError::new(element)); |
314 | | } |
315 | | let len = self.len(); |
316 | | |
317 | | // follows is just like Vec<T> |
318 | | unsafe { // infallible |
319 | | // The spot to put the new value |
320 | | { |
321 | | let p: *mut _ = self.get_unchecked_ptr(index); |
322 | | // Shift everything over to make space. (Duplicating the |
323 | | // `index`th element into two consecutive places.) |
324 | | ptr::copy(p, p.offset(1), len - index); |
325 | | // Write it in, overwriting the first copy of the `index`th |
326 | | // element. |
327 | | ptr::write(p, element); |
328 | | } |
329 | | self.set_len(len + 1); |
330 | | } |
331 | | Ok(()) |
332 | | } |
333 | | |
334 | | /// Remove the last element in the vector and return it. |
335 | | /// |
336 | | /// Return `Some(` *element* `)` if the vector is non-empty, else `None`. |
337 | | /// |
338 | | /// ``` |
339 | | /// use arrayvec::ArrayVec; |
340 | | /// |
341 | | /// let mut array = ArrayVec::<_, 2>::new(); |
342 | | /// |
343 | | /// array.push(1); |
344 | | /// |
345 | | /// assert_eq!(array.pop(), Some(1)); |
346 | | /// assert_eq!(array.pop(), None); |
347 | | /// ``` |
348 | | pub fn pop(&mut self) -> Option<T> { |
349 | | ArrayVecImpl::pop(self) |
350 | | } |
351 | | |
352 | | /// Remove the element at `index` and swap the last element into its place. |
353 | | /// |
354 | | /// This operation is O(1). |
355 | | /// |
356 | | /// Return the *element* if the index is in bounds, else panic. |
357 | | /// |
358 | | /// ***Panics*** if the `index` is out of bounds. |
359 | | /// |
360 | | /// ``` |
361 | | /// use arrayvec::ArrayVec; |
362 | | /// |
363 | | /// let mut array = ArrayVec::from([1, 2, 3]); |
364 | | /// |
365 | | /// assert_eq!(array.swap_remove(0), 1); |
366 | | /// assert_eq!(&array[..], &[3, 2]); |
367 | | /// |
368 | | /// assert_eq!(array.swap_remove(1), 2); |
369 | | /// assert_eq!(&array[..], &[3]); |
370 | | /// ``` |
371 | | pub fn swap_remove(&mut self, index: usize) -> T { |
372 | | self.swap_pop(index) |
373 | | .unwrap_or_else(|| { |
374 | | panic_oob!("swap_remove", index, self.len()) |
375 | | }) |
376 | | } |
377 | | |
378 | | /// Remove the element at `index` and swap the last element into its place. |
379 | | /// |
380 | | /// This is a checked version of `.swap_remove`. |
381 | | /// This operation is O(1). |
382 | | /// |
383 | | /// Return `Some(` *element* `)` if the index is in bounds, else `None`. |
384 | | /// |
385 | | /// ``` |
386 | | /// use arrayvec::ArrayVec; |
387 | | /// |
388 | | /// let mut array = ArrayVec::from([1, 2, 3]); |
389 | | /// |
390 | | /// assert_eq!(array.swap_pop(0), Some(1)); |
391 | | /// assert_eq!(&array[..], &[3, 2]); |
392 | | /// |
393 | | /// assert_eq!(array.swap_pop(10), None); |
394 | | /// ``` |
395 | | pub fn swap_pop(&mut self, index: usize) -> Option<T> { |
396 | | let len = self.len(); |
397 | | if index >= len { |
398 | | return None; |
399 | | } |
400 | | self.swap(index, len - 1); |
401 | | self.pop() |
402 | | } |
403 | | |
404 | | /// Remove the element at `index` and shift down the following elements. |
405 | | /// |
406 | | /// The `index` must be strictly less than the length of the vector. |
407 | | /// |
408 | | /// ***Panics*** if the `index` is out of bounds. |
409 | | /// |
410 | | /// ``` |
411 | | /// use arrayvec::ArrayVec; |
412 | | /// |
413 | | /// let mut array = ArrayVec::from([1, 2, 3]); |
414 | | /// |
415 | | /// let removed_elt = array.remove(0); |
416 | | /// assert_eq!(removed_elt, 1); |
417 | | /// assert_eq!(&array[..], &[2, 3]); |
418 | | /// ``` |
419 | | pub fn remove(&mut self, index: usize) -> T { |
420 | | self.pop_at(index) |
421 | | .unwrap_or_else(|| { |
422 | | panic_oob!("remove", index, self.len()) |
423 | | }) |
424 | | } |
425 | | |
426 | | /// Remove the element at `index` and shift down the following elements. |
427 | | /// |
428 | | /// This is a checked version of `.remove(index)`. Returns `None` if there |
429 | | /// is no element at `index`. Otherwise, return the element inside `Some`. |
430 | | /// |
431 | | /// ``` |
432 | | /// use arrayvec::ArrayVec; |
433 | | /// |
434 | | /// let mut array = ArrayVec::from([1, 2, 3]); |
435 | | /// |
436 | | /// assert!(array.pop_at(0).is_some()); |
437 | | /// assert_eq!(&array[..], &[2, 3]); |
438 | | /// |
439 | | /// assert!(array.pop_at(2).is_none()); |
440 | | /// assert!(array.pop_at(10).is_none()); |
441 | | /// ``` |
442 | | pub fn pop_at(&mut self, index: usize) -> Option<T> { |
443 | | if index >= self.len() { |
444 | | None |
445 | | } else { |
446 | | self.drain(index..index + 1).next() |
447 | | } |
448 | | } |
449 | | |
450 | | /// Retains only the elements specified by the predicate. |
451 | | /// |
452 | | /// In other words, remove all elements `e` such that `f(&mut e)` returns false. |
453 | | /// This method operates in place and preserves the order of the retained |
454 | | /// elements. |
455 | | /// |
456 | | /// ``` |
457 | | /// use arrayvec::ArrayVec; |
458 | | /// |
459 | | /// let mut array = ArrayVec::from([1, 2, 3, 4]); |
460 | | /// array.retain(|x| *x & 1 != 0 ); |
461 | | /// assert_eq!(&array[..], &[1, 3]); |
462 | | /// ``` |
463 | | pub fn retain<F>(&mut self, mut f: F) |
464 | | where F: FnMut(&mut T) -> bool |
465 | | { |
466 | | // Check the implementation of |
467 | | // https://doc.rust-lang.org/std/vec/struct.Vec.html#method.retain |
468 | | // for safety arguments (especially regarding panics in f and when |
469 | | // dropping elements). Implementation closely mirrored here. |
470 | | |
471 | | let original_len = self.len(); |
472 | | unsafe { self.set_len(0) }; |
473 | | |
474 | | struct BackshiftOnDrop<'a, T, const CAP: usize> { |
475 | | v: &'a mut ArrayVec<T, CAP>, |
476 | | processed_len: usize, |
477 | | deleted_cnt: usize, |
478 | | original_len: usize, |
479 | | } |
480 | | |
481 | | impl<T, const CAP: usize> Drop for BackshiftOnDrop<'_, T, CAP> { |
482 | | fn drop(&mut self) { |
483 | | if self.deleted_cnt > 0 { |
484 | | unsafe { |
485 | | ptr::copy( |
486 | | self.v.as_ptr().add(self.processed_len), |
487 | | self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt), |
488 | | self.original_len - self.processed_len |
489 | | ); |
490 | | } |
491 | | } |
492 | | unsafe { |
493 | | self.v.set_len(self.original_len - self.deleted_cnt); |
494 | | } |
495 | | } |
496 | | } |
497 | | |
498 | | let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len }; |
499 | | |
500 | | #[inline(always)] |
501 | | fn process_one<F: FnMut(&mut T) -> bool, T, const CAP: usize, const DELETED: bool>( |
502 | | f: &mut F, |
503 | | g: &mut BackshiftOnDrop<'_, T, CAP> |
504 | | ) -> bool { |
505 | | let cur = unsafe { g.v.as_mut_ptr().add(g.processed_len) }; |
506 | | if !f(unsafe { &mut *cur }) { |
507 | | g.processed_len += 1; |
508 | | g.deleted_cnt += 1; |
509 | | unsafe { ptr::drop_in_place(cur) }; |
510 | | return false; |
511 | | } |
512 | | if DELETED { |
513 | | unsafe { |
514 | | let hole_slot = cur.sub(g.deleted_cnt); |
515 | | ptr::copy_nonoverlapping(cur, hole_slot, 1); |
516 | | } |
517 | | } |
518 | | g.processed_len += 1; |
519 | | true |
520 | | } |
521 | | |
522 | | // Stage 1: Nothing was deleted. |
523 | | while g.processed_len != original_len { |
524 | | if !process_one::<F, T, CAP, false>(&mut f, &mut g) { |
525 | | break; |
526 | | } |
527 | | } |
528 | | |
529 | | // Stage 2: Some elements were deleted. |
530 | | while g.processed_len != original_len { |
531 | | process_one::<F, T, CAP, true>(&mut f, &mut g); |
532 | | } |
533 | | |
534 | | drop(g); |
535 | | } |
536 | | |
537 | | /// Set the vector’s length without dropping or moving out elements |
538 | | /// |
539 | | /// This method is `unsafe` because it changes the notion of the |
540 | | /// number of “valid” elements in the vector. Use with care. |
541 | | /// |
542 | | /// This method uses *debug assertions* to check that `length` is |
543 | | /// not greater than the capacity. |
544 | 1.16k | pub unsafe fn set_len(&mut self, length: usize) { |
545 | | // type invariant that capacity always fits in LenUint |
546 | 0 | debug_assert!(length <= self.capacity()); |
547 | 1.16k | self.len = length as LenUint; |
548 | 1.16k | } |
549 | | |
550 | | /// Copy all elements from the slice and append to the `ArrayVec`. |
551 | | /// |
552 | | /// ``` |
553 | | /// use arrayvec::ArrayVec; |
554 | | /// |
555 | | /// let mut vec: ArrayVec<usize, 10> = ArrayVec::new(); |
556 | | /// vec.push(1); |
557 | | /// vec.try_extend_from_slice(&[2, 3]).unwrap(); |
558 | | /// assert_eq!(&vec[..], &[1, 2, 3]); |
559 | | /// ``` |
560 | | /// |
561 | | /// # Errors |
562 | | /// |
563 | | /// This method will return an error if the capacity left (see |
564 | | /// [`remaining_capacity`]) is smaller then the length of the provided |
565 | | /// slice. |
566 | | /// |
567 | | /// [`remaining_capacity`]: #method.remaining_capacity |
568 | 1.16k | pub fn try_extend_from_slice(&mut self, other: &[T]) -> Result<(), CapacityError> |
569 | 1.16k | where T: Copy, |
570 | 1.16k | { |
571 | 1.16k | if self.remaining_capacity() < other.len() { |
572 | 0 | return Err(CapacityError::new(())); |
573 | 1.16k | } |
574 | 1.16k | |
575 | 1.16k | let self_len = self.len(); |
576 | 1.16k | let other_len = other.len(); |
577 | 1.16k | |
578 | 1.16k | unsafe { |
579 | 1.16k | let dst = self.get_unchecked_ptr(self_len); |
580 | 1.16k | ptr::copy_nonoverlapping(other.as_ptr(), dst, other_len); |
581 | 1.16k | self.set_len(self_len + other_len); |
582 | 1.16k | } |
583 | 1.16k | Ok(()) |
584 | 1.16k | } |
585 | | |
586 | | /// Create a draining iterator that removes the specified range in the vector |
587 | | /// and yields the removed items from start to end. The element range is |
588 | | /// removed even if the iterator is not consumed until the end. |
589 | | /// |
590 | | /// Note: It is unspecified how many elements are removed from the vector, |
591 | | /// if the `Drain` value is leaked. |
592 | | /// |
593 | | /// **Panics** if the starting point is greater than the end point or if |
594 | | /// the end point is greater than the length of the vector. |
595 | | /// |
596 | | /// ``` |
597 | | /// use arrayvec::ArrayVec; |
598 | | /// |
599 | | /// let mut v1 = ArrayVec::from([1, 2, 3]); |
600 | | /// let v2: ArrayVec<_, 3> = v1.drain(0..2).collect(); |
601 | | /// assert_eq!(&v1[..], &[3]); |
602 | | /// assert_eq!(&v2[..], &[1, 2]); |
603 | | /// ``` |
604 | | pub fn drain<R>(&mut self, range: R) -> Drain<T, CAP> |
605 | | where R: RangeBounds<usize> |
606 | | { |
607 | | // Memory safety |
608 | | // |
609 | | // When the Drain is first created, it shortens the length of |
610 | | // the source vector to make sure no uninitialized or moved-from elements |
611 | | // are accessible at all if the Drain's destructor never gets to run. |
612 | | // |
613 | | // Drain will ptr::read out the values to remove. |
614 | | // When finished, remaining tail of the vec is copied back to cover |
615 | | // the hole, and the vector length is restored to the new length. |
616 | | // |
617 | | let len = self.len(); |
618 | | let start = match range.start_bound() { |
619 | | Bound::Unbounded => 0, |
620 | | Bound::Included(&i) => i, |
621 | | Bound::Excluded(&i) => i.saturating_add(1), |
622 | | }; |
623 | | let end = match range.end_bound() { |
624 | | Bound::Excluded(&j) => j, |
625 | | Bound::Included(&j) => j.saturating_add(1), |
626 | | Bound::Unbounded => len, |
627 | | }; |
628 | | self.drain_range(start, end) |
629 | | } |
630 | | |
631 | | fn drain_range(&mut self, start: usize, end: usize) -> Drain<T, CAP> |
632 | | { |
633 | | let len = self.len(); |
634 | | |
635 | | // bounds check happens here (before length is changed!) |
636 | | let range_slice: *const _ = &self[start..end]; |
637 | | |
638 | | // Calling `set_len` creates a fresh and thus unique mutable references, making all |
639 | | // older aliases we created invalid. So we cannot call that function. |
640 | | self.len = start as LenUint; |
641 | | |
642 | | unsafe { |
643 | | Drain { |
644 | | tail_start: end, |
645 | | tail_len: len - end, |
646 | | iter: (*range_slice).iter(), |
647 | | vec: self as *mut _, |
648 | | } |
649 | | } |
650 | | } |
651 | | |
652 | | /// Return the inner fixed size array, if it is full to its capacity. |
653 | | /// |
654 | | /// Return an `Ok` value with the array if length equals capacity, |
655 | | /// return an `Err` with self otherwise. |
656 | | pub fn into_inner(self) -> Result<[T; CAP], Self> { |
657 | | if self.len() < self.capacity() { |
658 | | Err(self) |
659 | | } else { |
660 | | unsafe { Ok(self.into_inner_unchecked()) } |
661 | | } |
662 | | } |
663 | | |
664 | | /// Return the inner fixed size array. |
665 | | /// |
666 | | /// Safety: |
667 | | /// This operation is safe if and only if length equals capacity. |
668 | | pub unsafe fn into_inner_unchecked(self) -> [T; CAP] { |
669 | | debug_assert_eq!(self.len(), self.capacity()); |
670 | | let self_ = ManuallyDrop::new(self); |
671 | | let array = ptr::read(self_.as_ptr() as *const [T; CAP]); |
672 | | array |
673 | | } |
674 | | |
675 | | /// Returns the ArrayVec, replacing the original with a new empty ArrayVec. |
676 | | /// |
677 | | /// ``` |
678 | | /// use arrayvec::ArrayVec; |
679 | | /// |
680 | | /// let mut v = ArrayVec::from([0, 1, 2, 3]); |
681 | | /// assert_eq!([0, 1, 2, 3], v.take().into_inner().unwrap()); |
682 | | /// assert!(v.is_empty()); |
683 | | /// ``` |
684 | | pub fn take(&mut self) -> Self { |
685 | | mem::replace(self, Self::new()) |
686 | | } |
687 | | |
688 | | /// Return a slice containing all elements of the vector. |
689 | 11.2k | pub fn as_slice(&self) -> &[T] { |
690 | 11.2k | ArrayVecImpl::as_slice(self) |
691 | 11.2k | } _RNvMs_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB4_8ArrayVechKj1000_E8as_sliceCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 689 | 11.2k | pub fn as_slice(&self) -> &[T] { | 690 | 11.2k | ArrayVecImpl::as_slice(self) | 691 | 11.2k | } |
Unexecuted instantiation: _RNvMs_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB4_8ArrayVecjKj80_E8as_sliceCslLTLXfmDngu_8flex_dns |
692 | | |
693 | | /// Return a mutable slice containing all elements of the vector. |
694 | | pub fn as_mut_slice(&mut self) -> &mut [T] { |
695 | | ArrayVecImpl::as_mut_slice(self) |
696 | | } |
697 | | |
698 | | /// Return a raw pointer to the vector's buffer. |
699 | | pub fn as_ptr(&self) -> *const T { |
700 | | ArrayVecImpl::as_ptr(self) |
701 | | } |
702 | | |
703 | | /// Return a raw mutable pointer to the vector's buffer. |
704 | 1.16k | pub fn as_mut_ptr(&mut self) -> *mut T { |
705 | 1.16k | ArrayVecImpl::as_mut_ptr(self) |
706 | 1.16k | } |
707 | | } |
708 | | |
709 | | impl<T, const CAP: usize> ArrayVecImpl for ArrayVec<T, CAP> { |
710 | | type Item = T; |
711 | | const CAPACITY: usize = CAP; |
712 | | |
713 | 13.5k | fn len(&self) -> usize { self.len() } _RNvXs0_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB5_8ArrayVecjKj10_ENtNtB7_13arrayvec_impl12ArrayVecImpl3lenCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 713 | 1.12k | fn len(&self) -> usize { self.len() } |
_RNvXs0_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB5_8ArrayVechKj1000_ENtNtB7_13arrayvec_impl12ArrayVecImpl3lenCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 713 | 12.4k | fn len(&self) -> usize { self.len() } |
Unexecuted instantiation: _RNvXs0_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB5_8ArrayVecjKj80_ENtNtB7_13arrayvec_impl12ArrayVecImpl3lenCslLTLXfmDngu_8flex_dns |
714 | | |
715 | 1.12k | unsafe fn set_len(&mut self, length: usize) { |
716 | 0 | debug_assert!(length <= CAP); |
717 | 1.12k | self.len = length as LenUint; |
718 | 1.12k | } _RNvXs0_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB5_8ArrayVechKj1000_ENtNtB7_13arrayvec_impl12ArrayVecImpl7set_lenCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 715 | 1.12k | unsafe fn set_len(&mut self, length: usize) { | 716 | 0 | debug_assert!(length <= CAP); | 717 | 1.12k | self.len = length as LenUint; | 718 | 1.12k | } |
Unexecuted instantiation: _RNvXs0_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB5_8ArrayVecjKj10_ENtNtB7_13arrayvec_impl12ArrayVecImpl7set_lenCsgg978DXfVXR_13fuzz_target_1 Unexecuted instantiation: _RNvXs0_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB5_8ArrayVecjKj80_ENtNtB7_13arrayvec_impl12ArrayVecImpl7set_lenCslLTLXfmDngu_8flex_dns |
719 | | |
720 | 11.2k | fn as_ptr(&self) -> *const Self::Item { |
721 | 11.2k | self.xs.as_ptr() as _ |
722 | 11.2k | } _RNvXs0_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB5_8ArrayVechKj1000_ENtNtB7_13arrayvec_impl12ArrayVecImpl6as_ptrCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 720 | 11.2k | fn as_ptr(&self) -> *const Self::Item { | 721 | 11.2k | self.xs.as_ptr() as _ | 722 | 11.2k | } |
Unexecuted instantiation: _RNvXs0_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB5_8ArrayVecjKj80_ENtNtB7_13arrayvec_impl12ArrayVecImpl6as_ptrCslLTLXfmDngu_8flex_dns |
723 | | |
724 | 2.29k | fn as_mut_ptr(&mut self) -> *mut Self::Item { |
725 | 2.29k | self.xs.as_mut_ptr() as _ |
726 | 2.29k | } Unexecuted instantiation: _RNvXs0_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB5_8ArrayVecjKj10_ENtNtB7_13arrayvec_impl12ArrayVecImpl10as_mut_ptrCsgg978DXfVXR_13fuzz_target_1 _RNvXs0_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB5_8ArrayVechKj1000_ENtNtB7_13arrayvec_impl12ArrayVecImpl10as_mut_ptrCsgg978DXfVXR_13fuzz_target_1 Line | Count | Source | 724 | 2.29k | fn as_mut_ptr(&mut self) -> *mut Self::Item { | 725 | 2.29k | self.xs.as_mut_ptr() as _ | 726 | 2.29k | } |
Unexecuted instantiation: _RNvXs0_NtCskQaAGJdWXwX_8arrayvec8arrayvecINtB5_8ArrayVecjKj80_ENtNtB7_13arrayvec_impl12ArrayVecImpl10as_mut_ptrCslLTLXfmDngu_8flex_dns |
727 | | } |
728 | | |
729 | | impl<T, const CAP: usize> Deref for ArrayVec<T, CAP> { |
730 | | type Target = [T]; |
731 | | #[inline] |
732 | 0 | fn deref(&self) -> &Self::Target { |
733 | 0 | self.as_slice() |
734 | 0 | } |
735 | | } |
736 | | |
737 | | impl<T, const CAP: usize> DerefMut for ArrayVec<T, CAP> { |
738 | | #[inline] |
739 | | fn deref_mut(&mut self) -> &mut Self::Target { |
740 | | self.as_mut_slice() |
741 | | } |
742 | | } |
743 | | |
744 | | |
745 | | /// Create an `ArrayVec` from an array. |
746 | | /// |
747 | | /// ``` |
748 | | /// use arrayvec::ArrayVec; |
749 | | /// |
750 | | /// let mut array = ArrayVec::from([1, 2, 3]); |
751 | | /// assert_eq!(array.len(), 3); |
752 | | /// assert_eq!(array.capacity(), 3); |
753 | | /// ``` |
754 | | impl<T, const CAP: usize> From<[T; CAP]> for ArrayVec<T, CAP> { |
755 | | #[track_caller] |
756 | | fn from(array: [T; CAP]) -> Self { |
757 | | let array = ManuallyDrop::new(array); |
758 | | let mut vec = <ArrayVec<T, CAP>>::new(); |
759 | | unsafe { |
760 | | (&*array as *const [T; CAP] as *const [MaybeUninit<T>; CAP]) |
761 | | .copy_to_nonoverlapping(&mut vec.xs as *mut [MaybeUninit<T>; CAP], 1); |
762 | | vec.set_len(CAP); |
763 | | } |
764 | | vec |
765 | | } |
766 | | } |
767 | | |
768 | | |
769 | | /// Try to create an `ArrayVec` from a slice. This will return an error if the slice was too big to |
770 | | /// fit. |
771 | | /// |
772 | | /// ``` |
773 | | /// use arrayvec::ArrayVec; |
774 | | /// use std::convert::TryInto as _; |
775 | | /// |
776 | | /// let array: ArrayVec<_, 4> = (&[1, 2, 3] as &[_]).try_into().unwrap(); |
777 | | /// assert_eq!(array.len(), 3); |
778 | | /// assert_eq!(array.capacity(), 4); |
779 | | /// ``` |
780 | | impl<T, const CAP: usize> std::convert::TryFrom<&[T]> for ArrayVec<T, CAP> |
781 | | where T: Clone, |
782 | | { |
783 | | type Error = CapacityError; |
784 | | |
785 | | fn try_from(slice: &[T]) -> Result<Self, Self::Error> { |
786 | | if Self::CAPACITY < slice.len() { |
787 | | Err(CapacityError::new(())) |
788 | | } else { |
789 | | let mut array = Self::new(); |
790 | | array.extend_from_slice(slice); |
791 | | Ok(array) |
792 | | } |
793 | | } |
794 | | } |
795 | | |
796 | | |
797 | | /// Iterate the `ArrayVec` with references to each element. |
798 | | /// |
799 | | /// ``` |
800 | | /// use arrayvec::ArrayVec; |
801 | | /// |
802 | | /// let array = ArrayVec::from([1, 2, 3]); |
803 | | /// |
804 | | /// for elt in &array { |
805 | | /// // ... |
806 | | /// } |
807 | | /// ``` |
808 | | impl<'a, T: 'a, const CAP: usize> IntoIterator for &'a ArrayVec<T, CAP> { |
809 | | type Item = &'a T; |
810 | | type IntoIter = slice::Iter<'a, T>; |
811 | | fn into_iter(self) -> Self::IntoIter { self.iter() } |
812 | | } |
813 | | |
814 | | /// Iterate the `ArrayVec` with mutable references to each element. |
815 | | /// |
816 | | /// ``` |
817 | | /// use arrayvec::ArrayVec; |
818 | | /// |
819 | | /// let mut array = ArrayVec::from([1, 2, 3]); |
820 | | /// |
821 | | /// for elt in &mut array { |
822 | | /// // ... |
823 | | /// } |
824 | | /// ``` |
825 | | impl<'a, T: 'a, const CAP: usize> IntoIterator for &'a mut ArrayVec<T, CAP> { |
826 | | type Item = &'a mut T; |
827 | | type IntoIter = slice::IterMut<'a, T>; |
828 | | fn into_iter(self) -> Self::IntoIter { self.iter_mut() } |
829 | | } |
830 | | |
831 | | /// Iterate the `ArrayVec` with each element by value. |
832 | | /// |
833 | | /// The vector is consumed by this operation. |
834 | | /// |
835 | | /// ``` |
836 | | /// use arrayvec::ArrayVec; |
837 | | /// |
838 | | /// for elt in ArrayVec::from([1, 2, 3]) { |
839 | | /// // ... |
840 | | /// } |
841 | | /// ``` |
842 | | impl<T, const CAP: usize> IntoIterator for ArrayVec<T, CAP> { |
843 | | type Item = T; |
844 | | type IntoIter = IntoIter<T, CAP>; |
845 | | fn into_iter(self) -> IntoIter<T, CAP> { |
846 | | IntoIter { index: 0, v: self, } |
847 | | } |
848 | | } |
849 | | |
850 | | |
851 | | #[cfg(feature = "zeroize")] |
852 | | /// "Best efforts" zeroing of the `ArrayVec`'s buffer when the `zeroize` feature is enabled. |
853 | | /// |
854 | | /// The length is set to 0, and the buffer is dropped and zeroized. |
855 | | /// Cannot ensure that previous moves of the `ArrayVec` did not leave values on the stack. |
856 | | /// |
857 | | /// ``` |
858 | | /// use arrayvec::ArrayVec; |
859 | | /// use zeroize::Zeroize; |
860 | | /// let mut array = ArrayVec::from([1, 2, 3]); |
861 | | /// array.zeroize(); |
862 | | /// assert_eq!(array.len(), 0); |
863 | | /// let data = unsafe { core::slice::from_raw_parts(array.as_ptr(), array.capacity()) }; |
864 | | /// assert_eq!(data, [0, 0, 0]); |
865 | | /// ``` |
866 | | impl<Z: zeroize::Zeroize, const CAP: usize> zeroize::Zeroize for ArrayVec<Z, CAP> { |
867 | | fn zeroize(&mut self) { |
868 | | // Zeroize all the contained elements. |
869 | | self.iter_mut().zeroize(); |
870 | | // Drop all the elements and set the length to 0. |
871 | | self.clear(); |
872 | | // Zeroize the backing array. |
873 | | self.xs.zeroize(); |
874 | | } |
875 | | } |
876 | | |
877 | | /// By-value iterator for `ArrayVec`. |
878 | | pub struct IntoIter<T, const CAP: usize> { |
879 | | index: usize, |
880 | | v: ArrayVec<T, CAP>, |
881 | | } |
882 | | |
883 | | impl<T, const CAP: usize> Iterator for IntoIter<T, CAP> { |
884 | | type Item = T; |
885 | | |
886 | | fn next(&mut self) -> Option<Self::Item> { |
887 | | if self.index == self.v.len() { |
888 | | None |
889 | | } else { |
890 | | unsafe { |
891 | | let index = self.index; |
892 | | self.index = index + 1; |
893 | | Some(ptr::read(self.v.get_unchecked_ptr(index))) |
894 | | } |
895 | | } |
896 | | } |
897 | | |
898 | | fn size_hint(&self) -> (usize, Option<usize>) { |
899 | | let len = self.v.len() - self.index; |
900 | | (len, Some(len)) |
901 | | } |
902 | | } |
903 | | |
904 | | impl<T, const CAP: usize> DoubleEndedIterator for IntoIter<T, CAP> { |
905 | | fn next_back(&mut self) -> Option<Self::Item> { |
906 | | if self.index == self.v.len() { |
907 | | None |
908 | | } else { |
909 | | unsafe { |
910 | | let new_len = self.v.len() - 1; |
911 | | self.v.set_len(new_len); |
912 | | Some(ptr::read(self.v.get_unchecked_ptr(new_len))) |
913 | | } |
914 | | } |
915 | | } |
916 | | } |
917 | | |
918 | | impl<T, const CAP: usize> ExactSizeIterator for IntoIter<T, CAP> { } |
919 | | |
920 | | impl<T, const CAP: usize> Drop for IntoIter<T, CAP> { |
921 | | fn drop(&mut self) { |
922 | | // panic safety: Set length to 0 before dropping elements. |
923 | | let index = self.index; |
924 | | let len = self.v.len(); |
925 | | unsafe { |
926 | | self.v.set_len(0); |
927 | | let elements = slice::from_raw_parts_mut( |
928 | | self.v.get_unchecked_ptr(index), |
929 | | len - index); |
930 | | ptr::drop_in_place(elements); |
931 | | } |
932 | | } |
933 | | } |
934 | | |
935 | | impl<T, const CAP: usize> Clone for IntoIter<T, CAP> |
936 | | where T: Clone, |
937 | | { |
938 | | fn clone(&self) -> IntoIter<T, CAP> { |
939 | | let mut v = ArrayVec::new(); |
940 | | v.extend_from_slice(&self.v[self.index..]); |
941 | | v.into_iter() |
942 | | } |
943 | | } |
944 | | |
945 | | impl<T, const CAP: usize> fmt::Debug for IntoIter<T, CAP> |
946 | | where |
947 | | T: fmt::Debug, |
948 | | { |
949 | | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
950 | | f.debug_list() |
951 | | .entries(&self.v[self.index..]) |
952 | | .finish() |
953 | | } |
954 | | } |
955 | | |
956 | | /// A draining iterator for `ArrayVec`. |
957 | | pub struct Drain<'a, T: 'a, const CAP: usize> { |
958 | | /// Index of tail to preserve |
959 | | tail_start: usize, |
960 | | /// Length of tail |
961 | | tail_len: usize, |
962 | | /// Current remaining range to remove |
963 | | iter: slice::Iter<'a, T>, |
964 | | vec: *mut ArrayVec<T, CAP>, |
965 | | } |
966 | | |
967 | | unsafe impl<'a, T: Sync, const CAP: usize> Sync for Drain<'a, T, CAP> {} |
968 | | unsafe impl<'a, T: Send, const CAP: usize> Send for Drain<'a, T, CAP> {} |
969 | | |
970 | | impl<'a, T: 'a, const CAP: usize> Iterator for Drain<'a, T, CAP> { |
971 | | type Item = T; |
972 | | |
973 | | fn next(&mut self) -> Option<Self::Item> { |
974 | | self.iter.next().map(|elt| |
975 | | unsafe { |
976 | | ptr::read(elt as *const _) |
977 | | } |
978 | | ) |
979 | | } |
980 | | |
981 | | fn size_hint(&self) -> (usize, Option<usize>) { |
982 | | self.iter.size_hint() |
983 | | } |
984 | | } |
985 | | |
986 | | impl<'a, T: 'a, const CAP: usize> DoubleEndedIterator for Drain<'a, T, CAP> |
987 | | { |
988 | | fn next_back(&mut self) -> Option<Self::Item> { |
989 | | self.iter.next_back().map(|elt| |
990 | | unsafe { |
991 | | ptr::read(elt as *const _) |
992 | | } |
993 | | ) |
994 | | } |
995 | | } |
996 | | |
997 | | impl<'a, T: 'a, const CAP: usize> ExactSizeIterator for Drain<'a, T, CAP> {} |
998 | | |
999 | | impl<'a, T: 'a, const CAP: usize> Drop for Drain<'a, T, CAP> { |
1000 | | fn drop(&mut self) { |
1001 | | // len is currently 0 so panicking while dropping will not cause a double drop. |
1002 | | |
1003 | | // exhaust self first |
1004 | | while let Some(_) = self.next() { } |
1005 | | |
1006 | | if self.tail_len > 0 { |
1007 | | unsafe { |
1008 | | let source_vec = &mut *self.vec; |
1009 | | // memmove back untouched tail, update to new length |
1010 | | let start = source_vec.len(); |
1011 | | let tail = self.tail_start; |
1012 | | let ptr = source_vec.as_mut_ptr(); |
1013 | | ptr::copy(ptr.add(tail), ptr.add(start), self.tail_len); |
1014 | | source_vec.set_len(start + self.tail_len); |
1015 | | } |
1016 | | } |
1017 | | } |
1018 | | } |
1019 | | |
1020 | | struct ScopeExitGuard<T, Data, F> |
1021 | | where F: FnMut(&Data, &mut T) |
1022 | | { |
1023 | | value: T, |
1024 | | data: Data, |
1025 | | f: F, |
1026 | | } |
1027 | | |
1028 | | impl<T, Data, F> Drop for ScopeExitGuard<T, Data, F> |
1029 | | where F: FnMut(&Data, &mut T) |
1030 | | { |
1031 | | fn drop(&mut self) { |
1032 | | (self.f)(&self.data, &mut self.value) |
1033 | | } |
1034 | | } |
1035 | | |
1036 | | |
1037 | | |
1038 | | /// Extend the `ArrayVec` with an iterator. |
1039 | | /// |
1040 | | /// ***Panics*** if extending the vector exceeds its capacity. |
1041 | | impl<T, const CAP: usize> Extend<T> for ArrayVec<T, CAP> { |
1042 | | /// Extend the `ArrayVec` with an iterator. |
1043 | | /// |
1044 | | /// ***Panics*** if extending the vector exceeds its capacity. |
1045 | | #[track_caller] |
1046 | | fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) { |
1047 | | unsafe { |
1048 | | self.extend_from_iter::<_, true>(iter) |
1049 | | } |
1050 | | } |
1051 | | } |
1052 | | |
1053 | | #[inline(never)] |
1054 | | #[cold] |
1055 | | #[track_caller] |
1056 | | fn extend_panic() { |
1057 | | panic!("ArrayVec: capacity exceeded in extend/from_iter"); |
1058 | | } |
1059 | | |
1060 | | impl<T, const CAP: usize> ArrayVec<T, CAP> { |
1061 | | /// Extend the arrayvec from the iterable. |
1062 | | /// |
1063 | | /// ## Safety |
1064 | | /// |
1065 | | /// Unsafe because if CHECK is false, the length of the input is not checked. |
1066 | | /// The caller must ensure the length of the input fits in the capacity. |
1067 | | #[track_caller] |
1068 | | pub(crate) unsafe fn extend_from_iter<I, const CHECK: bool>(&mut self, iterable: I) |
1069 | | where I: IntoIterator<Item = T> |
1070 | | { |
1071 | | let take = self.capacity() - self.len(); |
1072 | | let len = self.len(); |
1073 | | let mut ptr = raw_ptr_add(self.as_mut_ptr(), len); |
1074 | | let end_ptr = raw_ptr_add(ptr, take); |
1075 | | // Keep the length in a separate variable, write it back on scope |
1076 | | // exit. To help the compiler with alias analysis and stuff. |
1077 | | // We update the length to handle panic in the iteration of the |
1078 | | // user's iterator, without dropping any elements on the floor. |
1079 | | let mut guard = ScopeExitGuard { |
1080 | | value: &mut self.len, |
1081 | | data: len, |
1082 | | f: move |&len, self_len| { |
1083 | | **self_len = len as LenUint; |
1084 | | } |
1085 | | }; |
1086 | | let mut iter = iterable.into_iter(); |
1087 | | loop { |
1088 | | if let Some(elt) = iter.next() { |
1089 | | if ptr == end_ptr && CHECK { extend_panic(); } |
1090 | | debug_assert_ne!(ptr, end_ptr); |
1091 | | ptr.write(elt); |
1092 | | ptr = raw_ptr_add(ptr, 1); |
1093 | | guard.data += 1; |
1094 | | } else { |
1095 | | return; // success |
1096 | | } |
1097 | | } |
1098 | | } |
1099 | | |
1100 | | /// Extend the ArrayVec with clones of elements from the slice; |
1101 | | /// the length of the slice must be <= the remaining capacity in the arrayvec. |
1102 | | pub(crate) fn extend_from_slice(&mut self, slice: &[T]) |
1103 | | where T: Clone |
1104 | | { |
1105 | | let take = self.capacity() - self.len(); |
1106 | | debug_assert!(slice.len() <= take); |
1107 | | unsafe { |
1108 | | let slice = if take < slice.len() { &slice[..take] } else { slice }; |
1109 | | self.extend_from_iter::<_, false>(slice.iter().cloned()); |
1110 | | } |
1111 | | } |
1112 | | } |
1113 | | |
1114 | | /// Rawptr add but uses arithmetic distance for ZST |
1115 | | unsafe fn raw_ptr_add<T>(ptr: *mut T, offset: usize) -> *mut T { |
1116 | | if mem::size_of::<T>() == 0 { |
1117 | | // Special case for ZST |
1118 | | ptr.cast::<u8>().wrapping_add(offset).cast() |
1119 | | } else { |
1120 | | ptr.add(offset) |
1121 | | } |
1122 | | } |
1123 | | |
1124 | | /// Create an `ArrayVec` from an iterator. |
1125 | | /// |
1126 | | /// ***Panics*** if the number of elements in the iterator exceeds the arrayvec's capacity. |
1127 | | impl<T, const CAP: usize> iter::FromIterator<T> for ArrayVec<T, CAP> { |
1128 | | /// Create an `ArrayVec` from an iterator. |
1129 | | /// |
1130 | | /// ***Panics*** if the number of elements in the iterator exceeds the arrayvec's capacity. |
1131 | | fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self { |
1132 | | let mut array = ArrayVec::new(); |
1133 | | array.extend(iter); |
1134 | | array |
1135 | | } |
1136 | | } |
1137 | | |
1138 | | impl<T, const CAP: usize> Clone for ArrayVec<T, CAP> |
1139 | | where T: Clone |
1140 | | { |
1141 | | fn clone(&self) -> Self { |
1142 | | self.iter().cloned().collect() |
1143 | | } |
1144 | | |
1145 | | fn clone_from(&mut self, rhs: &Self) { |
1146 | | // recursive case for the common prefix |
1147 | | let prefix = cmp::min(self.len(), rhs.len()); |
1148 | | self[..prefix].clone_from_slice(&rhs[..prefix]); |
1149 | | |
1150 | | if prefix < self.len() { |
1151 | | // rhs was shorter |
1152 | | self.truncate(prefix); |
1153 | | } else { |
1154 | | let rhs_elems = &rhs[self.len()..]; |
1155 | | self.extend_from_slice(rhs_elems); |
1156 | | } |
1157 | | } |
1158 | | } |
1159 | | |
1160 | | impl<T, const CAP: usize> Hash for ArrayVec<T, CAP> |
1161 | | where T: Hash |
1162 | | { |
1163 | | fn hash<H: Hasher>(&self, state: &mut H) { |
1164 | | Hash::hash(&**self, state) |
1165 | | } |
1166 | | } |
1167 | | |
1168 | | impl<T, const CAP: usize> PartialEq for ArrayVec<T, CAP> |
1169 | | where T: PartialEq |
1170 | | { |
1171 | | fn eq(&self, other: &Self) -> bool { |
1172 | | **self == **other |
1173 | | } |
1174 | | } |
1175 | | |
1176 | | impl<T, const CAP: usize> PartialEq<[T]> for ArrayVec<T, CAP> |
1177 | | where T: PartialEq |
1178 | | { |
1179 | | fn eq(&self, other: &[T]) -> bool { |
1180 | | **self == *other |
1181 | | } |
1182 | | } |
1183 | | |
1184 | | impl<T, const CAP: usize> Eq for ArrayVec<T, CAP> where T: Eq { } |
1185 | | |
1186 | | impl<T, const CAP: usize> Borrow<[T]> for ArrayVec<T, CAP> { |
1187 | | fn borrow(&self) -> &[T] { self } |
1188 | | } |
1189 | | |
1190 | | impl<T, const CAP: usize> BorrowMut<[T]> for ArrayVec<T, CAP> { |
1191 | | fn borrow_mut(&mut self) -> &mut [T] { self } |
1192 | | } |
1193 | | |
1194 | | impl<T, const CAP: usize> AsRef<[T]> for ArrayVec<T, CAP> { |
1195 | | fn as_ref(&self) -> &[T] { self } |
1196 | | } |
1197 | | |
1198 | | impl<T, const CAP: usize> AsMut<[T]> for ArrayVec<T, CAP> { |
1199 | | fn as_mut(&mut self) -> &mut [T] { self } |
1200 | | } |
1201 | | |
1202 | | impl<T, const CAP: usize> fmt::Debug for ArrayVec<T, CAP> where T: fmt::Debug { |
1203 | | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { (**self).fmt(f) } |
1204 | | } |
1205 | | |
1206 | | impl<T, const CAP: usize> Default for ArrayVec<T, CAP> { |
1207 | | /// Return an empty array |
1208 | | fn default() -> ArrayVec<T, CAP> { |
1209 | | ArrayVec::new() |
1210 | | } |
1211 | | } |
1212 | | |
1213 | | impl<T, const CAP: usize> PartialOrd for ArrayVec<T, CAP> where T: PartialOrd { |
1214 | | fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> { |
1215 | | (**self).partial_cmp(other) |
1216 | | } |
1217 | | |
1218 | | fn lt(&self, other: &Self) -> bool { |
1219 | | (**self).lt(other) |
1220 | | } |
1221 | | |
1222 | | fn le(&self, other: &Self) -> bool { |
1223 | | (**self).le(other) |
1224 | | } |
1225 | | |
1226 | | fn ge(&self, other: &Self) -> bool { |
1227 | | (**self).ge(other) |
1228 | | } |
1229 | | |
1230 | | fn gt(&self, other: &Self) -> bool { |
1231 | | (**self).gt(other) |
1232 | | } |
1233 | | } |
1234 | | |
1235 | | impl<T, const CAP: usize> Ord for ArrayVec<T, CAP> where T: Ord { |
1236 | | fn cmp(&self, other: &Self) -> cmp::Ordering { |
1237 | | (**self).cmp(other) |
1238 | | } |
1239 | | } |
1240 | | |
1241 | | #[cfg(feature="std")] |
1242 | | /// `Write` appends written data to the end of the vector. |
1243 | | /// |
1244 | | /// Requires `features="std"`. |
1245 | | impl<const CAP: usize> io::Write for ArrayVec<u8, CAP> { |
1246 | | fn write(&mut self, data: &[u8]) -> io::Result<usize> { |
1247 | | let len = cmp::min(self.remaining_capacity(), data.len()); |
1248 | | let _result = self.try_extend_from_slice(&data[..len]); |
1249 | | debug_assert!(_result.is_ok()); |
1250 | | Ok(len) |
1251 | | } |
1252 | | fn flush(&mut self) -> io::Result<()> { Ok(()) } |
1253 | | } |
1254 | | |
1255 | | #[cfg(feature="serde")] |
1256 | | /// Requires crate feature `"serde"` |
1257 | | impl<T: Serialize, const CAP: usize> Serialize for ArrayVec<T, CAP> { |
1258 | | fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> |
1259 | | where S: Serializer |
1260 | | { |
1261 | | serializer.collect_seq(self) |
1262 | | } |
1263 | | } |
1264 | | |
1265 | | #[cfg(feature="serde")] |
1266 | | /// Requires crate feature `"serde"` |
1267 | | impl<'de, T: Deserialize<'de>, const CAP: usize> Deserialize<'de> for ArrayVec<T, CAP> { |
1268 | | fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> |
1269 | | where D: Deserializer<'de> |
1270 | | { |
1271 | | use serde::de::{Visitor, SeqAccess, Error}; |
1272 | | use std::marker::PhantomData; |
1273 | | |
1274 | | struct ArrayVecVisitor<'de, T: Deserialize<'de>, const CAP: usize>(PhantomData<(&'de (), [T; CAP])>); |
1275 | | |
1276 | | impl<'de, T: Deserialize<'de>, const CAP: usize> Visitor<'de> for ArrayVecVisitor<'de, T, CAP> { |
1277 | | type Value = ArrayVec<T, CAP>; |
1278 | | |
1279 | | fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result { |
1280 | | write!(formatter, "an array with no more than {} items", CAP) |
1281 | | } |
1282 | | |
1283 | | fn visit_seq<SA>(self, mut seq: SA) -> Result<Self::Value, SA::Error> |
1284 | | where SA: SeqAccess<'de>, |
1285 | | { |
1286 | | let mut values = ArrayVec::<T, CAP>::new(); |
1287 | | |
1288 | | while let Some(value) = seq.next_element()? { |
1289 | | if let Err(_) = values.try_push(value) { |
1290 | | return Err(SA::Error::invalid_length(CAP + 1, &self)); |
1291 | | } |
1292 | | } |
1293 | | |
1294 | | Ok(values) |
1295 | | } |
1296 | | } |
1297 | | |
1298 | | deserializer.deserialize_seq(ArrayVecVisitor::<T, CAP>(PhantomData)) |
1299 | | } |
1300 | | } |