concurrent_avl_tree 0.1.0

//! # Atomic AVL Tree Node
//!
//! Single-element container for balanced binary search tree traversal.
//!
//! ## License & Attribution
//! SPDX-License-Identifier: MIT | Author: Dzulkifli Anwar | Version: 0.1.0 | Date: 2026-04-30

use std::sync::atomic::AtomicPtr;

/// # AVL Tree Node
///
/// Stores key, value, height, and left/right child pointers.
///
/// ## Description
/// Maintains height invariant for AVL balancing. Child pointers use atomic types.
/// Structure aligns to cache line to prevent false sharing. Arena allocator manages lifetime.
///
/// ## Invariant
/// `height == max(left.height(), right.height()) + 1`
///
/// ## Thread Safety
/// `left_child` and `right_child` support concurrent reads. Writers replace entire subtree.
///
/// ## Performance
/// Cache-line aligned. Zero dynamic allocation post-construction. Trivially copyable keys/values preferred.
///
/// ## See Also
/// `crate::memory::arena::GenerationalArena`
pub struct Node<K, V> {
    /// Immutable key for search navigation.
    pub key: K,
    /// Immutable payload copy.
    pub value: V,
    /// Height of the subtree rooted at this node.
    pub height: i32,
    /// Left child pointer.
    pub left_child: AtomicPtr<Node<K, V>>,
    /// Right child pointer.
    pub right_child: AtomicPtr<Node<K, V>>,
}

impl<K: PartialOrd, V> Node<K, V> {
    /// # Construct Node
    ///
    /// Initializes with key-value pair, default height zero, and null children.
    ///
    /// ## Parameters
    /// - `key`: Search key. Consumed by caller.
    /// - `value`: Payload value. Consumed by caller.
    ///
    /// ## Returns
    /// Owned `Node<K, V>` instance.
    ///
    /// ## Complexity
    /// Time: O(1), Space: O(1)
    pub fn new(key: K, value: V) -> Self {
        Self {
            key,
            value,
            height: 0,
            left_child: AtomicPtr::new(std::ptr::null_mut()),
            right_child: AtomicPtr::new(std::ptr::null_mut()),
        }
    }
}