Struct StringInterner 

pub struct StringInterner { /* private fields */ }

String interner for symbol name deduplication.

StringInterner stores strings efficiently by maintaining a single copy of each unique string. When the same string is interned multiple times, the same StringId is returned.

Reference Counting

Each interned string has an associated reference count. This enables garbage collection of unused strings during compaction phases.

Thread Safety

The interner uses Arc<str> for string storage, making it safe to share resolved strings across threads. However, the interner itself requires external synchronization (e.g., RwLock) for concurrent access.

Example

let mut interner = StringInterner::new();

let id1 = interner.intern("foo");
let id2 = interner.intern("foo");
assert_eq!(id1, id2); // Same string → same ID

let resolved = interner.resolve(id1).unwrap();
assert_eq!(&*resolved, "foo");

Implementations

impl StringInterner

pub fn new() -> Self

Creates a new empty string interner.

pub fn with_capacity(capacity: usize) -> Self

Creates a new interner with the specified capacity.

pub fn with_max_ids(max_ids: u32) -> Self

Creates a new interner with a hard limit on the number of IDs.

This constructor is designed for testing error paths. It allows deterministic testing of InternError::CapacityExhausted handling without requiring billions of strings.

Arguments

• max_ids - Maximum number of unique strings that can be interned. Once this limit is reached, intern() will return InternError::CapacityExhausted.

Example

// Create an interner that can only hold 3 strings
let mut interner = StringInterner::with_max_ids(3);

interner.intern("a").unwrap(); // OK
interner.intern("b").unwrap(); // OK
interner.intern("c").unwrap(); // OK
assert!(interner.intern("d").is_err()); // CapacityExhausted

pub fn len(&self) -> usize

Returns the number of interned strings (excluding INVALID slot).

Panics

Panics if the lookup is stale (bulk slots written without rebuild).

pub fn is_empty(&self) -> bool

Returns true if no strings are interned.

Panics

Panics if the lookup is stale (bulk slots written without rebuild).

pub fn intern(&mut self, s: &str) -> Result<StringId, InternError>

Interns a string and returns its StringId.

If the string was already interned, returns the existing ID and increments its reference count. Otherwise, allocates a new ID.

Errors

Returns InternError::CapacityExhausted if the interner has exhausted all available IDs (> 2^32 - 2 strings), or if max_ids is set and the limit has been reached.

Panics

Panics if the lookup is stale and has not been rebuilt with build_dedup_table().

pub fn intern_without_ref(&mut self, s: &str) -> Result<StringId, InternError>

Interns a string and returns its StringId without incrementing ref count.

This is useful when the string is being stored in a structure that will manage its own lifetime (e.g., node entry).

Errors

Returns InternError::CapacityExhausted if the interner has exhausted all available IDs (> 2^32 - 2 strings), or if max_ids is set and the limit has been reached.

Panics

Panics if the lookup is stale and has not been rebuilt with build_dedup_table().

pub fn resolve(&self, id: StringId) -> Option<Arc<str>>

Resolves a StringId to its string value.

Returns None if the ID is invalid or has been recycled.

pub fn ref_count(&self, id: StringId) -> u32

Returns the reference count for a string.

Returns 0 if the ID is invalid or has been recycled.

pub fn inc_ref(&mut self, id: StringId) -> Option<u32>

Increments the reference count for a string.

Returns the new count, or None if the ID is invalid.

pub fn dec_ref(&mut self, id: StringId) -> Option<u32>

Decrements the reference count for a string.

Returns the new count, or None if the ID is invalid. Note: This does NOT automatically recycle the string when count reaches 0. Use recycle_unreferenced() during compaction for that.

pub fn recycle_unreferenced(&mut self) -> usize

Recycles all strings with zero reference count.

Returns the number of strings recycled. This should be called during compaction phases.

Panics

Panics if the lookup is stale (bulk slots written without rebuild).

