Struct List

Source

pub struct List { /* private fields */ }

Expand description

A list of elements, in order, reachable from both ends.

Implementations§

Source §

impl List

Source

pub fn new() -> List

An empty list, in the band every list starts in.

Source

pub fn len(&self) -> usize

How many elements it holds.

Source

pub fn is_empty(&self) -> bool

Whether it holds nothing.

A list that reaches zero is deleted by the keyspace, the same as a set that does, so this is a question about the moment between the last pop and that delete rather than a state a client can observe.

Source

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

Write this list out as the bytes it comes back from.

What a demotion turns the body into. The packed band goes out as the listpack bytes it already is, and the ring goes out chunk by chunk, each one its element count and its live bytes.

Chunk by chunk and not element by element, because a chunk’s bytes are already in the encoding Chunk::adopt takes, so a list of a million elements is a couple of thousand copies out and the same number back rather than two million encodes. The ring also comes back with the same chunk boundaries it left with, which keeps MEMORY USAGE and the walk cost of an index the same on both sides of a trip to the device.

The dead space at either end of a chunk is not written. A chunk that had room to push into comes back full, and pushing into it again allocates a new chunk where the old one would have grown in place. That is a list which was quiet long enough to be demoted paying one allocation on the write that wakes it, and it is worth the bytes it saves on the device.

Source

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

Read a list back out of what List::freeze wrote.

§Errors

Broken for bytes that are not the shape freeze wrote, which is a read that came back torn rather than anything a caller did.

Source

pub const fn encoding(&self) -> Encoding

What OBJECT ENCODING says about it.

Source

pub fn memory_bytes(&self) -> usize

What it costs, not counting anything a caller is holding.

Source

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

The element at index from the front.

Source

pub fn front(&self) -> Option<Element<'_>>

The first element.

Source

pub fn back(&self) -> Option<Element<'_>>

The last element.

Reads the back length rather than walking, in both bands, which is what makes RPOP on a long list cost the same as LPOP on one.

Source

pub fn iter(&self) -> impl Iterator<Item = Element<'_>>

A forward walk over every element.

Source

pub fn iter_back(&self) -> impl Iterator<Item = Element<'_>>

The same walk the other way.

Both bands keep a length behind every element, so this costs what the forward walk costs. LPOS with a negative rank is what wants it.

Source

pub fn range( &self, start: usize, count: usize, ) -> impl Iterator<Item = Element<'_>>

count elements starting at start, which is LRANGE.

Both ends are already normalised by the caller, because the wire’s start and stop can be negative, can be the wrong way round and can hang off either end, and every one of those turns into an empty reply rather than into an error.

A window in the middle does not walk to its start. The packed band skips entries because that is all a hundred and twenty eight of them costs, and the chunked band steps over whole chunks and only decodes the ones it is going to hand back. LRANGE mylist 500000 500099 on a million element list reads a hundred elements and not five hundred thousand.

Source

pub fn push_front(&mut self, value: &[u8], limits: &Limits)

Put value at the front.

Source

pub fn push_back(&mut self, value: &[u8], limits: &Limits)

Put value at the back.

Source

pub fn insert(&mut self, index: usize, value: &[u8], limits: &Limits) -> bool

Put value in at index, pushing what was there along, which is the half of LINSERT that already knows where the pivot was.

An index equal to the length appends. Anything past that is nothing.

Source

pub fn insert_at_pivot( &mut self, pivot: &[u8], value: &[u8], before: bool, limits: &Limits, ) -> Option<usize>

Put value next to the first pivot in the list, which is LINSERT.

Gives back the new length, or nothing when the pivot is not there, which is the difference between the reply being a length and being -1.

Source

pub fn set(&mut self, index: usize, value: &[u8], limits: &Limits) -> bool

Put value where the element at index is, which is LSET.

Source

pub fn find(&self, value: &[u8]) -> Option<usize>

Where the first value is, front to back.

This is what LINSERT spends its time in, and on a long list it is essentially all of it: the insert itself is a couple of hundred nanoseconds and the pivot search in front of it is however long the list is. So it goes to the band rather than through the element walk, and the band reads entry headers instead of decoding elements.

Source

pub fn positions( &self, value: &[u8], rank: i64, count: usize, maxlen: usize, found: &mut dyn FnMut(usize), ) -> usize

Where value is, as many times as asked, which is LPOS.

rank is which match to start at and which way to look: 1 is the first from the front, -1 the first from the back, 2 the second from the front. count is how many to give back with 0 meaning all of them, and maxlen is how many elements may be compared before giving up, with 0 meaning no limit. The indexes handed back are always from the front, whichever way the walk went, because that is what the client can use.

Each answer is handed to found as it is discovered, and the number of them comes back, because this runs on a shard thread and a shard thread that allocates aborts. The wire writes each position straight into the reply buffer and never holds a list of them at all.

found is a dyn call rather than a generic, so that the two walks below stay one body. Monomorphising this over the sink would double a function whose whole cost is the comparison inside it.

Like List::find this goes to the band rather than through the element walk, and for the same reason: an LPOS that is not answered by the first few elements reads the list, and reading the list one decoded Element at a time costs about three times what reading it as entry headers does. The walk carries the MAXLEN budget itself rather than counting elements out here, because counting them out here means the budget is only checked between calls into the band, which on a ring is once a chunk.

Source

pub fn remove(&mut self, count: i64, value: &[u8], limits: &Limits) -> usize

Take out up to count elements equal to value, which is LREM.

A positive count works from the front, a negative one from the back, and zero means every one of them. Gives back how many went.

Source

pub fn trim(&mut self, start: usize, count: usize, limits: &Limits)

Keep count elements starting at start and drop the rest, which is LTRIM.

Both ends are normalised by the caller, the same as List::range, and a count of zero empties the list, which on the wire deletes the key.

Source

pub fn drop_front(&mut self, limits: &Limits) -> bool

Drop the first element, and say whether there was one.

The read and the removal are separate so that LPOP on the wire can write the element straight into the reply buffer and then drop it, which is the same split crate::set::Set::drop_at exists for.

Source