Struct IndexedMap

pub struct IndexedMap<K: Hash + Ord, V> { /* private fields */ }

A map which can be iterated in a deterministic order.

This would traditionally be accomplished by simply using a BTreeMap, however B-Trees generally have very slow lookups. Because we use a nodes+channels map while finding routes across the network graph, our network graph backing map must be as performant as possible. However, because peers expect to sync the network graph from us (and we need to support that without holding a lock on the graph for the duration of the sync or dumping the entire graph into our outbound message queue), we need an iterable map with a consistent iteration order we can jump to a starting point on.

Thus, we have a custom data structure here - its API mimics that of Rust’s BTreeMap, but is actually backed by a HashMap, with some additional tracking to ensure we can iterate over keys in the order defined by Ord.

This is not exported to bindings users as bindings provide alternate accessors rather than exposing maps directly.

Implementations

impl<K: Clone + Hash + Ord, V> IndexedMap<K, V>

pub fn new() -> Self

Constructs a new, empty map

pub fn with_capacity(capacity: usize) -> Self

Constructs a new, empty map with the given capacity pre-allocated

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

Fetches the element with the given key, if one exists.

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

Fetches a mutable reference to the element with the given key, if one exists.

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

Fetches the key-value pair corresponding to the supplied key, if one exists.

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

Returns true if an element with the given key exists in the map.

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

Removes the element with the given key, returning it, if one exists.

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

Inserts the given key/value pair into the map, returning the element that was previously stored at the given key, if one exists.

pub fn entry(&mut self, key: K) -> Entry<'_, K, V>

Returns an Entry for the given key in the map, allowing access to the value.

pub fn unordered_keys(&self) -> impl Iterator<Item = &K>

Returns an iterator which iterates over the keys in the map, in a random order.

pub fn unordered_iter(&self) -> impl Iterator<Item = (&K, &V)>

Returns an iterator which iterates over the key/value pairs in a random order.

pub fn unordered_iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)>

Returns an iterator which iterates over the keys and mutable references to values in a random order.

pub fn range<R: RangeBounds<K>>(&mut self, range: R) -> Range<'_, K, V>

Returns an iterator which iterates over the key/value pairs in a given range.

pub fn len(&self) -> usize

Returns the number of key/value pairs in the map

pub fn is_empty(&self) -> bool

Returns true if there are no elements in the map

Trait Implementations

impl<K: Clone + Hash + Ord, V: Clone> Clone for IndexedMap<K, V>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: Debug + Hash + Ord, V: Debug> Debug for IndexedMap<K, V>

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

Formats the value using the given formatter.

impl<K: Hash + Ord + PartialEq, V: PartialEq> PartialEq for IndexedMap<K, V>

fn eq(&self, other: &Self) -> 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: Eq + Hash + Ord, V: Eq> Eq for IndexedMap<K, V>