Struct differential_dataflow::trace::layers::hashed::HashedLayer

pub struct HashedLayer<K: HashOrdered, L> {
    pub keys: Vec<Entry<K>>,
    pub vals: L,
}

A level of the trie, with keys and offsets into a lower layer.

If keys[i].1 == 0 then entry i should be ignored. This is our version of Option<(K, usize)>, which comes at the cost of requiring K: Default to populate empty keys.

Each region of this layer is an independent immutable RHH map, whose size should equal something like (1 << i) + i for some value of i. The first (1 << i) elements are where we expect to find keys, and the remaining i are for spill-over due to collisions near the end of the first region.

We might do something like “if X or fewer elements, just use an ordered list”.

Fields

keys: Vec<Entry<K>>

Keys and offsets for the keys.

vals: L

A lower layer containing ranges of values.

Trait Implementations

impl<K: HashOrdered, L: Trie> Cursor<HashedLayer<K, L>> for HashedCursor<L>

type Key = K

The type revealed by the cursor.

fn key<'a>(&self, storage: &'a HashedLayer<K, L>) -> &'a Self::Key

Reveals the current key.

fn step(&mut self, storage: &HashedLayer<K, L>)

Advances the cursor by one element.

fn seek(&mut self, storage: &HashedLayer<K, L>, key: &Self::Key)

Advances the cursor until the location where key would be expected.

fn valid(&self, _storage: &HashedLayer<K, L>) -> bool

Returns true if the cursor points at valid data. Returns false if the cursor is exhausted.

fn rewind(&mut self, storage: &HashedLayer<K, L>)

Rewinds the cursor to its initial state.

fn reposition(&mut self, storage: &HashedLayer<K, L>, lower: usize, upper: usize)

Repositions the cursor to a different range of values.

impl<K: Debug + HashOrdered, L: Debug> Debug for HashedLayer<K, L>

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

Formats the value using the given formatter.

impl<K: Clone + HashOrdered + Default, L: Trie> Trie for HashedLayer<K, L>

type Item = (K, <L as Trie>::Item)

The type of item from which the type is constructed.

type Cursor = HashedCursor<L>

The type of cursor used to navigate the type.

type MergeBuilder = HashedBuilder<K, <L as Trie>::MergeBuilder>

The type used to merge instances of the type together.

type TupleBuilder = HashedBuilder<K, <L as Trie>::TupleBuilder>

The type used to assemble instances of the type from its Items.

fn keys(&self) -> usize

The number of distinct keys, as distinct from the total number of tuples.

fn tuples(&self) -> usize

The total number of tuples in the collection.

fn cursor_from(&self, lower: usize, upper: usize) -> Self::Cursor

Returns a cursor over a range of data, commonly used by others to restrict navigation to sub-collections.

fn cursor(&self) -> Self::Cursor

Returns a cursor capable of navigating the collection.

fn merge(&self, other: &Self) -> Self

Merges two collections into a third.