Struct Array

Source

pub struct Array { /* private fields */ }

Expand description

A sparse array of values, indexed by a u64.

Implementations§

Source §

impl Array

Source

pub fn new() -> Array

A new, empty array.

Source

pub fn len(&self) -> u64

The highest populated index plus one, which is ARLEN.

Zero for an empty array, and note that this is not the number of elements. See Array::count for that.

Source

pub const fn count(&self) -> u64

How many indices are populated, which is ARCOUNT.

Source

pub const fn is_empty(&self) -> bool

Whether anything is stored at all.

Source

pub fn get(&self, idx: u64) -> Option<Element<'_>>

The value at idx, or none if that position is a hole.

A missing key and a hole are the same answer to a client, which is why there is one None here and not two.

Source

pub fn set(&mut self, idx: u64, val: &[u8]) -> Result<bool>

Writes val at idx, and answers whether that position was empty.

The count of newly filled positions is what ARSET and ARMSET reply with, so the boolean is the useful return rather than the old value.

§Errors

Code::Full when the blob of long values would pass four gigabytes, which is a recorded divergence: Redis heap allocates each of those and has no per key ceiling.

Source

pub fn del(&mut self, idx: u64) -> bool

Clears idx, and answers whether anything was there.

Source

pub fn delete_range(&mut self, lo: u64, hi: u64) -> u64

Clears every populated index in lo..=hi, and answers how many there were.

The cost is in the slices the range touches and not in the width of the range, so ARDELRANGE k 0 18446744073709551614 on a key holding three elements is three deletes and not a walk of the index space.

Source

pub const fn next_index(&self) -> Option<u64>

The index the next ARINSERT would write to, which is ARNEXT.

None when the cursor has run out of space, which happens only after an ARSEEK to the very top: the next append would have nowhere to go, and Redis answers a null rather than an index it cannot honour.

Source

pub const fn seek(&mut self, idx: u64)

Points the cursor so that the next append lands on idx, which is ARSEEK.

Seeking to zero is not the same as seeking to one less than one: it puts the cursor back in the state it was in before anything was appended, which is also the state ARRING reads as “do not reshape me”.

Source

pub fn append<'v>( &mut self, values: impl Iterator<Item = &'v [u8]> + Clone, ) -> Result<u64>

Appends values at consecutive indices from the cursor, which is ARINSERT, and answers where the last one landed.

§Errors

Code::Invalid with INSERT_OVERFLOW when the batch would run off the top of the index space, checked before any of it is written so that a batch either lands whole or not at all.

Source

pub fn ring<'v>( &mut self, size: u64, values: impl Iterator<Item = &'v [u8]>, ) -> Result<u64>

Writes values into a ring of size positions, which is ARRING, and answers where the last one landed.

The ring is not a structure, it is an agreement about indices: writes go to the cursor plus one modulo the size, so a ring of ten holds indices zero to nine and the eleventh write goes back over the first. Changing the size between calls is the only expensive case, because the positions that survive have to be renumbered so that they stay in order, and that is the O(N + M) in the command’s complexity.

§Errors

Whatever Array::set can fail with, which is the two size ceilings.

Source

pub fn last_items<F>(&self, count: u64, newest_first: bool, f: F) -> u64
where F: FnMut(Option<Element<'_>>),

The last count positions from the cursor, which is ARLASTITEMS, and answers how many that turned out to be.

Positions and not elements, so a hole inside the window is reported as one, and the walk wraps at the bottom of the array back to the top. f is called oldest first, or newest first when newest_first.

Source

pub fn scan<F>(&self, start: u64, end: u64, f: F)
where F: FnMut(u64, Element<'_>) -> bool,

Hands every populated index in start..=end to f, which is ARSCAN.

Low to high, or high to low when the two ends come the other way round. f answers whether to keep going, which is how LIMIT stops the walk without the walk knowing what a limit is. Holes are skipped rather than reported, which is the whole difference between this and ARGETRANGE, and it is why this one needs no cap: the cost is the elements it finds and the slices it has to look in, not the width of the range.

Source

pub fn info(&self, full: bool) -> Info

What ARINFO says about the array.

The per layout numbers cost a walk of the directory and are only filled in when full, which is the same split Redis makes and for the same reason: the seven cheap numbers are all read off fields.

Source

pub fn memory_bytes(&self) -> usize

What the array is holding on the heap, for MEMORY USAGE.

Source

pub fn freeze(&self, out: &mut Vec<u8>)

Write this array out in a form a device can hold.

The directory goes out as it stands, slice by slice and word by word, rather than as the index and value pairs a client would see. Rebuilding from pairs would go through Array::set, and the layout a slice ends up in depends on the order it was written in as well as on what is in it, so a slice that had been filled and partly emptied would come back sparse where it went out dense. ARINFO reports that split, so an array whose layout changed because it was quiet long enough to be demoted would be an array whose answers depend on memory pressure.

The blob is written live bytes only, in the order the words are walked in, so a demotion is also a compaction and the dead space does not reach the device. It goes in front of the directory because a word carries where its value starts, and reading the blob first is what lets every one of those be checked as it arrives rather than in a second pass.

Source

pub fn thaw(bytes: &[u8]) -> Result<Array, Broken>

Read back what Array::freeze wrote.

Everything the rest of this file takes for granted is checked here, since this is the one way a directory arrives without having been built by Array::set: offsets inside a slice go up and stay under SLICE_SIZE, a sparse slice holds no holes, a dense window has a populated word at each end, the slice ids go up, the counts add up to the array’s own, and every value in the blob is pointed at by exactly one word. A body that fails any of them is an error, because the alternative is an ARGET that reads off the end of the blob.