Struct KeyInterner 

pub struct KeyInterner<K, S = FxBuildHasher> { /* private fields */ }

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 within a single generation; see KeyInterner::generation for detecting reuse across KeyInterner::clear cycles.

Type Parameters

• K: Key type, must be Eq + Hash + Clone for intern
• S: Hash builder; defaults to FxBuildHasher. Swap for a DoS-resistant builder (e.g. std::collections::hash_map::RandomState) when keys may come from untrusted input — see the module-level security notes.

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

impl<K> KeyInterner<K, FxBuildHasher>

pub fn new() -> Self

Creates an empty interner with the default FxBuildHasher.

Security

The default hasher is not DoS-resistant. If keys may be attacker-controlled, prefer KeyInterner::with_hasher with a randomised builder such as std::collections::hash_map::RandomState. See the module-level security notes.

Example

use cachekit::ds::KeyInterner;

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

pub fn with_capacity(capacity: usize) -> Self

where K: Eq + Hash,

Creates an interner with pre-allocated capacity, using the default FxBuildHasher.

The requested capacity is silently clamped to KeyInterner::MAX_CAPACITY and, beyond that, the allocator is allowed to refuse the reservation without aborting. This keeps configuration-derived capacities from crashing the process. Use try_with_capacity to observe both the clamp and the allocator failure explicitly.

Example

use cachekit::ds::KeyInterner;

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

pub fn try_with_capacity(capacity: usize) -> Result<Self, InternerError>

where K: Eq + Hash,

Fallible version of with_capacity: returns an error instead of clamping if capacity > MAX_CAPACITY, and surfaces allocator failures rather than aborting.

Errors

• InternerError::CapacityExceeded if capacity > MAX_CAPACITY.
• InternerError::AllocationFailed if the underlying allocator refuses the reservation.

impl<K, S> KeyInterner<K, S>

pub const MAX_CAPACITY: usize

Maximum number of unique keys a single KeyInterner will hold.

Chosen to bound per-instance memory at a clearly “not-usually-legit” ceiling while leaving several orders of magnitude of headroom over realistic cache-key cardinalities. Even at the cap, the interner occupies at least MAX_CAPACITY * (size_of::<(K, u64)>() + size_of::<K>()) bytes — for K = String the hidden heap-allocated payloads dominate this figure, so callers exposing KeyInterner to untrusted input should impose a much smaller admission-control cap of their own.

Derived from isize::MAX as usize / 64 to stay well below the allocation limit on the target platform.

pub fn with_hasher(hash_builder: S) -> Self

Creates an empty interner with the given hash builder.

Example

use cachekit::ds::KeyInterner;
use std::collections::hash_map::RandomState;

// DoS-resistant hasher for untrusted keys.
let interner: KeyInterner<String, RandomState> =
    KeyInterner::with_hasher(RandomState::new());
assert!(interner.is_empty());

pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self

where K: Eq + Hash, S: BuildHasher,

Creates an interner with pre-allocated capacity and a custom hash builder.

capacity is silently clamped to KeyInterner::MAX_CAPACITY, and any further allocator refusal is absorbed rather than aborting the process. Use try_with_capacity_and_hasher to observe the clamp or allocator failure.

pub fn try_with_capacity_and_hasher( capacity: usize, hash_builder: S, ) -> Result<Self, InternerError>

where K: Eq + Hash, S: BuildHasher,

Fallible version of with_capacity_and_hasher.

Errors

• InternerError::CapacityExceeded if capacity > MAX_CAPACITY.
• InternerError::AllocationFailed if the allocator refuses.

pub fn hasher(&self) -> &S

Returns a reference to the hash builder used by this interner.

pub fn generation(&self) -> u64

Returns the current generation counter.

The counter starts at 0 and is incremented on every clear / clear_shrink. Callers that persist handles across a possible clear can store (generation, handle) pairs and reject handles whose recorded generation no longer matches the live value — this is the documented mitigation for the clear-cycle handle-reuse hazard described in the module-level security notes.

