pub struct RandomEvictionMap<V> {
shards: Box<[Mutex<Shard<V>>]>,
shard_bits: u32,
shard_capacity: usize,
next_sweep: AtomicUsize,
}Expand description
A concurrent map of at most a fixed number of records keyed by [HoprSurbId], evicting a random
record to admit a new one when full. See the module docs for why.
Fields§
§shards: Box<[Mutex<Shard<V>>]>§shard_bits: u32log2 of the number of shards.
shard_capacity: usizeRecords one shard holds; the map holds at most shards.len() times this.
next_sweep: AtomicUsizeWhere the next expire_step starts.
Implementations§
Source§impl<V> RandomEvictionMap<V>
impl<V> RandomEvictionMap<V>
Sourcepub fn new(budget_bytes: u64) -> Self
pub fn new(budget_bytes: u64) -> Self
A map holding as many records as fit in budget_bytes, at record_bytes each, seeded from
the system RNG. Always holds at least one.
Sourcepub(crate) fn with_seed(records: usize, seed: u64) -> Self
pub(crate) fn with_seed(records: usize, seed: u64) -> Self
A map holding at most records records (at least one), with the eviction RNG seeded by seed:
the same inserts evict the same records, for deterministic tests.
The map is split into a power of two of shards, about one per RECORDS_PER_SHARD records, so
that a map of a few thousand records is a single shard and evicts uniformly over all of it.
fn shard_of(&self, id: &HoprSurbId) -> &Mutex<Shard<V>>
Sourcepub fn insert(&self, id: HoprSurbId, value: V) -> Option<(HoprSurbId, V)>
pub fn insert(&self, id: HoprSurbId, value: V) -> Option<(HoprSurbId, V)>
Stores value under id and returns the record it evicted to make room, if the map was full.
The new record is always admitted. Replacing the record under id evicts nothing. The evicted
record is returned, not handled, so the caller acts on it after the lock is released.
Sourcepub fn update<R>(
&self,
id: &HoprSurbId,
change: impl FnOnce(&mut V) -> R,
) -> Option<R>
pub fn update<R>( &self, id: &HoprSurbId, change: impl FnOnce(&mut V) -> R, ) -> Option<R>
Changes the record under id in place and returns what change returns, or None if there is
no such record.
The change happens under the shard’s lock and never inserts, so a record that a concurrent
remove took is never brought back by it.
An update counts as a write: the record’s expiry runs from it, as it did when the update was a re-insert. The registry opens every reply race through such an update, so after it the record lives a further full horizon, far past the race’s own lifetime, and expiry can never drop a record while a race that only its reply can close is still open.
Sourcepub fn contains_key(&self, id: &HoprSurbId) -> bool
pub fn contains_key(&self, id: &HoprSurbId) -> bool
Whether there is a record under id.
Sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
The number of records, summed over the shards one after the other, so approximate while the map is being changed.
Sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Whether the map holds no record, to the same approximation as len.
Sourcepub fn for_each(&self, visit: impl FnMut(&HoprSurbId, &V))
pub fn for_each(&self, visit: impl FnMut(&HoprSurbId, &V))
Calls visit for every record, shard by shard, holding one shard’s lock at a time.
A record moved or removed while the walk is on another shard may be visited twice or not at all,
and visit must not call back into this map, which it would deadlock on: collect what it needs
and act after the walk.
Sourcepub fn expire_step(&self, horizon: Duration) -> usize
pub fn expire_step(&self, horizon: Duration) -> usize
Drops the records last written longer than horizon ago from the next 1 / EXPIRY_SWEEP_STEPS of
the shards (at least one), so that every shard is swept once per that many calls, and returns
how many it dropped.
Called once per flush tick, which at a horizon of minutes sweeps every shard far more often than it must, and holds one shard lock at a time.
Trait Implementations§
Auto Trait Implementations§
impl<V> !Freeze for RandomEvictionMap<V>
impl<V> !RefUnwindSafe for RandomEvictionMap<V>
impl<V> Send for RandomEvictionMap<V>where
V: Send,
impl<V> Sync for RandomEvictionMap<V>where
V: Send,
impl<V> Unpin for RandomEvictionMap<V>
impl<V> UnsafeUnpin for RandomEvictionMap<V>
impl<V> UnwindSafe for RandomEvictionMap<V>where
V: UnwindSafe,
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
impl<ST, DT> CastableFrom<ST, Initialized, Initialized> for DT
impl<ST, DT> CastableFrom<ST, Uninit, Uninit> for DT
§impl<T> Conv for T
impl<T> Conv for T
§impl<T> FmtForward for T
impl<T> FmtForward for T
§fn fmt_binary(self) -> FmtBinary<Self>where
Self: Binary,
fn fmt_binary(self) -> FmtBinary<Self>where
Self: Binary,
self to use its Binary implementation when Debug-formatted.§fn fmt_display(self) -> FmtDisplay<Self>where
Self: Display,
fn fmt_display(self) -> FmtDisplay<Self>where
Self: Display,
self to use its Display implementation when
Debug-formatted.§fn fmt_lower_exp(self) -> FmtLowerExp<Self>where
Self: LowerExp,
fn fmt_lower_exp(self) -> FmtLowerExp<Self>where
Self: LowerExp,
self to use its LowerExp implementation when
Debug-formatted.§fn fmt_lower_hex(self) -> FmtLowerHex<Self>where
Self: LowerHex,
fn fmt_lower_hex(self) -> FmtLowerHex<Self>where
Self: LowerHex,
self to use its LowerHex implementation when
Debug-formatted.§fn fmt_octal(self) -> FmtOctal<Self>where
Self: Octal,
fn fmt_octal(self) -> FmtOctal<Self>where
Self: Octal,
self to use its Octal implementation when Debug-formatted.§fn fmt_pointer(self) -> FmtPointer<Self>where
Self: Pointer,
fn fmt_pointer(self) -> FmtPointer<Self>where
Self: Pointer,
self to use its Pointer implementation when
Debug-formatted.§fn fmt_upper_exp(self) -> FmtUpperExp<Self>where
Self: UpperExp,
fn fmt_upper_exp(self) -> FmtUpperExp<Self>where
Self: UpperExp,
self to use its UpperExp implementation when
Debug-formatted.§fn fmt_upper_hex(self) -> FmtUpperHex<Self>where
Self: UpperHex,
fn fmt_upper_hex(self) -> FmtUpperHex<Self>where
Self: UpperHex,
self to use its UpperHex implementation when
Debug-formatted.§fn fmt_list(self) -> FmtList<Self>where
&'a Self: for<'a> IntoIterator,
fn fmt_list(self) -> FmtList<Self>where
&'a Self: for<'a> IntoIterator,
§impl<T> FutureExt for T
impl<T> FutureExt for T
§fn with_context(self, otel_cx: Context) -> WithContext<Self>
fn with_context(self, otel_cx: Context) -> WithContext<Self>
§fn with_current_context(self) -> WithContext<Self>
fn with_current_context(self) -> WithContext<Self>
§impl<T> Instrument for T
impl<T> Instrument for T
§fn instrument(self, span: Span) -> Instrumented<Self>
fn instrument(self, span: Span) -> Instrumented<Self>
§fn in_current_span(self) -> Instrumented<Self>
fn in_current_span(self) -> Instrumented<Self>
Source§impl<T> IntoEither for T
impl<T> IntoEither for T
Source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
self into a Left variant of Either<Self, Self>
if into_left is true.
Converts self into a Right variant of Either<Self, Self>
otherwise. Read moreSource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
self into a Left variant of Either<Self, Self>
if into_left(&self) returns true.
Converts self into a Right variant of Either<Self, Self>
otherwise. Read more§impl<T> Pipe for Twhere
T: ?Sized,
impl<T> Pipe for Twhere
T: ?Sized,
§fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> Rwhere
Self: Sized,
fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> Rwhere
Self: Sized,
§fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> Rwhere
R: 'a,
fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> Rwhere
R: 'a,
self and passes that borrow into the pipe function. Read more§fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> Rwhere
R: 'a,
fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> Rwhere
R: 'a,
self and passes that borrow into the pipe function. Read more§fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R
fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R
§fn pipe_borrow_mut<'a, B, R>(
&'a mut self,
func: impl FnOnce(&'a mut B) -> R,
) -> R
fn pipe_borrow_mut<'a, B, R>( &'a mut self, func: impl FnOnce(&'a mut B) -> R, ) -> R
§fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R
fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R
self, then passes self.as_ref() into the pipe function.§fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R
fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R
self, then passes self.as_mut() into the pipe
function.§fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R
fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R
self, then passes self.deref() into the pipe function.§impl<T> Pointable for T
impl<T> Pointable for T
§impl<T> PolicyExt for Twhere
T: ?Sized,
impl<T> PolicyExt for Twhere
T: ?Sized,
impl<T> Read<Exclusive, BecauseExclusive> for Twhere
T: ?Sized,
§impl<T> Tap for T
impl<T> Tap for T
§fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self
fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self
Borrow<B> of a value. Read more§fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self
fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self
BorrowMut<B> of a value. Read more§fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self
fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self
AsRef<R> view of a value. Read more§fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self
fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self
AsMut<R> view of a value. Read more§fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self
fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self
Deref::Target of a value. Read more§fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self
fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self
Deref::Target of a value. Read more§fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self
fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self
.tap() only in debug builds, and is erased in release builds.§fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self
fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self
.tap_mut() only in debug builds, and is erased in release
builds.§fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self
fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self
.tap_borrow() only in debug builds, and is erased in release
builds.§fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self
fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self
.tap_borrow_mut() only in debug builds, and is erased in release
builds.§fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self
fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self
.tap_ref() only in debug builds, and is erased in release
builds.§fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self
fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self
.tap_ref_mut() only in debug builds, and is erased in release
builds.§fn tap_deref_dbg<T>(self, func: impl FnOnce(&T)) -> Self
fn tap_deref_dbg<T>(self, func: impl FnOnce(&T)) -> Self
.tap_deref() only in debug builds, and is erased in release
builds.