radix_immutable 0.1.0

use std::alloc::{GlobalAlloc, Layout, System};
use std::collections::HashMap;
use std::sync::atomic::{AtomicUsize, Ordering};

use radix_immutable::StringTrie;

/// A thin wrapper around System that counts bytes allocated.
struct TrackingAllocator;

static ALLOCATED: AtomicUsize = AtomicUsize::new(0);
static FREED: AtomicUsize = AtomicUsize::new(0);

unsafe impl GlobalAlloc for TrackingAllocator {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        ALLOCATED.fetch_add(layout.size(), Ordering::Relaxed);
        unsafe { System.alloc(layout) }
    }

    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        FREED.fetch_add(layout.size(), Ordering::Relaxed);
        unsafe { System.dealloc(ptr, layout) }
    }
}

#[global_allocator]
static ALLOC: TrackingAllocator = TrackingAllocator;

fn reset_counters() {
    ALLOCATED.store(0, Ordering::SeqCst);
    FREED.store(0, Ordering::SeqCst);
}

fn currently_allocated() -> usize {
    ALLOCATED.load(Ordering::SeqCst) - FREED.load(Ordering::SeqCst)
}

fn make_paths(n: usize) -> Vec<String> {
    let segments = ["api", "users", "posts", "comments", "auth", "admin", "static", "assets"];
    (0..n)
        .map(|i| {
            let depth = (i % 4) + 1;
            let mut path = String::from("/");
            for d in 0..depth {
                path.push_str(segments[(i + d) % segments.len()]);
                path.push('/');
            }
            path.push_str(&i.to_string());
            path
        })
        .collect()
}

#[test]
fn test_structural_sharing_memory_vs_hashmap() {
    let paths = make_paths(500);
    let num_versions = 10;

    // Build a base trie, then create N new versions by inserting unique keys.
    // Keep all versions alive to measure shared memory.
    let mut base_trie = StringTrie::<String, usize>::new();
    for (i, p) in paths.iter().enumerate() {
        base_trie = base_trie.insert(p.clone(), i);
    }

    reset_counters();
    let _trie_versions: Vec<_> = (0..num_versions)
        .map(|i| base_trie.insert(format!("/unique/version/{i}"), i))
        .collect();
    let trie_mem = currently_allocated();

    // Same thing with HashMap: clone + insert for each version
    let mut base_map = HashMap::new();
    for (i, p) in paths.iter().enumerate() {
        base_map.insert(p.clone(), i);
    }

    reset_counters();
    let _map_versions: Vec<_> = (0..num_versions)
        .map(|i| {
            let mut cloned = base_map.clone();
            cloned.insert(format!("/unique/version/{i}"), i);
            cloned
        })
        .collect();
    let hashmap_mem = currently_allocated();

    let ratio = hashmap_mem as f64 / trie_mem.max(1) as f64;

    eprintln!("--- Memory: {num_versions} versions from a 500-entry base ---");
    eprintln!("  Trie (structural sharing): {:.1} KB", trie_mem as f64 / 1024.0);
    eprintln!("  HashMap (full clones):     {:.1} KB", hashmap_mem as f64 / 1024.0);
    eprintln!("  Ratio:                     {ratio:.1}x less memory for trie");

    // The trie should use substantially less memory for N snapshots
    assert!(
        ratio > 5.0,
        "Expected trie to use much less memory than HashMap clones, but ratio was only {ratio:.1}x"
    );
}