pub fn contains(&self, s: &str) -> bool

Checks if a string is interned.

Panics

Panics if the lookup is stale (bulk slots written without rebuild).

pub fn get(&self, s: &str) -> Option<StringId>

Gets the StringId for a string if it’s already interned.

Unlike intern(), this does not create a new entry or modify ref counts.

Panics

Panics if the lookup is stale (bulk slots written without rebuild).

pub fn iter(&self) -> impl Iterator<Item = (StringId, &Arc<str>)>

Returns an iterator over all interned strings with their IDs.

pub fn clear(&mut self)

Clears all interned strings.

Resets the interner to empty state, including clearing the lookup_stale flag (lookup is trivially consistent when empty).

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more strings.

pub fn alloc_range(&mut self, count: u32) -> Result<u32, InternError>

Pre-allocates count string slots for bulk parallel commit.

The new slots are initialized with None (no string) and ref_count = 0. Returns the start index of the allocated range. The caller can then fill slots start..start+count via StringInterner::bulk_slices_mut.

This method does not touch the free_list — it always appends to the end of the strings and ref_counts vectors. This is intentional: during parallel commit, each file gets a contiguous, non-overlapping range.

Errors

Returns InternError::CapacityExhausted if the allocation would exceed the LOCAL_TAG_BIT boundary (2^31 indices reserved for global IDs).

Arguments

• count - Number of slots to pre-allocate. If 0, this is a no-op returning the current length.

pub fn bulk_slices_mut( &mut self, start: u32, count: u32, ) -> (&mut [Option<Arc<str>>], &mut [u32])

Returns mutable sub-slices into the strings and ref_counts arrays for the range start..start+count.

This enables parallel file commit workers to write directly into their pre-allocated range without contention. The caller is responsible for ensuring no overlapping ranges are accessed concurrently.

Defensively marks the lookup as stale when count > 0, since the returned slices allow direct mutation of string slots without updating the lookup HashMap.

Panics

Panics if start + count exceeds the current vector length.

pub fn build_dedup_table(&mut self) -> HashMap<StringId, StringId>

Scans all string slots and deduplicates identical strings.

After parallel commit, multiple file workers may have inserted the same string into different slots. This method:

1. Iterates slots 1..N in index order (deterministic).
2. For the first occurrence of each string value, that slot becomes the canonical entry.
3. For duplicate occurrences, their ref_count is accumulated into the canonical slot, and the duplicate slot is cleared (None, ref_count = 0).
4. The lookup HashMap is rebuilt from canonical entries only.

Returns a remap table mapping duplicate StringId to canonical StringId. Canonical entries are not included in the returned map.

pub fn truncate_to(&mut self, saved_len: usize)

Truncates the strings and ref_counts vectors to saved_len.

This rolls back a failed bulk allocation by removing all slots at index saved_len and beyond. The lookup HashMap is not modified (the caller is responsible for ensuring no lookup entries point to the truncated region).

Panics

Panics if saved_len is 0 (would remove the sentinel slot).

pub fn string_count_raw(&self) -> usize

Returns the total number of string slots including the sentinel at index 0.

This is the raw vector length, not the number of interned strings. Useful for saving/restoring allocation state.

pub fn is_lookup_stale(&self) -> bool

Returns whether the lookup HashMap is stale (bulk slots written without a build_dedup_table() rebuild).

This is primarily useful for testing and diagnostics.

pub fn stats(&self) -> InternerStats

Returns statistics about the interner.

Safe to call even when lookup is stale — uses slot-based counting instead of lookup length.

Trait Implementations

impl Clone for StringInterner

fn clone(&self) -> StringInterner

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for StringInterner

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

Formats the value using the given formatter.

impl Default for StringInterner

fn default() -> Self

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for StringInterner

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Display for StringInterner

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

Formats the value using the given formatter.

impl Serialize for StringInterner

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

where __S: Serializer,

Serialize this value into the given Serde serializer.