lock_free/

list_o1.rs

//! O(1) Lock-free List Implementations
//! 
//! This module provides several O(1) list variants:
//! 1. AppendOnlyList - O(1) append, O(n) search
//! 2. IndexedList - O(1) get/set by index, fixed capacity
//! 3. UnorderedSet - O(1) insert/remove/contains using hash table

use std::sync::atomic::{AtomicPtr, AtomicUsize, Ordering};
use std::ptr::{self, null_mut};
use std::marker::PhantomData;
use std::alloc::{alloc_zeroed, dealloc, Layout};
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;

/// Node for append-only list
struct Node<T> {
    data: T,
    next: AtomicPtr<Node<T>>,
}

/// O(1) Append-only list (like a log)
/// - Append: O(1) 
/// - Iterate: O(n)
/// - No removal
pub struct AppendOnlyList<T> {
    head: AtomicPtr<Node<T>>,
    tail: AtomicPtr<Node<T>>,
    size: AtomicUsize,
    _phantom: PhantomData<T>,
}

impl<T> AppendOnlyList<T> {
    pub fn new() -> Self {
        Self {
            head: AtomicPtr::new(null_mut()),
            tail: AtomicPtr::new(null_mut()),
            size: AtomicUsize::new(0),
            _phantom: PhantomData,
        }
    }

    /// Append item - O(1)
    pub fn append(&self, data: T) {
        let new_node = Box::into_raw(Box::new(Node {
            data,
            next: AtomicPtr::new(null_mut()),
        }));

        loop {
            let tail = self.tail.load(Ordering::Acquire);
            
            if tail.is_null() {
                // Empty list
                match self.head.compare_exchange(
                    null_mut(),
                    new_node,
                    Ordering::Release,
                    Ordering::Acquire
                ) {
                    Ok(_) => {
                        self.tail.store(new_node, Ordering::Release);
                        self.size.fetch_add(1, Ordering::Relaxed);
                        return;
                    }
                    Err(_) => continue,
                }
            } else {
                // Non-empty list
                let tail_next = unsafe { &(*tail).next };
                
                match tail_next.compare_exchange(
                    null_mut(),
                    new_node,
                    Ordering::Release,
                    Ordering::Acquire
                ) {
                    Ok(_) => {
                        // Try to update tail
                        let _ = self.tail.compare_exchange(
                            tail,
                            new_node,
                            Ordering::Release,
                            Ordering::Acquire
                        );
                        self.size.fetch_add(1, Ordering::Relaxed);
                        return;
                    }
                    Err(_) => {
                        // Help update tail
                        let actual_tail = tail_next.load(Ordering::Acquire);
                        if !actual_tail.is_null() {
                            let _ = self.tail.compare_exchange(
                                tail,
                                actual_tail,
                                Ordering::Release,
                                Ordering::Acquire
                            );
                        }
                    }
                }
            }
        }
    }

    /// Get size - O(1)
    pub fn len(&self) -> usize {
        self.size.load(Ordering::Relaxed)
    }

    /// Iterate - O(n)
    pub fn iter(&self) -> AppendOnlyIterator<T> {
        AppendOnlyIterator {
            current: self.head.load(Ordering::Acquire),
            _phantom: PhantomData,
        }
    }
}

pub struct AppendOnlyIterator<T> {
    current: *mut Node<T>,
    _phantom: PhantomData<T>,
}

impl<T> Iterator for AppendOnlyIterator<T> {
    type Item = *const T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current.is_null() {
            None
        } else {
            unsafe {
                let node = &*self.current;
                let data_ptr = &node.data as *const T;
                self.current = node.next.load(Ordering::Acquire);
                Some(data_ptr)
            }
        }
    }
}

/// O(1) Fixed-capacity indexed list
/// - Get by index: O(1)
/// - Set by index: O(1) 
/// - Fixed capacity
pub struct IndexedList<T> {
    data: *mut AtomicPtr<T>,
    capacity: usize,
    size: AtomicUsize,
    _phantom: PhantomData<T>,
}

