Struct Cached 

pub struct Cached<T: Indexable>
where
    T::Key: FastHash + Default,
{ /* private fields */ }

A PGM-Index wrapper with a small hot-key cache.

This struct uses interior mutability (Cell) to update the cache on read operations. Therefore, it is !Sync and cannot be shared across threads without synchronization (e.g., Mutex<Cached>).

Note: When serialized with serde, only the inner index is saved. The cache is recreated empty on deserialization.

Example

use pgm_extra::index::external::Cached;

let keys: Vec<u64> = (0..10000).collect();
let index = Cached::new(&keys, 64, 4).unwrap();

// First lookup - cache miss, populates cache
assert!(index.contains(&keys, &5000));

// Second lookup - cache hit
assert!(index.contains(&keys, &5000));

Implementations

impl<T: Indexable> Cached<T>

where T::Key: Ord + FastHash + Default,

pub fn new( data: &[T], epsilon: usize, epsilon_recursive: usize, ) -> Result<Self, Error>

Build a new cached PGM-Index from sorted data.

pub fn from_index(index: Static<T>) -> Self

Wrap an existing index with a cache.

pub fn search(&self, value: &T) -> ApproxPos

Get an approximate position for the given value.

pub fn lower_bound(&self, data: &[T], value: &T) -> usize

where T: Ord,

Find the first position where data[pos] >= value.

pub fn upper_bound(&self, data: &[T], value: &T) -> usize

where T: Ord,

Find the first position where data[pos] > value.

pub fn contains(&self, data: &[T], value: &T) -> bool

where T: Ord,

Check if the value exists in the data.

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn segments_count(&self) -> usize

pub fn height(&self) -> usize

pub fn epsilon(&self) -> usize

pub fn epsilon_recursive(&self) -> usize

pub fn size_in_bytes(&self) -> usize

pub fn clear_cache(&self)

Clear all cached entries.

pub fn inner(&self) -> &Static<T>

Get a reference to the inner index.

pub fn into_inner(self) -> Static<T>

Consume and return the inner index.

pub fn range_indices<R>(&self, data: &[T], range: R) -> (usize, usize)

where T: Ord, R: RangeBounds<T>,

Returns the (start, end) indices for iterating over data in the given range.

pub fn range<'a, R>( &self, data: &'a [T], range: R, ) -> impl DoubleEndedIterator<Item = &'a T>

where T: Ord, R: RangeBounds<T>,

Returns an iterator over data in the given range.

Trait Implementations

impl<T: Indexable> Archive for Cached<T>

where T::Key: FastHash + Default, Static<T>: Archive, Skip: ArchiveWith<HotCache<T::Key>>,

type Archived = ArchivedCached<T>

The archived representation of this type.

type Resolver = CachedResolver<T>

The resolver for this type. It must contain all the additional information from serializing needed to make the archived type from the normal type.

fn resolve(&self, resolver: Self::Resolver, out: Place<Self::Archived>)

Creates the archived version of this value at the given position and writes it to the given output.

const COPY_OPTIMIZATION: CopyOptimization<Self> = _

An optimization flag that allows the bytes of this type to be copied directly to a writer instead of calling serialize.

impl<T: Debug + Indexable> Debug for Cached<T>

where T::Key: FastHash + Default + Debug,

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

Formats the value using the given formatter.

impl<'de, T: Indexable> Deserialize<'de> for Cached<T>

where T::Key: FastHash + Default + Serialize + DeserializeOwned,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<__D: Fallible + ?Sized, T: Indexable> Deserialize<Cached<T>, __D> for Archived<Cached<T>>

where T::Key: FastHash + Default, Static<T>: Archive, <Static<T> as Archive>::Archived: Deserialize<Static<T>, __D>, Skip: ArchiveWith<HotCache<T::Key>> + DeserializeWith<<Skip as ArchiveWith<HotCache<T::Key>>>::Archived, HotCache<T::Key>, __D>,

fn deserialize( &self, deserializer: &mut __D, ) -> Result<Cached<T>, <__D as Fallible>::Error>

Deserializes using the given deserializer

impl<T: Indexable> External<T> for Cached<T>

where T::Key: Ord + FastHash + Default,

fn search(&self, value: &T) -> ApproxPos

Get an approximate position for the value.

fn lower_bound(&self, data: &[T], value: &T) -> usize

where T: Ord,

Find the first position where data[pos] >= value.

fn upper_bound(&self, data: &[T], value: &T) -> usize

where T: Ord,

Find the first position where data[pos] > value.

fn contains(&self, data: &[T], value: &T) -> bool

where T: Ord,

Check if the value exists in the sorted slice.

fn len(&self) -> usize

Number of elements the index was built for.

fn segments_count(&self) -> usize

Number of segments in the index.

fn epsilon(&self) -> usize

Epsilon value used for the bottom level.

fn size_in_bytes(&self) -> usize

Approximate memory usage in bytes.

fn is_empty(&self) -> bool

Whether the index is empty.

impl<T: Indexable> From<Cached<T>> for Static<T>

where T::Key: Ord + FastHash + Default,

fn from(cached: Cached<T>) -> Self

Converts to this type from the input type.

impl<T: Indexable> From<Static<T>> for Cached<T>

where T::Key: Ord + FastHash + Default,

fn from(index: Static<T>) -> Self

Converts to this type from the input type.

impl<__S: Fallible + ?Sized, T: Indexable> Serialize<__S> for Cached<T>

where T::Key: FastHash + Default, Static<T>: Serialize<__S>, Skip: SerializeWith<HotCache<T::Key>, __S>,

fn serialize( &self, serializer: &mut __S, ) -> Result<<Self as Archive>::Resolver, <__S as Fallible>::Error>

Writes the dependencies for the object and returns a resolver that can create the archived type.

impl<T: Indexable> Serialize for Cached<T>

where T::Key: FastHash + Default + Serialize + DeserializeOwned,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.