packed/
packed_vec.rs

1// Copyright 2026 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5//! A memory-efficient vector that stores dynamically sized items in a single contiguous buffer.
6
7use crate::PackedItem;
8use std::borrow::Cow;
9use std::iter::{Extend, FromIterator};
10use std::ops::Index;
11
12/// A packed vector that stores slices of an element type in a single contiguous buffer.
13///
14/// This behaves somewhat like a `Vec<Box<[T]>>` or `Vec<Vec<T>>`, but allows
15/// for better memory locality and fewer allocations by storing all elements
16/// in one `Vec<T::Item>`.
17pub struct PackedVec<T: ?Sized + PackedItem> {
18    data: Vec<u8>,
19    // offsets stores the end index of each slice.
20    // The slice at index i is data[offsets[i-1]..offsets[i]] (with offsets[-1] implicitly 0).
21    // We always maintain offsets.len() == self.len().
22    offsets: Vec<usize>,
23    // We use `PhantomData<fn() -> T>` instead of `PhantomData<T>` to bypass
24    // strict dropcheck (dropck) rules. `PackedVec` owns raw bytes, not actual
25    // instances of `T`, so dropping `PackedVec` does not drop any `T`s.
26    // If we used `PhantomData<T>`, the compiler would incorrectly assume we
27    // are dropping `T`s, which can cause spurious lifetime errors (e.g., preventing
28    // the collection from being dropped if a lifetime in `T` has expired).
29    // `fn() -> T` preserves covariance over `T` and auto-traits like Send/Sync
30    // while confirming to the compiler that we do not own a `T` that needs dropping.
31    _phantom: std::marker::PhantomData<fn() -> T>,
32}
33
34impl<T: ?Sized + PackedItem> PackedVec<T> {
35    /// Creates a new empty `PackedVec`.
36    pub fn new() -> Self {
37        Self { data: Vec::new(), offsets: Vec::new(), _phantom: std::marker::PhantomData }
38    }
39
40    /// Creates a new `PackedVec` with the specified capacities.
41    ///
42    /// The `element_capacity` argument specifies the number of slices that can be
43    /// stored without reallocating the offsets vector. The `buffer_capacity`
44    /// argument specifies the cumulative length of slices that can be stored
45    /// without reallocating the data vector.
46    pub fn with_capacity(element_capacity: usize, buffer_capacity: usize) -> Self {
47        Self {
48            data: Vec::with_capacity(buffer_capacity),
49            offsets: Vec::with_capacity(element_capacity),
50            _phantom: std::marker::PhantomData,
51        }
52    }
53
54    /// Clears the vector, removing all elements.
55    pub fn clear(&mut self) {
56        self.data.clear();
57        self.offsets.clear();
58    }
59
60    /// Creates a new `PackedVec` from a slice of element slices, pre-allocating
61    /// the required capacity.
62    pub fn from_slice<U: AsRef<T>>(slices: &[U]) -> Self {
63        let element_capacity = slices.len();
64        let buffer_capacity = slices.iter().map(|s| s.as_ref().as_bytes().len()).sum();
65        let mut vec = Self::with_capacity(element_capacity, buffer_capacity);
66        vec.extend(slices);
67        vec
68    }
69
70    /// Reserves capacity for at least `additional` more elements to be inserted.
71    pub fn reserve(&mut self, additional: usize) {
72        self.offsets.reserve(additional);
73    }
74
75    /// Shrinks the capacity of the vector as much as possible.
76    pub fn shrink_to_fit(&mut self) {
77        self.data.shrink_to_fit();
78        self.offsets.shrink_to_fit();
79    }
80
81    /// Appends an item to the back of the collection.
82    pub fn push(&mut self, slice: &T) {
83        self.data.extend_from_slice(slice.as_bytes());
84        self.offsets.push(self.data.len());
85    }
86
87    /// Returns the slice at the given index, or `None` if out of bounds.
88    pub fn get(&self, index: usize) -> Option<&T> {
89        if index >= self.len() {
90            return None;
91        }
92        // SAFETY: We checked `index < self.len()`.
93        Some(unsafe { self.get_unchecked(index) })
94    }
95
96    /// Returns a reference to the slice at the given index without bounds checking.
97    ///
98    /// # Safety
99    ///
100    /// The index must be less than `self.len()`.
101    pub unsafe fn get_unchecked(&self, index: usize) -> &T {
102        let start = if index == 0 {
103            0
104        } else {
105            // SAFETY: Since `index > 0`, `index - 1` is in bounds of `self.offsets`.
106            unsafe { *self.offsets.get_unchecked(index - 1) }
107        };
108
109        // SAFETY: The caller guarantees `index < self.len()`. Since `self.len()` is
110        // exactly `self.offsets.len()`, the index is guaranteed to be in-bounds.
111        let end = unsafe { *self.offsets.get_unchecked(index) };
112
113        // SAFETY: Because T: Unaligned, no padding was ever inserted. The bytes
114        // of the item are stored contiguously between `start` and `end`.
115        let bytes = unsafe { self.data.get_unchecked(start..end) };
116
117        // SAFETY: `PackedItem::from_bytes` requires the input bytes to have
118        // been created by `IntoBytes::as_bytes()`. This property is maintained
119        // by the bytes packed into the vector by `push()` using valid
120        // instances of `T`.
121        unsafe { T::from_bytes(bytes) }
122    }
123
124    /// Returns the number of slices in the vector.
125    pub fn len(&self) -> usize {
126        self.offsets.len()
127    }
128
129    /// Returns the cumulative length of all slices in the vector in bytes.
130    pub fn buffer_len(&self) -> usize {
131        self.data.len()
132    }
133
134    /// Returns `true` if the vector contains no slices.
135    pub fn is_empty(&self) -> bool {
136        self.offsets.is_empty()
137    }
138
139    /// Binary searches this sorted vector for a given element.
140    ///
141    /// If the value is found then [`Result::Ok`] is returned, containing the index
142    /// of the matching element. If there are multiple matches, then any one of the
143    /// matches could be returned.
144    ///
145    /// If the value is not found then [`Result::Err`] is returned, containing the
146    /// index where a matching element could be inserted while maintaining sorted
147    /// order.
148    pub fn binary_search(&self, x: &T) -> Result<usize, usize>
149    where
150        T: Ord,
151    {
152        self.binary_search_by(|p| p.cmp(x))
153    }
154
155    /// Binary searches this sorted vector for a given element.
156    ///
157    /// If the value is found then [`Result::Ok`] is returned, containing the index
158    /// of the matching element. If there are multiple matches, then any one of the
159    /// matches could be returned.
160    ///
161    /// If the value is not found then [`Result::Err`] is returned, containing the
162    /// index where a matching element could be inserted while maintaining sorted
163    /// order.
164    pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
165    where
166        F: FnMut(&'a T) -> std::cmp::Ordering,
167    {
168        // We want to leverage the Vec::binary_search, since it is better
169        // optimized than a simple binary search algorithm. However, we can't
170        // just pass a closure that operates on `&T` because `binary_search`
171        // operates on `offsets` side table, and not our string table. We can
172        // get the behavior we want by:
173        //
174        // 1. Take the `&usize` from the binary search step.
175        // 2. Determine the start and end pointers of `self.data` using the
176        //    start of the vector for the first element, and the `&usize` for
177        //    the rest.
178        // 3. Get the value at the given index.
179        // 4. Apply the predicate to the value.
180        self.offsets.binary_search_by(|end| {
181            // SAFETY: `end` is a reference to an element in `offsets`.
182            // We use pointer arithmetic to find the index of this element.
183            let end_ptr = end as *const usize;
184            let index = unsafe { end_ptr.offset_from_unsigned(self.offsets.as_ptr()) };
185
186            // SAFETY: `offsets.binary_search_by` iterates over `offsets`, so `index` is valid.
187            let slice = unsafe { self.get_unchecked(index) };
188            f(slice)
189        })
190    }
191
192    /// Returns the first element of the vector, or `None` if it is empty.
193    pub fn first(&self) -> Option<&T> {
194        self.get(0)
195    }
196
197    /// Returns the last element of the vector, or `None` if it is empty.
198    pub fn last(&self) -> Option<&T> {
199        let len = self.len();
200        if len == 0 {
201            None
202        } else {
203            // SAFETY: We checked `len > 0`, so `len - 1` is a valid index.
204            Some(unsafe { self.get_unchecked(len - 1) })
205        }
206    }
207
208    /// Returns an iterator over the slices.
209    pub fn iter(&self) -> Iter<'_, T> {
210        Iter { vec: self, range: 0..self.len() }
211    }
212
213    /// Returns a draining iterator that removes all elements and yields them.
214    pub fn drain(&mut self) -> Drain<'_, T> {
215        let len = self.len();
216        Drain { vec: self, cursor: 0, len }
217    }
218
219    /// Returns an iterator over a sub-range of slices in the vector.
220    ///
221    /// The bounds must be `usize` bounds (representing indices).
222    /// If bounds are outside the vector length or inverted, they will be clipped.
223    pub fn range<R: std::ops::RangeBounds<usize>>(&self, range: R) -> Iter<'_, T> {
224        let range = crate::compute_range_indices(self.len(), range, |&idx| Ok(idx));
225        Iter { vec: self, range }
226    }
227}
228
229impl<T: ?Sized + PackedItem> Default for PackedVec<T> {
230    fn default() -> Self {
231        Self::new()
232    }
233}
234
235impl<T: ?Sized + PackedItem> Clone for PackedVec<T> {
236    fn clone(&self) -> Self {
237        Self {
238            data: self.data.clone(),
239            offsets: self.offsets.clone(),
240            _phantom: std::marker::PhantomData,
241        }
242    }
243}
244
245impl<T: ?Sized + PackedItem> PartialEq for PackedVec<T> {
246    fn eq(&self, other: &Self) -> bool {
247        self.data == other.data && self.offsets == other.offsets
248    }
249}
250
251impl<T: ?Sized + PackedItem> Eq for PackedVec<T> {}
252
253impl<T: ?Sized + PackedItem> std::hash::Hash for PackedVec<T> {
254    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
255        self.data.hash(state);
256        self.offsets.hash(state);
257    }
258}
259
260impl<T: ?Sized + PackedItem> std::fmt::Debug for PackedVec<T>
261where
262    T: std::fmt::Debug,
263{
264    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
265        f.debug_list().entries::<&T, _>(self.iter()).finish()
266    }
267}
268
269impl<'a, T: ?Sized + PackedItem> IntoIterator for &'a PackedVec<T> {
270    type Item = &'a T;
271    type IntoIter = Iter<'a, T>;
272
273    fn into_iter(self) -> Self::IntoIter {
274        Iter::<T> { vec: self, range: 0..self.len() }
275    }
276}
277
278/// An iterator over the slices in a [`PackedVec`].
279pub struct Iter<'a, T: ?Sized + PackedItem> {
280    vec: &'a PackedVec<T>,
281    range: std::ops::Range<usize>,
282}
283
284impl<'a, T: ?Sized + PackedItem> Iterator for Iter<'a, T> {
285    type Item = &'a T;
286
287    fn next(&mut self) -> Option<Self::Item> {
288        let i = self.range.next()?;
289        self.vec.get(i)
290    }
291
292    fn size_hint(&self) -> (usize, Option<usize>) {
293        self.range.size_hint()
294    }
295}
296
297impl<'a, T: ?Sized + PackedItem> DoubleEndedIterator for Iter<'a, T> {
298    fn next_back(&mut self) -> Option<Self::Item> {
299        let i = self.range.next_back()?;
300        self.vec.get(i)
301    }
302}
303
304impl<'a, T: ?Sized + PackedItem> ExactSizeIterator for Iter<'a, T> {}
305
306/// A draining lending iterator over the slices in a [`PackedVec`].
307pub struct Drain<'a, T: ?Sized + PackedItem> {
308    vec: &'a mut PackedVec<T>,
309    cursor: usize,
310    len: usize,
311}
312
313impl<'a, T: ?Sized + PackedItem> Drain<'a, T> {
314    /// Returns the next element in the draining iterator.
315    pub fn next(&mut self) -> Option<&T> {
316        if self.cursor >= self.len {
317            return None;
318        }
319        let i = self.cursor;
320        self.cursor += 1;
321        self.vec.get(i)
322    }
323
324    /// Returns the next element from the back in the draining iterator.
325    pub fn next_back(&mut self) -> Option<&T> {
326        if self.cursor >= self.len {
327            return None;
328        }
329        self.len -= 1;
330        self.vec.get(self.len)
331    }
332
333    /// Returns the number of elements remaining in the draining iterator.
334    pub fn len(&self) -> usize {
335        self.len - self.cursor
336    }
337}
338
339impl<'a, T: ?Sized + PackedItem> Drop for Drain<'a, T> {
340    fn drop(&mut self) {
341        self.vec.clear();
342    }
343}
344
345impl<T: ?Sized + PackedItem> Index<usize> for PackedVec<T> {
346    type Output = T;
347
348    fn index(&self, index: usize) -> &Self::Output {
349        self.get(index).expect("index out of bounds")
350    }
351}
352
353impl<U: AsRef<T>, T: ?Sized + PackedItem> Extend<U> for PackedVec<T> {
354    fn extend<I: IntoIterator<Item = U>>(&mut self, iter: I) {
355        let iter = iter.into_iter();
356        let (lower, _) = iter.size_hint();
357        self.offsets.reserve(lower);
358        for item in iter {
359            self.push(item.as_ref());
360        }
361    }
362}
363
364impl<U: AsRef<T>, T: ?Sized + PackedItem> FromIterator<U> for PackedVec<T> {
365    fn from_iter<I: IntoIterator<Item = U>>(iter: I) -> Self {
366        let iter = iter.into_iter();
367        let (lower, _) = iter.size_hint();
368        let mut vec = Self::with_capacity(lower, 0);
369        vec.extend(iter);
370        vec
371    }
372}
373
374impl<U, T: ?Sized + PackedItem, const N: usize> From<[U; N]> for PackedVec<T>
375where
376    U: AsRef<T>,
377{
378    fn from(arr: [U; N]) -> Self {
379        Self::from_iter(arr)
380    }
381}
382
383impl<T: ?Sized + PackedItem> serde::Serialize for PackedVec<T>
384where
385    T: serde::Serialize,
386{
387    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
388        use serde::ser::SerializeSeq;
389        let mut seq = serializer.serialize_seq(Some(self.len()))?;
390        for item in self.iter() {
391            seq.serialize_element(item)?;
392        }
393        seq.end()
394    }
395}
396
397impl<'de, T: ?Sized + PackedItem + 'de> serde::Deserialize<'de> for PackedVec<T>
398where
399    T: ToOwned,
400    Cow<'de, T>: serde::Deserialize<'de>,
401{
402    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
403        struct SeqVisitor<T: ?Sized + PackedItem>(std::marker::PhantomData<fn() -> T>);
404
405        impl<'de, T: ?Sized + PackedItem + 'de> serde::de::Visitor<'de> for SeqVisitor<T>
406        where
407            T: ToOwned,
408            Cow<'de, T>: serde::Deserialize<'de>,
409        {
410            type Value = PackedVec<T>;
411
412            fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
413                formatter.write_str("a sequence of items")
414            }
415
416            fn visit_seq<A: serde::de::SeqAccess<'de>>(
417                self,
418                mut seq: A,
419            ) -> Result<Self::Value, A::Error> {
420                let mut vec = PackedVec::with_capacity(seq.size_hint().unwrap_or(0), 0);
421                while let Some(elem) = seq.next_element::<Cow<'de, T>>()? {
422                    vec.push(elem.as_ref());
423                }
424                Ok(vec)
425            }
426        }
427
428        deserializer.deserialize_seq(SeqVisitor(std::marker::PhantomData))
429    }
430}
431
432#[cfg(test)]
433mod tests {
434    use super::*;
435
436    #[test]
437    fn test_with_capacity() {
438        let pv: PackedVec<[u8]> = PackedVec::with_capacity(10, 20);
439        assert!(pv.offsets.capacity() >= 10);
440        assert!(pv.data.capacity() >= 20);
441        assert_eq!(pv.len(), 0);
442    }
443
444    #[test]
445    fn test_from_slice() {
446        let slices: &[&[u8]] = &[&[1, 2], &[3], &[4, 5, 6]];
447        let pv = PackedVec::from_slice(slices);
448        assert_eq!(pv.len(), 3);
449        assert_eq!(pv.get(0), Some(&[1, 2][..]));
450        assert_eq!(pv.get(1), Some(&[3][..]));
451        assert_eq!(pv.get(2), Some(&[4, 5, 6][..]));
452        assert!(pv.offsets.capacity() >= 3);
453        assert!(pv.data.capacity() >= 6);
454    }
455
456    #[test]
457    fn test_packed_vec() {
458        let mut pv: PackedVec<[u8]> = PackedVec::new();
459        pv.push(&[1u8, 2][..]);
460        pv.push(&[][..]);
461        pv.push(&[3, 4, 5][..]);
462
463        assert_eq!(pv.len(), 3);
464        assert!(!pv.is_empty());
465
466        assert_eq!(pv.get(0), Some(&[1u8, 2][..]));
467        assert_eq!(pv.get(1), Some(&[] as &[u8]));
468        assert_eq!(pv.get(2), Some(&[3u8, 4, 5][..]));
469        assert_eq!(pv.get(3), None);
470
471        assert_eq!(pv.get(0).unwrap(), &[1u8, 2][..]);
472        assert_eq!(pv.get(1).unwrap(), &[] as &[u8]);
473
474        let collected: Vec<_> = pv.iter().collect();
475        assert_eq!(collected, vec![&[1u8, 2][..], &[] as &[u8], &[3u8, 4, 5][..]]);
476    }
477
478    #[test]
479    fn test_first_last() {
480        let mut pv: PackedVec<[u8]> = PackedVec::new();
481        assert_eq!(pv.first(), None);
482        assert_eq!(pv.last(), None);
483
484        pv.push(&[1][..]);
485        assert_eq!(pv.first(), Some(&[1][..]));
486        assert_eq!(pv.last(), Some(&[1][..]));
487
488        pv.push(&[2, 3][..]);
489        assert_eq!(pv.first(), Some(&[1][..]));
490        assert_eq!(pv.last(), Some(&[2, 3][..]));
491    }
492
493    #[test]
494    fn test_extend_from_iterator() {
495        let pv: PackedVec<[u8]> = vec![vec![1], vec![2, 3]].iter().map(|v| v.as_slice()).collect();
496        assert_eq!(pv.len(), 2);
497        let slice: &[u8] = pv.get(1).unwrap();
498        assert_eq!(slice, &[2, 3][..]);
499    }
500
501    #[test]
502    fn test_drain() {
503        let mut pv: PackedVec<[u8]> = PackedVec::new();
504        pv.push(&[1][..]);
505        pv.push(&[2, 3][..]);
506        pv.push(&[4, 5, 6][..]);
507
508        let mut drain = pv.drain();
509        assert_eq!(drain.len(), 3);
510
511        // Test next()
512        assert_eq!(drain.next(), Some(&[1][..]));
513        assert_eq!(drain.len(), 2);
514
515        // Test next_back()
516        assert_eq!(drain.next_back(), Some(&[4, 5, 6][..]));
517        assert_eq!(drain.len(), 1);
518
519        // Test next() again
520        assert_eq!(drain.next(), Some(&[2, 3][..]));
521        assert_eq!(drain.len(), 0);
522
523        // Test None
524        assert_eq!(drain.next(), None);
525        assert_eq!(drain.next_back(), None);
526    }
527
528    #[test]
529    fn test_drain_drop_clears() {
530        let mut pv: PackedVec<[u8]> = PackedVec::new();
531        pv.push(&[1][..]);
532        pv.push(&[2, 3][..]);
533
534        {
535            let mut drain = pv.drain();
536            assert_eq!(drain.next(), Some(&[1][..]));
537            // Drop happens here
538        }
539
540        assert!(pv.is_empty());
541        assert_eq!(pv.len(), 0);
542
543        // Make sure both vectors were cleared, not just one.
544        assert!(pv.offsets.is_empty());
545        assert!(pv.data.is_empty());
546    }
547
548    #[test]
549    fn test_binary_search_empty() {
550        let pv: PackedVec<[u8]> = PackedVec::new();
551        assert_eq!(pv.binary_search_by(|x| x.cmp(&[1u8][..])), Err(0));
552    }
553
554    #[test]
555    fn test_binary_search() {
556        let mut pv: PackedVec<[u8]> = PackedVec::new();
557        pv.push(&[1]);
558        pv.push(&[3]);
559        pv.push(&[5]);
560
561        assert_eq!(pv.binary_search_by(|x| x.cmp(&[1u8][..])), Ok(0));
562        assert_eq!(pv.binary_search_by(|x| x.cmp(&[3u8][..])), Ok(1));
563        assert_eq!(pv.binary_search_by(|x| x.cmp(&[5u8][..])), Ok(2));
564        assert_eq!(pv.binary_search_by(|x| x.cmp(&[2u8][..])), Err(1));
565        assert_eq!(pv.binary_search_by(|x| x.cmp(&[0u8][..])), Err(0));
566        assert_eq!(pv.binary_search_by(|x| x.cmp(&[6u8][..])), Err(3));
567    }
568
569    #[test]
570    fn test_packed_str_vec() {
571        let mut pv: PackedVec<str> = PackedVec::new();
572        pv.push("hello");
573        pv.push("");
574        pv.push("world!!");
575
576        assert_eq!(pv.len(), 3);
577        assert!(!pv.is_empty());
578
579        assert_eq!(pv.get(0), Some("hello"));
580        assert_eq!(pv.get(1), Some(""));
581        assert_eq!(pv.get(2), Some("world!!"));
582        assert_eq!(pv.get(3), None);
583
584        assert_eq!(pv.get(0).unwrap(), "hello");
585        assert_eq!(pv.get(1).unwrap(), "");
586
587        let collected: Vec<_> = pv.iter().collect();
588        assert_eq!(collected, vec!["hello", "", "world!!"]);
589    }
590
591    #[test]
592    fn test_serde() {
593        let mut pv: PackedVec<str> = PackedVec::new();
594        pv.push("hello");
595        pv.push("world");
596        let serialized = serde_json::to_string(&pv).unwrap();
597        let deserialized: PackedVec<str> = serde_json::from_str(&serialized).unwrap();
598        assert_eq!(pv, deserialized);
599    }
600}
packed/packed_vec.rs

packed/
packed_vec.rs
