Struct Elements 

pub struct Elements<V> { /* private fields */ }

An open addressed table of elements, keyed by name, dense in insertion order.

The payload is whatever the collection needs. A set uses (), a hash uses the value address and the TTL slot, a sorted set uses the score.

Implementations

impl<V: Copy> Elements<V>

pub fn new() -> Elements<V>

An empty table that has not allocated anything yet.

A collection is created by its first write, so the empty case is the one that happens most often and it does not deserve an allocation.

pub fn tailed(n: usize, blob: usize) -> Elements<V>

An empty table that keeps each element’s bytes behind its name.

Room for n elements and blob bytes of names and tails together. See Elements::tailed for what a tail is and why it is not a second blob.

pub fn with_capacity(n: usize) -> Elements<V>

An empty table with room for n elements already taken.

This is Y18’s presize rule. SINTERSTORE knows the result is no larger than its smaller input, so it says so once instead of growing eight times on the way there.

pub fn reserve(&mut self, n: usize)

Room for n elements in a table that already exists.

Elements::with_capacity for a table being reused rather than built. A scratch table that is cleared and refilled on every call keeps whatever it grew to last time, so this does nothing at all unless the run coming up is bigger than any run before it, which is what takes the allocator off a SUNION sent in a loop.

The slot array is only rebuilt when it could not hold n at the load factor, rather than whenever a size is named. Rebuilding it to the size it already is would be an allocation asked for by a call whose whole point is to avoid one.

pub fn len(&self) -> usize

How many elements are here.

pub fn is_empty(&self) -> bool

Whether the collection is empty, which for Redis means it does not exist.

pub fn get(&self, name: &[u8]) -> Option<&V>

What is stored against this name.

pub fn get_mut(&mut self, name: &[u8]) -> Option<&mut V>

The payload, to be changed in place.

This is the HINCRBY and ZINCRBY path. Neither of them writes a name, so neither of them should pay for one.

pub fn contains(&self, name: &[u8]) -> bool

Whether this name is here at all. SISMEMBER and HEXISTS.

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

Which row this name is in, for a caller keeping an array beside the rows.

A hash’s field deadlines are indexed by row position rather than by a number in the row (crate::ttl says why), so HEXPIRE needs the position the probe found rather than the payload it found there. That is the only caller, and it is why this is a position and not a payload.

The position is only good until the next insert or remove, since a remove moves the last row into the hole.

pub fn hash_of(name: &[u8]) -> u64

The hash of a name, for a caller about to ask several tables about it.

SINTER over k sets asks the same question k times, and hashing the member once instead of k times is the difference between the hash being noise and it being most of the work. Pair it with Elements::contains_hashed.

pub fn contains_hashed(&self, h: u64, name: &[u8]) -> bool

Whether this name is here, with its hash already in hand.

The hash must be Elements::hash_of of the same bytes. Anything else gives a wrong answer rather than an error, which is why this takes the name too and compares it: a caller cannot fake membership with a number.

pub fn index_of_hashed(&self, h: u64, name: &[u8]) -> Option<usize>

Which row this name is in, with its hash already in hand.

pub fn get_hashed(&self, h: u64, name: &[u8]) -> Option<&V>

What is stored against this name, with its hash already in hand.

pub fn get_hashed_mut(&mut self, h: u64, name: &[u8]) -> Option<&mut V>

The payload to be changed in place, with the hash already in hand.

pub fn insert(&mut self, name: &[u8], value: V) -> Result<Option<V>, Full>

Store value against name, and say what was there before.

None means the element is new, which is the number SADD and HSET report. A name over NAME_MAX or a table at MAX_ROWS is refused rather than truncated, and refusing is a false here and an error message from the layer above, which is the one that knows which command is being answered.

pub fn insert_hashed( &mut self, h: u64, name: &[u8], value: V, ) -> Result<Option<V>, Full>

Store value against name, with its hash already in hand.

The partitioned band hashes once to pick a partition and would otherwise hash again to place the row inside it, which on a short member is most of the write.

pub fn set_tailed( &mut self, name: &[u8], tail: &[u8], value: V, ) -> Result<(usize, bool), Full>

Store tail against name, and say which row it is in and whether the name is new.

HSET. Only for a table built by Elements::tailed.

A name that is already here keeps its row and its slot and gets a fresh span in the blob, because the new tail need not be the length of the old one. That copies the name again, which is the one thing this arrangement costs that a separate value blob did not, and it is a few bytes against the four an offset would have cost every field in the hash forever.

