TinyUFO

https://docs.rs/TinyUFO/0.8.1
Admin
A lock-free, in-memory cache implementation utilizing TinyLFU as its admission policy and S3-FIFO...
Tokens:31,543
Snippets:296
Trust Score:9.1
Update:3 months ago
Show doc for...
Tokens:
Raw
### Example Searches

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=

Common search patterns that can be used with the data structures.

```text
std::vec
```

```text
u32 -> bool
```

```text
Option<T>, (T -> U) -> Option<U>
```

--------------------------------

### Rust Vec Insertion and Retrieval Example

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=std%3A%3Avec

Demonstrates inserting a `Bucket` struct into a `Compact` (presumably a Vec or similar collection) and retrieving its data. Shows how to handle cases where the key might not exist.

```rust
assert!(compact.get_map(&1, |_| ()).is_none());

        let bucket = Bucket {
            queue: crate::Location::new_small(),
            weight: 1,
            uses: Default::default(),
            data: 1,
        };
        compact.insert(1, bucket);

        assert_eq!(compact.get_map(&1, |v| v.data), Some(1));

        compact.remove(&1);
        assert!(compact.get_map(&1, |_| ()).is_none());
```

--------------------------------

### TinyUfo::new_compact

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.TinyUfo.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Creates a memory-efficient TinyUfo cache with a trade-off in `get()` performance.

```APIDOC
## TinyUfo::new_compact

### Description
Creates a new TinyUfo cache but with more memory efficient data structures. The trade-off is that the the get() is slower by a constant factor. The cache hit ratio could be higher as this type of TinyUFO allows to store more assets with the same memory.

### Signature
`pub fn new_compact(total_weight_limit: usize, estimated_size: usize) -> Self`
```

--------------------------------

### TinyLfu Methods

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=

Provides methods for interacting with the TinyLfu frequency estimator. Users can get current counts, increment counts, and initialize the estimator with different configurations.

```APIDOC
## TinyLfu Methods

### `get<T: Hash>(&self, key: T) -> u8`

Retrieves the current estimated frequency count for a given key.

- **key** (T): The key to query. Must implement the `Hash` trait.
- **Returns**: `u8` - The estimated frequency count.

### `incr<T: Hash>(&self, key: T) -> u8`

Increments the frequency count for a given key. This method also handles window-based aging of the estimator.

- **key** (T): The key to increment. Must implement the `Hash` trait.
- **Returns**: `u8` - The updated estimated frequency count.

### `new(cache_size: usize) -> Self`

Creates a new `TinyLfu` instance with optimal parameters for the given cache size.

- **cache_size** (usize): The desired cache size, used to determine estimator parameters.
- **Returns**: `Self` - A new `TinyLfu` instance.

### `new_compact(cache_size: usize) -> Self`

Creates a new `TinyLfu` instance with compact parameters for the given cache size.

- **cache_size** (usize): The desired cache size, used to determine estimator parameters.
- **Returns**: `Self` - A new `TinyLfu` instance.
```

--------------------------------

### TinyUfo Get with u32 Key and bool Value

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.TinyUfo.html?search=u32+-%3E+bool

Demonstrates calling the `get` method on `TinyUfo` where the key type is `u32` and the value type is `bool`.

```rust
tinyufo::TinyUfo::get
&TinyUfo<K, T>, &**K** -> Option<**T** >
where
u32 matches **K**
bool matches **T**
```

--------------------------------

### Rust Bucket Insertion and Retrieval Example

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

This snippet demonstrates inserting a 'Bucket' into a compact data structure, retrieving it using a closure, and then removing it. It highlights the use of `insert`, `get_map`, and `remove` methods.

```rust
        assert!(compact.get_map(&1, |_| ()).is_none());

        let bucket = Bucket {
            queue: crate::Location::new_small(),
            weight: 1,
            uses: Default::default(),
            data: 1,
        };
        compact.insert(1, bucket);

        assert_eq!(compact.get_map(&1, |v| v.data), Some(1));

        compact.remove(&1);
        assert!(compact.get_map(&1, |_| ()).is_none());
```

--------------------------------

### TinyUfo::new_compact

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.TinyUfo.html?search=

Creates a new, more memory-efficient TinyUfo cache with a potential trade-off in `get()` performance.

```APIDOC
## TinyUfo::new_compact

### Description
Creates a new TinyUfo cache but with more memory-efficient data structures. The trade-off is that the `get()` operation is slower by a constant factor. The cache hit ratio could be higher as this type of TinyUFO allows storing more assets with the same memory.

### Method
`new_compact(total_weight_limit: usize, estimated_size: usize) -> Self`

### Parameters
* `total_weight_limit` (usize) - The maximum total weight the cache can hold.
* `estimated_size` (usize) - The estimated size limit for the ghost queue.
```

--------------------------------

### TinyUfo::new_compact

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.TinyUfo.html

Creates a memory-efficient TinyUfo cache with a specified weight limit and estimated size. Note that `get()` operations are slower but cache hit ratios may be higher.

```APIDOC
## TinyUfo::new_compact

### Description
Create a new TinyUfo cache but with more memory efficient data structures. The trade-off is that the the get() is slower by a constant factor. The cache hit ratio could be higher as this type of TinyUFO allows to store more assets with the same memory.

### Method
`new_compact`

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Request Example
None

### Response
#### Success Response (Self)
- **Self** (TinyUfo<K, T>) - A new, memory-efficient instance of the TinyUfo cache.

### Response Example
None
```

