grafeo-core 0.5.41

//! Hash index for O(1) point lookups.
//!
//! Use this when you need to find entities by exact key - like looking up
//! a user by their unique username or finding a node by a primary key.
//!
//! Uses DashMap for lock-free concurrent reads (sharded hash map).
//! This provides 4-6x improvement over RwLock-based approaches under contention.

use dashmap::DashMap;
use grafeo_common::types::NodeId;
use std::hash::Hash;

/// A thread-safe hash index for O(1) key lookups.
///
/// Backed by DashMap (sharded concurrent hash map) for lock-free reads.
/// Each read operation only locks one of ~16 internal shards, enabling
/// high concurrent throughput without global lock contention.
///
/// Best for exact-match queries on unique keys.
///
/// # Performance
///
/// - Concurrent reads: ~6x faster than RwLock under contention
/// - Point lookups: O(1) average case
/// - No lock acquisition for reads in common case
///
/// # Example
///
/// ```
/// use grafeo_core::index::HashIndex;
/// use grafeo_common::types::NodeId;
///
/// let index: HashIndex<String, NodeId> = HashIndex::new();
/// index.insert("alix".to_string(), NodeId::new(1));
/// index.insert("gus".to_string(), NodeId::new(2));
///
/// assert_eq!(index.get(&"alix".to_string()), Some(NodeId::new(1)));
/// ```
pub struct HashIndex<K: Hash + Eq, V: Copy> {
    /// The underlying sharded hash map for lock-free reads.
    map: DashMap<K, V>,
}

impl<K: Hash + Eq, V: Copy> HashIndex<K, V> {
    /// Creates a new empty hash index.
    #[must_use]
    pub fn new() -> Self {
        Self {
            map: DashMap::new(),
        }
    }

    /// Creates a new hash index with the given capacity.
    #[must_use]
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            map: DashMap::with_capacity(capacity),
        }
    }

    /// Inserts a key-value pair into the index.
    ///
    /// Returns the previous value if the key was already present.
    pub fn insert(&self, key: K, value: V) -> Option<V> {
        self.map.insert(key, value)
    }

    /// Gets the value for a key.
    ///
    /// This is a lock-free read operation that only briefly locks
    /// one of the internal shards.
    pub fn get(&self, key: &K) -> Option<V> {
        self.map.get(key).map(|v| *v)
    }

    /// Removes a key from the index.
    ///
    /// Returns the value if the key was present.
    pub fn remove(&self, key: &K) -> Option<V> {
        self.map.remove(key).map(|(_, v)| v)
    }

    /// Checks if a key exists in the index.
    pub fn contains(&self, key: &K) -> bool {
        self.map.contains_key(key)
    }

    /// Returns the number of entries in the index.
    pub fn len(&self) -> usize {
        self.map.len()
    }

    /// Returns true if the index is empty.
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Clears all entries from the index.
    pub fn clear(&self) {
        self.map.clear();
    }
}

impl<K: Hash + Eq, V: Copy> Default for HashIndex<K, V> {
    fn default() -> Self {
        Self::new()
    }
}

/// A hash index from string keys to NodeIds.
pub type StringKeyIndex = HashIndex<String, NodeId>;

/// A hash index from NodeIds to NodeIds.
pub type NodeIdIndex = HashIndex<NodeId, NodeId>;

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_hash_index_basic() {
        let index: HashIndex<u64, NodeId> = HashIndex::new();

        index.insert(1, NodeId::new(100));
        index.insert(2, NodeId::new(200));

        assert_eq!(index.get(&1), Some(NodeId::new(100)));
        assert_eq!(index.get(&2), Some(NodeId::new(200)));
        assert_eq!(index.get(&3), None);
    }

    #[test]
    fn test_hash_index_update() {
        let index: HashIndex<u64, NodeId> = HashIndex::new();

        index.insert(1, NodeId::new(100));
        let old = index.insert(1, NodeId::new(200));

        assert_eq!(old, Some(NodeId::new(100)));
        assert_eq!(index.get(&1), Some(NodeId::new(200)));
    }

    #[test]
    fn test_hash_index_remove() {
        let index: HashIndex<u64, NodeId> = HashIndex::new();

        index.insert(1, NodeId::new(100));
        assert!(index.contains(&1));

        let removed = index.remove(&1);
        assert_eq!(removed, Some(NodeId::new(100)));
        assert!(!index.contains(&1));
    }

    #[test]
    fn test_hash_index_len() {
        let index: HashIndex<u64, NodeId> = HashIndex::new();

        assert!(index.is_empty());
        assert_eq!(index.len(), 0);

        index.insert(1, NodeId::new(100));
        index.insert(2, NodeId::new(200));

        assert!(!index.is_empty());
        assert_eq!(index.len(), 2);
    }

    #[test]
    fn test_hash_index_clear() {
        let index: HashIndex<u64, NodeId> = HashIndex::new();

        index.insert(1, NodeId::new(100));
        index.insert(2, NodeId::new(200));

        index.clear();

        assert!(index.is_empty());
        assert_eq!(index.get(&1), None);
    }

    #[test]
    fn test_string_key_index() {
        let index: StringKeyIndex = HashIndex::new();

        index.insert("alix".to_string(), NodeId::new(1));
        index.insert("gus".to_string(), NodeId::new(2));

        assert_eq!(index.get(&"alix".to_string()), Some(NodeId::new(1)));
        assert_eq!(index.get(&"gus".to_string()), Some(NodeId::new(2)));
    }
}