impl<T> IndexedList<T> {
    pub fn new(capacity: usize) -> Self {
        let layout = Layout::array::<AtomicPtr<T>>(capacity).unwrap();
        let data = unsafe {
            let ptr = alloc_zeroed(layout) as *mut AtomicPtr<T>;
            for i in 0..capacity {
                ptr::write(ptr.add(i), AtomicPtr::new(null_mut()));
            }
            ptr
        };

        Self {
            data,
            capacity,
            size: AtomicUsize::new(0),
            _phantom: PhantomData,
        }
    }

    /// Set value at index - O(1)
    pub fn set(&self, index: usize, value: T) -> Result<Option<T>, T> {
        if index >= self.capacity {
            return Err(value);
        }

        let ptr = Box::into_raw(Box::new(value));
        let slot = unsafe { &*self.data.add(index) };
        let old = slot.swap(ptr, Ordering::AcqRel);

        if old.is_null() {
            self.size.fetch_add(1, Ordering::Relaxed);
            Ok(None)
        } else {
            Ok(Some(unsafe { *Box::from_raw(old) }))
        }
    }

    /// Get value at index - O(1)
    pub fn get(&self, index: usize) -> Option<*const T> {
        if index >= self.capacity {
            return None;
        }

        let slot = unsafe { &*self.data.add(index) };
        let ptr = slot.load(Ordering::Acquire);
        
        if ptr.is_null() {
            None
        } else {
            Some(ptr as *const T)
        }
    }

    /// Remove value at index - O(1)
    pub fn remove(&self, index: usize) -> Option<T> {
        if index >= self.capacity {
            return None;
        }

        let slot = unsafe { &*self.data.add(index) };
        let ptr = slot.swap(null_mut(), Ordering::AcqRel);
        
        if ptr.is_null() {
            None
        } else {
            self.size.fetch_sub(1, Ordering::Relaxed);
            Some(unsafe { *Box::from_raw(ptr) })
        }
    }

    pub fn capacity(&self) -> usize {
        self.capacity
    }

    pub fn len(&self) -> usize {
        self.size.load(Ordering::Relaxed)
    }
}

/// O(1) Unordered set using hash table
/// - Insert: O(1) average
/// - Remove: O(1) average  
/// - Contains: O(1) average
pub struct UnorderedSet<T: Hash + Eq> {
    buckets: *mut Bucket<T>,
    bucket_count: usize,
    mask: usize,
    size: AtomicUsize,
    _phantom: PhantomData<T>,
}

#[repr(align(64))]
struct Bucket<T> {
    // Simple chaining with atomic operations
    head: AtomicPtr<SetNode<T>>,
}

struct SetNode<T> {
    data: T,
    hash: u64,
    next: AtomicPtr<SetNode<T>>,
}

impl<T: Hash + Eq> UnorderedSet<T> {
    pub fn new() -> Self {
        Self::with_capacity(1024)
    }

    pub fn with_capacity(capacity: usize) -> Self {
        let bucket_count = capacity.next_power_of_two();
        let layout = Layout::array::<Bucket<T>>(bucket_count).unwrap();
        
        let buckets = unsafe {
            let ptr = alloc_zeroed(layout) as *mut Bucket<T>;
            for i in 0..bucket_count {
                ptr::write(ptr.add(i), Bucket {
                    head: AtomicPtr::new(null_mut()),
                });
            }
            ptr
        };

        Self {
            buckets,
            bucket_count,
            mask: bucket_count - 1,
            size: AtomicUsize::new(0),
            _phantom: PhantomData,
        }
    }

    fn hash(item: &T) -> u64 {
        let mut hasher = DefaultHasher::new();
        item.hash(&mut hasher);
        hasher.finish()
    }

    /// Insert item - O(1) average
    pub fn insert(&self, item: T) -> bool {
        let hash = Self::hash(&item);
        let bucket_idx = (hash as usize) & self.mask;
        let bucket = unsafe { &*self.buckets.add(bucket_idx) };

        // Check if already exists
        let mut current = bucket.head.load(Ordering::Acquire);
        while !current.is_null() {
            let node = unsafe { &*current };
            if node.hash == hash && node.data == item {
                return false; // Already exists
            }
            current = node.next.load(Ordering::Acquire);
        }

        // Insert new node
        let new_node = Box::into_raw(Box::new(SetNode {
            data: item,
            hash,
            next: AtomicPtr::new(null_mut()),
        }));

        loop {
            let head = bucket.head.load(Ordering::Acquire);
            unsafe {
                (*new_node).next.store(head, Ordering::Relaxed);
            }

            match bucket.head.compare_exchange(
                head,
                new_node,
                Ordering::Release,
                Ordering::Acquire
            ) {
                Ok(_) => {
                    self.size.fetch_add(1, Ordering::Relaxed);
                    return true;
                }
                Err(_) => continue,
            }
        }
    }

