`reserve()`

The goal of `reserve(n)`

is simple: allocate enough memory to perform `n`

pushes
without allocating more memory.

This is a useful function, because, as we've seen, `allocate_bucket`

requires
some heavy atomics with `compare_exchange`

. If we can do our allocations in a
calmer scenario with less contention, we'll experience some performance gains.

We start by calculating the number of allocations we'll need to perform to
reserve enough space. The calculation is a little funky, and there's an edge
case where it can't distinguish between 0 and sizes between 1 and
`FIRST_BUCKET_SIZE`

. That's why we need to explicitly allocate the first bucket.
We'll see the implementation of `size()`

later, but it does use some atomic
synchronization, so we just cache the result so we can keep using it later
without calling `size`

again.

`#![allow(unused)] fn main() { pub fn reserve(&self, size: usize) { // Cache the size to prevent another atomic op from due to calling `size()` again let current_size = self.size(); if current_size == 0 { self.allocate_bucket(0); } }`

Now, we calculate the number of allocations we've made.

`highest_bit`

returns the highest set bit in a number. A bit is set
if it's equal to one. The highest set bit of 7 (`0b111`

), for example, is 2
(0-indexed). Since the buckets are increasing by a factor of two each time, the
highest set bit of the indices in each bucket is one greater than the highest
set bit of the indices in the previous bucket. Therefore, by using the highest
bit of a number in conjunction with `FIRST_BUCKET_SIZE`

, we can figure out how
many allocations are needed for a certain capacity. I know I'm waving my hands a
little; I haven't taken the time to rigorously understand the arithmetic, as
it's not that interesting to me, and in practice it works.

`#![allow(unused)] fn main() { let mut num_current_allocs = highest_bit(current_size.saturating_add(FIRST_BUCKET_SIZE) - 1) .saturating_sub(highest_bit(FIRST_BUCKET_SIZE)); }`

Then we calculate the number of allocations we need to reserve the space, and for each allocation missing, we allocate.

`#![allow(unused)] fn main() { // Compare with the number of allocations needed for size `new` while num_current_allocs < highest_bit(size.saturating_add(FIRST_BUCKET_SIZE) - 1) .saturating_sub(highest_bit(FIRST_BUCKET_SIZE)) { num_current_allocs += 1; self.allocate_bucket(num_current_allocs as usize); } } }`

And that's it for memory. We can now do every thing we need to do to access and top up the vector's memory. Now's time for the really hard part: actually implementing the vector's functions.

### Complete source for `reserve()`

`#![allow(unused)] fn main() { pub fn reserve(&self, size: usize) { // Cache the size to prevent another atomic op from due to calling `size()` again let current_size = self.size(); if current_size == 0 { self.allocate_bucket(0); } // Number of allocations needed for current size let mut num_current_allocs = highest_bit(current_size.saturating_add(FIRST_BUCKET_SIZE) - 1) .saturating_sub(highest_bit(FIRST_BUCKET_SIZE)); // Compare with the number of allocations needed for size `new` while num_current_allocs < highest_bit(size.saturating_add(FIRST_BUCKET_SIZE) - 1) .saturating_sub(highest_bit(FIRST_BUCKET_SIZE)) { num_current_allocs += 1; self.allocate_bucket(num_current_allocs as usize); } } }`