--------------------------------

### Create New Compact TinyUfo Cache

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.TinyUfo.html?search=

Instantiates a memory-efficient TinyUfo cache. Offers higher cache hit ratios at the cost of slower get operations.

```rust
pub fn new_compact(total_weight_limit: usize, estimated_size: usize) -> Self
```

--------------------------------

### TinyLfu get Method

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=u32+-%3E+bool

Retrieves the estimated count for a given key from the TinyLfu cache.

```rust
pub fn get<T: Hash>(&self, key: T) -> u8 {
        self.estimator.get(key)
    }
```

--------------------------------

### Get and map an entry from Compact bucket

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=std%3A%3Avec

Retrieves an entry from the Compact bucket and applies a function to it, returning the result. Returns None if the key is not found.

```rust
pub fn get_map<V, F: FnOnce(Entry<Key, Bucket<T>>) -> V>(&self, key: &Key, f: F) -> Option<V> {
        let v = self.get(key);
        v.map(f)
    }
```

--------------------------------

### get

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/lib.rs.html

Retrieves the value associated with a given key from the cache. Returns Some(T) if the key exists, otherwise None.

```APIDOC
## get

### Description
Read the given key from the cache. Return Some(T) if the key exists.

### Method
GET (conceptual)

### Endpoint
N/A (SDK method)

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Request Example
```rust
let value = tiny_ufo.get(&key);
```

### Response
#### Success Response
- **Option<T>** - Some(T) if the key exists, None otherwise.

#### Response Example
```rust
Some(value)
```
```

--------------------------------

### TinyLfu Basic Functionality Test

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=std%3A%3Avec

Tests the basic get and incr operations of the TinyLfu cache, including initial values and increments.

```rust
    #[test]
    fn test_tiny_lfu() {
        let tiny = TinyLfu::new(1);
        assert_eq!(tiny.get(1), 0);
        assert_eq!(tiny.incr(1), 1);
        assert_eq!(tiny.incr(1), 2);
        assert_eq!(tiny.get(1), 2);

        // Might have hash collisions for the others, need to
        // get() before can assert on the incr() value.
        let two = tiny.get(2);
        assert_eq!(tiny.incr(2), two + 1);
        assert_eq!(tiny.incr(2), two + 2);
        assert_eq!(tiny.get(2), two + 2);

        let three = tiny.get(3);
        assert_eq!(tiny.incr(3), three + 1);
        assert_eq!(tiny.incr(3), three + 2);
        assert_eq!(tiny.incr(3), three + 3);
        assert_eq!(tiny.incr(3), three + 4);

        // 8 incr(), now resets on next incr
        // can only assert they are greater than or equal
        // to the incr() we do per key.

        assert!(tiny.incr(3) >= 3); // had 4, reset to 2, added another.
        assert!(tiny.incr(1) >= 2); // had 2, reset to 1, added another.
        assert!(tiny.incr(2) >= 2); // had 2, reset to 1, added another.
    }
```

--------------------------------

### TinyLfu Methods

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=std%3A%3Avec

Provides methods for interacting with the TinyLfu cache, including getting item frequencies and incrementing them. The `incr` method also handles window-based aging of the estimator.

```APIDOC
## TinyLfu

### Description
A bare-minimum LFU cache with CM-Sketch for frequency estimation.

### Methods

#### `get<T: Hash>(&self, key: T) -> u8`

Retrieves the estimated frequency of a given key.

- **key** (`T` where `T: Hash`) - The key to look up.
- **Returns**: (`u8`) The estimated frequency of the key.

#### `incr<T: Hash>(&self, key: T) -> u8`

Increments the estimated frequency of a given key. This method also manages the sliding window for the estimator, resetting and aging it when the window limit is reached.

- **key** (`T` where `T: Hash`) - The key to increment.
- **Returns**: (`u8`) The new estimated frequency of the key.

#### `new(cache_size: usize) -> Self`

Creates a new `TinyLfu` instance with optimal CM-Sketch parameters for the given cache size.

- **cache_size** (`usize`) - The desired cache size.
- **Returns**: (`Self`) A new `TinyLfu` instance.

#### `new_compact(cache_size: usize) -> Self`

Creates a new `TinyLfu` instance with compact CM-Sketch parameters for the given cache size.

- **cache_size** (`usize`) - The desired cache size.
- **Returns**: (`Self`) A new `TinyLfu` instance.

#### `new_seeded(cache_size: usize) -> Self` (Test only)

Creates a new `TinyLfu` instance with seeded optimal CM-Sketch parameters for the given cache size. This is intended for testing purposes.

- **cache_size** (`usize`) - The desired cache size.
- **Returns**: (`Self`) A new `TinyLfu` instance.

#### `new_compact_seeded(cache_size: usize) -> Self` (Test only)

Creates a new `TinyLfu` instance with seeded compact CM-Sketch parameters for the given cache size. This is intended for testing purposes.

- **cache_size** (`usize`) - The desired cache size.
- **Returns**: (`Self`) A new `TinyLfu` instance.
```

--------------------------------

### TinyLfu Basic Functionality Test

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=u32+-%3E+bool

Tests the basic get and incr operations of the TinyLfu cache, including handling of potential hash collisions and window resets.

