Struct strudel::st_hash_map::StHashMap

pub struct StHashMap<K, V, S = RandomState> { /* private fields */ }

An insertion-ordered hash map implemented with HashMap and Vec.

StHashMap is designed to implement the st_hash C API and be FFI-friendly.

StHashMap is built on top of a hashing algorithm selected to provide resistance against HashDoS attacks. See RandomState.

StHashMap supports updating keys in place. See StHashMap::update.

The optional api and capi modules in strudel build on top of StHashMap to implement a compatible C API to st_hash. This API includes support for iterating over a mutable map and inplace updates of (key, value) pairs. These features distinguish it from the HashMap in Rust std.

Implementations

impl<K, V> StHashMap<K, V, RandomState>

pub fn new() -> Self

Creates an empty StHashMap.

The hash map is initially created with a capacity of 0, so it will not allocate until it is first inserted into.

Examples

use strudel::StHashMap;
let mut map: StHashMap<&str, i32> = StHashMap::new();
assert_eq!(0, map.capacity());

pub fn with_capacity(capacity: usize) -> Self

Creates an empty StHashMap with the specified capacity.

The hash map will be able to hold at least capacity elements without reallocating. If capacity is 0, the hash map will not allocate.

Examples

use strudel::StHashMap;
let mut map: StHashMap<&str, i32> = StHashMap::with_capacity(10);
assert!(map.capacity() >= 10);

impl<K, V, S> StHashMap<K, V, S>

pub fn with_hasher(hash_builder: S) -> Self

Creates an empty StHashMap which will use the given hash builder to hash keys.

The created map has the default initial capacity.

Warning: hash_builder is normally randomly generated, and is designed to allow StHashMaps to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The hash_builder passed should implement the BuildHasher trait for the StHashMap to be useful, see its documentation for details.

Examples

use strudel::StHashMap;
use std::collections::hash_map::RandomState;

let s = RandomState::new();
let mut map = StHashMap::with_hasher(s);
assert_eq!(0, map.capacity());
map.insert(1, 2);

pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self

Creates an empty StHashMap with the specified capacity, using the given hash builder to hash keys.

The hash map will be able to hold at least capacity elements without reallocating. If capacity is 0, the hash map will not allocate.

Warning: hash_builder is normally randomly generated, and is designed to allow StHashMaps to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The hash_builder passed should implement the BuildHasher trait for the StHashMap to be useful, see its documentation for details.

Examples

use strudel::StHashMap;
use std::collections::hash_map::RandomState;

let s = RandomState::new();
let mut map = StHashMap::with_capacity_and_hasher(10, s);
assert!(map.capacity() >= 10);
map.insert(1, 2);

pub fn capacity(&self) -> usize

Returns the number of elements the map can hold without reallocating.

This number is a lower bound; the StHashMap might be able to hold more, but is guaranteed to be able to hold at least this many.

Examples

use strudel::StHashMap;
let mut map: StHashMap<&str, i32> = StHashMap::with_capacity(100);
assert!(map.capacity() >= 100);

pub fn keys(&self) -> Keys<'_, K, V>

An iterator visiting all keys in insertion order. The iterator element type is &'a K.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);

for key in map.keys() {
    println!("key: {}", key);
}

pub fn values(&self) -> Values<'_, K, V>

An iterator visiting all values in insertion order. The iterator element type is &'a V.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);

for val in map.values() {
    println!("val: {}", val);
}

pub fn iter(&self) -> Iter<'_, K, V>

An iterator for visiting all key-value pairs in insertion order. The iterator element type is (&'a K, &'a V).

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);

for (key, val) in map.iter() {
    println!("key: {} val: {}", key, val);
}

pub fn insert_ranks_from(&self, rank: usize) -> InsertRanks

An iterator for visiting all insertion counters in insertion order starting from the given rank. The iterator element type is usize.

This iterator may return insertion counters to dead elements.

The yielded elements may be passed to get_nth to retrieve the (key, value) pair in the nth insertion slot.