    /// Check if contains - O(1) average
    pub fn contains(&self, item: &T) -> bool {
        let hash = Self::hash(item);
        let bucket_idx = (hash as usize) & self.mask;
        let bucket = unsafe { &*self.buckets.add(bucket_idx) };

        let mut current = bucket.head.load(Ordering::Acquire);
        while !current.is_null() {
            let node = unsafe { &*current };
            if node.hash == hash && node.data == *item {
                return true;
            }
            current = node.next.load(Ordering::Acquire);
        }
        false
    }

    /// Remove item - O(1) average
    pub fn remove(&self, item: &T) -> bool {
        let hash = Self::hash(item);
        let bucket_idx = (hash as usize) & self.mask;
        let bucket = unsafe { &*self.buckets.add(bucket_idx) };

        // Use a sentinel node to simplify removal
        let mut prev = &bucket.head as *const AtomicPtr<SetNode<T>>;
        let mut current = bucket.head.load(Ordering::Acquire);

        while !current.is_null() {
            let node = unsafe { &*current };
            if node.hash == hash && node.data == *item {
                let next = node.next.load(Ordering::Acquire);
                
                let prev_atomic = unsafe { &*prev };
                match prev_atomic.compare_exchange(
                    current,
                    next,
                    Ordering::Release,
                    Ordering::Acquire
                ) {
                    Ok(_) => {
                        self.size.fetch_sub(1, Ordering::Relaxed);
                        unsafe { Box::from_raw(current); }
                        return true;
                    }
                    Err(_) => return false, // Concurrent modification
                }
            }
            
            prev = &node.next as *const AtomicPtr<SetNode<T>>;
            current = node.next.load(Ordering::Acquire);
        }
        false
    }

    pub fn len(&self) -> usize {
        self.size.load(Ordering::Relaxed)
    }
}

// Implement Drop for all types
impl<T> Drop for AppendOnlyList<T> {
    fn drop(&mut self) {
        let mut current = self.head.load(Ordering::Acquire);
        while !current.is_null() {
            let next = unsafe {
                let node = Box::from_raw(current);
                node.next.load(Ordering::Acquire)
            };
            current = next;
        }
    }
}

impl<T> Drop for IndexedList<T> {
    fn drop(&mut self) {
        for i in 0..self.capacity {
            let slot = unsafe { &*self.data.add(i) };
            let ptr = slot.load(Ordering::Acquire);
            if !ptr.is_null() {
                unsafe { Box::from_raw(ptr); }
            }
        }
        
        let layout = Layout::array::<AtomicPtr<T>>(self.capacity).unwrap();
        unsafe {
            dealloc(self.data as *mut u8, layout);
        }
    }
}

impl<T: Hash + Eq> Drop for UnorderedSet<T> {
    fn drop(&mut self) {
        for i in 0..self.bucket_count {
            let bucket = unsafe { &*self.buckets.add(i) };
            let mut current = bucket.head.load(Ordering::Acquire);
            
            while !current.is_null() {
                let next = unsafe {
                    let node = Box::from_raw(current);
                    node.next.load(Ordering::Acquire)
                };
                current = next;
            }
        }
        
        let layout = Layout::array::<Bucket<T>>(self.bucket_count).unwrap();
        unsafe {
            dealloc(self.buckets as *mut u8, layout);
        }
    }
}

unsafe impl<T: Send> Send for AppendOnlyList<T> {}
unsafe impl<T: Send + Sync> Sync for AppendOnlyList<T> {}

unsafe impl<T: Send> Send for IndexedList<T> {}
unsafe impl<T: Send + Sync> Sync for IndexedList<T> {}

unsafe impl<T: Send + Hash + Eq> Send for UnorderedSet<T> {}
unsafe impl<T: Send + Sync + Hash + Eq> Sync for UnorderedSet<T> {}