```rust
#[test]
    fn test_tiny_lfu() {
        let tiny = TinyLfu::new(1);
        assert_eq!(tiny.get(1), 0);
        assert_eq!(tiny.incr(1), 1);
        assert_eq!(tiny.incr(1), 2);
        assert_eq!(tiny.get(1), 2);

        // Might have hash collisions for the others, need to
        // get() before can assert on the incr() value.
        let two = tiny.get(2);
        assert_eq!(tiny.incr(2), two + 1);
        assert_eq!(tiny.incr(2), two + 2);
        assert_eq!(tiny.get(2), two + 2);

        let three = tiny.get(3);
        assert_eq!(tiny.incr(3), three + 1);
        assert_eq!(tiny.incr(3), three + 2);
        assert_eq!(tiny.incr(3), three + 3);
        assert_eq!(tiny.incr(3), three + 4);

        // 8 incr(), now resets on next incr
        // can only assert they are greater than or equal
        // to the incr() we do per key.

        assert!(tiny.incr(3) >= 3); // had 4, reset to 2, added another.
        assert!(tiny.incr(1) >= 2); // had 2, reset to 1, added another.
        assert!(tiny.incr(2) >= 2); // had 2, reset to 1, added another.
    }
```

--------------------------------

### Get and map from generic Buckets

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=std%3A%3Avec

Retrieves an entry from the `Buckets` instance by key and applies a mapping function. Handles the different `get_map` signatures of `Compact` and `Fast`.

```rust
pub fn get_map<V, F: FnOnce(&Bucket<T>) -> V>(&self, key: &Key, f: F) -> Option<V> {
        match self {
            Self::Compact(c) => c.get_map(key, |v| f(v.value())),
            Self::Fast(c) => c.get_map(key, f),
        }
    }
```

--------------------------------

### Get Key

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/lib.rs.html?search=

Retrieves the value associated with a given key from the cache. Returns Some(T) if the key exists, otherwise None.

```APIDOC
## get

### Description
Retrieves the value associated with a given key from the cache. Returns Some(T) if the key exists, otherwise None.

### Method
GET (conceptual)

### Endpoint
N/A (SDK method)

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Request Example
```rust
let value = tiny_ufo.get(&key);
```

### Response
#### Success Response
- **Option<T>** - Some(T) if the key exists, None otherwise.

#### Response Example
```rust
Some(value)
// or
None
```
```

--------------------------------

### Get an entry from Compact bucket

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=std%3A%3Avec

Retrieves an entry from the Compact bucket based on the key. The shard is determined by the key's hash modulo the number of shards.

```rust
pub fn get(&self, key: &Key) -> Option<Entry<'_, Key, Bucket<T>>> {
        let shard = *key as usize % self.0.len();
        self.0[shard].get(key)
    }
```

--------------------------------

### Get and map from Fast bucket

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=std%3A%3Avec

Retrieves a value from the Fast bucket using a key and applies a mapping function. This method pins the HashMap for safe concurrent access.

```rust
pub fn get_map<V, F: FnOnce(&Bucket<T>) -> V>(&self, key: &Key, f: F) -> Option<V> {
        let pinned = self.0.pin();
        let v = pinned.get(key);
        v.map(f)
    }
```

--------------------------------

### Creating and Using Compact Buckets

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html

Demonstrates the creation of a compact bucket, insertion of data, retrieval using a map function, and removal of an element. Asserts the state of the bucket at various stages.

```rust
let mut compact = Buckets::new_compact(10, 2);

assert!(compact.get_map(&1, |_| ()).is_none());

let bucket = Bucket {
    queue: crate::Location::new_small(),
    weight: 1,
    uses: Default::default(),
    data: 1,
};
compact.insert(1, bucket);

assert_eq!(compact.get_map(&1, |v| v.data), Some(1));

compact.remove(&1);
assert!(compact.get_map(&1, |_| ()).is_none());
```

--------------------------------

### Create and Use Fast Hash Map

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=

Demonstrates creating a new Fast hash map with a specified capacity, inserting a bucket, retrieving it using a closure, and then removing it.

```rust
// Concurrent hash map, fast but use more memory
pub struct Fast<T>(HashMap<Key, Bucket<T>, RandomState>);

impl<T: Send + Sync> Fast<T> {
    pub fn new(total_items: usize) -> Self {
        Self(HashMap::with_capacity_and_hasher(
            total_items,
            RandomState::new(),
        ))
    }

    pub fn get_map<V, F: FnOnce(&Bucket<T>) -> V>(&self, key: &Key, f: F) -> Option<V> {
        let pinned = self.0.pin();
        let v = pinned.get(key);
        v.map(f)
    }

    fn insert(&self, key: Key, value: Bucket<T>) -> Option<()> {
        let pinned = self.0.pin();
        pinned.insert(key, value).map(|_| ())
    }

    fn remove(&self, key: &Key) {
        let pinned = self.0.pin();
        pinned.remove(key);
    }
}

#[cfg(test)]
mod tests {
    use super::super::Bucket;
    use super::Fast;

    #[test]
    fn test_fast() {
        let fast = Fast::new(10);

        // Attempt to get a non-existent key
        assert!(fast.get_map(&1, |_| ()).is_none());

        let bucket = Bucket {
            queue: crate::Location::new_small(),
            weight: 1,
            uses: Default::default(),
            data: 1,
        };
        fast.insert(1, bucket);

        // Retrieve the inserted bucket
        assert_eq!(fast.get_map(&1, |v| v.data), Some(1));

        fast.remove(&1);
        // Verify removal
        assert!(fast.get_map(&1, |_| ()).is_none());
    }
}
```