This API can be used to build a mutable iterator over the map that can safely be invalidated. This is safe because new inserts always have higher insert rank. See api::st_foreach.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);

map.remove(&"a");
map.insert("b", 100);

let insert_ranks = map.insert_ranks_from(0).collect::<Vec<_>>();
assert_eq!(vec![0, 1, 2], insert_ranks);

assert_eq!(None, map.get_nth(0));
assert_eq!(Some((&"b", &100)), map.get_nth(1));
assert_eq!(Some((&"c", &3)), map.get_nth(2));
assert_eq!(None, map.get_nth(4));

assert_eq!(0, map.insert_ranks_from(100).count());

pub fn first(&self) -> Option<(&K, &V)>

Returns the first key-value pair in the map. The key in this pair is equal to the key inserted earliest into the map.

Key-value pairs are ordered by insertion order. Insertion order is maintained if there are deletions. Insertion order is by slot, so in-place updates to keys maintain the same insertion position.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
assert_eq!(Some((&"a", &1)), map.first());

map.remove(&"a");
map.insert("b", 100);
assert_eq!(Some((&"b", &100)), map.first());

pub fn last(&self) -> Option<(&K, &V)>

Returns the last key-value pair in the map. The key in this pair is equal to the key inserted most recently into the map.

Key-value pairs are ordered by insertion order. Insertion order is maintained if there are deletions. Insertion order is by slot, so in-place updates to keys maintain the same insertion position.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
assert_eq!(Some((&"c", &3)), map.last());

map.remove(&"a");
map.insert("b", 100);
assert_eq!(Some((&"c", &3)), map.last());

pub fn get_nth(&self, n: usize) -> Option<(&K, &V)>

Returns the nth key-value pair in the map. The key in this pair is equal to the key inserted nth earliest into the map.

Key-value pairs are ordered by insertion order. Insertion order is maintained if there are deletions. Insertion order is by slot, so in-place updates to keys maintain the same insertion position.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);

map.remove(&"a");
map.insert("b", 100);

let insert_ranks = map.insert_ranks_from(0).collect::<Vec<_>>();
assert_eq!(vec![0, 1, 2], insert_ranks);

assert_eq!(None, map.get_nth(0));
assert_eq!(Some((&"b", &100)), map.get_nth(1));
assert_eq!(Some((&"c", &3)), map.get_nth(2));
assert_eq!(None, map.get_nth(4));

assert_eq!(0, map.insert_ranks_from(100).count());

pub fn min_insert_rank(&self) -> usize

Insertion counter for the first key-value pair in the map.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
assert_eq!(0, map.min_insert_rank());

map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
assert_eq!(0, map.min_insert_rank());

map.remove(&"a");
map.insert("b", 100);
assert_eq!(1, map.min_insert_rank());

pub fn max_insert_rank(&self) -> usize

Insertion counter for the last key-value pair in the map.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
assert_eq!(0, map.max_insert_rank());

map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
assert_eq!(2, map.max_insert_rank());

map.remove(&"a");
map.insert("b", 100);
assert_eq!(2, map.max_insert_rank());

pub fn len(&self) -> usize

Returns the number of elements in the map.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
assert_eq!(0, map.len());
map.insert(1, "a");
assert_eq!(1, map.len());

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
assert!(map.is_empty());
map.insert(1, "a");
assert!(!map.is_empty());

pub fn clear(&mut self)

Clears the map, removing all key-value pairs. Keeps the allocated memory for reuse.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert(1, "a");
map.clear();
assert!(map.is_empty());

pub fn hasher(&self) -> &S

Returns a reference to the map’s BuildHasher.

Examples

use strudel::StHashMap;
use std::collections::hash_map::RandomState;

let hasher = RandomState::new();
let map: StHashMap<i32, i32> = StHashMap::with_hasher(hasher);
let hasher: &RandomState = map.hasher();

pub fn estimated_memsize(&self) -> usize

Return an estimate of the byte size of memory allocted for this map.

Examples

use strudel::StHashMap;
let empty: StHashMap<i32, i32> = StHashMap::with_capacity(0);
let map: StHashMap<i32, i32> = StHashMap::with_capacity(100);
assert!(map.estimated_memsize() > empty.estimated_memsize());

