1 use super::*; 2 use core::convert::{TryFrom, TryInto}; 3 4 #[cfg(feature = "serde")] 5 use core::marker::PhantomData; 6 #[cfg(feature = "serde")] 7 use serde::de::{ 8 Deserialize, Deserializer, Error as DeserializeError, SeqAccess, Visitor, 9 }; 10 #[cfg(feature = "serde")] 11 use serde::ser::{Serialize, SerializeSeq, Serializer}; 12 13 /// Helper to make an `ArrayVec`. 14 /// 15 /// You specify the backing array type, and optionally give all the elements you 16 /// want to initially place into the array. 17 /// 18 /// ```rust 19 /// use tinyvec::*; 20 /// 21 /// // The backing array type can be specified in the macro call 22 /// let empty_av = array_vec!([u8; 16]); 23 /// let some_ints = array_vec!([i32; 4] => 1, 2, 3); 24 /// 25 /// // Or left to inference 26 /// let empty_av: ArrayVec<[u8; 10]> = array_vec!(); 27 /// let some_ints: ArrayVec<[u8; 10]> = array_vec!(5, 6, 7, 8); 28 /// ``` 29 #[macro_export] 30 macro_rules! array_vec { 31 ($array_type:ty => $($elem:expr),* $(,)?) => { 32 { 33 let mut av: $crate::ArrayVec<$array_type> = Default::default(); 34 $( av.push($elem); )* 35 av 36 } 37 }; 38 ($array_type:ty) => { 39 $crate::ArrayVec::<$array_type>::default() 40 }; 41 ($($elem:expr),*) => { 42 $crate::array_vec!(_ => $($elem),*) 43 }; 44 ($elem:expr; $n:expr) => { 45 $crate::ArrayVec::from([$elem; $n]) 46 }; 47 () => { 48 $crate::array_vec!(_) 49 }; 50 } 51 52 /// An array-backed, vector-like data structure. 53 /// 54 /// * `ArrayVec` has a fixed capacity, equal to the array size. 55 /// * `ArrayVec` has a variable length, as you add and remove elements. Attempts 56 /// to fill the vec beyond its capacity will cause a panic. 57 /// * All of the vec's array slots are always initialized in terms of Rust's 58 /// memory model. When you remove a element from a location, the old value at 59 /// that location is replaced with the type's default value. 60 /// 61 /// The overall API of this type is intended to, as much as possible, emulate 62 /// the API of the [`Vec`](https://doc.rust-lang.org/alloc/vec/struct.Vec.html) 63 /// type. 64 /// 65 /// ## Construction 66 /// 67 /// You can use the `array_vec!` macro similarly to how you might use the `vec!` 68 /// macro. Specify the array type, then optionally give all the initial values 69 /// you want to have. 70 /// ```rust 71 /// # use tinyvec::*; 72 /// let some_ints = array_vec!([i32; 4] => 1, 2, 3); 73 /// assert_eq!(some_ints.len(), 3); 74 /// ``` 75 /// 76 /// The [`default`](ArrayVec::new) for an `ArrayVec` is to have a default 77 /// array with length 0. The [`new`](ArrayVec::new) method is the same as 78 /// calling `default` 79 /// ```rust 80 /// # use tinyvec::*; 81 /// let some_ints = ArrayVec::<[i32; 7]>::default(); 82 /// assert_eq!(some_ints.len(), 0); 83 /// 84 /// let more_ints = ArrayVec::<[i32; 7]>::new(); 85 /// assert_eq!(some_ints, more_ints); 86 /// ``` 87 /// 88 /// If you have an array and want the _whole thing_ so count as being "in" the 89 /// new `ArrayVec` you can use one of the `from` implementations. If you want 90 /// _part of_ the array then you can use 91 /// [`from_array_len`](ArrayVec::from_array_len): 92 /// ```rust 93 /// # use tinyvec::*; 94 /// let some_ints = ArrayVec::from([5, 6, 7, 8]); 95 /// assert_eq!(some_ints.len(), 4); 96 /// 97 /// let more_ints = ArrayVec::from_array_len([5, 6, 7, 8], 2); 98 /// assert_eq!(more_ints.len(), 2); 99 /// 100 /// let no_ints: ArrayVec<[u8; 5]> = ArrayVec::from_array_empty([1, 2, 3, 4, 5]); 101 /// assert_eq!(no_ints.len(), 0); 102 /// ``` 103 #[repr(C)] 104 pub struct ArrayVec<A> { 105 len: u16, 106 pub(crate) data: A, 107 } 108 109 impl<A> Clone for ArrayVec<A> 110 where 111 A: Array + Clone, 112 A::Item: Clone, 113 { 114 #[inline] clone(&self) -> Self115 fn clone(&self) -> Self { 116 Self { data: self.data.clone(), len: self.len } 117 } 118 119 #[inline] clone_from(&mut self, o: &Self)120 fn clone_from(&mut self, o: &Self) { 121 let iter = self 122 .data 123 .as_slice_mut() 124 .iter_mut() 125 .zip(o.data.as_slice()) 126 .take(self.len.max(o.len) as usize); 127 for (dst, src) in iter { 128 dst.clone_from(src) 129 } 130 if let Some(to_drop) = 131 self.data.as_slice_mut().get_mut((o.len as usize)..(self.len as usize)) 132 { 133 to_drop.iter_mut().for_each(|x| drop(take(x))); 134 } 135 self.len = o.len; 136 } 137 } 138 139 impl<A> Copy for ArrayVec<A> 140 where 141 A: Array + Copy, 142 A::Item: Copy, 143 { 144 } 145 146 impl<A: Array> Default for ArrayVec<A> { default() -> Self147 fn default() -> Self { 148 Self { len: 0, data: A::default() } 149 } 150 } 151 152 impl<A: Array> Deref for ArrayVec<A> { 153 type Target = [A::Item]; 154 #[inline(always)] 155 #[must_use] deref(&self) -> &Self::Target156 fn deref(&self) -> &Self::Target { 157 &self.data.as_slice()[..self.len as usize] 158 } 159 } 160 161 impl<A: Array> DerefMut for ArrayVec<A> { 162 #[inline(always)] 163 #[must_use] deref_mut(&mut self) -> &mut Self::Target164 fn deref_mut(&mut self) -> &mut Self::Target { 165 &mut self.data.as_slice_mut()[..self.len as usize] 166 } 167 } 168 169 impl<A: Array, I: SliceIndex<[A::Item]>> Index<I> for ArrayVec<A> { 170 type Output = <I as SliceIndex<[A::Item]>>::Output; 171 #[inline(always)] 172 #[must_use] index(&self, index: I) -> &Self::Output173 fn index(&self, index: I) -> &Self::Output { 174 &self.deref()[index] 175 } 176 } 177 178 impl<A: Array, I: SliceIndex<[A::Item]>> IndexMut<I> for ArrayVec<A> { 179 #[inline(always)] 180 #[must_use] index_mut(&mut self, index: I) -> &mut Self::Output181 fn index_mut(&mut self, index: I) -> &mut Self::Output { 182 &mut self.deref_mut()[index] 183 } 184 } 185 186 #[cfg(feature = "serde")] 187 #[cfg_attr(docs_rs, doc(cfg(feature = "serde")))] 188 impl<A: Array> Serialize for ArrayVec<A> 189 where 190 A::Item: Serialize, 191 { 192 #[must_use] serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer,193 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> 194 where 195 S: Serializer, 196 { 197 let mut seq = serializer.serialize_seq(Some(self.len()))?; 198 for element in self.iter() { 199 seq.serialize_element(element)?; 200 } 201 seq.end() 202 } 203 } 204 205 #[cfg(feature = "serde")] 206 #[cfg_attr(docs_rs, doc(cfg(feature = "serde")))] 207 impl<'de, A: Array> Deserialize<'de> for ArrayVec<A> 208 where 209 A::Item: Deserialize<'de>, 210 { deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>,211 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> 212 where 213 D: Deserializer<'de>, 214 { 215 deserializer.deserialize_seq(ArrayVecVisitor(PhantomData)) 216 } 217 } 218 219 #[cfg(all(feature = "arbitrary", feature = "nightly_const_generics"))] 220 #[cfg_attr( 221 docs_rs, 222 doc(cfg(all(feature = "arbitrary", feature = "nightly_const_generics"))) 223 )] 224 impl<'a, T, const N: usize> arbitrary::Arbitrary<'a> for ArrayVec<[T; N]> 225 where 226 T: arbitrary::Arbitrary<'a> + Default, 227 { arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self>228 fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> { 229 let v = <[T; N]>::arbitrary(u)?; 230 let av = ArrayVec::from(v); 231 Ok(av) 232 } 233 } 234 235 impl<A: Array> ArrayVec<A> { 236 /// Move all values from `other` into this vec. 237 /// 238 /// ## Panics 239 /// * If the vec overflows its capacity 240 /// 241 /// ## Example 242 /// ```rust 243 /// # use tinyvec::*; 244 /// let mut av = array_vec!([i32; 10] => 1, 2, 3); 245 /// let mut av2 = array_vec!([i32; 10] => 4, 5, 6); 246 /// av.append(&mut av2); 247 /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]); 248 /// assert_eq!(av2, &[][..]); 249 /// ``` 250 #[inline] append(&mut self, other: &mut Self)251 pub fn append(&mut self, other: &mut Self) { 252 assert!( 253 self.try_append(other).is_none(), 254 "ArrayVec::append> total length {} exceeds capacity {}!", 255 self.len() + other.len(), 256 A::CAPACITY 257 ); 258 } 259 260 /// Move all values from `other` into this vec. 261 /// If appending would overflow the capacity, Some(other) is returned. 262 /// ## Example 263 /// ```rust 264 /// # use tinyvec::*; 265 /// let mut av = array_vec!([i32; 7] => 1, 2, 3); 266 /// let mut av2 = array_vec!([i32; 7] => 4, 5, 6); 267 /// av.append(&mut av2); 268 /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]); 269 /// assert_eq!(av2, &[][..]); 270 /// 271 /// let mut av3 = array_vec!([i32; 7] => 7, 8, 9); 272 /// assert!(av.try_append(&mut av3).is_some()); 273 /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]); 274 /// assert_eq!(av3, &[7, 8, 9][..]); 275 /// ``` 276 #[inline] try_append<'other>( &mut self, other: &'other mut Self, ) -> Option<&'other mut Self>277 pub fn try_append<'other>( 278 &mut self, other: &'other mut Self, 279 ) -> Option<&'other mut Self> { 280 let new_len = self.len() + other.len(); 281 if new_len > A::CAPACITY { 282 return Some(other); 283 } 284 285 let iter = other.iter_mut().map(take); 286 for item in iter { 287 self.push(item); 288 } 289 290 other.set_len(0); 291 292 return None; 293 } 294 295 /// A `*mut` pointer to the backing array. 296 /// 297 /// ## Safety 298 /// 299 /// This pointer has provenance over the _entire_ backing array. 300 #[inline(always)] 301 #[must_use] as_mut_ptr(&mut self) -> *mut A::Item302 pub fn as_mut_ptr(&mut self) -> *mut A::Item { 303 self.data.as_slice_mut().as_mut_ptr() 304 } 305 306 /// Performs a `deref_mut`, into unique slice form. 307 #[inline(always)] 308 #[must_use] as_mut_slice(&mut self) -> &mut [A::Item]309 pub fn as_mut_slice(&mut self) -> &mut [A::Item] { 310 self.deref_mut() 311 } 312 313 /// A `*const` pointer to the backing array. 314 /// 315 /// ## Safety 316 /// 317 /// This pointer has provenance over the _entire_ backing array. 318 #[inline(always)] 319 #[must_use] as_ptr(&self) -> *const A::Item320 pub fn as_ptr(&self) -> *const A::Item { 321 self.data.as_slice().as_ptr() 322 } 323 324 /// Performs a `deref`, into shared slice form. 325 #[inline(always)] 326 #[must_use] as_slice(&self) -> &[A::Item]327 pub fn as_slice(&self) -> &[A::Item] { 328 self.deref() 329 } 330 331 /// The capacity of the `ArrayVec`. 332 /// 333 /// This is fixed based on the array type, but can't yet be made a `const fn` 334 /// on Stable Rust. 335 #[inline(always)] 336 #[must_use] capacity(&self) -> usize337 pub fn capacity(&self) -> usize { 338 // Note: This shouldn't use A::CAPACITY, because unsafe code can't rely on 339 // any Array invariants. This ensures that at the very least, the returned 340 // value is a valid length for a subslice of the backing array. 341 self.data.as_slice().len() 342 } 343 344 /// Truncates the `ArrayVec` down to length 0. 345 #[inline(always)] clear(&mut self)346 pub fn clear(&mut self) { 347 self.truncate(0) 348 } 349 350 /// Creates a draining iterator that removes the specified range in the vector 351 /// and yields the removed items. 352 /// 353 /// ## Panics 354 /// * If the start is greater than the end 355 /// * If the end is past the edge of the vec. 356 /// 357 /// ## Example 358 /// ```rust 359 /// # use tinyvec::*; 360 /// let mut av = array_vec!([i32; 4] => 1, 2, 3); 361 /// let av2: ArrayVec<[i32; 4]> = av.drain(1..).collect(); 362 /// assert_eq!(av.as_slice(), &[1][..]); 363 /// assert_eq!(av2.as_slice(), &[2, 3][..]); 364 /// 365 /// av.drain(..); 366 /// assert_eq!(av.as_slice(), &[]); 367 /// ``` 368 #[inline] drain<R>(&mut self, range: R) -> ArrayVecDrain<'_, A::Item> where R: RangeBounds<usize>,369 pub fn drain<R>(&mut self, range: R) -> ArrayVecDrain<'_, A::Item> 370 where 371 R: RangeBounds<usize>, 372 { 373 ArrayVecDrain::new(self, range) 374 } 375 376 /// Returns the inner array of the `ArrayVec`. 377 /// 378 /// This returns the full array, even if the `ArrayVec` length is currently 379 /// less than that. 380 /// 381 /// ## Example 382 /// 383 /// ```rust 384 /// # use tinyvec::{array_vec, ArrayVec}; 385 /// let mut favorite_numbers = array_vec!([i32; 5] => 87, 48, 33, 9, 26); 386 /// assert_eq!(favorite_numbers.clone().into_inner(), [87, 48, 33, 9, 26]); 387 /// 388 /// favorite_numbers.pop(); 389 /// assert_eq!(favorite_numbers.into_inner(), [87, 48, 33, 9, 0]); 390 /// ``` 391 /// 392 /// A use for this function is to build an array from an iterator by first 393 /// collecting it into an `ArrayVec`. 394 /// 395 /// ```rust 396 /// # use tinyvec::ArrayVec; 397 /// let arr_vec: ArrayVec<[i32; 10]> = (1..=3).cycle().take(10).collect(); 398 /// let inner = arr_vec.into_inner(); 399 /// assert_eq!(inner, [1, 2, 3, 1, 2, 3, 1, 2, 3, 1]); 400 /// ``` 401 #[inline] into_inner(self) -> A402 pub fn into_inner(self) -> A { 403 self.data 404 } 405 406 /// Clone each element of the slice into this `ArrayVec`. 407 /// 408 /// ## Panics 409 /// * If the `ArrayVec` would overflow, this will panic. 410 #[inline] extend_from_slice(&mut self, sli: &[A::Item]) where A::Item: Clone,411 pub fn extend_from_slice(&mut self, sli: &[A::Item]) 412 where 413 A::Item: Clone, 414 { 415 if sli.is_empty() { 416 return; 417 } 418 419 let new_len = self.len as usize + sli.len(); 420 assert!( 421 new_len <= A::CAPACITY, 422 "ArrayVec::extend_from_slice> total length {} exceeds capacity {}!", 423 new_len, 424 A::CAPACITY 425 ); 426 427 let target = &mut self.data.as_slice_mut()[self.len as usize..new_len]; 428 target.clone_from_slice(sli); 429 self.set_len(new_len); 430 } 431 432 /// Fill the vector until its capacity has been reached. 433 /// 434 /// Successively fills unused space in the spare slice of the vector with 435 /// elements from the iterator. It then returns the remaining iterator 436 /// without exhausting it. This also allows appending the head of an 437 /// infinite iterator. 438 /// 439 /// This is an alternative to `Extend::extend` method for cases where the 440 /// length of the iterator can not be checked. Since this vector can not 441 /// reallocate to increase its capacity, it is unclear what to do with 442 /// remaining elements in the iterator and the iterator itself. The 443 /// interface also provides no way to communicate this to the caller. 444 /// 445 /// ## Panics 446 /// * If the `next` method of the provided iterator panics. 447 /// 448 /// ## Example 449 /// 450 /// ```rust 451 /// # use tinyvec::*; 452 /// let mut av = array_vec!([i32; 4]); 453 /// let mut to_inf = av.fill(0..); 454 /// assert_eq!(&av[..], [0, 1, 2, 3]); 455 /// assert_eq!(to_inf.next(), Some(4)); 456 /// ``` 457 #[inline] fill<I: IntoIterator<Item = A::Item>>( &mut self, iter: I, ) -> I::IntoIter458 pub fn fill<I: IntoIterator<Item = A::Item>>( 459 &mut self, iter: I, 460 ) -> I::IntoIter { 461 // If this is written as a call to push for each element in iter, the 462 // compiler emits code that updates the length for every element. The 463 // additional complexity from that length update is worth nearly 2x in 464 // the runtime of this function. 465 let mut iter = iter.into_iter(); 466 let mut pushed = 0; 467 let to_take = self.capacity() - self.len(); 468 let target = &mut self.data.as_slice_mut()[self.len as usize..]; 469 for element in iter.by_ref().take(to_take) { 470 target[pushed] = element; 471 pushed += 1; 472 } 473 self.len += pushed as u16; 474 iter 475 } 476 477 /// Wraps up an array and uses the given length as the initial length. 478 /// 479 /// If you want to simply use the full array, use `from` instead. 480 /// 481 /// ## Panics 482 /// 483 /// * The length specified must be less than or equal to the capacity of the 484 /// array. 485 #[inline] 486 #[must_use] 487 #[allow(clippy::match_wild_err_arm)] from_array_len(data: A, len: usize) -> Self488 pub fn from_array_len(data: A, len: usize) -> Self { 489 match Self::try_from_array_len(data, len) { 490 Ok(out) => out, 491 Err(_) => panic!( 492 "ArrayVec::from_array_len> length {} exceeds capacity {}!", 493 len, 494 A::CAPACITY 495 ), 496 } 497 } 498 499 /// Inserts an item at the position given, moving all following elements +1 500 /// index. 501 /// 502 /// ## Panics 503 /// * If `index` > `len` 504 /// * If the capacity is exhausted 505 /// 506 /// ## Example 507 /// ```rust 508 /// use tinyvec::*; 509 /// let mut av = array_vec!([i32; 10] => 1, 2, 3); 510 /// av.insert(1, 4); 511 /// assert_eq!(av.as_slice(), &[1, 4, 2, 3]); 512 /// av.insert(4, 5); 513 /// assert_eq!(av.as_slice(), &[1, 4, 2, 3, 5]); 514 /// ``` 515 #[inline] insert(&mut self, index: usize, item: A::Item)516 pub fn insert(&mut self, index: usize, item: A::Item) { 517 let x = self.try_insert(index, item); 518 assert!(x.is_none(), "ArrayVec::insert> capacity overflow!"); 519 } 520 521 /// Tries to insert an item at the position given, moving all following 522 /// elements +1 index. 523 /// Returns back the element if the capacity is exhausted, 524 /// otherwise returns None. 525 /// 526 /// ## Panics 527 /// * If `index` > `len` 528 /// 529 /// ## Example 530 /// ```rust 531 /// use tinyvec::*; 532 /// let mut av = array_vec!([&'static str; 4] => "one", "two", "three"); 533 /// av.insert(1, "four"); 534 /// assert_eq!(av.as_slice(), &["one", "four", "two", "three"]); 535 /// assert_eq!(av.try_insert(4, "five"), Some("five")); 536 /// ``` 537 #[inline] try_insert( &mut self, index: usize, mut item: A::Item, ) -> Option<A::Item>538 pub fn try_insert( 539 &mut self, index: usize, mut item: A::Item, 540 ) -> Option<A::Item> { 541 assert!( 542 index <= self.len as usize, 543 "ArrayVec::try_insert> index {} is out of bounds {}", 544 index, 545 self.len 546 ); 547 548 // A previous implementation used self.try_push and slice::rotate_right 549 // rotate_right and rotate_left generate a huge amount of code and fail to 550 // inline; calling them here incurs the cost of all the cases they 551 // handle even though we're rotating a usually-small array by a constant 552 // 1 offset. This swap-based implementation benchmarks much better for 553 // small array lengths in particular. 554 555 if (self.len as usize) < A::CAPACITY { 556 self.len += 1; 557 } else { 558 return Some(item); 559 } 560 561 let target = &mut self.as_mut_slice()[index..]; 562 for i in 0..target.len() { 563 core::mem::swap(&mut item, &mut target[i]); 564 } 565 return None; 566 } 567 568 /// Checks if the length is 0. 569 #[inline(always)] 570 #[must_use] is_empty(&self) -> bool571 pub fn is_empty(&self) -> bool { 572 self.len == 0 573 } 574 575 /// The length of the `ArrayVec` (in elements). 576 #[inline(always)] 577 #[must_use] len(&self) -> usize578 pub fn len(&self) -> usize { 579 self.len as usize 580 } 581 582 /// Makes a new, empty `ArrayVec`. 583 #[inline(always)] 584 #[must_use] new() -> Self585 pub fn new() -> Self { 586 Self::default() 587 } 588 589 /// Remove and return the last element of the vec, if there is one. 590 /// 591 /// ## Failure 592 /// * If the vec is empty you get `None`. 593 /// 594 /// ## Example 595 /// ```rust 596 /// # use tinyvec::*; 597 /// let mut av = array_vec!([i32; 10] => 1, 2); 598 /// assert_eq!(av.pop(), Some(2)); 599 /// assert_eq!(av.pop(), Some(1)); 600 /// assert_eq!(av.pop(), None); 601 /// ``` 602 #[inline] pop(&mut self) -> Option<A::Item>603 pub fn pop(&mut self) -> Option<A::Item> { 604 if self.len > 0 { 605 self.len -= 1; 606 let out = take(&mut self.data.as_slice_mut()[self.len as usize]); 607 Some(out) 608 } else { 609 None 610 } 611 } 612 613 /// Place an element onto the end of the vec. 614 /// 615 /// ## Panics 616 /// * If the length of the vec would overflow the capacity. 617 /// 618 /// ## Example 619 /// ```rust 620 /// # use tinyvec::*; 621 /// let mut av = array_vec!([i32; 2]); 622 /// assert_eq!(&av[..], []); 623 /// av.push(1); 624 /// assert_eq!(&av[..], [1]); 625 /// av.push(2); 626 /// assert_eq!(&av[..], [1, 2]); 627 /// // av.push(3); this would overflow the ArrayVec and panic! 628 /// ``` 629 #[inline(always)] push(&mut self, val: A::Item)630 pub fn push(&mut self, val: A::Item) { 631 let x = self.try_push(val); 632 assert!(x.is_none(), "ArrayVec::push> capacity overflow!"); 633 } 634 635 /// Tries to place an element onto the end of the vec.\ 636 /// Returns back the element if the capacity is exhausted, 637 /// otherwise returns None. 638 /// ```rust 639 /// # use tinyvec::*; 640 /// let mut av = array_vec!([i32; 2]); 641 /// assert_eq!(av.as_slice(), []); 642 /// assert_eq!(av.try_push(1), None); 643 /// assert_eq!(&av[..], [1]); 644 /// assert_eq!(av.try_push(2), None); 645 /// assert_eq!(&av[..], [1, 2]); 646 /// assert_eq!(av.try_push(3), Some(3)); 647 /// ``` 648 #[inline(always)] try_push(&mut self, val: A::Item) -> Option<A::Item>649 pub fn try_push(&mut self, val: A::Item) -> Option<A::Item> { 650 debug_assert!(self.len as usize <= A::CAPACITY); 651 652 let itemref = match self.data.as_slice_mut().get_mut(self.len as usize) { 653 None => return Some(val), 654 Some(x) => x, 655 }; 656 657 *itemref = val; 658 self.len += 1; 659 return None; 660 } 661 662 /// Removes the item at `index`, shifting all others down by one index. 663 /// 664 /// Returns the removed element. 665 /// 666 /// ## Panics 667 /// 668 /// * If the index is out of bounds. 669 /// 670 /// ## Example 671 /// 672 /// ```rust 673 /// # use tinyvec::*; 674 /// let mut av = array_vec!([i32; 4] => 1, 2, 3); 675 /// assert_eq!(av.remove(1), 2); 676 /// assert_eq!(&av[..], [1, 3]); 677 /// ``` 678 #[inline] remove(&mut self, index: usize) -> A::Item679 pub fn remove(&mut self, index: usize) -> A::Item { 680 let targets: &mut [A::Item] = &mut self.deref_mut()[index..]; 681 let item = take(&mut targets[0]); 682 683 // A previous implementation used rotate_left 684 // rotate_right and rotate_left generate a huge amount of code and fail to 685 // inline; calling them here incurs the cost of all the cases they 686 // handle even though we're rotating a usually-small array by a constant 687 // 1 offset. This swap-based implementation benchmarks much better for 688 // small array lengths in particular. 689 690 for i in 0..targets.len() - 1 { 691 targets.swap(i, i + 1); 692 } 693 self.len -= 1; 694 item 695 } 696 697 /// As [`resize_with`](ArrayVec::resize_with) 698 /// and it clones the value as the closure. 699 /// 700 /// ## Example 701 /// 702 /// ```rust 703 /// # use tinyvec::*; 704 /// 705 /// let mut av = array_vec!([&str; 10] => "hello"); 706 /// av.resize(3, "world"); 707 /// assert_eq!(&av[..], ["hello", "world", "world"]); 708 /// 709 /// let mut av = array_vec!([i32; 10] => 1, 2, 3, 4); 710 /// av.resize(2, 0); 711 /// assert_eq!(&av[..], [1, 2]); 712 /// ``` 713 #[inline] resize(&mut self, new_len: usize, new_val: A::Item) where A::Item: Clone,714 pub fn resize(&mut self, new_len: usize, new_val: A::Item) 715 where 716 A::Item: Clone, 717 { 718 self.resize_with(new_len, || new_val.clone()) 719 } 720 721 /// Resize the vec to the new length. 722 /// 723 /// If it needs to be longer, it's filled with repeated calls to the provided 724 /// function. If it needs to be shorter, it's truncated. 725 /// 726 /// ## Example 727 /// 728 /// ```rust 729 /// # use tinyvec::*; 730 /// 731 /// let mut av = array_vec!([i32; 10] => 1, 2, 3); 732 /// av.resize_with(5, Default::default); 733 /// assert_eq!(&av[..], [1, 2, 3, 0, 0]); 734 /// 735 /// let mut av = array_vec!([i32; 10]); 736 /// let mut p = 1; 737 /// av.resize_with(4, || { 738 /// p *= 2; 739 /// p 740 /// }); 741 /// assert_eq!(&av[..], [2, 4, 8, 16]); 742 /// ``` 743 #[inline] resize_with<F: FnMut() -> A::Item>( &mut self, new_len: usize, mut f: F, )744 pub fn resize_with<F: FnMut() -> A::Item>( 745 &mut self, new_len: usize, mut f: F, 746 ) { 747 match new_len.checked_sub(self.len as usize) { 748 None => self.truncate(new_len), 749 Some(new_elements) => { 750 for _ in 0..new_elements { 751 self.push(f()); 752 } 753 } 754 } 755 } 756 757 /// Walk the vec and keep only the elements that pass the predicate given. 758 /// 759 /// ## Example 760 /// 761 /// ```rust 762 /// # use tinyvec::*; 763 /// 764 /// let mut av = array_vec!([i32; 10] => 1, 1, 2, 3, 3, 4); 765 /// av.retain(|&x| x % 2 == 0); 766 /// assert_eq!(&av[..], [2, 4]); 767 /// ``` 768 #[inline] retain<F: FnMut(&A::Item) -> bool>(&mut self, mut acceptable: F)769 pub fn retain<F: FnMut(&A::Item) -> bool>(&mut self, mut acceptable: F) { 770 // Drop guard to contain exactly the remaining elements when the test 771 // panics. 772 struct JoinOnDrop<'vec, Item> { 773 items: &'vec mut [Item], 774 done_end: usize, 775 // Start of tail relative to `done_end`. 776 tail_start: usize, 777 } 778 779 impl<Item> Drop for JoinOnDrop<'_, Item> { 780 fn drop(&mut self) { 781 self.items[self.done_end..].rotate_left(self.tail_start); 782 } 783 } 784 785 let mut rest = JoinOnDrop { 786 items: &mut self.data.as_slice_mut()[..self.len as usize], 787 done_end: 0, 788 tail_start: 0, 789 }; 790 791 let len = self.len as usize; 792 for idx in 0..len { 793 // Loop start invariant: idx = rest.done_end + rest.tail_start 794 if !acceptable(&rest.items[idx]) { 795 let _ = take(&mut rest.items[idx]); 796 self.len -= 1; 797 rest.tail_start += 1; 798 } else { 799 rest.items.swap(rest.done_end, idx); 800 rest.done_end += 1; 801 } 802 } 803 } 804 805 /// Forces the length of the vector to `new_len`. 806 /// 807 /// ## Panics 808 /// * If `new_len` is greater than the vec's capacity. 809 /// 810 /// ## Safety 811 /// * This is a fully safe operation! The inactive memory already counts as 812 /// "initialized" by Rust's rules. 813 /// * Other than "the memory is initialized" there are no other guarantees 814 /// regarding what you find in the inactive portion of the vec. 815 #[inline(always)] set_len(&mut self, new_len: usize)816 pub fn set_len(&mut self, new_len: usize) { 817 if new_len > A::CAPACITY { 818 // Note(Lokathor): Technically we don't have to panic here, and we could 819 // just let some other call later on trigger a panic on accident when the 820 // length is wrong. However, it's a lot easier to catch bugs when things 821 // are more "fail-fast". 822 panic!( 823 "ArrayVec::set_len> new length {} exceeds capacity {}", 824 new_len, 825 A::CAPACITY 826 ) 827 } 828 829 let new_len: u16 = new_len 830 .try_into() 831 .expect("ArrayVec::set_len> new length is not in range 0..=u16::MAX"); 832 self.len = new_len; 833 } 834 835 /// Splits the collection at the point given. 836 /// 837 /// * `[0, at)` stays in this vec 838 /// * `[at, len)` ends up in the new vec. 839 /// 840 /// ## Panics 841 /// * if at > len 842 /// 843 /// ## Example 844 /// 845 /// ```rust 846 /// # use tinyvec::*; 847 /// let mut av = array_vec!([i32; 4] => 1, 2, 3); 848 /// let av2 = av.split_off(1); 849 /// assert_eq!(&av[..], [1]); 850 /// assert_eq!(&av2[..], [2, 3]); 851 /// ``` 852 #[inline] split_off(&mut self, at: usize) -> Self853 pub fn split_off(&mut self, at: usize) -> Self { 854 // FIXME: should this just use drain into the output? 855 if at > self.len() { 856 panic!( 857 "ArrayVec::split_off> at value {} exceeds length of {}", 858 at, self.len 859 ); 860 } 861 let mut new = Self::default(); 862 let moves = &mut self.as_mut_slice()[at..]; 863 let split_len = moves.len(); 864 let targets = &mut new.data.as_slice_mut()[..split_len]; 865 moves.swap_with_slice(targets); 866 867 /* moves.len() <= u16::MAX, so these are surely in u16 range */ 868 new.len = split_len as u16; 869 self.len = at as u16; 870 new 871 } 872 873 /// Creates a splicing iterator that removes the specified range in the 874 /// vector, yields the removed items, and replaces them with elements from 875 /// the provided iterator. 876 /// 877 /// `splice` fuses the provided iterator, so elements after the first `None` 878 /// are ignored. 879 /// 880 /// ## Panics 881 /// * If the start is greater than the end. 882 /// * If the end is past the edge of the vec. 883 /// * If the provided iterator panics. 884 /// * If the new length would overflow the capacity of the array. Because 885 /// `ArrayVecSplice` adds elements to this vec in its destructor when 886 /// necessary, this panic would occur when it is dropped. 887 /// 888 /// ## Example 889 /// ```rust 890 /// use tinyvec::*; 891 /// let mut av = array_vec!([i32; 4] => 1, 2, 3); 892 /// let av2: ArrayVec<[i32; 4]> = av.splice(1.., 4..=6).collect(); 893 /// assert_eq!(av.as_slice(), &[1, 4, 5, 6][..]); 894 /// assert_eq!(av2.as_slice(), &[2, 3][..]); 895 /// 896 /// av.splice(.., None); 897 /// assert_eq!(av.as_slice(), &[]); 898 /// ``` 899 #[inline] splice<R, I>( &mut self, range: R, replacement: I, ) -> ArrayVecSplice<'_, A, core::iter::Fuse<I::IntoIter>> where R: RangeBounds<usize>, I: IntoIterator<Item = A::Item>,900 pub fn splice<R, I>( 901 &mut self, range: R, replacement: I, 902 ) -> ArrayVecSplice<'_, A, core::iter::Fuse<I::IntoIter>> 903 where 904 R: RangeBounds<usize>, 905 I: IntoIterator<Item = A::Item>, 906 { 907 use core::ops::Bound; 908 let start = match range.start_bound() { 909 Bound::Included(x) => *x, 910 Bound::Excluded(x) => x.saturating_add(1), 911 Bound::Unbounded => 0, 912 }; 913 let end = match range.end_bound() { 914 Bound::Included(x) => x.saturating_add(1), 915 Bound::Excluded(x) => *x, 916 Bound::Unbounded => self.len(), 917 }; 918 assert!( 919 start <= end, 920 "ArrayVec::splice> Illegal range, {} to {}", 921 start, 922 end 923 ); 924 assert!( 925 end <= self.len(), 926 "ArrayVec::splice> Range ends at {} but length is only {}!", 927 end, 928 self.len() 929 ); 930 931 ArrayVecSplice { 932 removal_start: start, 933 removal_end: end, 934 parent: self, 935 replacement: replacement.into_iter().fuse(), 936 } 937 } 938 939 /// Remove an element, swapping the end of the vec into its place. 940 /// 941 /// ## Panics 942 /// * If the index is out of bounds. 943 /// 944 /// ## Example 945 /// ```rust 946 /// # use tinyvec::*; 947 /// let mut av = array_vec!([&str; 4] => "foo", "bar", "quack", "zap"); 948 /// 949 /// assert_eq!(av.swap_remove(1), "bar"); 950 /// assert_eq!(&av[..], ["foo", "zap", "quack"]); 951 /// 952 /// assert_eq!(av.swap_remove(0), "foo"); 953 /// assert_eq!(&av[..], ["quack", "zap"]); 954 /// ``` 955 #[inline] swap_remove(&mut self, index: usize) -> A::Item956 pub fn swap_remove(&mut self, index: usize) -> A::Item { 957 assert!( 958 index < self.len(), 959 "ArrayVec::swap_remove> index {} is out of bounds {}", 960 index, 961 self.len 962 ); 963 if index == self.len() - 1 { 964 self.pop().unwrap() 965 } else { 966 let i = self.pop().unwrap(); 967 replace(&mut self[index], i) 968 } 969 } 970 971 /// Reduces the vec's length to the given value. 972 /// 973 /// If the vec is already shorter than the input, nothing happens. 974 #[inline] truncate(&mut self, new_len: usize)975 pub fn truncate(&mut self, new_len: usize) { 976 if new_len >= self.len as usize { 977 return; 978 } 979 980 if needs_drop::<A::Item>() { 981 let len = self.len as usize; 982 self.data.as_slice_mut()[new_len..len] 983 .iter_mut() 984 .map(take) 985 .for_each(drop); 986 } 987 988 /* new_len is less than self.len */ 989 self.len = new_len as u16; 990 } 991 992 /// Wraps an array, using the given length as the starting length. 993 /// 994 /// If you want to use the whole length of the array, you can just use the 995 /// `From` impl. 996 /// 997 /// ## Failure 998 /// 999 /// If the given length is greater than the capacity of the array this will 1000 /// error, and you'll get the array back in the `Err`. 1001 #[inline] try_from_array_len(data: A, len: usize) -> Result<Self, A>1002 pub fn try_from_array_len(data: A, len: usize) -> Result<Self, A> { 1003 /* Note(Soveu): Should we allow A::CAPACITY > u16::MAX for now? */ 1004 if len <= A::CAPACITY { 1005 Ok(Self { data, len: len as u16 }) 1006 } else { 1007 Err(data) 1008 } 1009 } 1010 } 1011 1012 impl<A> ArrayVec<A> { 1013 /// Wraps up an array as a new empty `ArrayVec`. 1014 /// 1015 /// If you want to simply use the full array, use `from` instead. 1016 /// 1017 /// ## Examples 1018 /// 1019 /// This method in particular allows to create values for statics: 1020 /// 1021 /// ```rust 1022 /// # use tinyvec::ArrayVec; 1023 /// static DATA: ArrayVec<[u8; 5]> = ArrayVec::from_array_empty([0; 5]); 1024 /// assert_eq!(DATA.len(), 0); 1025 /// ``` 1026 /// 1027 /// But of course it is just an normal empty `ArrayVec`: 1028 /// 1029 /// ```rust 1030 /// # use tinyvec::ArrayVec; 1031 /// let mut data = ArrayVec::from_array_empty([1, 2, 3, 4]); 1032 /// assert_eq!(&data[..], &[]); 1033 /// data.push(42); 1034 /// assert_eq!(&data[..], &[42]); 1035 /// ``` 1036 #[inline] 1037 #[must_use] from_array_empty(data: A) -> Self1038 pub const fn from_array_empty(data: A) -> Self { 1039 Self { data, len: 0 } 1040 } 1041 } 1042 1043 #[cfg(feature = "grab_spare_slice")] 1044 impl<A: Array> ArrayVec<A> { 1045 /// Obtain the shared slice of the array _after_ the active memory. 1046 /// 1047 /// ## Example 1048 /// ```rust 1049 /// # use tinyvec::*; 1050 /// let mut av = array_vec!([i32; 4]); 1051 /// assert_eq!(av.grab_spare_slice().len(), 4); 1052 /// av.push(10); 1053 /// av.push(11); 1054 /// av.push(12); 1055 /// av.push(13); 1056 /// assert_eq!(av.grab_spare_slice().len(), 0); 1057 /// ``` 1058 #[inline(always)] grab_spare_slice(&self) -> &[A::Item]1059 pub fn grab_spare_slice(&self) -> &[A::Item] { 1060 &self.data.as_slice()[self.len as usize..] 1061 } 1062 1063 /// Obtain the mutable slice of the array _after_ the active memory. 1064 /// 1065 /// ## Example 1066 /// ```rust 1067 /// # use tinyvec::*; 1068 /// let mut av = array_vec!([i32; 4]); 1069 /// assert_eq!(av.grab_spare_slice_mut().len(), 4); 1070 /// av.push(10); 1071 /// av.push(11); 1072 /// assert_eq!(av.grab_spare_slice_mut().len(), 2); 1073 /// ``` 1074 #[inline(always)] grab_spare_slice_mut(&mut self) -> &mut [A::Item]1075 pub fn grab_spare_slice_mut(&mut self) -> &mut [A::Item] { 1076 &mut self.data.as_slice_mut()[self.len as usize..] 1077 } 1078 } 1079 1080 #[cfg(feature = "nightly_slice_partition_dedup")] 1081 impl<A: Array> ArrayVec<A> { 1082 /// De-duplicates the vec contents. 1083 #[inline(always)] dedup(&mut self) where A::Item: PartialEq,1084 pub fn dedup(&mut self) 1085 where 1086 A::Item: PartialEq, 1087 { 1088 self.dedup_by(|a, b| a == b) 1089 } 1090 1091 /// De-duplicates the vec according to the predicate given. 1092 #[inline(always)] dedup_by<F>(&mut self, same_bucket: F) where F: FnMut(&mut A::Item, &mut A::Item) -> bool,1093 pub fn dedup_by<F>(&mut self, same_bucket: F) 1094 where 1095 F: FnMut(&mut A::Item, &mut A::Item) -> bool, 1096 { 1097 let len = { 1098 let (dedup, _) = self.as_mut_slice().partition_dedup_by(same_bucket); 1099 dedup.len() 1100 }; 1101 self.truncate(len); 1102 } 1103 1104 /// De-duplicates the vec according to the key selector given. 1105 #[inline(always)] dedup_by_key<F, K>(&mut self, mut key: F) where F: FnMut(&mut A::Item) -> K, K: PartialEq,1106 pub fn dedup_by_key<F, K>(&mut self, mut key: F) 1107 where 1108 F: FnMut(&mut A::Item) -> K, 1109 K: PartialEq, 1110 { 1111 self.dedup_by(|a, b| key(a) == key(b)) 1112 } 1113 } 1114 1115 /// Splicing iterator for `ArrayVec` 1116 /// See [`ArrayVec::splice`](ArrayVec::<A>::splice) 1117 pub struct ArrayVecSplice<'p, A: Array, I: Iterator<Item = A::Item>> { 1118 parent: &'p mut ArrayVec<A>, 1119 removal_start: usize, 1120 removal_end: usize, 1121 replacement: I, 1122 } 1123 1124 impl<'p, A: Array, I: Iterator<Item = A::Item>> Iterator 1125 for ArrayVecSplice<'p, A, I> 1126 { 1127 type Item = A::Item; 1128 1129 #[inline] next(&mut self) -> Option<A::Item>1130 fn next(&mut self) -> Option<A::Item> { 1131 if self.removal_start < self.removal_end { 1132 match self.replacement.next() { 1133 Some(replacement) => { 1134 let removed = core::mem::replace( 1135 &mut self.parent[self.removal_start], 1136 replacement, 1137 ); 1138 self.removal_start += 1; 1139 Some(removed) 1140 } 1141 None => { 1142 let removed = self.parent.remove(self.removal_start); 1143 self.removal_end -= 1; 1144 Some(removed) 1145 } 1146 } 1147 } else { 1148 None 1149 } 1150 } 1151 1152 #[inline] size_hint(&self) -> (usize, Option<usize>)1153 fn size_hint(&self) -> (usize, Option<usize>) { 1154 let len = self.len(); 1155 (len, Some(len)) 1156 } 1157 } 1158 1159 impl<'p, A, I> ExactSizeIterator for ArrayVecSplice<'p, A, I> 1160 where 1161 A: Array, 1162 I: Iterator<Item = A::Item>, 1163 { 1164 #[inline] len(&self) -> usize1165 fn len(&self) -> usize { 1166 self.removal_end - self.removal_start 1167 } 1168 } 1169 1170 impl<'p, A, I> FusedIterator for ArrayVecSplice<'p, A, I> 1171 where 1172 A: Array, 1173 I: Iterator<Item = A::Item>, 1174 { 1175 } 1176 1177 impl<'p, A, I> DoubleEndedIterator for ArrayVecSplice<'p, A, I> 1178 where 1179 A: Array, 1180 I: Iterator<Item = A::Item> + DoubleEndedIterator, 1181 { 1182 #[inline] next_back(&mut self) -> Option<A::Item>1183 fn next_back(&mut self) -> Option<A::Item> { 1184 if self.removal_start < self.removal_end { 1185 match self.replacement.next_back() { 1186 Some(replacement) => { 1187 let removed = core::mem::replace( 1188 &mut self.parent[self.removal_end - 1], 1189 replacement, 1190 ); 1191 self.removal_end -= 1; 1192 Some(removed) 1193 } 1194 None => { 1195 let removed = self.parent.remove(self.removal_end - 1); 1196 self.removal_end -= 1; 1197 Some(removed) 1198 } 1199 } 1200 } else { 1201 None 1202 } 1203 } 1204 } 1205 1206 impl<'p, A: Array, I: Iterator<Item = A::Item>> Drop 1207 for ArrayVecSplice<'p, A, I> 1208 { drop(&mut self)1209 fn drop(&mut self) { 1210 for _ in self.by_ref() {} 1211 1212 // FIXME: reserve lower bound of size_hint 1213 1214 for replacement in self.replacement.by_ref() { 1215 self.parent.insert(self.removal_end, replacement); 1216 self.removal_end += 1; 1217 } 1218 } 1219 } 1220 1221 impl<A: Array> AsMut<[A::Item]> for ArrayVec<A> { 1222 #[inline(always)] 1223 #[must_use] as_mut(&mut self) -> &mut [A::Item]1224 fn as_mut(&mut self) -> &mut [A::Item] { 1225 &mut *self 1226 } 1227 } 1228 1229 impl<A: Array> AsRef<[A::Item]> for ArrayVec<A> { 1230 #[inline(always)] 1231 #[must_use] as_ref(&self) -> &[A::Item]1232 fn as_ref(&self) -> &[A::Item] { 1233 &*self 1234 } 1235 } 1236 1237 impl<A: Array> Borrow<[A::Item]> for ArrayVec<A> { 1238 #[inline(always)] 1239 #[must_use] borrow(&self) -> &[A::Item]1240 fn borrow(&self) -> &[A::Item] { 1241 &*self 1242 } 1243 } 1244 1245 impl<A: Array> BorrowMut<[A::Item]> for ArrayVec<A> { 1246 #[inline(always)] 1247 #[must_use] borrow_mut(&mut self) -> &mut [A::Item]1248 fn borrow_mut(&mut self) -> &mut [A::Item] { 1249 &mut *self 1250 } 1251 } 1252 1253 impl<A: Array> Extend<A::Item> for ArrayVec<A> { 1254 #[inline] extend<T: IntoIterator<Item = A::Item>>(&mut self, iter: T)1255 fn extend<T: IntoIterator<Item = A::Item>>(&mut self, iter: T) { 1256 for t in iter { 1257 self.push(t) 1258 } 1259 } 1260 } 1261 1262 impl<A: Array> From<A> for ArrayVec<A> { 1263 #[inline(always)] 1264 #[must_use] 1265 /// The output has a length equal to the full array. 1266 /// 1267 /// If you want to select a length, use 1268 /// [`from_array_len`](ArrayVec::from_array_len) from(data: A) -> Self1269 fn from(data: A) -> Self { 1270 let len: u16 = data 1271 .as_slice() 1272 .len() 1273 .try_into() 1274 .expect("ArrayVec::from> lenght must be in range 0..=u16::MAX"); 1275 Self { len, data } 1276 } 1277 } 1278 1279 /// The error type returned when a conversion from a slice to an [`ArrayVec`] 1280 /// fails. 1281 #[derive(Debug, Copy, Clone)] 1282 pub struct TryFromSliceError(()); 1283 1284 impl<T, A> TryFrom<&'_ [T]> for ArrayVec<A> 1285 where 1286 T: Clone + Default, 1287 A: Array<Item = T>, 1288 { 1289 type Error = TryFromSliceError; 1290 1291 #[inline] 1292 #[must_use] 1293 /// The output has a length equal to that of the slice, with the same capacity 1294 /// as `A`. try_from(slice: &[T]) -> Result<Self, Self::Error>1295 fn try_from(slice: &[T]) -> Result<Self, Self::Error> { 1296 if slice.len() > A::CAPACITY { 1297 Err(TryFromSliceError(())) 1298 } else { 1299 let mut arr = ArrayVec::new(); 1300 // We do not use ArrayVec::extend_from_slice, because it looks like LLVM 1301 // fails to deduplicate all the length-checking logic between the 1302 // above if and the contents of that method, thus producing much 1303 // slower code. Unlike many of the other optimizations in this 1304 // crate, this one is worth keeping an eye on. I see no reason, for 1305 // any element type, that these should produce different code. But 1306 // they do. (rustc 1.51.0) 1307 arr.set_len(slice.len()); 1308 arr.as_mut_slice().clone_from_slice(slice); 1309 Ok(arr) 1310 } 1311 } 1312 } 1313 1314 impl<A: Array> FromIterator<A::Item> for ArrayVec<A> { 1315 #[inline] 1316 #[must_use] from_iter<T: IntoIterator<Item = A::Item>>(iter: T) -> Self1317 fn from_iter<T: IntoIterator<Item = A::Item>>(iter: T) -> Self { 1318 let mut av = Self::default(); 1319 for i in iter { 1320 av.push(i) 1321 } 1322 av 1323 } 1324 } 1325 1326 /// Iterator for consuming an `ArrayVec` and returning owned elements. 1327 pub struct ArrayVecIterator<A: Array> { 1328 base: u16, 1329 tail: u16, 1330 data: A, 1331 } 1332 1333 impl<A: Array> ArrayVecIterator<A> { 1334 /// Returns the remaining items of this iterator as a slice. 1335 #[inline] 1336 #[must_use] as_slice(&self) -> &[A::Item]1337 pub fn as_slice(&self) -> &[A::Item] { 1338 &self.data.as_slice()[self.base as usize..self.tail as usize] 1339 } 1340 } 1341 impl<A: Array> FusedIterator for ArrayVecIterator<A> {} 1342 impl<A: Array> Iterator for ArrayVecIterator<A> { 1343 type Item = A::Item; 1344 #[inline] next(&mut self) -> Option<Self::Item>1345 fn next(&mut self) -> Option<Self::Item> { 1346 let slice = 1347 &mut self.data.as_slice_mut()[self.base as usize..self.tail as usize]; 1348 let itemref = slice.first_mut()?; 1349 self.base += 1; 1350 return Some(take(itemref)); 1351 } 1352 #[inline(always)] 1353 #[must_use] size_hint(&self) -> (usize, Option<usize>)1354 fn size_hint(&self) -> (usize, Option<usize>) { 1355 let s = self.tail - self.base; 1356 let s = s as usize; 1357 (s, Some(s)) 1358 } 1359 #[inline(always)] count(self) -> usize1360 fn count(self) -> usize { 1361 self.size_hint().0 1362 } 1363 #[inline] last(mut self) -> Option<Self::Item>1364 fn last(mut self) -> Option<Self::Item> { 1365 self.next_back() 1366 } 1367 #[inline] nth(&mut self, n: usize) -> Option<A::Item>1368 fn nth(&mut self, n: usize) -> Option<A::Item> { 1369 let slice = &mut self.data.as_slice_mut(); 1370 let slice = &mut slice[self.base as usize..self.tail as usize]; 1371 1372 if let Some(x) = slice.get_mut(n) { 1373 /* n is in range [0 .. self.tail - self.base) so in u16 range */ 1374 self.base += n as u16 + 1; 1375 return Some(take(x)); 1376 } 1377 1378 self.base = self.tail; 1379 return None; 1380 } 1381 } 1382 1383 impl<A: Array> DoubleEndedIterator for ArrayVecIterator<A> { 1384 #[inline] next_back(&mut self) -> Option<Self::Item>1385 fn next_back(&mut self) -> Option<Self::Item> { 1386 let slice = 1387 &mut self.data.as_slice_mut()[self.base as usize..self.tail as usize]; 1388 let item = slice.last_mut()?; 1389 self.tail -= 1; 1390 return Some(take(item)); 1391 } 1392 #[cfg(feature = "rustc_1_40")] 1393 #[inline] nth_back(&mut self, n: usize) -> Option<Self::Item>1394 fn nth_back(&mut self, n: usize) -> Option<Self::Item> { 1395 let base = self.base as usize; 1396 let tail = self.tail as usize; 1397 let slice = &mut self.data.as_slice_mut()[base..tail]; 1398 let n = n.saturating_add(1); 1399 1400 if let Some(n) = slice.len().checked_sub(n) { 1401 let item = &mut slice[n]; 1402 /* n is in [0..self.tail - self.base] range, so in u16 range */ 1403 self.tail = self.base + n as u16; 1404 return Some(take(item)); 1405 } 1406 1407 self.tail = self.base; 1408 return None; 1409 } 1410 } 1411 1412 impl<A: Array> Debug for ArrayVecIterator<A> 1413 where 1414 A::Item: Debug, 1415 { 1416 #[allow(clippy::missing_inline_in_public_items)] fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result1417 fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result { 1418 f.debug_tuple("ArrayVecIterator").field(&self.as_slice()).finish() 1419 } 1420 } 1421 1422 impl<A: Array> IntoIterator for ArrayVec<A> { 1423 type Item = A::Item; 1424 type IntoIter = ArrayVecIterator<A>; 1425 #[inline(always)] 1426 #[must_use] into_iter(self) -> Self::IntoIter1427 fn into_iter(self) -> Self::IntoIter { 1428 ArrayVecIterator { base: 0, tail: self.len, data: self.data } 1429 } 1430 } 1431 1432 impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> { 1433 type Item = &'a mut A::Item; 1434 type IntoIter = core::slice::IterMut<'a, A::Item>; 1435 #[inline(always)] 1436 #[must_use] into_iter(self) -> Self::IntoIter1437 fn into_iter(self) -> Self::IntoIter { 1438 self.iter_mut() 1439 } 1440 } 1441 1442 impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> { 1443 type Item = &'a A::Item; 1444 type IntoIter = core::slice::Iter<'a, A::Item>; 1445 #[inline(always)] 1446 #[must_use] into_iter(self) -> Self::IntoIter1447 fn into_iter(self) -> Self::IntoIter { 1448 self.iter() 1449 } 1450 } 1451 1452 impl<A: Array> PartialEq for ArrayVec<A> 1453 where 1454 A::Item: PartialEq, 1455 { 1456 #[inline] 1457 #[must_use] eq(&self, other: &Self) -> bool1458 fn eq(&self, other: &Self) -> bool { 1459 self.as_slice().eq(other.as_slice()) 1460 } 1461 } 1462 impl<A: Array> Eq for ArrayVec<A> where A::Item: Eq {} 1463 1464 impl<A: Array> PartialOrd for ArrayVec<A> 1465 where 1466 A::Item: PartialOrd, 1467 { 1468 #[inline] 1469 #[must_use] partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering>1470 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> { 1471 self.as_slice().partial_cmp(other.as_slice()) 1472 } 1473 } 1474 impl<A: Array> Ord for ArrayVec<A> 1475 where 1476 A::Item: Ord, 1477 { 1478 #[inline] 1479 #[must_use] cmp(&self, other: &Self) -> core::cmp::Ordering1480 fn cmp(&self, other: &Self) -> core::cmp::Ordering { 1481 self.as_slice().cmp(other.as_slice()) 1482 } 1483 } 1484 1485 impl<A: Array> PartialEq<&A> for ArrayVec<A> 1486 where 1487 A::Item: PartialEq, 1488 { 1489 #[inline] 1490 #[must_use] eq(&self, other: &&A) -> bool1491 fn eq(&self, other: &&A) -> bool { 1492 self.as_slice().eq(other.as_slice()) 1493 } 1494 } 1495 1496 impl<A: Array> PartialEq<&[A::Item]> for ArrayVec<A> 1497 where 1498 A::Item: PartialEq, 1499 { 1500 #[inline] 1501 #[must_use] eq(&self, other: &&[A::Item]) -> bool1502 fn eq(&self, other: &&[A::Item]) -> bool { 1503 self.as_slice().eq(*other) 1504 } 1505 } 1506 1507 impl<A: Array> Hash for ArrayVec<A> 1508 where 1509 A::Item: Hash, 1510 { 1511 #[inline] hash<H: Hasher>(&self, state: &mut H)1512 fn hash<H: Hasher>(&self, state: &mut H) { 1513 self.as_slice().hash(state) 1514 } 1515 } 1516 1517 #[cfg(feature = "experimental_write_impl")] 1518 impl<A: Array<Item = u8>> core::fmt::Write for ArrayVec<A> { write_str(&mut self, s: &str) -> core::fmt::Result1519 fn write_str(&mut self, s: &str) -> core::fmt::Result { 1520 let my_len = self.len(); 1521 let str_len = s.as_bytes().len(); 1522 if my_len + str_len <= A::CAPACITY { 1523 let remainder = &mut self.data.as_slice_mut()[my_len..]; 1524 let target = &mut remainder[..str_len]; 1525 target.copy_from_slice(s.as_bytes()); 1526 Ok(()) 1527 } else { 1528 Err(core::fmt::Error) 1529 } 1530 } 1531 } 1532 1533 // // // // // // // // 1534 // Formatting impls 1535 // // // // // // // // 1536 1537 impl<A: Array> Binary for ArrayVec<A> 1538 where 1539 A::Item: Binary, 1540 { 1541 #[allow(clippy::missing_inline_in_public_items)] fmt(&self, f: &mut Formatter) -> core::fmt::Result1542 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result { 1543 write!(f, "[")?; 1544 if f.alternate() { 1545 write!(f, "\n ")?; 1546 } 1547 for (i, elem) in self.iter().enumerate() { 1548 if i > 0 { 1549 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?; 1550 } 1551 Binary::fmt(elem, f)?; 1552 } 1553 if f.alternate() { 1554 write!(f, ",\n")?; 1555 } 1556 write!(f, "]") 1557 } 1558 } 1559 1560 impl<A: Array> Debug for ArrayVec<A> 1561 where 1562 A::Item: Debug, 1563 { 1564 #[allow(clippy::missing_inline_in_public_items)] fmt(&self, f: &mut Formatter) -> core::fmt::Result1565 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result { 1566 write!(f, "[")?; 1567 if f.alternate() { 1568 write!(f, "\n ")?; 1569 } 1570 for (i, elem) in self.iter().enumerate() { 1571 if i > 0 { 1572 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?; 1573 } 1574 Debug::fmt(elem, f)?; 1575 } 1576 if f.alternate() { 1577 write!(f, ",\n")?; 1578 } 1579 write!(f, "]") 1580 } 1581 } 1582 1583 impl<A: Array> Display for ArrayVec<A> 1584 where 1585 A::Item: Display, 1586 { 1587 #[allow(clippy::missing_inline_in_public_items)] fmt(&self, f: &mut Formatter) -> core::fmt::Result1588 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result { 1589 write!(f, "[")?; 1590 if f.alternate() { 1591 write!(f, "\n ")?; 1592 } 1593 for (i, elem) in self.iter().enumerate() { 1594 if i > 0 { 1595 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?; 1596 } 1597 Display::fmt(elem, f)?; 1598 } 1599 if f.alternate() { 1600 write!(f, ",\n")?; 1601 } 1602 write!(f, "]") 1603 } 1604 } 1605 1606 impl<A: Array> LowerExp for ArrayVec<A> 1607 where 1608 A::Item: LowerExp, 1609 { 1610 #[allow(clippy::missing_inline_in_public_items)] fmt(&self, f: &mut Formatter) -> core::fmt::Result1611 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result { 1612 write!(f, "[")?; 1613 if f.alternate() { 1614 write!(f, "\n ")?; 1615 } 1616 for (i, elem) in self.iter().enumerate() { 1617 if i > 0 { 1618 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?; 1619 } 1620 LowerExp::fmt(elem, f)?; 1621 } 1622 if f.alternate() { 1623 write!(f, ",\n")?; 1624 } 1625 write!(f, "]") 1626 } 1627 } 1628 1629 impl<A: Array> LowerHex for ArrayVec<A> 1630 where 1631 A::Item: LowerHex, 1632 { 1633 #[allow(clippy::missing_inline_in_public_items)] fmt(&self, f: &mut Formatter) -> core::fmt::Result1634 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result { 1635 write!(f, "[")?; 1636 if f.alternate() { 1637 write!(f, "\n ")?; 1638 } 1639 for (i, elem) in self.iter().enumerate() { 1640 if i > 0 { 1641 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?; 1642 } 1643 LowerHex::fmt(elem, f)?; 1644 } 1645 if f.alternate() { 1646 write!(f, ",\n")?; 1647 } 1648 write!(f, "]") 1649 } 1650 } 1651 1652 impl<A: Array> Octal for ArrayVec<A> 1653 where 1654 A::Item: Octal, 1655 { 1656 #[allow(clippy::missing_inline_in_public_items)] fmt(&self, f: &mut Formatter) -> core::fmt::Result1657 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result { 1658 write!(f, "[")?; 1659 if f.alternate() { 1660 write!(f, "\n ")?; 1661 } 1662 for (i, elem) in self.iter().enumerate() { 1663 if i > 0 { 1664 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?; 1665 } 1666 Octal::fmt(elem, f)?; 1667 } 1668 if f.alternate() { 1669 write!(f, ",\n")?; 1670 } 1671 write!(f, "]") 1672 } 1673 } 1674 1675 impl<A: Array> Pointer for ArrayVec<A> 1676 where 1677 A::Item: Pointer, 1678 { 1679 #[allow(clippy::missing_inline_in_public_items)] fmt(&self, f: &mut Formatter) -> core::fmt::Result1680 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result { 1681 write!(f, "[")?; 1682 if f.alternate() { 1683 write!(f, "\n ")?; 1684 } 1685 for (i, elem) in self.iter().enumerate() { 1686 if i > 0 { 1687 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?; 1688 } 1689 Pointer::fmt(elem, f)?; 1690 } 1691 if f.alternate() { 1692 write!(f, ",\n")?; 1693 } 1694 write!(f, "]") 1695 } 1696 } 1697 1698 impl<A: Array> UpperExp for ArrayVec<A> 1699 where 1700 A::Item: UpperExp, 1701 { 1702 #[allow(clippy::missing_inline_in_public_items)] fmt(&self, f: &mut Formatter) -> core::fmt::Result1703 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result { 1704 write!(f, "[")?; 1705 if f.alternate() { 1706 write!(f, "\n ")?; 1707 } 1708 for (i, elem) in self.iter().enumerate() { 1709 if i > 0 { 1710 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?; 1711 } 1712 UpperExp::fmt(elem, f)?; 1713 } 1714 if f.alternate() { 1715 write!(f, ",\n")?; 1716 } 1717 write!(f, "]") 1718 } 1719 } 1720 1721 impl<A: Array> UpperHex for ArrayVec<A> 1722 where 1723 A::Item: UpperHex, 1724 { 1725 #[allow(clippy::missing_inline_in_public_items)] fmt(&self, f: &mut Formatter) -> core::fmt::Result1726 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result { 1727 write!(f, "[")?; 1728 if f.alternate() { 1729 write!(f, "\n ")?; 1730 } 1731 for (i, elem) in self.iter().enumerate() { 1732 if i > 0 { 1733 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?; 1734 } 1735 UpperHex::fmt(elem, f)?; 1736 } 1737 if f.alternate() { 1738 write!(f, ",\n")?; 1739 } 1740 write!(f, "]") 1741 } 1742 } 1743 1744 #[cfg(feature = "alloc")] 1745 use alloc::vec::Vec; 1746 1747 #[cfg(feature = "alloc")] 1748 impl<A: Array> ArrayVec<A> { 1749 /// Drains all elements to a Vec, but reserves additional space 1750 /// ``` 1751 /// # use tinyvec::*; 1752 /// let mut av = array_vec!([i32; 7] => 1, 2, 3); 1753 /// let v = av.drain_to_vec_and_reserve(10); 1754 /// assert_eq!(v, &[1, 2, 3]); 1755 /// assert_eq!(v.capacity(), 13); 1756 /// ``` drain_to_vec_and_reserve(&mut self, n: usize) -> Vec<A::Item>1757 pub fn drain_to_vec_and_reserve(&mut self, n: usize) -> Vec<A::Item> { 1758 let cap = n + self.len(); 1759 let mut v = Vec::with_capacity(cap); 1760 let iter = self.iter_mut().map(take); 1761 v.extend(iter); 1762 self.set_len(0); 1763 return v; 1764 } 1765 1766 /// Drains all elements to a Vec 1767 /// ``` 1768 /// # use tinyvec::*; 1769 /// let mut av = array_vec!([i32; 7] => 1, 2, 3); 1770 /// let v = av.drain_to_vec(); 1771 /// assert_eq!(v, &[1, 2, 3]); 1772 /// assert_eq!(v.capacity(), 3); 1773 /// ``` drain_to_vec(&mut self) -> Vec<A::Item>1774 pub fn drain_to_vec(&mut self) -> Vec<A::Item> { 1775 self.drain_to_vec_and_reserve(0) 1776 } 1777 } 1778 1779 #[cfg(feature = "serde")] 1780 struct ArrayVecVisitor<A: Array>(PhantomData<A>); 1781 1782 #[cfg(feature = "serde")] 1783 impl<'de, A: Array> Visitor<'de> for ArrayVecVisitor<A> 1784 where 1785 A::Item: Deserialize<'de>, 1786 { 1787 type Value = ArrayVec<A>; 1788 expecting( &self, formatter: &mut core::fmt::Formatter, ) -> core::fmt::Result1789 fn expecting( 1790 &self, formatter: &mut core::fmt::Formatter, 1791 ) -> core::fmt::Result { 1792 formatter.write_str("a sequence") 1793 } 1794 visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error> where S: SeqAccess<'de>,1795 fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error> 1796 where 1797 S: SeqAccess<'de>, 1798 { 1799 let mut new_arrayvec: ArrayVec<A> = Default::default(); 1800 1801 let mut idx = 0usize; 1802 while let Some(value) = seq.next_element()? { 1803 if new_arrayvec.len() >= new_arrayvec.capacity() { 1804 return Err(DeserializeError::invalid_length(idx, &self)); 1805 } 1806 new_arrayvec.push(value); 1807 idx = idx + 1; 1808 } 1809 1810 Ok(new_arrayvec) 1811 } 1812 } 1813