Example

use cachekit::ds::KeyInterner;

let mut interner: KeyInterner<String> = KeyInterner::new();
let gen_before = interner.generation();
let h = interner.intern(&"k".to_owned());

// Later, after a clear_shrink elsewhere:
interner.clear_shrink();
let gen_after = interner.generation();
assert_ne!(gen_before, gen_after);

// The stored handle is stale.
let stored = (gen_before, h);
assert_ne!(stored.0, gen_after);

impl<K, S> KeyInterner<K, S>

where K: Eq + Hash + Clone, S: BuildHasher,

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.

Panics

Panics if the interner is already holding MAX_CAPACITY unique keys, or if the allocator refuses to grow the backing storage. Use try_intern for a non-panicking variant — callers that process untrusted keys should always prefer try_intern, since this method is a trivial DoS vector otherwise.

Exception safety

intern is designed so that, assuming K’s Hash / Eq / Clone impls do not panic, a panic from HashMap::insert cannot leave the interner with len(keys) > len(index) — which would otherwise cause a subsequent intern(&same_key) to mint a second handle for the same key and permanently strand the first one. In detail:

1. Capacity is reserved via try_reserve up front, so neither the Vec::push nor the HashMap::insert below can fail for allocator reasons.
2. The key is then inserted into index first. If K::hash or K::eq panics (a pathological impl), the keys vector is untouched, so the interner retains its invariant.
3. Only after the insert returns do we push onto keys.

Panicking Clone / Drop impls for K can still violate the invariant; the standard-library HashMap makes no stronger guarantee either.

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

pub fn try_intern(&mut self, key: &K) -> Result<u64, InternerError>

Fallible counterpart to intern.

Returns the existing handle if key has already been interned; otherwise assigns the next sequential handle and stores the key. Returns InternerError::CapacityExceeded if the interner is already at MAX_CAPACITY, and InternerError::AllocationFailed if the allocator refuses growth. Preferred over intern whenever keys can come from untrusted input.

Example

use cachekit::ds::KeyInterner;

let mut interner: KeyInterner<String> = KeyInterner::new();
let h = interner.try_intern(&"k".to_owned()).unwrap();
assert_eq!(h, 0);
// Idempotent just like `intern`.
assert_eq!(interner.try_intern(&"k".to_owned()).unwrap(), h);

impl<K, S> KeyInterner<K, S>

where K: Eq + Hash, S: BuildHasher,

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);

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);

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();

pub fn clear_shrink(&mut self)

Clears all interned keys and shrinks internal storage.

After calling this, all previously returned handles become invalid and the generation counter is bumped. Callers holding handles across the clear should compare generation() to detect staleness — see the module-level security notes.

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

impl<K, S> KeyInterner<K, S>

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

Resolves a handle to its original key.

Returns None if the handle is out of bounds.

Note: handles are not capability-safe across clear cycles or across distinct KeyInterner instances. See the module-level security notes.

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

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);

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());

pub fn clear(&mut self)

Clears all interned keys and bumps generation.

After calling this, all previously returned handles become invalid. The internal allocations are retained; use clear_shrink to also release spare capacity.

Example

use cachekit::ds::KeyInterner;

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

let gen_before = interner.generation();
interner.clear();
assert!(interner.is_empty());
assert_ne!(gen_before, interner.generation());

pub fn approx_bytes(&self) -> usize

Returns an approximate memory footprint in bytes.

Uses saturating arithmetic internally so that pathological capacities cannot under-report the footprint via usize overflow. Under-reporting here would let an attacker bypass any admission- control check that consults approx_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);

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")]);

Trait Implementations

impl<K, S> Clone for KeyInterner<K, S>

where K: Clone + Eq + Hash, S: BuildHasher + Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K, S> Debug for KeyInterner<K, S>

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

Formats the value using the given formatter.

impl<K, S> Default for KeyInterner<K, S>

where S: Default,

fn default() -> Self

Returns the “default value” for a type.