impl<K, V, S> StHashMap<K, V, S>

where K: Eq + Hash, S: BuildHasher,

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the StHashMap. The collection may reserve more space to avoid frequent reallocations.

Panics

Panics if the new allocation size overflows usize.

Examples

use strudel::StHashMap;
let mut map: StHashMap<&str, i32> = StHashMap::new();
assert_eq!(0, map.capacity());
map.reserve(10);
assert!(map.capacity() >= 10);

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the map as much as possible. It will drop down as much as possible while maintaining the internal rules and possibly leaving some space in accordance with the resize policy.

Examples

use strudel::StHashMap;
let mut map: StHashMap<i32, i32> = StHashMap::with_capacity(100);
map.insert(1, 2);
map.insert(3, 4);
assert!(map.capacity() >= 100);
map.shrink_to_fit();
assert!(map.capacity() >= 2);

pub fn contains_key(&self, key: &K) -> bool

Returns true if the map contains a value for the specified key.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert(1, "a");
assert_eq!(map.contains_key(&1), true);
assert_eq!(map.contains_key(&2), false);

pub fn get(&self, key: &K) -> Option<&V>

Returns a reference to the value corresponding to the key.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert(1, "a");
assert_eq!(map.get(&1), Some(&"a"));
assert_eq!(map.get(&2), None);

pub fn get_key_value(&self, key: &K) -> Option<(&K, &V)>

Returns the key-value pair corresponding to the supplied key.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert(1, "a");
assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
assert_eq!(map.get_key_value(&2), None);

impl<K, V, S> StHashMap<K, V, S>

where K: Eq + Hash + Clone, V: PartialEq + Clone, S: BuildHasher,

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Inserts a key-value pair into the map.

If the map did not have this key present, None is returned.

If the map did have this key present, the value is updated, and the old value is returned. The key is not updated, though. To update the key in-place, use StHashMap::update.

pub fn update(&mut self, key: K, value: V)

Inserts a key-value pair into the map and update the key in place if an entry is already present.

This function maintains the insertion rank of the key-value pair.

If you do not wish to update the key in-place, use StHashMap::insert.

pub fn remove(&mut self, key: &K) -> Option<V>

Removes a key from the map, returning the stored key if the key was previously in the map.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert(1, "a");
assert_eq!(map.remove(&1), Some("a"));
assert_eq!(map.remove(&1), None);

pub fn remove_entry(&mut self, key: &K) -> Option<(K, V)>

Removes a key from the map, returning the stored key and value if the key was previously in the map.

Examples

use strudel::StHashMap;

let mut map = StHashMap::new();
map.insert(1, "a");
assert_eq!(map.remove_entry(&1), Some((1, "a")));
assert_eq!(map.remove(&1), None);

Trait Implementations

impl<K: Clone, V: Clone, S: Clone> Clone for StHashMap<K, V, S>

fn clone(&self) -> StHashMap<K, V, S>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug, S: Debug> Debug for StHashMap<K, V, S>

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

Formats the value using the given formatter.

impl<K: Default, V: Default, S: Default> Default for StHashMap<K, V, S>

fn default() -> StHashMap<K, V, S>

Returns the “default value” for a type.

impl<K, V, S> Index<&K> for StHashMap<K, V, S>

where K: Eq + Hash, S: BuildHasher,

fn index(&self, key: &K) -> &V

Returns a reference to the value corresponding to the supplied key.

Panics

Panics if the key is not present in the HashMap.

type Output = V

The returned type after indexing.

impl<'a, K: 'a, V: 'a, S> IntoIterator for &'a StHashMap<K, V, S>

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, S> IntoIterator for StHashMap<K, V, S>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, S> PartialEq for StHashMap<K, V, S>

where K: Eq + Hash, V: PartialEq, S: BuildHasher,

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<K, V, S> Eq for StHashMap<K, V, S>

where K: Eq + Hash, V: PartialEq, S: BuildHasher,