Struct KeyInterner

Source

pub struct KeyInterner<K> { /* private fields */ }

Expand description

Monotonic key interner that assigns a u64 handle to each unique key.

Maps external keys to compact u64 handles for efficient storage and lookup. Handles are assigned sequentially starting from 0 and never reused.

§Type Parameters

K: Key type, must be Eq + Hash + Clone

§Example

use cachekit::ds::KeyInterner;

let mut interner = KeyInterner::new();

// Intern returns a handle
let handle = interner.intern(&"my_key");
assert_eq!(handle, 0);  // First key gets handle 0

// Same key returns same handle
assert_eq!(interner.intern(&"my_key"), 0);

// Different key gets next handle
assert_eq!(interner.intern(&"other_key"), 1);

// Resolve handle back to key
assert_eq!(interner.resolve(0), Some(&"my_key"));

§Use Case: Frequency Tracking

use cachekit::ds::KeyInterner;
use std::collections::HashMap;

let mut interner = KeyInterner::new();
let mut freq: HashMap<u64, u32> = HashMap::new();

// Track access frequency using handles (cheaper than cloning keys)
fn access(interner: &mut KeyInterner<String>, freq: &mut HashMap<u64, u32>, key: &str) {
    let handle = interner.intern(&key.to_owned());
    *freq.entry(handle).or_insert(0) += 1;
}

access(&mut interner, &mut freq, "page_a");
access(&mut interner, &mut freq, "page_a");
access(&mut interner, &mut freq, "page_b");

let handle_a = interner.get_handle_borrowed("page_a").unwrap();
assert_eq!(freq[&handle_a], 2);

Implementations§

Source §

impl<K> KeyInterner<K>

Source

pub fn new() -> Self

Creates an empty interner.

§Example

use cachekit::ds::KeyInterner;

let interner: KeyInterner<String> = KeyInterner::new();
assert!(interner.is_empty());

Source

pub fn with_capacity(capacity: usize) -> Self

Creates an interner with pre-allocated capacity.

Pre-allocates space for capacity keys to avoid rehashing during growth.

§Example

use cachekit::ds::KeyInterner;

let interner: KeyInterner<String> = KeyInterner::with_capacity(1000);
assert!(interner.is_empty());

Source §

impl<K> KeyInterner<K>
where K: Eq + Hash + Clone,

Source

pub fn intern(&mut self, key: &K) -> u64

Returns the handle for key, inserting it if missing.

If the key is already interned, returns the existing handle. Otherwise, assigns the next sequential handle and stores the key.

§Example

use cachekit::ds::KeyInterner;

let mut interner = KeyInterner::new();

// First key gets handle 0
let h1 = interner.intern(&"key_a");
assert_eq!(h1, 0);

// Second key gets handle 1
let h2 = interner.intern(&"key_b");
assert_eq!(h2, 1);

// Same key returns same handle (no new entry)
let h1_again = interner.intern(&"key_a");
assert_eq!(h1_again, 0);
assert_eq!(interner.len(), 2);  // Still only 2 keys

Source §

impl<K> KeyInterner<K>
where K: Eq + Hash,

Source

pub fn get_handle(&self, key: &K) -> Option<u64>

Returns the handle for key if it exists.

Does not insert the key if missing.

§Example

use cachekit::ds::KeyInterner;

let mut interner = KeyInterner::new();
let handle = interner.intern(&"existing");

assert_eq!(interner.get_handle(&"existing"), Some(handle));
assert_eq!(interner.get_handle(&"missing"), None);

Source

pub fn get_handle_borrowed<Q>(&self, key: &Q) -> Option<u64>
where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Returns the handle for a borrowed form of K if it exists.

This enables allocation-free lookups for owned key types like String by querying with &str.

§Example

use cachekit::ds::KeyInterner;

let mut interner: KeyInterner<String> = KeyInterner::new();
interner.intern(&"hello".to_string());

// Lookup by &str without allocating a String
assert_eq!(interner.get_handle_borrowed("hello"), Some(0));
assert_eq!(interner.get_handle_borrowed("missing"), None);

Source

pub fn shrink_to_fit(&mut self)

Shrinks internal storage to fit current length.

§Example

use cachekit::ds::KeyInterner;

let mut interner = KeyInterner::new();
for i in 0..100u32 {
    interner.intern(&i);
}
interner.clear();
interner.shrink_to_fit();

Source

pub fn clear_shrink(&mut self)

Clears all interned keys and shrinks internal storage.

After calling this, all previously returned handles become invalid.

§Example

use cachekit::ds::KeyInterner;

let mut interner = KeyInterner::new();
let handle = interner.intern(&"key");
assert_eq!(interner.resolve(handle), Some(&"key"));

interner.clear_shrink();
assert!(interner.is_empty());
assert_eq!(interner.resolve(handle), None);  // Handle now invalid

Source §

impl<K> KeyInterner<K>

Source

pub fn resolve(&self, handle: u64) -> Option<&K>

Resolves a handle to its original key.

Returns None if the handle is out of bounds.

§Example

use cachekit::ds::KeyInterner;

let mut interner = KeyInterner::new();
let handle = interner.intern(&"my_key");

assert_eq!(interner.resolve(handle), Some(&"my_key"));
assert_eq!(interner.resolve(999), None);  // Invalid handle

Source

pub fn len(&self) -> usize

Returns the number of interned keys.

§Example

use cachekit::ds::KeyInterner;

let mut interner = KeyInterner::new();
assert_eq!(interner.len(), 0);

interner.intern(&"a");
interner.intern(&"b");
assert_eq!(interner.len(), 2);

// Re-interning same key doesn't increase count
interner.intern(&"a");
assert_eq!(interner.len(), 2);

Source

pub fn is_empty(&self) -> bool

Returns true if no keys are interned.

§Example

use cachekit::ds::KeyInterner;

let mut interner: KeyInterner<&str> = KeyInterner::new();
assert!(interner.is_empty());

interner.intern(&"key");
assert!(!interner.is_empty());

Source

pub fn clear(&mut self)

Clears all interned keys.

After calling this, all previously returned handles become invalid.

§Example

use cachekit::ds::KeyInterner;

let mut interner = KeyInterner::new();
interner.intern(&"key");
assert!(!interner.is_empty());

interner.clear();
assert!(interner.is_empty());

Source

pub fn approx_bytes(&self) -> usize

Returns an approximate memory footprint in bytes.

§Example

use cachekit::ds::KeyInterner;

let mut interner: KeyInterner<String> = KeyInterner::new();
let base_bytes = interner.approx_bytes();

// Add some keys
for i in 0..100 {
    interner.intern(&format!("key_{}", i));
}

assert!(interner.approx_bytes() > base_bytes);

Source

pub fn iter(&self) -> impl Iterator<Item = (u64, &K)> + '_

Returns an iterator over (handle, key) pairs in insertion order.

§Example

use cachekit::ds::KeyInterner;

let mut interner = KeyInterner::new();
interner.intern(&"a");
interner.intern(&"b");

let pairs: Vec<_> = interner.iter().collect();
assert_eq!(pairs, vec![(0, &"a"), (1, &"b")]);