Struct csf::ls::Map

pub struct Map<S = BuildDefaultSeededHasher> { /* private fields */ }

Static function (immutable map) that maps hashable keys to unsigned integer values of given bit-size.

It takes about 1.23bn bits to represent a function from an n-element set into a set of b-bit values. It has a computational construction and access time complexity of O(n) and O(1), respectively.

Its construction is based on solving linear system of equations by hyper-graphs peeling. The implementation is based on the paper:

• D. Belazzougui, P. Boldi, G. Ottaviano, R. Venturini, S. Vigna, Cache-Oblivious Peeling of Random Hypergraphs, In A. Bilgin, M. W. Marcellin, J. Serra-Sagristà, & J. A. Storer (Eds.), Proceedings of Data Compression Conference 26-28 March 2014, Snowbird, Utah, USA (pp. 352-361). (Data Compression Conference. Proceedings; Vol. 2375-0391). IEEE. https://doi.org/10.1109/DCC.2014.48

Implementations

impl<S> Map<S>

pub fn write_bytes(&self) -> usize

Returns number of bytes which write will write.

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

Writes self to the output.

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

Reads self from the input (hasher must be the same as used by written Map).

impl Map<BuildDefaultSeededHasher>

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

Reads self from the input. Only Maps that use default hasher can be read by this method.

pub fn try_with_fn<K, V, BC>( keys: &[K], values: V, bits_per_value: u8 ) -> Option<Self>

where K: Hash, V: Fn(usize, u8) -> u64,

pub fn try_with_bitset<K, BC>( keys: &[K], values: &[u64], bits_per_value: u8 ) -> Option<Self>

where K: Hash, BC: FnOnce(usize) -> Box<[u64]>,

pub fn try_with_kv_bpv<K, V, BC>( keys: &[K], values: &[V], bits_per_value: u8 ) -> Option<Self>

where K: Hash, V: Into<u64> + Copy,

pub fn try_with_kv<K, V, BC>(keys: &[K], values: &[V]) -> Option<Self>

where K: Hash, V: Into<u64> + Copy + Ord,

impl<S: BuildSeededHasher> Map<S>

pub fn try_with_conf_fn<K, KBorrow, KVIntoIterator, FKVIntoIterator, BM>( kv: FKVIntoIterator, kv_len: usize, bits_per_value: u8, conf: MapConf<BM, S> ) -> Option<Self>

where KVIntoIterator: IntoIterator<Item = (KBorrow, u64)>, FKVIntoIterator: Fn() -> KVIntoIterator, K: Hash, KBorrow: Borrow<K>, BM: ValuesPreFiller,

Tries to construct Map with key-value pairs produced by the iterator returned by the kv function, using the given configuration.

The iterator returned by kv should produce exactly kv_len key-value pairs. Each value should occupy up to bits_per_value (least significant) bits (the most significant bits must be zeroed).

pub fn try_with_conf_bitset<K, BM>( keys: &[K], values: &[u64], bits_per_value: u8, conf: MapConf<BM, S> ) -> Option<Self>

where K: Hash, BM: ValuesPreFiller,

Tries to construct Map with key-value pairs stored in keys and values respectively. The values array should contain (at least) keys.len() fragments, each with a size of bits_per_value bits.

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

where K: Hash, V: Into<u64> + Clone, BM: ValuesPreFiller,

Tries to construct Map with key-value pairs stored in keys and values respectively.

The values array usually consists of u8, u16, u32 or u64 items. The keys and values arrays must have the same length. Each value must be convertible to u64 and should occupy up to bits_per_value (least significant) bits (the most significant bits must be zeroed).

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

where K: Hash, V: Into<u64> + Clone, BM: ValuesPreFiller,

Tries to construct Map with key-value pairs stored in keys and values respectively.

The values array usually consists of u8, u16, u32 or u64 items. The keys and values arrays must have the same length.

pub fn try_from_hashmap_bpv<K, V, HMS, BM>( map: HashMap<K, V, HMS>, bits_per_value: u8, conf: MapConf<BM, S> ) -> Option<Self>

where K: Hash, V: Into<u64> + Clone, BM: ValuesPreFiller,

Tries to construct Map with key-value pairs stored in map.

Values are usually of type u8, u16, u32 or u64. Each value must be convertible to u64 and should occupy up to bits_per_value (least significant) bits (the most significant bits must be zeroed).

pub fn try_from_hashmap<K, V, HMS, BM>( map: HashMap<K, V, HMS>, conf: MapConf<BM, S> ) -> Option<Self>

where K: Hash, V: Into<u64> + Clone, BM: ValuesPreFiller,

Tries to construct Map with key-value pairs stored in map.

Values are usually of type u8, u16, u32 or u64. Each value must be convertible to u64.

pub fn get<K: Hash>(&self, key: &K) -> u64

Returns value assigned to the given key. If the key was not in the input collection, an unpredictable value is returned.

Trait Implementations

impl<K: Hash, V: Into<u64> + Clone, S: BuildSeededHasher + Default> From<&[(K, V)]> for Map<S>

fn from(map: &[(K, V)]) -> Self

Converts to this type from the input type.

impl<K: Hash, V: Into<u64> + Clone, S: BuildSeededHasher + Default, HMS> From<HashMap<K, V, HMS>> for Map<S>

fn from(map: HashMap<K, V, HMS>) -> Self

Converts to this type from the input type.

impl<S> GetSize for Map<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

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.