--------------------------------

### Create and Use Compact Skip Map

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=

Demonstrates creating a new Compact skip map with specified total items and items per shard, inserting a bucket, retrieving it, and then removing it.

```rust
use super::{Bucket, Key};
use ahash::RandomState;
use crossbeam_skiplist::{map::Entry, SkipMap};
use flurry::HashMap;

/// N-shard skip list. Memory efficient, constant time lookup on average, but a bit slower
/// than hash map
pub struct Compact<T>(Box<[SkipMap<Key, Bucket<T>>]>);

impl<T: Send + 'static> Compact<T> {
    /// Create a new [Compact]
    pub fn new(total_items: usize, items_per_shard: usize) -> Self {
        assert!(items_per_shard > 0);

        let shards = std::cmp::max(total_items / items_per_shard, 1);
        let mut shard_array = vec![];
        for _ in 0..shards {
            shard_array.push(SkipMap::new());
        }
        Self(shard_array.into_boxed_slice())
    }

    pub fn get(&self, key: &Key) -> Option<Entry<'_, Key, Bucket<T>>> {
        let shard = *key as usize % self.0.len();
        self.0[shard].get(key)
    }

    pub fn get_map<V, F: FnOnce(Entry<Key, Bucket<T>>) -> V>(&self, key: &Key, f: F) -> Option<V> {
        let v = self.get(key);
        v.map(f)
    }

    fn insert(&self, key: Key, value: Bucket<T>) -> Option<()> {
        let shard = key as usize % self.0.len();
        let removed = self.0[shard].remove(&key);
        self.0[shard].insert(key, value);
        removed.map(|_| ())
    }

    fn remove(&self, key: &Key) {
        let shard = *key as usize % self.0.len();
        (&self.0)[shard].remove(key);
    }
}

#[cfg(test)]
mod tests {
    use super::super::Bucket;
    use super::Compact;

    #[test]
    fn test_compact() {
        let compact = Compact::new(10, 2);

        // Attempt to get a non-existent key
        assert!(compact.get_map(&1, |entry| entry.value().data).is_none());

        let bucket = Bucket {
            queue: crate::Location::new_small(),
            weight: 1,
            uses: Default::default(),
            data: 1,
        };
        compact.insert(1, bucket);

        // Retrieve the inserted bucket
        assert_eq!(compact.get_map(&1, |entry| entry.value().data), Some(1));

        compact.remove(&1);
        // Verify removal
        assert!(compact.get_map(&1, |entry| entry.value().data).is_none());
    }
}
```

--------------------------------

### Bucket Insertion and Retrieval

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=

Demonstrates how to create a Bucket, insert it into a Compact structure, retrieve its data, and remove it. Asserts are used to verify the state after each operation.

```rust
let bucket = Bucket {
            queue: crate::Location::new_small(),
            weight: 1,
            uses: Default::default(),
            data: 1,
        };
        compact.insert(1, bucket);

        assert_eq!(compact.get_map(&1, |v| v.data), Some(1));

        compact.remove(&1);
        assert!(compact.get_map(&1, |_| ()).is_none());
```

--------------------------------

### Create a new Compact bucket

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=std%3A%3Avec

Initializes a new Compact bucket with a specified total capacity and items per shard. Ensures at least one shard is created.

```rust
pub fn new(total_items: usize, items_per_shard: usize) -> Self {
        assert!(items_per_shard > 0);

        let shards = std::cmp::max(total_items / items_per_shard, 1);
        let mut shard_array = vec![];
        for _ in 0..shards {
            shard_array.push(SkipMap::new());
        }
        Self(shard_array.into_boxed_slice())
    }
```

--------------------------------

### Insert and Retrieve Bucket Data

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=u32+-%3E+bool

Demonstrates inserting a bucket with data and then retrieving it using its key. Asserts that the data is correctly retrieved and that the bucket is removed.

```rust
let mut compact = crate::Compact::<u32, Bucket>::new();

        let bucket = Bucket {
            queue: crate::Location::new_small(),
            weight: 1,
            uses: Default::default(),
            data: 1,
        };
        compact.insert(1, bucket);

        assert_eq!(compact.get_map(&1, |v| v.data), Some(1));

        compact.remove(&1);
        assert!(compact.get_map(&1, |_| ()).is_none());
```

--------------------------------

### TinyLfu::new_compact Constructor

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Creates a new `TinyLfu` instance using compact CM-Sketch parameters. The window limit is heuristically set to 8 times the cache size.

```rust
pub fn new_compact(cache_size: usize) -> Self {
    Self {
        estimator: Estimator::compact(cache_size),
        window_counter: Default::default(),
        // 8x: just a heuristic to balance the memory usage and accuracy
        window_limit: cache_size * 8,
    }
}
```

--------------------------------

### deref_mut Method

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.KV.html

Dereferences a pointer to get a mutable reference to the object. This is an unsafe operation and part of the Pointable trait.

```rust
unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T
```

--------------------------------

### Create a new Estimator with optimal parameters

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=std%3A%3Avec

Initializes an Estimator with parameters calculated for optimal performance based on the expected number of items.

