Struct IdIndex

pub struct IdIndex<K, P, const N: usize> { /* private fields */ }

In-memory immutable index to do prefix lookup of key K through P.

In a nutshell, this is a mapping of K -> P -> S::Entry where S: IdIndexSource<P>. The source table S isn’t owned by this index.

This index stores first N bytes of each key K associated with the pointer P. K may be a heap-allocated object. P is supposed to be a cheap value type like u32 or usize. As the index entry of type ([u8; N], P) is small and has no indirect reference, constructing the index should be faster than sorting the source (K, _) pairs.

A key K must be at least N bytes long.

Implementations

impl<K, P, const N: usize> IdIndex<K, P, N>

where K: ObjectId + Ord,

pub fn builder() -> IdIndexBuilder<K, P, N>

pub fn with_capacity(capacity: usize) -> IdIndexBuilder<K, P, N>

pub fn resolve_prefix_with<B, S, U>( &self, source: S, prefix: &HexPrefix, entry_mapper: impl FnMut(S::Entry) -> U, ) -> PrefixResolution<(K, B)>

where B: FromIterator<U>, S: IdIndexSource<P>, S::Entry: IdIndexSourceEntry<K>,

Looks up entries with the given prefix, and collects values if matched entries have unambiguous keys.

pub fn resolve_prefix_to_key<S>( &self, source: S, prefix: &HexPrefix, ) -> PrefixResolution<K>

where S: IdIndexSource<P>, S::Entry: IdIndexSourceEntry<K>,

Looks up unambiguous key with the given prefix.

pub fn lookup_exact<'i, 'q, S>( &'i self, source: S, key: &'q K, ) -> Option<IdIndexLookup<'i, 'q, K, P, S, N>>

where S: IdIndexSource<P>, S::Entry: IdIndexSourceEntry<K>,

Looks up entry for the key. Returns accessor to neighbors.

pub fn shortest_unique_prefix_len<S>(&self, source: S, key: &K) -> usize

where S: IdIndexSource<P>, S::Entry: IdIndexSourceEntry<K>,

This function returns the shortest length of a prefix of key that disambiguates it from every other key in the index.

The length to be returned is a number of hexadecimal digits.

This has some properties that we do not currently make much use of:

• The algorithm works even if key itself is not in the index.

• In the special case when there are keys in the trie for which our key is an exact prefix, returns key.len() + 1. Conceptually, in order to disambiguate, you need every letter of the key and the additional fact that it’s the entire key). This case is extremely unlikely for hashes with 12+ hexadecimal characters.

Trait Implementations

impl<K: Clone, P: Clone, const N: usize> Clone for IdIndex<K, P, N>

fn clone(&self) -> IdIndex<K, P, N>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: Debug, P: Debug, const N: usize> Debug for IdIndex<K, P, N>

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

Formats the value using the given formatter.