Struct Chunk 

pub struct Chunk { /* private fields */ }

A run of entries, filled from one end or the other.

Implementations

impl Chunk

pub fn for_back() -> Chunk

An empty chunk that grows toward the back.

pub fn for_front() -> Chunk

An empty chunk that grows toward the front.

pub fn plain(value: &[u8]) -> Chunk

A chunk of its own for one element too big for an ordinary one.

A list element can be half a gigabyte and a chunk is eight kilobytes, so something has to give. Redis calls this a plain node and so does this: the chunk is exactly the size of the element, it is full the moment it is made, and every push against it is refused, which puts the next element in a chunk of its own rather than growing this one to hold both.

pub fn adopt(entries: &[u8], count: usize) -> Chunk

A chunk holding entries somebody else already encoded.

The promotion out of the packed band, where the bytes in question are a listpack’s entry region. They are in this encoding already, so the band change is one copy and not a re-encode of every element, and the chunk that comes out of it grows toward the back because a list that has just outgrown a listpack is nearly always one that is being appended to.

pub const fn len(&self) -> usize

How many elements are in it.

pub const fn is_empty(&self) -> bool

Whether it holds nothing.

pub fn memory_bytes(&self) -> usize

What it costs, buffer included.

pub const fn live_bytes(&self) -> usize

How many bytes the entries themselves take.

pub fn entries(&self) -> &[u8]

The encoded entries, without the dead space at either end.

The reverse of Chunk::adopt, and the two are a pair: what comes out of here goes back in there and gives a chunk holding the same elements. That is what a demotion needs, because the ring is rebuilt on the way back and rebuilding it by pushing every element one at a time would re-encode a list that arrived already encoded.

pub fn push_back(&mut self, value: &[u8]) -> bool

Put value at the back, or say there was no room.

The count cap is checked here rather than by the caller because a chunk that is full for either reason is full in exactly the same way, and a caller that had to check one of the two would eventually forget.

pub fn push_front(&mut self, value: &[u8]) -> bool

Put value at the front, or say there was no room.

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

The first element, without taking it out.

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

The last element, without taking it out.

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

The element at index from the front.

pub fn drop_front(&mut self) -> bool

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

The bytes stay where they are. A chunk that has been emptied from the front is dropped whole by the deque above, so there is nobody left to care that the room it is holding is at the wrong end.

pub fn drop_back(&mut self) -> bool

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

pub fn drop_front_n(&mut self, n: usize) -> usize

Drop the first n elements.

A walk of n entries and one move of the head cursor, with no bytes touched at all, which is what makes LTRIM of the front of a long list cost the walk and nothing else. Stops early and says how many it really dropped if the chunk runs out first.

pub fn drop_back_n(&mut self, n: usize) -> usize

Drop the last n elements.

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

Put value in at index, pushing what was there along.

Says no when the chunk has no room, which the deque above answers by splitting the chunk and asking one of the halves. The bytes on one side of the hole do have to move, because the elements between the cursors are a run, but it is whichever side is shorter and it is at most the size of a chunk. That is the same move a quicklist makes for an insert and the difference is that a list only inserts in the middle when a client asks it to, where a quicklist does it on every LPOP.

pub fn remove_at(&mut self, index: usize) -> bool

Take the element at index out, closing the gap behind it.

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

Put value where the element at index was.

The common case is a value the same size as the one it replaces, which is written where it lies. Anything else is a remove and an insert, and it can fail for the same reason an insert can.

pub fn split_off(&mut self, index: usize) -> Chunk

Split this chunk in two, keeping the first index elements.

The entries are a run in one encoding, so the tail of the run is already a chunk’s worth of bytes and the split is one copy. This is how an insert into a full chunk gets its room: the deque splits at the insertion point and both halves come back with space.

pub fn seal(&mut self)

Give back the room this chunk was keeping for pushes it will not see.

Called when a chunk stops being an end of the list. It is a copy of the live bytes and a shrink, and it happens once per chunk in the life of a list that is only ever appended to.

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

Where value is in this chunk, or nothing.

The same walk crate::listpack::Listpack::find_parsed does and the same code, because a chunk is the same entries in a run with a cursor at each end rather than a blob with a header. LINSERT on a long list is almost entirely this call repeated over a few thousand chunks, so it reads headers and rejects on length rather than decoding every element into an crate::listpack::Entry on the way past.

pub fn find_each( &self, value: &[u8], as_int: Option<i64>, limit: usize, hit: &mut dyn FnMut(usize) -> bool, ) -> usize

Every place value is in this chunk, front to back.

limit caps how many elements are looked at with 0 meaning no cap, hit says whether to carry on, and what comes back is how many elements were looked at so a caller walking a ring can carry one budget across it.

pub fn find_each_back( &self, value: &[u8], as_int: Option<i64>, limit: usize, hit: &mut dyn FnMut(usize) -> bool, ) -> usize

The same from the back, with indexes counted from the last element here.

pub fn iter(&self) -> Iter<'_>

A forward walk over what is here.

pub fn iter_back(&self) -> RevIter<'_>

The same walk the other way.

Every entry carries its own length behind it, which is what the back cursor reads to find the entry before it, so this costs the same per element as the forward walk rather than being a forward walk per element. LPOS with a negative rank is the reason it exists.

pub fn iter_from(&self, index: usize) -> Iter<'_>

A forward walk that starts at index rather than at the front.

LRANGE in the middle of a list lands in the middle of a chunk, and the only other way to start there is to walk the entries in front of it and throw them away. This finds the byte offset by whichever end is closer and hands back a walk from there.

Trait Implementations

impl Clone for Chunk

fn clone(&self) -> Chunk

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Chunk

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Eq for Chunk

impl PartialEq for Chunk

fn eq(&self, other: &Chunk) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl StructuralPartialEq for Chunk