Struct Ida 

pub struct Ida { /* private fields */ }

A thread-safe ID allocator for sparse ID spaces.

Ida (ID Allocator) manages a pool of unique integer IDs, implemented as a radix tree for memory efficiency. It’s particularly well-suited for scenarios where allocated IDs may be far apart (e.g., allocating IDs 5 and 5,000,000).

Thread Safety

All methods are thread-safe and can be safely shared across threads using Arc. The implementation uses a spinlock internally for synchronization.

Memory Efficiency

The radix tree structure ensures that only allocated regions of the ID space consume memory. Sparse allocations do not waste space on unallocated ranges.

Examples

Basic usage:

use ida_rs::Ida;

let ida = Ida::new();
let id1 = ida.alloc().unwrap();
let id2 = ida.alloc().unwrap();
ida.free(id1);
let id3 = ida.alloc().unwrap(); // Reuses id1

Multi-threaded usage:

use ida_rs::Ida;
use std::sync::Arc;
use std::thread;

let ida = Arc::new(Ida::new());
let mut handles = vec![];

for _ in 0..4 {
    let ida_clone = Arc::clone(&ida);
    let handle = thread::spawn(move || {
        ida_clone.alloc()
    });
    handles.push(handle);
}

for handle in handles {
    let id = handle.join().unwrap();
    println!("Allocated ID: {:?}", id);
}

Implementations

impl Ida

pub fn new() -> Self

Creates a new, empty ID allocator.

The allocator starts with no IDs allocated. The first call to alloc will return ID 0.

Examples

use ida_rs::Ida;

let ida = Ida::new();
assert_eq!(ida.alloc(), Some(0));

Examples found in repository

examples/real_world_test.rs (line 8)

fn main() {
    println!("Simulating a real-world scenario with multiple threads...");

    let allocator = Arc::new(Ida::new());
    let mut handles = vec![];

    // Spawn 5 threads. Each will try to allocate 3 IDs.
    for i in 0..5 {
        let allocator_clone = Arc::clone(&allocator);
        let handle = thread::spawn(move || {
            let mut allocated_ids = vec![];
            for _ in 0..3 {
                match allocator_clone.alloc() {
                    Some(id) => {
                        println!("Thread {i} allocated ID: {id}");
                        allocated_ids.push(id);
                    }
                    None => {
                        println!("Thread {i} failed to allocate an ID.");
                    }
                }
                // Simulate some work
                thread::sleep(std::time::Duration::from_millis(10));
            }
            allocated_ids
        });
        handles.push(handle);
    }

    // Wait for all threads to finish and collect the results
    let mut all_ids = vec![];
    for handle in handles {
        all_ids.extend(handle.join().unwrap());
    }

    println!("\nAll threads finished.");
    println!("Total IDs allocated: {}", all_ids.len());
    println!("Allocated IDs: {all_ids:?}");

    // Verify correctness: sort and check for duplicates
    all_ids.sort();
    let mut unique_ids = all_ids.clone();
    unique_ids.dedup();

    assert_eq!(
        all_ids.len(),
        unique_ids.len(),
        "Error: Duplicate IDs were allocated!"
    );

    println!("\nVerification successful: No duplicate IDs were issued.");
}

pub fn alloc(&self) -> Option<usize>

Allocates and returns the next available ID.

This method always returns the lowest available ID. If an ID has been freed, it will be reused before allocating higher IDs.

Returns

• Some(id) - The allocated ID (a usize value)
• None - If the allocator has exhausted the available ID space

Thread Safety

This method is thread-safe and can be called concurrently from multiple threads. Each call is guaranteed to return a unique ID.

Examples

use ida_rs::Ida;

let ida = Ida::new();

// Allocate IDs sequentially
let id1 = ida.alloc().unwrap();
let id2 = ida.alloc().unwrap();
assert_eq!(id1, 0);
assert_eq!(id2, 1);

// Free an ID and reallocate
ida.free(id1);
let id3 = ida.alloc().unwrap();
assert_eq!(id3, 0); // Reuses the freed ID

Examples found in repository

examples/real_world_test.rs (line 17)

fn main() {
    println!("Simulating a real-world scenario with multiple threads...");

    let allocator = Arc::new(Ida::new());
    let mut handles = vec![];

    // Spawn 5 threads. Each will try to allocate 3 IDs.
    for i in 0..5 {
        let allocator_clone = Arc::clone(&allocator);
        let handle = thread::spawn(move || {
            let mut allocated_ids = vec![];
            for _ in 0..3 {
                match allocator_clone.alloc() {
                    Some(id) => {
                        println!("Thread {i} allocated ID: {id}");
                        allocated_ids.push(id);
                    }
                    None => {
                        println!("Thread {i} failed to allocate an ID.");
                    }
                }
                // Simulate some work
                thread::sleep(std::time::Duration::from_millis(10));
            }
            allocated_ids
        });
        handles.push(handle);
    }

    // Wait for all threads to finish and collect the results
    let mut all_ids = vec![];
    for handle in handles {
        all_ids.extend(handle.join().unwrap());
    }

    println!("\nAll threads finished.");
    println!("Total IDs allocated: {}", all_ids.len());
    println!("Allocated IDs: {all_ids:?}");

    // Verify correctness: sort and check for duplicates
    all_ids.sort();
    let mut unique_ids = all_ids.clone();
    unique_ids.dedup();

    assert_eq!(
        all_ids.len(),
        unique_ids.len(),
        "Error: Duplicate IDs were allocated!"
    );

    println!("\nVerification successful: No duplicate IDs were issued.");
}

pub fn free(&self, id: usize)

Frees a previously allocated ID, making it available for reuse.

Once freed, the ID becomes available for future allocations. The next call to alloc will prefer reusing freed IDs before allocating new ones.

Parameters

• id - The ID to free. Must be a value that was previously returned by alloc.

Behavior

• Freeing an already-free ID is safe but has no effect
• Freeing an ID that was never allocated is safe but has no effect
• After freeing, the internal tree structure may be compacted to save memory

Thread Safety

This method is thread-safe and can be called concurrently from multiple threads.

Examples

use ida_rs::Ida;

let ida = Ida::new();
let id = ida.alloc().unwrap();

// Use the ID...

// Free it when done
ida.free(id);

// The ID can now be reallocated
let reused_id = ida.alloc().unwrap();
assert_eq!(id, reused_id);

pub fn is_allocated(&self, id: usize) -> bool

Checks if a given ID is currently allocated.

This method queries whether a specific ID has been allocated and not yet freed. It’s useful for debugging, validation, or tracking ID states.

Parameters

• id - The ID to check

Returns

• true - If the ID is currently allocated
• false - If the ID is free or has never been allocated

Thread Safety

This method is thread-safe and provides a consistent view at the time of the call. Note that in concurrent scenarios, the status may change immediately after this method returns.

Examples

use ida_rs::Ida;

let ida = Ida::new();

// Initially, no IDs are allocated
assert!(!ida.is_allocated(0));
assert!(!ida.is_allocated(100));

// Allocate an ID
let id = ida.alloc().unwrap();
assert_eq!(id, 0);

// Check allocation status
assert!(ida.is_allocated(0));
assert!(!ida.is_allocated(1));

// Free the ID
ida.free(0);
assert!(!ida.is_allocated(0));

Trait Implementations

impl Debug for Ida

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

Formats the value using the given formatter.

impl Default for Ida

fn default() -> Self

Creates a new ID allocator using the default configuration.

This is equivalent to calling Ida::new().

Examples

use ida_rs::Ida;

let ida = Ida::default();
assert_eq!(ida.alloc(), Some(0));