pub(crate) struct DenseRangeMap<K, V1, V2>{
starts: Cow<'static, [K]>,
values1: Cow<'static, [Option<V1>]>,
values2: Option<Cow<'static, [Option<V2>]>>,
}Expand description
An immutable map from ranges to Option<V1>, Option<V2>-pairs.
This type is optimized for reasonable O(lg N) performance, and for space efficiency in the case where:
Option<V>is the same size as V, or at least not much larger.- most or all ranges have no gaps between them.
- we might not want to record any values for V2 at all.
- we are willing to treat “no entry” and “maps to None” as equivalent.
That is to say, we get our space efficiency wins in the case where, if some range (K..=V) in the map, (V+1..=K2) is also likely to be in the map.
(This is true for around like 99% of our IPv4 ranges and around 91% of our IPv6 ranges.)
This type is crate-internal because its functionality is limited, and because we may want to switch to some other approach to geoip in the future.
§Overview
We consider a map of disjoint ranges (S..=E) => V
as a dense map from (S'..=E') => Option<V1, V2>,
such that there is is exactly one (S'..E') range covering every value from
min(S) through K::MAX inclusive.
Because this map is dense, we can encode these ranges as a sorted list of S’,
and then use a binary search to find which Option<V1, V2> corresponds
to any given value.
§Invariants
startsis sorted and contains no duplicates.values1.len() == starts.len()- If
values2is present,values2.len() == starts.len()
§Semantics:
This table maps keys to value as follows:
If starts is empty, then every key maps to None.
Otherwise:
- Every key such that
K::min <= key < starts[0]maps to None. - Every key such that
starts[idx] <= key < starts[idx+1]maps tovalues[idx], which may be Some or None. - Every key such that
key >= starts.last()maps to values.last(), which may be Some or None.
If values2 is present, then keys map to the same indices in values2
as they do in values1.
Fields§
§starts: Cow<'static, [K]>A list of the starting points of each range or gap.
values1: Cow<'static, [Option<V1>]>A list of values.
If starts[i] is the start of a range, then values[i] is Some(v)
where v is the value of that range for every
values2: Option<Cow<'static, [Option<V2>]>>An optional list of secondary values.
Implementations§
Source§impl<K, V1, V2> DenseRangeMap<K, V1, V2>
impl<K, V1, V2> DenseRangeMap<K, V1, V2>
Sourcepub(crate) fn from_static_parts(
starts: &'static [K],
values1: &'static [Option<V1>],
values2: Option<&'static [Option<V2>]>,
) -> Self
pub(crate) fn from_static_parts( starts: &'static [K], values1: &'static [Option<V1>], values2: Option<&'static [Option<V2>]>, ) -> Self
Create a new map from its raw parts.
Requires that the slices are actually the results of calling
export() on a map of this type.
Sourcepub(crate) fn try_from_sorted_inclusive_ranges<S, E>(
iter: S,
discard_v2: bool,
) -> Result<Self, E>
pub(crate) fn try_from_sorted_inclusive_ranges<S, E>( iter: S, discard_v2: bool, ) -> Result<Self, E>
Construct a DenseRangeMap from an iterator of
Result<(range,optvalue1,optvalue2)> tuples.
The ranges must be disjoint and sorted in ascending order by their start.
Sourcepub(crate) fn index_for_key(&self, key: &K) -> Option<usize>
pub(crate) fn index_for_key(&self, key: &K) -> Option<usize>
Return the index for the values corresponding to key.
Sourcepub(crate) fn get1(&self, key: &K) -> Option<&V1>
pub(crate) fn get1(&self, key: &K) -> Option<&V1>
Return the value, if any, associated with the given key.
Trait Implementations§
Source§impl<K, V1, V2> Clone for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> Clone for DenseRangeMap<K, V1, V2>
Source§impl<K, V1, V2> Debug for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> Debug for DenseRangeMap<K, V1, V2>
Source§impl<K, V1, V2> Default for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> Default for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> Eq for DenseRangeMap<K, V1, V2>
Source§impl<K, V1, V2> PartialEq for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> PartialEq for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> StructuralPartialEq for DenseRangeMap<K, V1, V2>
Auto Trait Implementations§
impl<K, V1, V2> Forget for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> Freeze for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> Move for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> RefUnwindSafe for DenseRangeMap<K, V1, V2>where
Cow<'static, [K]>: RefUnwindSafe,
Cow<'static, [Option<V1>]>: RefUnwindSafe,
Option<Cow<'static, [Option<V2>]>>: RefUnwindSafe,
impl<K, V1, V2> Send for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> Sync for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> Unpin for DenseRangeMap<K, V1, V2>
impl<K, V1, V2> UnsafeUnpin for DenseRangeMap<K, V1, V2>where
Cow<'static, [K]>: UnsafeUnpin,
Cow<'static, [Option<V1>]>: UnsafeUnpin,
Option<Cow<'static, [Option<V2>]>>: UnsafeUnpin,
impl<K, V1, V2> UnwindSafe for DenseRangeMap<K, V1, V2>where
Cow<'static, [K]>: UnwindSafe,
Cow<'static, [Option<V1>]>: UnwindSafe,
Option<Cow<'static, [Option<V2>]>>: UnwindSafe,
Blanket Implementations§
Source§impl<'a, T, E> AsTaggedExplicit<'a, E> for Twhere
T: 'a,
impl<'a, T, E> AsTaggedExplicit<'a, E> for Twhere
T: 'a,
Source§impl<'a, T, E> AsTaggedImplicit<'a, E> for Twhere
T: 'a,
impl<'a, T, E> AsTaggedImplicit<'a, E> for Twhere
T: 'a,
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
Source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
Source§impl<T> Downcast for Twhere
T: Any,
impl<T> Downcast for Twhere
T: Any,
Source§fn into_any(self: Box<T>) -> Box<dyn Any>
fn into_any(self: Box<T>) -> Box<dyn Any>
Box<dyn Trait> (where Trait: Downcast) to Box<dyn Any>, which can then be
downcast into Box<dyn ConcreteType> where ConcreteType implements Trait.Source§fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
Rc<Trait> (where Trait: Downcast) to Rc<Any>, which can then be further
downcast into Rc<ConcreteType> where ConcreteType implements Trait.Source§fn as_any(&self) -> &(dyn Any + 'static)
fn as_any(&self) -> &(dyn Any + 'static)
&Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot
generate &Any’s vtable from &Trait’s.Source§fn as_any_mut(&mut self) -> &mut (dyn Any + 'static)
fn as_any_mut(&mut self) -> &mut (dyn Any + 'static)
&mut Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot
generate &mut Any’s vtable from &mut Trait’s.Source§impl<T> DowncastSend for T
impl<T> DowncastSend for T
Source§impl<T> DowncastSync for T
impl<T> DowncastSync for T
Source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
Source§impl<T> Instrument for T
impl<T> Instrument for T
Source§fn instrument(self, span: Span) -> Instrumented<Self> ⓘ
fn instrument(self, span: Span) -> Instrumented<Self> ⓘ
Source§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