pub struct Set { /* private fields */ }Expand description
A set of members.
Implementations§
Source§impl Set
impl Set
Sourcepub fn new() -> Set
pub fn new() -> Set
An empty set, which starts as an intset.
This is what SADD on a missing key creates when it has no size hint,
and the first member decides nothing: an intset that receives a string
converts on the spot, and it costs a conversion of nothing.
Sourcepub fn with_hint(first: &[u8], hint: usize, limits: &Limits) -> Set
pub fn with_hint(first: &[u8], hint: usize, limits: &Limits) -> Set
An empty set sized for what is about to go in it.
Redis’s setTypeCreate, which picks the representation from the first
member and the count the caller expects, so that SADD k a b c ... with
a thousand arguments builds a table once rather than converting twice on
the way there. hint is only a hint and being wrong about it costs a
conversion and no correctness.
An integer first member sends it to the intset even when the count is
past set-max-intset-entries, where Redis would go straight to a
dictionary. A large set of integers is the case the runs exist for, and
building a table and never leaving it would give up the whole saving on
the one call that said in advance it was going to matter. The listpack
band in between is still honoured, because a set that small has nothing
to save and a server configured that way expects a listpack.
Sourcepub const fn encoding(&self) -> Encoding
pub const fn encoding(&self) -> Encoding
Which representation this is in.
Four bodies and three words, and the intset accounts for two of the
missing ones. The partitioned body answers hashtable because it is one,
and an intset past set-max-intset-entries answers hashtable because
that is what a real server would have turned into by then, even though
nothing here was rehashed.
Sourcepub fn freeze(&self, out: &mut Vec<u8>)
pub fn freeze(&self, out: &mut Vec<u8>)
Write the set out as the bytes it becomes when it leaves memory.
One form byte and then whatever that form needs. The two representations that already have a flat layout, the single run intset and the listpack, are written as themselves and cost one byte, because those bytes are exactly what has to come back. The other two are written as their members.
The form carries enough to land back in the same representation, which
crate::rdb deliberately does not: ints_past_limit rides in the top
bit of the form byte, and a set of integers that has split into runs is
its own form rather than a list of members, so that a million integers do
not come back as a hash table at thirty bytes a member. A value that
changed encoding because it was quiet long enough to be demoted would be a
value whose OBJECT ENCODING depends on memory pressure.
See Set::thaw, which is the other half and reads exactly this.
Sourcepub fn thaw(bytes: &[u8]) -> Result<Set, Broken>
pub fn thaw(bytes: &[u8]) -> Result<Set, Broken>
Read back a set written by Set::freeze.
The count in the member form is a capacity and not a promise. It picks the body and sizes it, and then the members decide the length, so a count that disagrees with what follows costs a rehash and never a wrong set.
Sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Whether there are none.
An empty set does not exist in Redis, so the caller deletes the key when this turns true rather than storing an empty one.
Sourcepub fn has(&self, needle: &Needle<'_>) -> bool
pub fn has(&self, needle: &Needle<'_>) -> bool
The same question asked with the work already done. See Needle.
This is what set algebra probes with. Every arm is the arm
Set::contains would have taken, with the parse and the hash lifted
out of it, so the two cannot disagree about what a member is.
Sourcepub fn at(&self, index: usize) -> Option<Member<'_>>
pub fn at(&self, index: usize) -> Option<Member<'_>>
The member at index, in whatever order the representation holds them.
Ascending for an intset, insertion order for the other two. Redis makes no promise about set order and neither does this, but a uniform draw needs positions and this is what gives it them (K9).
Sourcepub const fn ints(&self) -> Option<&Intset>
pub const fn ints(&self) -> Option<&Intset>
The members as a sorted array of integers, when that is what this is.
The one place the representation is not an implementation detail, and it
is here for crate::setops: two sorted arrays intersect by stepping
through both of them with no hash anywhere, which is a different order of
cost from asking a table a question per member. That was worth nothing
while an all integer set turned into a table at five hundred and twelve
members, and it is worth a great deal now that it does not.
Sourcepub fn scan<F>(&self, cursor: Cursor, count: usize, f: F) -> Cursor
pub fn scan<F>(&self, cursor: Cursor, count: usize, f: F) -> Cursor
Walk part of the set and say where to resume. This is SSCAN.
Only the table and the partitioned band walk in windows. An intset or a
listpack hands back
every member in one call and a cursor of Cursor::END, ignoring the
cursor it was given, which is what Redis does for the same two encodings
and for the same reason: a hundred and twenty eight members is smaller
than the reply header arithmetic to split them up, and a set that small
cannot block the loop long enough for the split to be worth anything.
Ignoring the cursor is safe rather than merely convenient, because promotion is one way. A set that gave a client a listpack cursor is not going to be a listpack again, so the only way to arrive at those two arms with a cursor from somewhere else is for the key to have been deleted and remade underneath the scan, and returning everything to that client returns a member twice at worst, which the guarantee allows.
A table cursor arriving at the band is the one crossing that does happen,
because a set can split part way through a client’s scan. That is handled
rather than ignored: a table cursor names one partition, and
Cursor::rebase reads the widening and restarts the walk at the top of
the new layout, so the client sees some members a second time and misses
none. Repeats are what the SCAN guarantee gives up in exchange for
surviving a resize, and a set only splits once.
Sourcepub fn memory_bytes(&self) -> usize
pub fn memory_bytes(&self) -> usize
Bytes held by whichever representation this is.
Sourcepub fn slot_bytes(&self) -> usize
pub fn slot_bytes(&self) -> usize
What the slot array costs on its own, or nothing if there is not one.
The three of these split Set::memory_bytes into the arrays it is made
of, which is what turns an argument about where the memory went into a
number. An intset and a listpack are one allocation with no index over
it, so they answer all of it under names and nothing under the other two.
Sourcepub fn name_bytes(&self) -> usize
pub fn name_bytes(&self) -> usize
What the member bytes cost, live ones and dead ones together.
Sourcepub fn add(&mut self, member: &[u8], limits: &Limits) -> bool
pub fn add(&mut self, member: &[u8], limits: &Limits) -> bool
Add member, promoting if it no longer fits. Answers whether it was new.
This is setTypeAdd, arm for arm.
Sourcepub fn remove(&mut self, member: &[u8]) -> bool
pub fn remove(&mut self, member: &[u8]) -> bool
Remove member. Answers whether it was there.
Never demotes, which is Y4’s one-way rule and Redis’s behaviour.
Sourcepub fn remove_at(&mut self, index: usize) -> Option<Vec<u8>>
pub fn remove_at(&mut self, index: usize) -> Option<Vec<u8>>
Take out the member at index and hand it back.
This is what SPOP runs on top of. The table moves its last row into the
hole rather than shifting, so the position of every other member is
stable except for one; the other two shift. Neither is a promise a caller
can lean on, and SPOP does not need one because it draws again from the
new length each time.
Sourcepub fn drop_at(&mut self, index: usize) -> bool
pub fn drop_at(&mut self, index: usize) -> bool
Take out the member at index without building it into a Vec first.
The same removal as Set::remove_at for a caller that has already read
the member and does not need it handed back. That caller is SPOP on the
wire, which reads with Set::at, writes the bytes straight into the
reply buffer, and only then calls this. It is an allocation a member
saved on the one command in the set whose whole cost is the allocating.
Set::remove_at stays for the embedded API, where the caller wants the
bytes and has nowhere to put them.