[Pre-ACP] Add methods to `VecDeque` to get spare capacity

libs
1

The Vec type has methods for accessing spare capacity, so you can directly write to the uninitialized memory and then update the length. But VecDeque has no such access, and I recently came across some code where it would have been useful (specifically, inputting bytes from a read syscall into a queue to pull from later, which I wanted to back with a VecDeque<u8>).

Specifically, I propose the following methods be added to VecDeque<T, A: Allocator> (inspired by the similar methods which already exist for Vec):

/// Returns the remaining spare capacity.
///
/// The exact split point depends on implementation details and is not guaranteed.
///
/// If appending extra elements, you should start by writing to the first slice,
/// then the second if you run out of room, before marking the data as initialized
/// using the [`set_len`](Self::set_len) method.
pub fn spare_capacities_mut(&mut self) -> (&mut [MaybeUninit<T>], &mut [MaybeUninit<T>]);

/// Returns four slices containing the contents and spare capacity, in order.
///
/// If make_contiguous was previously called, all elements of the deque will be in
/// the first slice and the second slice will be empty. Otherwise, the exact split
/// point on implementation details and is not guaranteed. The split point for the
/// uninitialized memory is also an implementation detail.
///
/// If appending extra elements, you should start by writing to the first
/// uninitialized slice, then the second if you run out of room, before marking the
/// data as initialized using the [`set_len`](Self::set_len) method.
pub fn as_slices_with_spare_capacities_mut(&mut self) -> (&mut [T], &mut [T], &mut [MaybeUninit<T>], &mut [MaybeUninit<T>]);

/// Forces the length of the deque to new_len.
///
/// This is a low-level operation that maintains none of the normal invariants of the
/// type. Normally changing the length of a deque is done using one of the safe
/// operations instead, such as [`append()`](Self::append),
/// [`truncate()`](Self::truncate), or [`clear()`](Self::clear).
///
/// # Safety
/// * `new_len` must be less than or equal to [`capacity()`](Self::capacity).
/// * The elements at `old_len..new_len` must be initialized (see
///   [`spare_capacities_mut()`](Self::spare_capacities_mut) for a way to
///   initialize these elements.
pub unsafe fn set_len(&mut self, new_len: usize);

Any of y'all have thoughts about these methods?

EDIT: Removed guarantee about contiguous uninitialized memory that isn't actually provided without changes that worsen VecDeque.

2

I'm not too happy with the added requirements on make_contiguous:

If make_contiguous was previously called, all open capacity will be in the first slice and the second slice will be empty.

Currently make_contiguous is not required to do anything if the filled part if contiguous. Following your proposal it will need to also move the data if the uninitialized part is not contiguous. Which amounts to having to move data around whenever the first filled element isn't stored in the first slot in memory.

VecDeque is generally designed to allow adding and removing data both at the front and back. But set_length only allows adding data at the back, not at the front.

2 Likes
3

Good suggestion about the contiguousness! I assumed make_contiguous would move all data to 0..len, but that makes sense that it wouldn't do that.

As for adding at the front, that seems harder to make a good API for. I couldn't think of anything that hit me as being the "right" way like these three methods did, so I didn't include it. But I'm open to suggestions if you have any.

4

I think relative movement of the ends fits a queue better than setting the length. You generally know how many elements you added, and care little how many elements are already in the queue when you do.

// positive values extend, negative values shrink
unsafe fn move_front(&mut self, n: isize);
unsafe fn move_back(&mut self, n: isize);

or an extend-only version:

unsafe fn move_front(&mut self, n: usize);
unsafe fn move_back(&mut self, n: usize);

I think I prefer the extend-only version. It feels cleaner and keeps it single purpose. Discarding elements without running drop could be added as separate safe methods, but I'm not sure if there is any demand for that.

1 Like
5

VecDeque recently got truncate_front, so you might be inspired by that -- if set_len gets added then maybe set_len_front should be too? (Or better, more symmetric names could be found?)

Right, the "move everything to the front" is Vec<T>: From<VecDeque<T>> :slight_smile:

6

I'd assume that negative values extend the front and positive values shrink. So something less ambiguous is probably needed.

1 Like