```rust
fn optimal(items: usize) -> Self {
    let (slots, hashes) = Self::optimal_paras(items);
    Self::new(hashes, slots, RandomState::new)
}
```

--------------------------------

### deref Method

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.KV.html

Dereferences a pointer to get an immutable reference to the object. This is an unsafe operation and part of the Pointable trait.

```rust
unsafe fn deref<'a>(ptr: usize) -> &'a T
```

--------------------------------

### type_id Method

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.KV.html

Gets the TypeId of the current type. This is part of the Any trait implementation and is used for runtime type identification.

```rust
fn type_id(&self) -> TypeId
```

--------------------------------

### Get Data from TinyUfo Cache

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.TinyUfo.html?search=

Retrieves data associated with a given key from the cache. Returns Some(T) if the key exists, otherwise None.

```rust
pub fn get(&self, key: &K) -> Option<T>
```

--------------------------------

### TinyLfu::new Constructor

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Creates a new `TinyLfu` instance with optimal CM-Sketch parameters for the given cache size. The window limit is heuristically set to 8 times the cache size.

```rust
pub fn new(cache_size: usize) -> Self {
    Self {
        estimator: Estimator::optimal(cache_size),
        window_counter: Default::default(),
        // 8x: just a heuristic to balance the memory usage and accuracy
        window_limit: cache_size * 8,
    }
}
```

--------------------------------

### Create a seeded compact Estimator for testing

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=std%3A%3Avec

Initializes a compact Estimator with fixed seeds for reproducible hashing, used in testing scenarios where memory is constrained.

```rust
fn seeded_compact(items: usize) -> Self {
    let (slots, hashes) = Self::optimal_paras(items / 100);
    Self::new(hashes, slots, || RandomState::with_seeds(2, 3, 4, 5))
}
```

--------------------------------

### Get estimated frequency of a key

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=std%3A%3Avec

Retrieves the estimated frequency of a given key by finding the minimum value among its corresponding counters.

```rust
pub fn get<T: Hash>(&self, key: T) -> u8 {
    let mut min = u8::MAX;
    for (slot, hasher) in self.estimator.iter() {
        let hash = hasher.hash_one(&key) as usize;
        let counter = &slot[hash % slot.len()];
        let current = counter.load(Ordering::Relaxed);
        min = std::cmp::min(min, current);
    }
    min
}
```

--------------------------------

### Get Item from TinyUFO Cache

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/lib.rs.html?search=

Retrieves an item from the cache using its key. Returns `Some(T)` if the key exists, otherwise `None`. The key is hashed before lookup.

```rust
pub fn get(&self, key: &K) -> Option<T> {
        let key = self.random_status.hash_one(key);
        self.buckets.get_map(&key, |p| {
            p.uses.inc_uses();
            p.data.clone()
        })
    }
```

--------------------------------

### init Method

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.KV.html

Initializes an object with a given initializer. This is an unsafe operation and part of the Pointable trait.

```rust
unsafe fn init(init: <T as Pointable>::Init) -> usize
```

--------------------------------

### Create a compact Estimator

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=std%3A%3Avec

Initializes a compact Estimator, suitable for scenarios where memory usage is a concern, by reducing the number of slots.

```rust
fn compact(items: usize) -> Self {
    let (slots, hashes) = Self::optimal_paras(items / 100);
    Self::new(hashes, slots, RandomState::new)
}
```

--------------------------------

### TinyUfo::new

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.TinyUfo.html

Creates a new TinyUfo cache with a specified total weight limit and estimated size for the ghost queue.

```APIDOC
## TinyUfo::new

### Description
Create a new TinyUfo cache with the given weight limit and the given size limit of the ghost queue.

### Method
`new`

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Request Example
None

### Response
#### Success Response (Self)
- **Self** (TinyUfo<K, T>) - A new instance of the TinyUfo cache.

### Response Example
None
```

--------------------------------

### TinyUfo Initialization

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/lib.rs.html

Initializes a new TinyUfo cache with specified capacity and number of buckets. This is the constructor for the cache.

```rust
TinyUfo {
            queues,
            buckets: Buckets::new_compact(estimated_size, 32),
            random_status: RandomState::new(),
            _k: PhantomData,
        }
```

--------------------------------

### TinyLfu new_compact_seeded Constructor (Test Only)

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=u32+-%3E+bool

Creates a new TinyLfu cache with a seeded and compact CM-Sketch estimator, intended for testing purposes.

```rust
pub fn new_compact_seeded(cache_size: usize) -> Self {
        Self {
            estimator: Estimator::seeded_compact(cache_size),
            window_counter: Default::default(),
            // 8x: just a heuristic to balance the memory usage and accuracy
            window_limit: cache_size * 8,
        }
    }
```

--------------------------------

### TinyLfu new_compact Constructor

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=u32+-%3E+bool

Creates a new TinyLfu cache with a compact CM-Sketch estimator configuration.

```rust
pub fn new_compact(cache_size: usize) -> Self {
        Self {
            estimator: Estimator::compact(cache_size),
            window_counter: Default::default(),
            // 8x: just a heuristic to balance the memory usage and accuracy
            window_limit: cache_size * 8,
        }
    }
```

--------------------------------

### TinyUfo::new

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.TinyUfo.html?search=

Creates a new TinyUfo cache with specified weight and size limits for the ghost queue.

