Struct csf::ls::CMap

pub struct CMap<C, S = BuildDefaultSeededHasher> {
    pub value_fragments: Map<S>,
    pub value_coding: C,
}

Compressed static function (immutable map) that maps hashable keys to values of any type.

To represent a function f:X→Y, it uses the space slightly larger than |X|H (the overhead is 23% or slightly more), where H is the entropy of the distribution of the f values over X. The time complexity is O(c) for evaluation and O(|X|c) for construction (not counting building the encoding dictionary), where c is the average codeword length (given in code fragments) of the values.

It uses Map based on solving linear system to store fragments of value codes and usually minimum_redundancy::Coding to compress values.

Fields

value_fragments: Map<S>

value_coding: C

Implementations

impl<C: SerializableCoding, S> CMap<C, S>

pub fn write_bytes(&self, bytes_per_value: usize) -> usize

Returns the number of bytes which write will write, assuming that each call to write_value writes bytes_per_value bytes.

pub fn write<F>(&self, output: &mut dyn Write, write_value: F) -> Result<()>

where F: FnMut(&mut dyn Write, &C::Value) -> Result<()>,

Writes self to the output using write_value to write values.

pub fn read_with_hasher<F>( input: &mut dyn Read, read_value: F, hasher: S ) -> Result<Self>

where F: FnMut(&mut dyn Read) -> Result<C::Value>,

Reads self from the input, using read_value to read values (hasher must be the same as used by stored BDZHMap).

impl<C: SerializableCoding> CMap<C, BuildHasherDefault<DefaultHasher>>

pub fn read<F>(input: &mut dyn Read, read_value: F) -> Result<Self>

where F: FnMut(&mut dyn Read) -> Result<C::Value>,

Reads BDZHMap from the input using read_value to read values. Only BDZHMaps that use default hasher can be read by this method.

impl<C: Coding, S: BuildSeededHasher> CMap<C, S>

pub fn try_from_mapf_with_coding_conf<'a, K, V, KvIntoIter, FKvIntoIter, BM>( map: FKvIntoIter, value_coding: C, conf: MapConf<BM, S>, extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash + 'a, V: Borrow<<C as Coding>::Value> + 'a, KvIntoIter: IntoIterator<Item = (&'a K, &'a V)> + 'a, FKvIntoIter: Fn() -> KvIntoIter, BM: ValuesPreFiller,

Underlying Map uses value_coding.bits_per_fragment()+extra_bits_per_fragment bits per fragment. extra_bits_per_fragment>0 increases a chance of detection absence of the key by get and get_stats.

pub fn try_from_map_with_coding_conf<K, MS, BM, V>( map: &HashMap<K, V, MS>, value_coding: C, conf: MapConf<BM, S>, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash, BM: ValuesPreFiller, V: Borrow<<C as Coding>::Value>,

pub fn try_from_kv_with_coding_conf<K, BM, V>( keys: &[K], values: &[V], value_coding: C, conf: MapConf<BM, S>, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash, BM: ValuesPreFiller, V: Borrow<<C as Coding>::Value>,

impl<C: Coding> CMap<C>

pub fn try_from_map_with_coding<K, MS, V>( map: &HashMap<K, V, MS>, value_coding: C, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash, V: Borrow<<C as Coding>::Value>,

pub fn try_from_mapf_with_coding<'a, K, KvIntoIter, FKvIntoIter, V>( map: FKvIntoIter, value_coding: C, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash + 'a, V: Borrow<<C as Coding>::Value> + 'a, KvIntoIter: IntoIterator<Item = (&'a K, &'a V)> + 'a, FKvIntoIter: Fn() -> KvIntoIter,

pub fn try_from_kv_with_coding<K, V>( keys: &[K], values: &[V], value_coding: C, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash, V: Borrow<<C as Coding>::Value>,

impl<C: Coding, S: BuildSeededHasher> CMap<C, S>

pub fn try_from_map_with_builder_bpf_conf<K, MS, BM, BC>( map: &HashMap<K, C::Value, MS>, build_coding: &BC, bits_per_fragment: u8, conf: MapConf<BM, S>, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash, BM: ValuesPreFiller, BC: BuildCoding<C::Value, Coding = C>,

pub fn try_from_map_with_builder_conf<K, MS, BM, BC>( map: &HashMap<K, C::Value, MS>, build_coding: &BC, conf: MapConf<BM, S>, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash, BM: ValuesPreFiller, BC: BuildCoding<C::Value, Coding = C>,

pub fn try_from_kv_with_builder_bpf_conf<K, BM, BC>( keys: &[K], values: &[C::Value], build_coding: &BC, bits_per_fragment: u8, conf: MapConf<BM, S>, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash, BM: ValuesPreFiller, BC: BuildCoding<C::Value, Coding = C>,

pub fn try_from_kv_with_builder_conf<K, BM, BC>( keys: &[K], values: &[C::Value], build_coding: &BC, conf: MapConf<BM, S>, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash, BM: ValuesPreFiller, BC: BuildCoding<C::Value, Coding = C>,

impl<V: Hash + Eq + Clone, S: BuildSeededHasher> CMap<Coding<V>, S>

pub fn try_from_map_with_conf<K, MS, BM>( map: &HashMap<K, V, MS>, bits_per_fragment: u8, conf: MapConf<BM, S>, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash, BM: ValuesPreFiller,

pub fn try_from_kv_with_conf<K, BM>( keys: &[K], values: &[V], bits_per_fragment: u8, conf: MapConf<BM, S>, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash, BM: ValuesPreFiller,

impl<V: Hash + Eq + Clone> CMap<Coding<V>>

pub fn try_from_map<K: Hash, MS>( map: &HashMap<K, V, MS>, bits_per_fragment: u8, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

pub fn try_from_mapf<'a, K, KvIntoIter, FKvIntoIter, BM>( map: FKvIntoIter, bits_per_fragment: u8, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

where K: Hash + 'a, V: 'a, KvIntoIter: IntoIterator<Item = (&'a K, &'a V)> + 'a, FKvIntoIter: Fn() -> KvIntoIter,

pub fn try_from_kv<K: Hash>( keys: &[K], values: &[V], bits_per_fragment: u8, bdz_extra_bits_per_fragment: u8 ) -> Option<Self>

impl<C: Coding, S: BuildSeededHasher> CMap<C, S>

pub fn get_stats<K: Hash + ?Sized, A: AccessStatsCollector>( &self, k: &K, access_stats: &mut A ) -> Option<<<C as Coding>::Decoder<'_> as Decoder>::Decoded>

Gets the value associated with the given key k and reports statistics to access_stats.

pub fn get<K: Hash + ?Sized>( &self, k: &K ) -> Option<<<C as Coding>::Decoder<'_> as Decoder>::Decoded>

Gets the value associated with the given key k.

Trait Implementations

impl<C: GetSize, S> GetSize for CMap<C, S>

fn size_bytes_dyn(&self) -> usize

Returns approximate number of bytes occupied by dynamic (heap) part of self. Same as self.size_bytes() - std::mem::size_of_val(self).

const USES_DYN_MEM: bool = _

true if and only if the variables of this type can use dynamic (heap) memory.

fn size_bytes_content_dyn(&self) -> usize

Returns approximate number of bytes occupied by dynamic (heap) part of self content. It usually equals to size_bytes_dyn(). However, sometimes it is smaller by the amount of memory reserved but not yet used (e.g., size_bytes_content_dyn() only takes into account the length of the vector and not its capacity).

fn size_bytes(&self) -> usize

Returns approximate, total (including heap memory) number of bytes occupied by self.