Struct DenseRangeMap 

pub(crate) struct DenseRangeMap<K, V1, V2>
where
    K: Clone + 'static,
    V1: Clone + 'static,
    V2: Clone + 'static,
{
    starts: Cow<'static, [K]>,
    values1: Cow<'static, [Option<V1>]>,
    values2: Option<Cow<'static, [Option<V2>]>>,
}

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

• starts is sorted and contains no duplicates.
• values1.len() == starts.len()
• If values2 is 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 to values[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

impl<K, V1, V2> DenseRangeMap<K, V1, V2>

where K: Clone + 'static + Eq + Ord + Successor, V1: Clone + 'static, V2: Clone + 'static,

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.

pub(crate) fn try_from_sorted_inclusive_ranges<S, E>( iter: S, discard_v2: bool, ) -> Result<Self, E>

where S: Iterator<Item = Result<(RangeInclusive<K>, Option<V1>, Option<V2>), E>>, E: From<Error>,

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.

pub(crate) fn index_for_key(&self, key: &K) -> Option<usize>

Return the index for the values corresponding to key.

pub(crate) fn get1(&self, key: &K) -> Option<&V1>

Return the value, if any, associated with the given key.

pub(crate) fn get2(&self, key: &K) -> Option<&V2>

Return the secondary value, if any, associated with the given key.

pub(crate) fn export(&self) -> (&[K], &[Option<V1>], Option<&[Option<V2>]>)

Return a triple of slices that encode this map.

Trait Implementations

impl<K, V1, V2> Clone for DenseRangeMap<K, V1, V2>

where K: Clone + 'static + Clone, V1: Clone + 'static + Clone, V2: Clone + 'static + Clone,

fn clone(&self) -> DenseRangeMap<K, V1, V2>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K, V1, V2> Debug for DenseRangeMap<K, V1, V2>

where K: Clone + 'static + Debug, V1: Clone + 'static + Debug, V2: Clone + 'static + Debug,

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

Formats the value using the given formatter.

impl<K, V1, V2> Default for DenseRangeMap<K, V1, V2>

where K: Clone + 'static, V1: Clone + 'static, V2: Clone + 'static,

fn default() -> Self

Returns the “default value” for a type.

impl<K, V1, V2> PartialEq for DenseRangeMap<K, V1, V2>

where K: Clone + 'static + PartialEq, V1: Clone + 'static + PartialEq, V2: Clone + 'static + PartialEq,

fn eq(&self, other: &DenseRangeMap<K, V1, V2>) -> bool

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K, V1, V2> Eq for DenseRangeMap<K, V1, V2>

where K: Clone + 'static + Eq, V1: Clone + 'static + Eq, V2: Clone + 'static + Eq,

impl<K, V1, V2> StructuralPartialEq for DenseRangeMap<K, V1, V2>

where K: Clone + 'static, V1: Clone + 'static, V2: Clone + 'static,