//! <div align="center">
//! <h1>Stretto</h1>
//! </div>
//! <div align="center">
//!
//! Stretto is a pure Rust implementation for <https://github.com/dgraph-io/ristretto>.
//!
//! A high performance thread-safe memory-bound Rust cache.
//!
//! English | [简体中文](https://github.com/al8n/stretto/blob/main/README-zh_CN.md)
//!
//! [<img alt="github" src="https://img.shields.io/badge/GITHUB-Stretto-8da0cb?style=for-the-badge&logo=Github" height="22">][Github-url]
//! [<img alt="Build" src="https://img.shields.io/github/workflow/status/al8n/stretto/CI/main?logo=Github-Actions&style=for-the-badge" height="22">][CI-url]
//! [<img alt="codecov" src="https://img.shields.io/codecov/c/gh/al8n/stretto?style=for-the-badge&token=P175Q03Q1L&logo=codecov" height="22">][codecov-url]
//!
//! [<img alt="docs.rs" src="https://img.shields.io/badge/docs.rs-stretto-66c2a5?style=for-the-badge&labelColor=555555&logo=data:image/svg+xml;base64,PHN2ZyByb2xlPSJpbWciIHhtbG5zPSJodHRwOi8vd3d3LnczLm9yZy8yMDAwL3N2ZyIgdmlld0JveD0iMCAwIDUxMiA1MTIiPjxwYXRoIGZpbGw9IiNmNWY1ZjUiIGQ9Ik00ODguNiAyNTAuMkwzOTIgMjE0VjEwNS41YzAtMTUtOS4zLTI4LjQtMjMuNC0zMy43bC0xMDAtMzcuNWMtOC4xLTMuMS0xNy4xLTMuMS0yNS4zIDBsLTEwMCAzNy41Yy0xNC4xIDUuMy0yMy40IDE4LjctMjMuNCAzMy43VjIxNGwtOTYuNiAzNi4yQzkuMyAyNTUuNSAwIDI2OC45IDAgMjgzLjlWMzk0YzAgMTMuNiA3LjcgMjYuMSAxOS45IDMyLjJsMTAwIDUwYzEwLjEgNS4xIDIyLjEgNS4xIDMyLjIgMGwxMDMuOS01MiAxMDMuOSA1MmMxMC4xIDUuMSAyMi4xIDUuMSAzMi4yIDBsMTAwLTUwYzEyLjItNi4xIDE5LjktMTguNiAxOS45LTMyLjJWMjgzLjljMC0xNS05LjMtMjguNC0yMy40LTMzLjd6TTM1OCAyMTQuOGwtODUgMzEuOXYtNjguMmw4NS0zN3Y3My4zek0xNTQgMTA0LjFsMTAyLTM4LjIgMTAyIDM4LjJ2LjZsLTEwMiA0MS40LTEwMi00MS40di0uNnptODQgMjkxLjFsLTg1IDQyLjV2LTc5LjFsODUtMzguOHY3NS40em0wLTExMmwtMTAyIDQxLjQtMTAyLTQxLjR2LS42bDEwMi0zOC4yIDEwMiAzOC4ydi42em0yNDAgMTEybC04NSA0Mi41di03OS4xbDg1LTM4Ljh2NzUuNHptMC0xMTJsLTEwMiA0MS40LTEwMi00MS40di0uNmwxMDItMzguMiAxMDIgMzguMnYuNnoiPjwvcGF0aD48L3N2Zz4K" height="20">][doc-url]
//! [<img alt="crates.io" src="https://img.shields.io/crates/v/stretto?style=for-the-badge&logo=data:image/svg+xml;base64,PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0iaXNvLTg4NTktMSI/Pg0KPCEtLSBHZW5lcmF0b3I6IEFkb2JlIElsbHVzdHJhdG9yIDE5LjAuMCwgU1ZHIEV4cG9ydCBQbHVnLUluIC4gU1ZHIFZlcnNpb246IDYuMDAgQnVpbGQgMCkgIC0tPg0KPHN2ZyB2ZXJzaW9uPSIxLjEiIGlkPSJMYXllcl8xIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHhtbG5zOnhsaW5rPSJodHRwOi8vd3d3LnczLm9yZy8xOTk5L3hsaW5rIiB4PSIwcHgiIHk9IjBweCINCgkgdmlld0JveD0iMCAwIDUxMiA1MTIiIHhtbDpzcGFjZT0icHJlc2VydmUiPg0KPGc+DQoJPGc+DQoJCTxwYXRoIGQ9Ik0yNTYsMEwzMS41MjgsMTEyLjIzNnYyODcuNTI4TDI1Niw1MTJsMjI0LjQ3Mi0xMTIuMjM2VjExMi4yMzZMMjU2LDB6IE0yMzQuMjc3LDQ1Mi41NjRMNzQuOTc0LDM3Mi45MTNWMTYwLjgxDQoJCQlsMTU5LjMwMyw3OS42NTFWNDUyLjU2NHogTTEwMS44MjYsMTI1LjY2MkwyNTYsNDguNTc2bDE1NC4xNzQsNzcuMDg3TDI1NiwyMDIuNzQ5TDEwMS44MjYsMTI1LjY2MnogTTQzNy4wMjYsMzcyLjkxMw0KCQkJbC0xNTkuMzAzLDc5LjY1MVYyNDAuNDYxbDE1OS4zMDMtNzkuNjUxVjM3Mi45MTN6IiBmaWxsPSIjRkZGIi8+DQoJPC9nPg0KPC9nPg0KPGc+DQo8L2c+DQo8Zz4NCjwvZz4NCjxnPg0KPC9nPg0KPGc+DQo8L2c+DQo8Zz4NCjwvZz4NCjxnPg0KPC9nPg0KPGc+DQo8L2c+DQo8Zz4NCjwvZz4NCjxnPg0KPC9nPg0KPGc+DQo8L2c+DQo8Zz4NCjwvZz4NCjxnPg0KPC9nPg0KPGc+DQo8L2c+DQo8Zz4NCjwvZz4NCjxnPg0KPC9nPg0KPC9zdmc+DQo=" height="22">][crates-url]
//! [<img alt="rustc" src="https://img.shields.io/badge/MSRV-1.55.0-fc8d62.svg?style=for-the-badge&logo=Rust" height="22">][rustc-url]
//!
//! [<img alt="license-apache" src="https://img.shields.io/badge/License-Apache%202.0-blue.svg?style=for-the-badge&logo=Apache" height="22">][license-apache-url]
//! [<img alt="license-mit" src="https://img.shields.io/badge/License-MIT-yellow.svg?style=for-the-badge&fontColor=white&logoColor=f5c076&logo=data:image/svg+xml;base64,PHN2ZyB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIGhlaWdodD0iMzZweCIgdmlld0JveD0iMCAwIDI0IDI0IiB3aWR0aD0iMzZweCIgZmlsbD0iI2Y1YzA3NiI+PHBhdGggZD0iTTAgMGgyNHYyNEgwVjB6IiBmaWxsPSJub25lIi8+PHBhdGggZD0iTTEwLjA4IDEwLjg2Yy4wNS0uMzMuMTYtLjYyLjMtLjg3cy4zNC0uNDYuNTktLjYyYy4yNC0uMTUuNTQtLjIyLjkxLS4yMy4yMy4wMS40NC4wNS42My4xMy4yLjA5LjM4LjIxLjUyLjM2cy4yNS4zMy4zNC41My4xMy40Mi4xNC42NGgxLjc5Yy0uMDItLjQ3LS4xMS0uOS0uMjgtMS4yOXMtLjQtLjczLS43LTEuMDEtLjY2LS41LTEuMDgtLjY2LS44OC0uMjMtMS4zOS0uMjNjLS42NSAwLTEuMjIuMTEtMS43LjM0cy0uODguNTMtMS4yLjkyLS41Ni44NC0uNzEgMS4zNlM4IDExLjI5IDggMTEuODd2LjI3YzAgLjU4LjA4IDEuMTIuMjMgMS42NHMuMzkuOTcuNzEgMS4zNS43Mi42OSAxLjIuOTFjLjQ4LjIyIDEuMDUuMzQgMS43LjM0LjQ3IDAgLjkxLS4wOCAxLjMyLS4yM3MuNzctLjM2IDEuMDgtLjYzLjU2LS41OC43NC0uOTQuMjktLjc0LjMtMS4xNWgtMS43OWMtLjAxLjIxLS4wNi40LS4xNS41OHMtLjIxLjMzLS4zNi40Ni0uMzIuMjMtLjUyLjNjLS4xOS4wNy0uMzkuMDktLjYuMS0uMzYtLjAxLS42Ni0uMDgtLjg5LS4yMy0uMjUtLjE2LS40NS0uMzctLjU5LS42MnMtLjI1LS41NS0uMy0uODgtLjA4LS42Ny0uMDgtMXYtLjI3YzAtLjM1LjAzLS42OC4wOC0xLjAxek0xMiAyQzYuNDggMiAyIDYuNDggMiAxMnM0LjQ4IDEwIDEwIDEwIDEwLTQuNDggMTAtMTBTMTcuNTIgMiAxMiAyem0wIDE4Yy00LjQxIDAtOC0zLjU5LTgtOHMzLjU5LTggOC04IDggMy41OSA4IDgtMy41OSA4LTggOHoiLz48L3N2Zz4=" height="22">][license-mit-url]
//!
//! </div>
//!
//! ## Features
//! * **Internal Mutability** - Do not need to use `Arc<RwLock<Cache<...>>` for concurrent code, you just need `Cache<...>` or `AsyncCache<...>`
//! * **Sync and Async** - Stretto support sync and runtime agnostic async.
//! * In sync, [`Cache`] starts two extra OS level threads. One is policy thread, the other is writing thread.
//! * In async, [`AsyncCache`] starts two extra green threads. One is policy thread, the other is writing thread.
//! * **Store policy** Stretto only store the value, which means the cache does not store the key.
//! * **High Hit Ratios** - with Dgrpah's developers unique admission/eviction policy pairing, Stretto's performance is best in class.
//! * **Eviction: SampledLFU** - on par with exact LRU and better performance on Search and Database traces.
//! * **Admission: TinyLFU** - extra performance with little memory overhead (12 bits per counter).
//! * **Fast Throughput** - use a variety of techniques for managing contention and the result is excellent throughput.
//! * **Cost-Based Eviction** - any large new item deemed valuable can evict multiple smaller items (cost could be anything).
//! * **Fully Concurrent** - you can use as many threads as you want with little throughput degradation.
//! * **Metrics** - optional performance metrics for throughput, hit ratios, and other stats.
//! * **Simple API** - just figure out your ideal [`CacheBuilder`] values and you're off and running.
//!
//! ## Table of Contents
//!
//! * [Usage](#Usage)
//! * [Example](#Example)
//! * [Sync](#Sync)
//! * [Async](#Async)
//! * [Config](#Config)
//! * [num_counters](#num_counters)
//! * [max_cost](#max_cost)
//! * [key_builder](#key_builder)
//! * [buffer_size](#buffer_size)
//! * [metrics](#metrics)
//! * [ignore_internal_cost](#ignore_internal_cost)
//! * [cleanup_duration](#cleanup_duration)
//! * [update_validator](#update_validator)
//! * [callback](#callback)
//! * [coster](#coster)
//! * [hasher](#hasher)
//!
//! ## Usage
//! ### Example
//! Please see [examples](https://github.com/al8n/stretto/tree/main/examples) on github.
//!
//! ### Config
//! The [`CacheBuilder`] or [`AsyncCacheBuilder`] struct is used when creating [`Cache`]/[`AsyncCache`] instances if you want to customize the [`Cache`]/[`AsyncCache`] settings.
//!
//! #### num_counters
//!
//! `num_counters` is the number of 4-bit access counters to keep for admission and eviction.
//! Dgraph's developers have seen good performance in setting this to 10x the number of
//! items you expect to keep in the cache when full.
//!
//! For example, if you expect each item to have a cost of 1 and `max_cost` is 100, set `num_counters` to 1,000.
//! Or, if you use variable cost values but expect the cache to hold around 10,000 items when full,
//! set num_counters to 100,000. The important thing is the *number of unique items* in the full cache,
//! not necessarily the `max_cost` value.
//!
//! #### max_cost
//!
//! `max_cost` is how eviction decisions are made. For example,
//! if max_cost is 100 and a new item with a cost of 1 increases total cache cost to 101,
//! 1 item will be evicted.
//!
//! `max_cost` can also be used to denote the max size in bytes. For example,
//! if max_cost is 1,000,000 (1MB) and the cache is full with 1,000 1KB items,
//! a new item (that's accepted) would cause 5 1KB items to be evicted.
//!
//! `max_cost` could be anything as long as it matches how you're using the cost values when calling `insert`.
//!
//! #### key_builder
//!
//! [`KeyBuilder`] is the hashing algorithm used for every key. In Stretto, the Cache will never store the real key.
//! The key will be processed by [`KeyBuilder`]. Stretto has two default built-in key builder,
//! one is [`TransparentKeyBuilder`], the other is [`DefaultKeyBuilder`]. If your key implements [`TransparentKey`] trait,
//! you can use [`TransparentKeyBuilder`] which is faster than [`DefaultKeyBuilder`]. Otherwise, you should use [`DefaultKeyBuilder`]
//! You can also write your own key builder for the Cache, by implementing [`KeyBuilder`] trait.
//!
//! Note that if you want 128bit hashes you should use the full `(u64, u64)`,
//! otherwise just fill the `u64` at the `0` position, and it will behave like
//! any 64bit hash.
//!
//! #### buffer_size
//!
//! `buffer_size` is the size of the insert buffers. The Dgraph's developers find that 32 * 1024 gives a good performance.
//!
//! If for some reason you see insert performance decreasing with lots of contention (you shouldn't),
//! try increasing this value in increments of 32 * 1024.
//! This is a fine-tuning mechanism and you probably won't have to touch this.
//!
//! #### metrics
//!
//! Metrics is true when you want real-time logging of a variety of stats.
//! The reason this is a CacheBuilder flag is because there's a 10% throughput performance overhead.
//!
//! #### ignore_internal_cost
//!
//! Set to true indicates to the cache that the cost of
//! internally storing the value should be ignored. This is useful when the
//! cost passed to set is not using bytes as units. Keep in mind that setting
//! this to true will increase the memory usage.
//!
//! #### cleanup_duration
//!
//! The Cache will cleanup the expired values every 500ms by default.
//!
//! #### update_validator
//!
//! By default, the Cache will always update the value if the value already exists in the cache.
//! [`UpdateValidator`] is a trait to support customized update policy (check if the value should be updated
//! if the value already exists in the cache).
//!
//! #### callback
//!
//! [`CacheCallback`] is for customize some extra operations on values when related event happens.
//!
//! #### coster
//!
//! [`Coster`] is a trait you can pass to the [`CacheBuilder`] in order to evaluate
//! item cost at runtime, and only for the [`insert`] calls that aren't dropped (this is
//! useful if calculating item cost is particularly expensive, and you don't want to
//! waste time on items that will be dropped anyways).
//!
//! To signal to Stretto that you'd like to use this [`Coster`] trait:
//!
//! 1. Set the [`Coster`] field to your own [`Coster`] implementation.
//! 2. When calling [`insert`] for new items or item updates, use a cost of 0.
//!
//! #### hasher
//!
//! The hasher for the Cache, default is SipHasher.
//!
//! [Github-url]: https://github.com/al8n/stretto/
//! [CI-url]: https://github.com/al8n/stretto/actions/workflows/ci.yml
//! [doc-url]: https://docs.rs/stretto
//! [crates-url]: https://crates.io/crates/stretto
//! [codecov-url]: https://app.codecov.io/gh/al8n/stretto/
//! [license-url]: https://opensource.org/licenses/Apache-2.0
//! [license-apache-url]: https://opensource.org/licenses/Apache-2.0
//! [license-mit-url]: https://opensource.org/licenses/MIT
//! [rustc-image]: https://img.shields.io/badge/rustc-1.52.0--nightly%2B-orange.svg?style=for-the-badge&logo=Rust
//! [rustc-url]: https://github.com/rust-lang/rust/blob/master/RELEASES.md
//! [`KeyBuilder`]: trait.KeyBuilder.html
//! [`TransparentKey`]: trait.TransparentKey.html
//! [`TransparentKeyBuilder`]: struct.TransparentKeyBuilder.html
//! [`DefaultKeyBuilder`]: struct.DefaultKeyBuilder.html
//! [`CacheBuilder`]: struct.CacheBuilder.html
//! [`AsyncCacheBuilder`]: struct.AsyncCacheBuilder.html
//! [`insert`]: struct.Cache.html#method.insert
//! [`UpdateValidator`]: trait.UpdateValidator.html
//! [`CacheCallback`]: trait.CacheCallback.html
//! [`Coster`]: trait.Coster.html
//! [`Cache`]: struct.Cache.html
//! [`AsyncCache`]: struct.AsyncCache.html
#![deny(missing_docs)]
#![allow(clippy::too_many_arguments, clippy::type_complexity)]
#![cfg_attr(docsrs, feature(doc_cfg))]
#![cfg_attr(docsrs, allow(unused_attributes))]
mod bbloom;
mod cache;
mod error;
mod histogram;
mod metrics;
/// This package includes multiple probabalistic data structures needed for
/// admission/eviction metadata. Most are Counting Bloom Filter variations, but
/// a caching-specific feature that is also required is a "freshness" mechanism,
/// which basically serves as a "lifetime" process. This freshness mechanism
/// was described in the original TinyLFU paper [1], but other mechanisms may
/// be better suited for certain data distributions.
///
/// [1]: https://arxiv.org/abs/1512.00727
#[allow(dead_code)]
mod policy;
mod sketch;
mod store;
mod ttl;
pub(crate) mod utils;
extern crate atomic;
#[cfg(feature = "log")]
extern crate log;
#[cfg(feature = "serde")]
extern crate serde;
#[cfg(feature = "async")]
#[cfg_attr(docsrs, doc(cfg(feature = "async")))]
pub(crate) mod axync {
pub(crate) use async_channel::{bounded, unbounded, Receiver, RecvError, Sender};
pub(crate) use futures::select;
pub(crate) type WaitGroup = wg::AsyncWaitGroup;
pub(crate) fn stop_channel() -> (Sender<()>, Receiver<()>) {
bounded(1)
}
}
#[cfg(feature = "async")]
#[cfg_attr(docsrs, doc(cfg(feature = "async")))]
pub use cache::{AsyncCache, AsyncCacheBuilder};
#[cfg(feature = "sync")]
#[cfg_attr(docsrs, doc(cfg(feature = "sync")))]
pub(crate) mod sync {
pub(crate) use crossbeam_channel::{bounded, select, unbounded, Receiver, Sender};
pub(crate) use std::thread::{spawn, JoinHandle};
pub(crate) use std::time::Instant;
pub(crate) type UnboundedSender<T> = Sender<T>;
pub(crate) type UnboundedReceiver<T> = Receiver<T>;
pub(crate) type WaitGroup = wg::WaitGroup;
pub(crate) fn stop_channel() -> (Sender<()>, Receiver<()>) {
bounded(0)
}
}
#[cfg(feature = "sync")]
#[cfg_attr(docsrs, doc(cfg(feature = "sync")))]
pub use cache::{Cache, CacheBuilder};
pub use error::CacheError;
pub use histogram::Histogram;
pub use metrics::{MetricType, Metrics};
pub use utils::{ValueRef, ValueRefMut};
use crate::ttl::Time;
use seahash::SeaHasher;
use std::fmt::{Debug, Formatter};
use std::hash::{BuildHasher, BuildHasherDefault, Hash, Hasher};
use std::marker::PhantomData;
/// Item is the parameter when Cache reject, evict value,
pub struct Item<V> {
/// the value of the entry
pub val: Option<V>,
/// the index of the entry(created by [`KeyBuilder`])
///
/// [`KeyBuilder`]: struct.KeyBuilder.html
pub index: u64,
/// the conflict of the entry(created by [`KeyBuilder`])
///
/// [`KeyBuilder`]: struct.KeyBuilder.html
pub conflict: u64,
/// the cost when store the entry in Cache.
pub cost: i64,
/// exp contains the ttl information.
pub exp: Time,
}
impl<V> Item<V> {
pub(crate) fn new(index: u64, conflict: u64, cost: i64, val: Option<V>, ttl: Time) -> Self {
Self {
val,
index,
conflict,
cost,
exp: ttl,
}
}
}
impl<V: Clone> Clone for Item<V> {
fn clone(&self) -> Self {
Self {
val: self.val.clone(),
index: self.index,
conflict: self.conflict,
cost: self.cost,
exp: self.exp,
}
}
}
impl<V: Copy> Copy for Item<V> {}
impl<V: Debug> Debug for Item<V> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
f.debug_struct("Item")
.field("value", &self.val)
.field("cost", &self.cost)
.field("ttl", &self.exp)
.finish()
}
}
/// By default, the Cache will always update the value if the value already exists in the cache,
/// this trait is for you to check if the value should be updated.
pub trait UpdateValidator: Send + Sync + 'static {
/// Value
type Value: Send + Sync + 'static;
/// should_update is called when a value already exists in cache and is being updated.
fn should_update(&self, prev: &Self::Value, curr: &Self::Value) -> bool;
}
/// DefaultUpdateValidator is a noop update validator.
#[doc(hidden)]
pub struct DefaultUpdateValidator<V> {
_marker: PhantomData<fn(V)>,
}
impl<V: Send + Sync> Default for DefaultUpdateValidator<V> {
fn default() -> Self {
Self {
_marker: PhantomData::<fn(V)>,
}
}
}
impl<V: Send + Sync + 'static> UpdateValidator for DefaultUpdateValidator<V> {
type Value = V;
#[inline]
fn should_update(&self, _prev: &Self::Value, _curr: &Self::Value) -> bool {
true
}
}
/// CacheCallback is for customize some extra operations on values when related event happens.
pub trait CacheCallback: Send + Sync + 'static {
/// Value
type Value: Send + Sync + 'static;
/// on_exit is called whenever a value is removed from cache. This can be
/// used to do manual memory deallocation. Would also be called on eviction
/// and rejection of the value.
fn on_exit(&self, val: Option<Self::Value>);
/// on_evict is called for every eviction and passes the hashed key, value,
/// and cost to the function.
fn on_evict(&self, item: Item<Self::Value>) {
self.on_exit(item.val)
}
/// on_reject is called for every rejection done via the policy.
fn on_reject(&self, item: Item<Self::Value>) {
self.on_exit(item.val)
}
}
/// DefaultCacheCallback is a noop CacheCallback implementation.
#[derive(Clone, Debug)]
#[doc(hidden)]
pub struct DefaultCacheCallback<V> {
_marker: PhantomData<V>,
}
impl<V> Default for DefaultCacheCallback<V> {
fn default() -> Self {
Self {
_marker: Default::default(),
}
}
}
impl<V: Send + Sync + 'static> CacheCallback for DefaultCacheCallback<V> {
type Value = V;
fn on_exit(&self, _val: Option<Self::Value>) {}
}
/// Cost is a trait you can pass to the CacheBuilder in order to evaluate
/// item cost at runtime, and only for the `insert` calls that aren't dropped (this is
/// useful if calculating item cost is particularly expensive, and you don't want to
/// waste time on items that will be dropped anyways).
///
/// To signal to Stretto that you'd like to use this Coster trait:
///
/// 1. Set the Coster field to your own Coster implementation.
/// 2. When calling `insert` for new items or item updates, use a `cost` of 0.
pub trait Coster: Send + Sync + 'static {
/// Value
type Value: Send + Sync + 'static;
/// cost evaluates a value and outputs a corresponding cost. This function
/// is ran after insert is called for a new item or an item update with a cost
/// param of 0.
fn cost(&self, val: &Self::Value) -> i64;
}
/// DefaultCoster is a noop Coster implementation.
#[doc(hidden)]
pub struct DefaultCoster<V> {
_marker: PhantomData<fn(V)>,
}
impl<V> Default for DefaultCoster<V> {
fn default() -> Self {
Self {
_marker: Default::default(),
}
}
}
impl<V: Send + Sync + 'static> Coster for DefaultCoster<V> {
type Value = V;
#[inline]
fn cost(&self, _val: &V) -> i64 {
0
}
}
/// [`KeyBuilder`] is the hashing algorithm used for every key. In Stretto, the Cache will never store the real key.
/// The key will be processed by [`KeyBuilder`]. Stretto has two default built-in key builder,
/// one is [`TransparentKeyBuilder`], the other is [`DefaultKeyBuilder`]. If your key implements [`TransparentKey`] trait,
/// you can use [`TransparentKeyBuilder`] which is faster than [`DefaultKeyBuilder`]. Otherwise, you should use [`DefaultKeyBuilder`]
/// You can also write your own key builder for the Cache, by implementing [`KeyBuilder`] trait.
///
/// Note that if you want 128bit hashes you should use the full `(u64, u64)`,
/// otherwise just fill the `u64` at the `0` position, and it will behave like
/// any 64bit hash.
///
/// [`KeyBuilder`]: trait.KeyBuilder.html
/// [`TransparentKey`]: trait.TransparentKey.html
/// [`TransparentKeyBuilder`]: struct.TransparentKeyBuilder.html
/// [`DefaultKeyBuilder`]: struct.DefaultKeyBuilder.html
pub trait KeyBuilder {
/// Key
type Key: Hash + Eq + ?Sized;
/// `hash_index` is used to hash the key to u64
fn hash_index<Q>(&self, key: &Q) -> u64
where
Self::Key: core::borrow::Borrow<Q>,
Q: core::hash::Hash + Eq + ?Sized;
/// if you want a 128bit hashes, you should implement this method,
/// or leave this method return 0
fn hash_conflict<Q>(&self, key: &Q) -> u64
where
Self::Key: core::borrow::Borrow<Q>,
Q: core::hash::Hash + Eq + ?Sized,
{
let _ = key;
0
}
/// build the key to 128bit hashes.
fn build_key<Q>(&self, k: &Q) -> (u64, u64)
where
Self::Key: core::borrow::Borrow<Q>,
Q: core::hash::Hash + Eq + ?Sized,
{
(self.hash_index(k), self.hash_conflict(k))
}
}
/// DefaultKeyBuilder is a built-in `KeyBuilder` for the Cache.
///
/// If the key implements [`TransparentKey`] trait, use [`TransparentKeyBuilder`].
/// u8, u16, u32, u64, i8, i16, i32, i64, bool implement [`TransparentKey`] by default.
///
/// See [`KeyBuilder`] if you want to write a customized [`KeyBuilder`].
///
/// [`KeyBuilder`]: trait.KeyBuilder.html
/// [`TransparentKey`]: trait.TransparentKey.html
/// [`TransparentKeyBuilder`]: struct.TransparentKeyBuilder.html
pub struct DefaultKeyBuilder<K> {
xx: xxhash_rust::xxh64::Xxh64Builder,
sea: BuildHasherDefault<SeaHasher>,
_marker: PhantomData<K>,
}
impl<K> Debug for DefaultKeyBuilder<K> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
f.debug_struct("DefaultKeyBuilder").finish()
}
}
impl<K> Default for DefaultKeyBuilder<K> {
fn default() -> Self {
use rand::{thread_rng, Rng};
let mut rng = thread_rng();
let seed = rng.gen::<u64>();
Self {
xx: xxhash_rust::xxh64::Xxh64Builder::new(seed),
sea: Default::default(),
_marker: Default::default(),
}
}
}
impl<K: Hash + Eq> KeyBuilder for DefaultKeyBuilder<K> {
type Key = K;
#[inline]
fn hash_index<Q>(&self, key: &Q) -> u64
where
Self::Key: core::borrow::Borrow<Q>,
Q: core::hash::Hash + Eq + ?Sized,
{
let mut s = self.sea.build_hasher();
key.hash(&mut s);
s.finish()
}
#[inline]
fn hash_conflict<Q>(&self, key: &Q) -> u64
where
Self::Key: core::borrow::Borrow<Q>,
Q: core::hash::Hash + Eq + ?Sized,
{
let mut x = self.xx.build_hasher();
key.hash(&mut x);
x.finish()
}
}
#[derive(Default, Copy, Clone, Eq, PartialEq, Debug)]
#[repr(transparent)]
struct TransparentHasher {
data: u64,
}
impl Hasher for TransparentHasher {
#[inline]
fn finish(&self) -> u64 {
self.data
}
#[inline]
fn write(&mut self, bytes: &[u8]) {
let mut data = [0u8; core::mem::size_of::<u64>()];
if bytes.len() > core::mem::size_of::<u64>() {
data.copy_from_slice(&bytes[..core::mem::size_of::<u64>()]);
} else {
data[..bytes.len()].copy_from_slice(bytes);
}
self.data = u64::from_ne_bytes(data);
}
fn write_u8(&mut self, i: u8) {
self.data = i as u64;
}
fn write_u16(&mut self, i: u16) {
self.data = i as u64;
}
fn write_u32(&mut self, i: u32) {
self.data = i as u64;
}
fn write_u64(&mut self, i: u64) {
self.data = i;
}
fn write_u128(&mut self, i: u128) {
self.data = i as u64;
}
fn write_usize(&mut self, i: usize) {
self.data = i as u64;
}
fn write_i8(&mut self, i: i8) {
self.data = i as u64;
}
fn write_i16(&mut self, i: i16) {
self.data = i as u64;
}
fn write_i32(&mut self, i: i32) {
self.data = i as u64;
}
fn write_i64(&mut self, i: i64) {
self.data = i as u64;
}
fn write_i128(&mut self, i: i128) {
self.data = i as u64;
}
fn write_isize(&mut self, i: isize) {
self.data = i as u64;
}
}
/// Implement this trait for the key, if you want to use [`TransparentKeyBuilder`] as the [`KeyBuilder`]
/// for the [`Cache`].
///
/// u8, u16, u32, u64, i8, i16, i32, i64, bool implement TransparentKey by default.
///
/// [`TransparentKeyBuilder`]: struct.TransparentKeyBuilder.html
/// [`KeyBuilder`]: trait.KeyBuilder.html
/// [`Cache`]: struct.Cache.html
pub trait TransparentKey: Hash + Eq {
/// convert self to `u64`
fn to_u64(&self) -> u64;
}
/// TransparentKeyBuilder converts key to `u64`.
/// If the key does not implement the trait [`TransparentKey`], please use [`DefaultKeyBuilder`]
/// or write a custom key builder.
///
/// [`DefaultKeyBuilder`]: struct.DefaultKeyBuilder.html
/// [`TransparentKey`]: trait.TransparentKey.html
#[derive(Default, Clone, Eq, PartialEq, Debug)]
pub struct TransparentKeyBuilder<K: TransparentKey> {
// hasher: TransparentHasher<K>,
_marker: PhantomData<K>,
}
impl<K: TransparentKey> KeyBuilder for TransparentKeyBuilder<K> {
type Key = K;
#[inline]
fn hash_index<Q>(&self, key: &Q) -> u64
where
Self::Key: core::borrow::Borrow<Q>,
Q: core::hash::Hash + Eq + ?Sized,
{
let mut hasher = TransparentHasher { data: 0 };
key.hash(&mut hasher);
hasher.finish()
}
#[inline]
fn hash_conflict<Q>(&self, _key: &Q) -> u64
where
Self::Key: core::borrow::Borrow<Q>,
Q: core::hash::Hash + Eq + ?Sized,
{
0
}
}
macro_rules! impl_transparent_key {
($($t:ty),*) => {
$(
impl TransparentKey for $t {
fn to_u64(&self) -> u64 {
*self as u64
}
}
)*
}
}
impl_transparent_key! {
bool,
u8,
u16,
u32,
u64,
usize,
i8,
i16,
i32,
i64,
isize
}