pub struct ItemFinder<'t, I> { /* private fields */ }
Expand description
In-memory index for efficient random-access to Item
s by index.
ItemFinder
can be obtained via ItemInformation::finder
. It starts out empty and must be
populated by calling ItemFinder::update
while iterating. There are two typedefs for easier
use:
TypeFinder
for findingType
s in aTypeInformation
(TPI stream).IdFinder
for findingId
s in aIdInformation
(IPI stream).
ItemFinder
allocates all the memory it needs when it is first created. The footprint is
directly proportional to the total number of types; see ItemInformation::len
.
Time/space trade-off
The naïve approach is to store the position of each Item
as they are covered in the stream.
The cost is memory: namely one u32
per Item
.
Compare this approach to an ItemFinder
that stores the position of every Nth item. Memory
requirements would be reduced by a factor of N in exchange for requiring an average of (N-1)/2
iterations per lookup. However, iteration is cheap sequential memory access, and spending less
memory on ItemFinder
means more of the data can fit in the cache, so this is likely a good
trade-off for small-ish values of N.
ItemFinder
is parameterized by shift
which controls this trade-off as powers of two:
- If
shift
is 0,ItemFinder
stores 4 bytes perItem
and always performs direct lookups. - If
shift
is 1,ItemFinder
stores 2 bytes perItem
and averages 0.5 iterations per lookup. - If
shift
is 2,ItemFinder
stores 1 byte perItem
and averages 1.5 iterations per lookup. - If
shift
is 3,ItemFinder
stores 4 bits perItem
and averages 3.5 iterations per lookup. - If
shift
is 4,ItemFinder
stores 2 bits perItem
and averages 7.5 iterations per lookup. - If
shift
is 5,ItemFinder
stores 1 bit perItem
and averages 15.5 iterations per lookup.
This list can continue but with rapidly diminishing returns. Iteration cost is proportional to item size, which varies, but typical numbers from a large program are:
- 24% of items are 12 bytes
- 34% of items are <= 16 bytes
- 84% of items are <= 32 bytes
A shift
of 2 or 3 is likely appropriate for most workloads. 500K items would require 1 MB or
500 KB of memory respectively, and lookups – though indirect – would still usually need only
one or two 64-byte cache lines.
Implementations
impl<'t, I> ItemFinder<'t, I> where
I: ItemIndex,
impl<'t, I> ItemFinder<'t, I> where
I: ItemIndex,
pub fn max_index(&self) -> I
pub fn max_index(&self) -> I
Returns the highest index which is currently served by this ItemFinder
.
When iterating through the stream, you shouldn’t need to consider this. Items only ever reference lower indexes. However, when loading items referenced by the symbols stream, this can be useful to check whether iteration is required.
pub fn update(&mut self, iterator: &ItemIter<'t, I>)
pub fn update(&mut self, iterator: &ItemIter<'t, I>)
Update this ItemFinder
based on the current position of a ItemIter
.
Do this each time you call .next()
. See documentation of ItemInformation
for an
example.
Trait Implementations
Auto Trait Implementations
impl<'t, I> RefUnwindSafe for ItemFinder<'t, I> where
I: RefUnwindSafe,
impl<'t, I> Send for ItemFinder<'t, I> where
I: Sync,
impl<'t, I> Sync for ItemFinder<'t, I> where
I: Sync,
impl<'t, I> Unpin for ItemFinder<'t, I>
impl<'t, I> UnwindSafe for ItemFinder<'t, I> where
I: RefUnwindSafe,
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
impl<I, T> ExtractContext<I, ()> for T
impl<I, T> ExtractContext<I, ()> for T
fn extract_context(self, _original_input: I)
fn extract_context(self, _original_input: I)
Given the context attached to a nom error, and given the original input to the nom parser, extract more the useful context information. Read more
impl<T> FmtForward for T
impl<T> FmtForward for T
fn fmt_binary(self) -> FmtBinary<Self> where
Self: Binary,
fn fmt_binary(self) -> FmtBinary<Self> where
Self: Binary,
Causes self
to use its Binary
implementation when Debug
-formatted. Read more
fn fmt_display(self) -> FmtDisplay<Self> where
Self: Display,
fn fmt_display(self) -> FmtDisplay<Self> where
Self: Display,
Causes self
to use its Display
implementation when
Debug
-formatted. Read more
fn fmt_lower_exp(self) -> FmtLowerExp<Self> where
Self: LowerExp,
fn fmt_lower_exp(self) -> FmtLowerExp<Self> where
Self: LowerExp,
Causes self
to use its LowerExp
implementation when
Debug
-formatted. Read more
fn fmt_lower_hex(self) -> FmtLowerHex<Self> where
Self: LowerHex,
fn fmt_lower_hex(self) -> FmtLowerHex<Self> where
Self: LowerHex,
Causes self
to use its LowerHex
implementation when
Debug
-formatted. Read more
fn fmt_octal(self) -> FmtOctal<Self> where
Self: Octal,
fn fmt_octal(self) -> FmtOctal<Self> where
Self: Octal,
Causes self
to use its Octal
implementation when Debug
-formatted. Read more
fn fmt_pointer(self) -> FmtPointer<Self> where
Self: Pointer,
fn fmt_pointer(self) -> FmtPointer<Self> where
Self: Pointer,
Causes self
to use its Pointer
implementation when
Debug
-formatted. Read more
fn fmt_upper_exp(self) -> FmtUpperExp<Self> where
Self: UpperExp,
fn fmt_upper_exp(self) -> FmtUpperExp<Self> where
Self: UpperExp,
Causes self
to use its UpperExp
implementation when
Debug
-formatted. Read more
fn fmt_upper_hex(self) -> FmtUpperHex<Self> where
Self: UpperHex,
fn fmt_upper_hex(self) -> FmtUpperHex<Self> where
Self: UpperHex,
Causes self
to use its UpperHex
implementation when
Debug
-formatted. Read more
fn fmt_list(self) -> FmtList<Self> where
&'a Self: for<'a> IntoIterator,
fn fmt_list(self) -> FmtList<Self> where
&'a Self: for<'a> IntoIterator,
Formats each item in a sequence. Read more
impl<T> Pipe for T where
T: ?Sized,
impl<T> Pipe for T where
T: ?Sized,
fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> R
fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> R
Pipes by value. This is generally the method you want to use. Read more
fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> R where
R: 'a,
fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> R where
R: 'a,
Borrows self
and passes that borrow into the pipe function. Read more
fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> R where
R: 'a,
fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> R where
R: 'a,
Mutably borrows self
and passes that borrow into the pipe function. Read more
fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R where
Self: Borrow<B>,
B: 'a + ?Sized,
R: 'a,
fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R where
Self: Borrow<B>,
B: 'a + ?Sized,
R: 'a,
Borrows self
, then passes self.borrow()
into the pipe function. Read more
fn pipe_borrow_mut<'a, B, R>(
&'a mut self,
func: impl FnOnce(&'a mut B) -> R
) -> R where
Self: BorrowMut<B>,
B: 'a + ?Sized,
R: 'a,
fn pipe_borrow_mut<'a, B, R>(
&'a mut self,
func: impl FnOnce(&'a mut B) -> R
) -> R where
Self: BorrowMut<B>,
B: 'a + ?Sized,
R: 'a,
Mutably borrows self
, then passes self.borrow_mut()
into the pipe
function. Read more
fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R where
Self: AsRef<U>,
U: 'a + ?Sized,
R: 'a,
fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R where
Self: AsRef<U>,
U: 'a + ?Sized,
R: 'a,
Borrows self
, then passes self.as_ref()
into the pipe function.
fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R where
Self: AsMut<U>,
U: 'a + ?Sized,
R: 'a,
fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R where
Self: AsMut<U>,
U: 'a + ?Sized,
R: 'a,
Mutably borrows self
, then passes self.as_mut()
into the pipe
function. Read more
fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R where
Self: Deref<Target = T>,
T: 'a + ?Sized,
R: 'a,
fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R where
Self: Deref<Target = T>,
T: 'a + ?Sized,
R: 'a,
Borrows self
, then passes self.deref()
into the pipe function.
impl<I> RecreateContext<I> for I
impl<I> RecreateContext<I> for I
fn recreate_context(_original_input: I, tail: I) -> I
fn recreate_context(_original_input: I, tail: I) -> I
Given the original input, as well as the context reported by nom, recreate a context in the original string where the error occurred. Read more
impl<T> Tap for T
impl<T> Tap for T
fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self where
Self: Borrow<B>,
B: ?Sized,
fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self where
Self: Borrow<B>,
B: ?Sized,
Immutable access to the Borrow<B>
of a value. Read more
fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self where
Self: BorrowMut<B>,
B: ?Sized,
fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self where
Self: BorrowMut<B>,
B: ?Sized,
Mutable access to the BorrowMut<B>
of a value. Read more
fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self where
Self: AsRef<R>,
R: ?Sized,
fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self where
Self: AsRef<R>,
R: ?Sized,
Immutable access to the AsRef<R>
view of a value. Read more
fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self where
Self: AsMut<R>,
R: ?Sized,
fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self where
Self: AsMut<R>,
R: ?Sized,
Mutable access to the AsMut<R>
view of a value. Read more
fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self where
Self: Deref<Target = T>,
T: ?Sized,
fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self where
Self: Deref<Target = T>,
T: ?Sized,
Immutable access to the Deref::Target
of a value. Read more
fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self where
Self: DerefMut<Target = T> + Deref,
T: ?Sized,
fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self where
Self: DerefMut<Target = T> + Deref,
T: ?Sized,
Mutable access to the Deref::Target
of a value. Read more
fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self
fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self
Calls .tap()
only in debug builds, and is erased in release builds.
fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self
fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self
Calls .tap_mut()
only in debug builds, and is erased in release
builds. Read more
fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self where
Self: Borrow<B>,
B: ?Sized,
fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self where
Self: Borrow<B>,
B: ?Sized,
Calls .tap_borrow()
only in debug builds, and is erased in release
builds. Read more
fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self where
Self: BorrowMut<B>,
B: ?Sized,
fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self where
Self: BorrowMut<B>,
B: ?Sized,
Calls .tap_borrow_mut()
only in debug builds, and is erased in release
builds. Read more
fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self where
Self: AsRef<R>,
R: ?Sized,
fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self where
Self: AsRef<R>,
R: ?Sized,
Calls .tap_ref()
only in debug builds, and is erased in release
builds. Read more
fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self where
Self: AsMut<R>,
R: ?Sized,
fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self where
Self: AsMut<R>,
R: ?Sized,
Calls .tap_ref_mut()
only in debug builds, and is erased in release
builds. Read more