```APIDOC
## TinyUfo::new

### Description
Creates a new TinyUfo cache with the given weight limit and the given size limit of the ghost queue.

### Method
`new(total_weight_limit: usize, estimated_size: usize) -> Self`

### Parameters
* `total_weight_limit` (usize) - The maximum total weight the cache can hold.
* `estimated_size` (usize) - The estimated size limit for the ghost queue.
```

--------------------------------

### Increment and get minimum count

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=u32+-%3E+bool

Increments the count for a given key and returns the minimum count across all hash functions. Handles atomic increments to prevent overflow.

```rust
pub fn incr<T: Hash>(&self, key: T) -> u8 {
        let mut min = u8::MAX;
        for (slot, hasher) in self.estimator.iter() {
            let hash = hasher.hash_one(&key) as usize;
            let counter = &slot[hash % slot.len()];
            let (_current, new) = incr_no_overflow(counter);
            min = std::cmp::min(min, new);
        }
        min
    }
```

--------------------------------

### TinyUfo::new

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.TinyUfo.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Creates a new TinyUfo cache with specified weight and size limits for the ghost queue.

```APIDOC
## TinyUfo::new

### Description
Creates a new TinyUfo cache with the given weight limit and the given size limit of the ghost queue.

### Signature
`pub fn new(total_weight_limit: usize, estimated_size: usize) -> Self`
```

--------------------------------

### Create a new Fast bucket

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=std%3A%3Avec

Initializes a new Fast bucket (concurrent HashMap) with a specified capacity and a RandomState hasher.

```rust
pub fn new(total_items: usize) -> Self {
        Self(HashMap::with_capacity_and_hasher(
            total_items,
            RandomState::new(),
        ))
    }
```

--------------------------------

### Get estimated frequency of a key

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=u32+-%3E+bool

Retrieves the estimated frequency of a given key by finding the minimum count across all hash functions. Uses relaxed ordering for atomic loads.

```rust
pub fn get<T: Hash>(&self, key: T) -> u8 {
        let mut min = u8::MAX;
        for (slot, hasher) in self.estimator.iter() {
            let hash = hasher.hash_one(&key) as usize;
            let counter = &slot[hash % slot.len()];
            let current = counter.load(Ordering::Relaxed);
            min = std::cmp::min(min, current);
        }
        min
    }
```

--------------------------------

### Compact SkipMap Implementation

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Offers a memory-efficient concurrent storage solution using a sharded SkipMap.

```APIDOC
## Compact SkipMap Implementation

### Description

Provides a memory-efficient concurrent storage solution using a sharded SkipMap. This implementation offers constant time lookup on average but is slower than a HashMap.

### Methods

- `new(total_items: usize, items_per_shard: usize) -> Self`
  Creates a new `Compact` SkipMap with a specified total capacity and items per shard. The number of shards is determined by `total_items / items_per_shard`, with a minimum of one shard.

- `get(&self, key: &Key) -> Option<Entry<'_, Key, Bucket<T>>>`
  Retrieves an entry for the given key from the appropriate shard. Returns `Some(Entry)` if the key is found, `None` otherwise.

- `get_map<V, F: FnOnce(Entry<Key, Bucket<T>>) -> V>(&self, key: &Key, f: F) -> Option<V>`
  Retrieves an entry for the given key and applies a function `f` to it. Returns `Some(V)` if the key exists, `None` otherwise.

- `insert(&self, key: Key, value: Bucket<T>) -> Option<()>`
  Inserts a key-value pair into the SkipMap. If a value already exists for the key, it is removed before the new value is inserted. Returns `Some(())` if a value was removed, `None` otherwise.

- `remove(&self, key: &Key)`
  Removes a key-value pair from the SkipMap based on the provided key.
```

--------------------------------

### T TryInto<U> Implementation

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.Bucket.html?search=std%3A%3Avec

Illustrates the blanket implementation of `TryInto<U>` for `T` where `U` implements `TryFrom<T>`. The `try_into` function attempts the conversion.

```rust
impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

type Error = <U as TryFrom<T>>::Error

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
```

--------------------------------

### TinyLFU Admission Algorithm

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/lib.rs.html

Implements the TinyLFU admission algorithm by comparing the frequency of an incoming item with the frequency of an evicted item. The more popular item is admitted to the cache.

```Rust
let evicted_freq = self.estimator.get(evicted_first.key);
if evicted_freq > new_freq {
    // put it back
    let first = evicted.pop().expect("just check non-empty");
    // return the put value
    evicted.push(KV { key, data, weight });
    (first.key, first.data, first.weight)
} else {
    (key, data, weight)
}
```

--------------------------------

### Get queue status from Buckets

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=u32+-%3E+bool

A test helper function to retrieve the queue status for a given key from the `Buckets` instance. It maps the bucket's queue to a boolean indicating if it's the main queue.

```rust
pub fn get_queue(&self, key: &Key) -> Option<bool> {
        self.get_map(key, |v| v.queue.is_main())
    }
```

--------------------------------

### TinyUFO Cache Admission Logic

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/lib.rs.html?search=

Demonstrates the initial step of admitting a new item into the TinyUFO cache. It increments the frequency count in the TinyLFU estimator for the given key.

```rust
157        let new_freq = self.estimator.incr(key);

```

--------------------------------

### TinyLfu::new

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html

Creates a new TinyLfu estimator with optimal parameters based on the provided cache size.

```APIDOC
## TinyLfu::new