pub fn tail(&self, name: &[u8]) -> Option<&[u8]>

The tail stored against name.

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

How long the tail stored against name is. HSTRLEN.

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

The name and tail of one row, by position.

pub fn pairs(&self) -> impl Iterator<Item = (&[u8], &[u8])>

Every name and tail, in insertion order. HGETALL.

pub fn remove(&mut self, name: &[u8]) -> Option<V>

Take an element out and hand back what it held.

SREM, HDEL and the removing half of SPOP.

pub fn remove_hashed(&mut self, h: u64, name: &[u8]) -> Option<V>

Take an element out, with its hash already in hand.

pub fn remove_at(&mut self, idx: usize) -> Option<V>

Take the element at a position out, without looking its name up again.

SPOP reads the name with Elements::at, writes it into the reply, and then calls this. That way the name is copied once, into the buffer it was going to be copied into anyway, rather than into a Vec that exists only to be dropped after the reply is framed.

pub fn at(&self, idx: usize) -> Option<(&[u8], &V)>

The name and payload of one row, by position.

The dense draw. SRANDMEMBER picks a number under Elements::len and calls this, and that is the whole operation: no walk, no ordered structure, no allocation.

pub fn at_mut(&mut self, idx: usize) -> Option<&mut V>

The payload at idx, to be written over.

The companion to Elements::index_of, for a caller that has probed once and wants to use the position it found rather than probe again.

pub fn take_at(&mut self, idx: usize) -> Option<(Vec<u8>, V)>

Take the row at idx out and hand back its name and payload.

The convenient form of a draw and a removal, for a caller that wants the name and does not have a buffer to put it in. It allocates. The path that answers a client uses Elements::at and then Elements::remove_at and allocates nothing.

pub fn iter(&self) -> impl Iterator<Item = (&[u8], &V)>

Every element, in insertion order.

The sequential walk. HGETALL, SMEMBERS and the scan cursor all read the row array front to back, which is one stream of cache lines and no pointer chasing.

pub fn payloads_mut(&mut self) -> impl Iterator<Item = &mut V>

Every payload, to be changed in place, with no names in the way.

For a payload that is a reference into somewhere else, which has to be fixed up when that somewhere else moves. The names are deliberately not offered here: this borrows the rows mutably, and handing out a name at the same time would borrow the name blob as well for no caller that wants it.

pub fn scan<F>(&self, cursor: Cursor, count: usize, f: F) -> Cursor

where F: FnMut(&[u8], &V),

Walk part of the table and say where to resume.

This is SSCAN, HSCAN and ZSCAN. It reads downward from the cursor, hands each element to f, and stops after count of them or at the bottom, whichever comes first. A returned cursor that is Cursor::is_end means the collection has been walked.

Downward is what makes the guarantee hold while the collection is being written, and crate::scan is where the argument for that lives. count is a hint in Redis and a limit here, and a zero is read as one, because a scan that returns nothing and the same cursor is a client that never finishes.

This band is one partition, so a cursor from a partitioned layout is rebased onto it before anything is read.

pub fn scan_pairs<F>(&self, cursor: Cursor, count: usize, f: F) -> Cursor

where F: FnMut(&[u8], &[u8]),

Elements::scan handing back names and tails. This is HSCAN.

pub fn clear(&mut self)

Throw everything away and keep the allocations.

Emptying a collection usually means it is about to be filled again, which is SINTERSTORE over the same destination in a loop.

pub fn memory_bytes(&self) -> usize

What this table costs, not counting anything the payload points at.

The payload is the caller’s, so a value that lives in the arena is counted by the arena and not twice here.

pub fn slot_bytes(&self) -> usize

What the slot array costs on its own, for the memory measurements.

pub fn row_bytes(&self) -> usize

What the row array costs on its own, capacity and not length, because the slack a doubling Vec is holding is memory this table is using.

pub fn name_bytes(&self) -> usize

What the name blob costs on its own, live bytes and dead ones together.

pub const fn dead_name_bytes(&self) -> usize

Name bytes no row points at any more.

Reported rather than hidden, because a set that has been written and rewritten holds them and INFO memory should say so.

Trait Implementations

impl<V: Clone> Clone for Elements<V>

fn clone(&self) -> Elements<V>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<V: Debug> Debug for Elements<V>

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

Formats the value using the given formatter.

impl<V: Copy> Default for Elements<V>

fn default() -> Elements<V>

Returns the “default value” for a type.