### Description
Creates a new TinyLfu estimator with optimal parameters based on the provided cache size.

### Method
`new(cache_size: usize) -> Self`

### Parameters
- **cache_size** (`usize`) - The size of the cache for which the estimator is being configured.

### Returns
- `Self` - A new instance of TinyLfu.
```

--------------------------------

### Increment count for a key and get minimum updated value

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=std%3A%3Avec

Increments the counter for a given key across all hash functions and returns the minimum updated value. Handles potential overflow by capping at u8::MAX.

```rust
pub fn incr<T: Hash>(&self, key: T) -> u8 {
    let mut min = u8::MAX;
    for (slot, hasher) in self.estimator.iter() {
        let hash = hasher.hash_one(&key) as usize;
        let counter = &slot[hash % slot.len()];
        let (_current, new) = incr_no_overflow(counter);
        min = std::cmp::min(min, new);
    }
    min
}
```

--------------------------------

### Test Item Removal from Cache

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/lib.rs.html?search=

Tests the functionality of removing specific items from the cache using the `remove` method. It verifies that removed items are no longer accessible via `get` and that the cache state is maintained correctly, including handling evictions after removal.

```rust
    #[test]
    fn test_remove() {
        let mut cache = TinyUfo::new(5, 5);
        cache.random_status = RandomState::with_seeds(2, 3, 4, 5);

        cache.put(1, 1, 1);
        cache.put(2, 2, 2);
        cache.put(3, 3, 2);

        assert_eq!(cache.remove(&1), Some(1));
        assert_eq!(cache.remove(&3), Some(3));
        assert_eq!(cache.get(&1), None);
        assert_eq!(cache.get(&3), None);

        // Verify empty keys get evicted when cache fills up
        // Fill cache to trigger eviction
        cache.put(5, 5, 2);
        cache.put(6, 6, 2);
        cache.put(7, 7, 2);

        // The removed items (1, 3) should be naturally evicted now
        // and new items should be in cache
        assert_eq!(cache.get(&1), None);
        assert_eq!(cache.get(&3), None);
        assert!(cache.get(&5).is_some() || cache.get(&6).is_some() || cache.get(&7).is_some());

        // Test weights after eviction cycles
        let total_weight =
            cache.queues.small_weight.load(SeqCst) + cache.queues.main_weight.load(SeqCst);
        assert!(total_weight <= 5); // Should not exceed limit
    }
```

--------------------------------

### TinyLfu new Constructor

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=u32+-%3E+bool

Creates a new TinyLfu cache with an optimal CM-Sketch estimator configuration based on the cache size.

```rust
pub fn new(cache_size: usize) -> Self {
        Self {
            estimator: Estimator::optimal(cache_size),
            window_counter: Default::default(),
            // 8x: just a heuristic to balance the memory usage and accuracy
            window_limit: cache_size * 8,
        }
    }
```

--------------------------------

### T TryFrom<U> Implementation

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.Bucket.html?search=std%3A%3Avec

Shows the blanket implementation of `TryFrom<U>` for `T` where `U` implements `Into<T>`. The `try_from` function attempts the conversion.

```rust
impl<T, U> TryFrom<U> for T
where U: Into<T>,

type Error = Infallible

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
```

--------------------------------

### Create new Compact Buckets instance

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=std%3A%3Avec

Creates a new `Buckets` instance using the `Compact` (SkipMap) implementation with specified total items and items per shard.

```rust
pub fn new_compact(items: usize, items_per_shard: usize) -> Self {
        Self::Compact(Compact::new(items, items_per_shard))
    }
```

--------------------------------

### Create New TinyUfo Cache

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.TinyUfo.html?search=

Instantiates a new TinyUfo cache with specified weight and size limits.

```rust
pub fn new(total_weight_limit: usize, estimated_size: usize) -> Self
```

--------------------------------

### FiFoQueues Admit Method

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/lib.rs.html

Handles the admission of a new key-value pair into the cache. It uses the TinyLFU estimator to track frequency and decides on admission based on cache policies.

```Rust
fn admit(
    &self,
    key: Key,
    data: T,
    weight: u16,
    ignore_lfu: bool,
    buckets: &Buckets<T>,
) -> Vec<KV<T>> {
    // Note that we only use TinyLFU during cache admission but not cache read.
    // So effectively we mostly sketch the popularity of less popular assets.
    // In this way the sketch is a bit more accurate on these assets.
    // Also we don't need another separated window cache to address the sparse burst issue as
    // this sketch doesn't favor very popular assets much.
    let new_freq = self.estimator.incr(key);

```

--------------------------------

### CloneToUninit Trait Implementation (Nightly)

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.KV.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

An experimental nightly-only API for cloning data into uninitialized memory.

```rust
impl<T> CloneToUninit for T
where
    T: Clone,
{
    unsafe fn clone_to_uninit(&self, dest: *mut u8) {
        // ... implementation details ...
    }
}
```

--------------------------------

### TinyLfu::new_compact_seeded

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Creates a new, compact TinyLfu estimator with seeded optimal parameters for a given cache size. Primarily for testing purposes.

```APIDOC
## TinyLfu::new_compact_seeded

### Description
Initializes a new, compact `TinyLfu` instance using seeded parameters, optimized for the specified cache size. This version is intended for testing and prioritizes memory efficiency.

### Method
`new_compact_seeded`

### Signature
`#[cfg(test)] pub fn new_compact_seeded(cache_size: usize) -> Self`

### Parameters
- **cache_size**: `usize` - The target size of the cache for which the estimator is being configured.

### Returns
- `Self` - A new, compact `TinyLfu` instance with seeded parameters.
```

--------------------------------

### Test Fast Bucket Implementation

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html

Unit test for the Fast bucket implementation, verifying insertion, retrieval, and removal of data.

```rust
    #[test]
    fn test_fast() {
        let fast = Buckets::new_fast(10);

        assert!(fast.get_map(&1, |_| ()).is_none());

        let bucket = Bucket {
            queue: crate::Location::new_small(),
            weight: 1,
            uses: Default::default(),
            data: 1,
        };
        fast.insert(1, bucket);

        assert_eq!(fast.get_map(&1, |v| v.data), Some(1));

        fast.remove(&1);
        assert!(fast.get_map(&1, |_| ()).is_none());
    }
```

--------------------------------

### TinyLfu::new_compact

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html

Creates a new, more compact TinyLfu estimator with optimal parameters based on the provided cache size.

```APIDOC
## TinyLfu::new_compact

### Description
Creates a new, more compact TinyLfu estimator with optimal parameters based on the provided cache size.

### Method
`new_compact(cache_size: usize) -> Self`

### Parameters
- **cache_size** (`usize`) - The size of the cache for which the estimator is being configured.

### Returns
- `Self` - A new instance of a compact TinyLfu.
```

--------------------------------

### Create new Fast Buckets instance

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=std%3A%3Avec

Creates a new `Buckets` instance using the `Fast` (HashMap) implementation with a specified initial capacity.

```rust
pub fn new_fast(items: usize) -> Self {
        Self::Fast(Box::new(Fast::new(items)))
    }
```

--------------------------------

### clone_to_uninit Method (Nightly)

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.KV.html

Nightly-only experimental API for performing copy-assignment to uninitialized memory. Use with caution.

```rust
unsafe fn clone_to_uninit(&self, dest: *mut u8)
```

--------------------------------

### T From<T> Implementation

Source: https://docs.rs/TinyUFO/0.8.1/tinyufo/struct.Bucket.html?search=std%3A%3Avec

Illustrates the blanket implementation of `From<T>` for `T`. The `from` function simply returns the argument unchanged.

```rust
impl<T> From<T> for T

fn from(t: T) -> T {
    t
}
```

--------------------------------

### Create a seeded Estimator for testing

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=std%3A%3Avec

Initializes an Estimator with fixed seeds for reproducible hashing, primarily used for testing purposes.

```rust
fn seeded(items: usize) -> Self {
    let (slots, hashes) = Self::optimal_paras(items);
    Self::new(hashes, slots, || RandomState::with_seeds(2, 3, 4, 5))
}
```

--------------------------------

### Test Eviction from Small to Main Queue

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/lib.rs.html?search=

Tests a scenario where items are initially in the 'small' queue, but after being accessed, they are expected to move to the 'main' queue during subsequent evictions. Asserts the queue status before eviction.

```rust
#[test]
    fn test_evict_from_small_to_main() {
        let mut cache = TinyUfo::new(5, 5);
        cache.random_status = RandomState::with_seeds(2, 3, 4, 5);
        cache.queues.estimator = TinyLfu::new_seeded(5);

        cache.put(1, 1, 1);
        cache.put(2, 2, 2);
        cache.put(3, 3, 2);
        // cache full now

        cache.get(&1);
        cache.get(&1); // 1 will be moved to main during next eviction

        assert_eq!(cache.peek_queue(1), Some(SMALL));
    }
```

--------------------------------

### TinyLfu new_seeded Constructor (Test Only)

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/estimation.rs.html?search=u32+-%3E+bool

Creates a new TinyLfu cache with a seeded CM-Sketch estimator, intended for testing purposes.

```rust
pub fn new_seeded(cache_size: usize) -> Self {
        Self {
            estimator: Estimator::seeded(cache_size),
            window_counter: Default::default(),
            // 8x: just a heuristic to balance the memory usage and accuracy
            window_limit: cache_size * 8,
        }
    }
```

--------------------------------

### Fast HashMap Implementation

Source: https://docs.rs/TinyUFO/0.8.1/src/tinyufo/buckets.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Provides a fast, memory-intensive concurrent storage solution using a HashMap.

```APIDOC
## Fast HashMap Implementation

### Description

Provides a fast, memory-intensive concurrent storage solution using a HashMap.

### Methods

- `new(total_items: usize) -> Self`
  Creates a new `Fast` HashMap with a specified capacity.

- `get_map<V, F: FnOnce(&Bucket<T>) -> V>(&self, key: &Key, f: F) -> Option<V>`
  Retrieves a value associated with a key and applies a function `f` to it. Returns `Some(V)` if the key exists, `None` otherwise.

- `insert(&self, key: Key, value: Bucket<T>) -> Option<()>`
  Inserts a key-value pair into the HashMap. Returns `Some(())` if the insertion was successful (overwriting an existing value), or `None` if the key did not exist previously (though the current implementation always returns `Some(())` after insertion).

- `remove(&self, key: &Key)`
  Removes a key-value pair from the HashMap based on the provided key.
```
Tokens:
Raw