#include <stdatomic.h>
#include <stdbool.h>
#include <stdint.h>

// Basic atomic types and operations
typedef struct {
    atomic_uintptr_t head;
    atomic_uintptr_t tail;
    atomic_size_t size;
    char padding[64 - 3 * sizeof(atomic_uintptr_t)]; // Cache line padding
} lockfree_queue_header_t;

// Memory ordering demonstration
void demonstrate_memory_ordering() {
    atomic_int shared_data = ATOMIC_VAR_INIT(0);
    atomic_bool flag = ATOMIC_VAR_INIT(false);
    
    // Relaxed ordering - no synchronization constraints
    atomic_store_explicit(&shared_data, 42, memory_order_relaxed);
    
    // Release ordering - all prior operations become visible
    atomic_store_explicit(&flag, true, memory_order_release);
    
    // Acquire ordering - all subsequent operations are ordered after this
    while (!atomic_load_explicit(&flag, memory_order_acquire)) {
        // Busy wait
    }
    
    // Sequential consistency - strongest ordering
    int value = atomic_load(&shared_data); // Implicitly memory_order_seq_cst
    
    // Compare and swap with explicit ordering
    int expected = 42;
    bool success = atomic_compare_exchange_strong_explicit(
        &shared_data, &expected, 100,
        memory_order_acq_rel,  // Success ordering
        memory_order_acquire   // Failure ordering
    );
}

// Double-width compare and swap for ABA problem mitigation
typedef struct {
    void *ptr;
    uintptr_t counter;
} tagged_pointer_t;

#ifdef __x86_64__
typedef union {
    __int128 atomic_value;
    tagged_pointer_t tagged;
} atomic_tagged_ptr_t;

bool compare_exchange_tagged_ptr(atomic_tagged_ptr_t *ptr,
                                tagged_pointer_t *expected,
                                tagged_pointer_t desired) {
    __int128 expected_val = ((__int128)expected->counter << 64) | 
                           (uintptr_t)expected->ptr;
    __int128 desired_val = ((__int128)desired.counter << 64) | 
                          (uintptr_t)desired.ptr;
    
    bool success = __atomic_compare_exchange_n(
        &ptr->atomic_value, &expected_val, desired_val,
        false, __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE
    );
    
    if (!success) {
        expected->ptr = (void*)(uintptr_t)expected_val;
        expected->counter = expected_val >> 64;
    }
    
    return success;
}
#endif

// Memory barrier utilities
static inline void memory_barrier_acquire() {
    atomic_thread_fence(memory_order_acquire);
}

static inline void memory_barrier_release() {
    atomic_thread_fence(memory_order_release);
}

static inline void memory_barrier_full() {
    atomic_thread_fence(memory_order_seq_cst);
}

// Cache-friendly atomic operations
#define CACHE_LINE_SIZE 64

typedef struct aligned_atomic {
    atomic_uintptr_t value;
    char padding[CACHE_LINE_SIZE - sizeof(atomic_uintptr_t)];
} __attribute__((aligned(CACHE_LINE_SIZE))) aligned_atomic_t;

// Node structure for lock-free stack
typedef struct stack_node {
    void *data;
    struct stack_node *next;
    atomic_uintptr_t ref_count;
} stack_node_t;

typedef struct {
    atomic_tagged_ptr_t head;
    atomic_size_t size;
    
    // Memory management
    atomic_uintptr_t retire_list;
    atomic_size_t retired_count;
    atomic_size_t epoch_counter;
    
    // Statistics
    atomic_size_t push_count;
    atomic_size_t pop_count;
    atomic_size_t contention_count;
} lockfree_stack_t;

// Initialize lock-free stack
lockfree_stack_t* lockfree_stack_create() {
    lockfree_stack_t *stack = aligned_alloc(CACHE_LINE_SIZE, sizeof(lockfree_stack_t));
    if (!stack) return NULL;
    
    memset(stack, 0, sizeof(lockfree_stack_t));
    
    // Initialize tagged pointer with null and counter 0
    tagged_pointer_t initial = {.ptr = NULL, .counter = 0};
    atomic_store(&stack->head.atomic_value, 
                ((__int128)initial.counter << 64) | (uintptr_t)initial.ptr);
    
    return stack;
}

// Push operation with ABA protection
bool lockfree_stack_push(lockfree_stack_t *stack, void *data) {
    stack_node_t *node = malloc(sizeof(stack_node_t));
    if (!node) return false;
    
    node->data = data;
    atomic_store(&node->ref_count, 1);
    
    tagged_pointer_t old_head, new_head;
    
    do {
        // Load current head with acquire semantics
        __int128 head_val = atomic_load_explicit(&stack->head.atomic_value, 
                                                memory_order_acquire);
        old_head.ptr = (void*)(uintptr_t)head_val;
        old_head.counter = head_val >> 64;
        
        // Set up new node
        node->next = (stack_node_t*)old_head.ptr;
        
        // Prepare new head with incremented counter
        new_head.ptr = node;
        new_head.counter = old_head.counter + 1;
        
    } while (!compare_exchange_tagged_ptr(&stack->head, &old_head, new_head));
    
    atomic_fetch_add(&stack->size, 1);
    atomic_fetch_add(&stack->push_count, 1);
    
    return true;
}

// Pop operation with hazard pointer protection
void* lockfree_stack_pop(lockfree_stack_t *stack) {
    tagged_pointer_t old_head, new_head;
    stack_node_t *node;
    void *data;
    
    do {
        __int128 head_val = atomic_load_explicit(&stack->head.atomic_value,
                                                memory_order_acquire);
        old_head.ptr = (void*)(uintptr_t)head_val;
        old_head.counter = head_val >> 64;
        
        node = (stack_node_t*)old_head.ptr;
        if (!node) {
            return NULL; // Stack is empty
        }
        
        // Increment reference count to protect against premature deallocation
        atomic_fetch_add(&node->ref_count, 1);
        
        // Verify node is still valid
        __int128 current_head = atomic_load(&stack->head.atomic_value);
        if (old_head.ptr != (void*)(uintptr_t)current_head) {
            // Head changed, retry
            atomic_fetch_sub(&node->ref_count, 1);
            atomic_fetch_add(&stack->contention_count, 1);
            continue;
        }
        
        new_head.ptr = node->next;
        new_head.counter = old_head.counter + 1;
        
    } while (!compare_exchange_tagged_ptr(&stack->head, &old_head, new_head));
    
    data = node->data;
    
    // Safely decrement reference count and potentially free
    if (atomic_fetch_sub(&node->ref_count, 1) == 1) {
        free(node);
    } else {
        // Add to retire list for later cleanup
        retire_node(stack, node);
    }
    
    atomic_fetch_sub(&stack->size, 1);
    atomic_fetch_add(&stack->pop_count, 1);
    
    return data;
}

// Safe memory reclamation using epoch-based approach
void retire_node(lockfree_stack_t *stack, stack_node_t *node) {
    uintptr_t old_retire_list;
    
    do {
        old_retire_list = atomic_load(&stack->retire_list);
        node->next = (stack_node_t*)old_retire_list;
    } while (!atomic_compare_exchange_weak(&stack->retire_list,
                                          &old_retire_list,
                                          (uintptr_t)node));
    
    atomic_fetch_add(&stack->retired_count, 1);
    
    // Trigger cleanup if too many retired nodes
    if (atomic_load(&stack->retired_count) > 1000) {
        cleanup_retired_nodes(stack);
    }
}

void cleanup_retired_nodes(lockfree_stack_t *stack) {
    uintptr_t retire_list = atomic_exchange(&stack->retire_list, 0);
    stack_node_t *node = (stack_node_t*)retire_list;
    
    while (node) {
        stack_node_t *next = node->next;
        
        // Check if node can be safely freed
        if (atomic_load(&node->ref_count) == 0) {
            free(node);
            atomic_fetch_sub(&stack->retired_count, 1);
        } else {
            // Re-add to retire list
            retire_node(stack, node);
        }
        
        node = next;
    }
}

// Queue node with padding to prevent false sharing
typedef struct queue_node {
    atomic_uintptr_t data;
    atomic_uintptr_t next;
    char padding[CACHE_LINE_SIZE - 2 * sizeof(atomic_uintptr_t)];
} __attribute__((aligned(CACHE_LINE_SIZE))) queue_node_t;

typedef struct {
    atomic_uintptr_t head;
    char padding1[CACHE_LINE_SIZE - sizeof(atomic_uintptr_t)];
    atomic_uintptr_t tail;
    char padding2[CACHE_LINE_SIZE - sizeof(atomic_uintptr_t)];
    
    // Statistics and management
    atomic_size_t size;
    atomic_size_t enqueue_count;
    atomic_size_t dequeue_count;
    
    // Memory pool for nodes
    atomic_uintptr_t free_list;
    atomic_size_t pool_size;
} lockfree_queue_t;

lockfree_queue_t* lockfree_queue_create() {
    lockfree_queue_t *queue = aligned_alloc(CACHE_LINE_SIZE, sizeof(lockfree_queue_t));
    if (!queue) return NULL;
    
    // Create dummy node
    queue_node_t *dummy = aligned_alloc(CACHE_LINE_SIZE, sizeof(queue_node_t));
    if (!dummy) {
        free(queue);
        return NULL;
    }
    
    atomic_store(&dummy->data, 0);
    atomic_store(&dummy->next, 0);
    
    // Initialize head and tail to point to dummy
    atomic_store(&queue->head, (uintptr_t)dummy);
    atomic_store(&queue->tail, (uintptr_t)dummy);
    
    atomic_store(&queue->size, 0);
    atomic_store(&queue->enqueue_count, 0);
    atomic_store(&queue->dequeue_count, 0);
    atomic_store(&queue->free_list, 0);
    atomic_store(&queue->pool_size, 0);
    
    return queue;
}

// Node allocation from memory pool
queue_node_t* allocate_queue_node(lockfree_queue_t *queue) {
    uintptr_t free_node;
    
    // Try to get node from free list
    do {
        free_node = atomic_load(&queue->free_list);
        if (!free_node) break;
        
        queue_node_t *node = (queue_node_t*)free_node;
        uintptr_t next_free = atomic_load(&node->next);
        
        if (atomic_compare_exchange_weak(&queue->free_list, &free_node, next_free)) {
            atomic_fetch_sub(&queue->pool_size, 1);
            return node;
        }
    } while (true);
    
    // Allocate new node if free list is empty
    return aligned_alloc(CACHE_LINE_SIZE, sizeof(queue_node_t));
}

// Return node to memory pool
void deallocate_queue_node(lockfree_queue_t *queue, queue_node_t *node) {
    uintptr_t old_free_list;
    
    do {
        old_free_list = atomic_load(&queue->free_list);
        atomic_store(&node->next, old_free_list);
    } while (!atomic_compare_exchange_weak(&queue->free_list,
                                          &old_free_list,
                                          (uintptr_t)node));
    
    atomic_fetch_add(&queue->pool_size, 1);
}

// Enqueue operation
bool lockfree_queue_enqueue(lockfree_queue_t *queue, void *data) {
    if (!data) return false;
    
    queue_node_t *node = allocate_queue_node(queue);
    if (!node) return false;
    
    atomic_store(&node->data, (uintptr_t)data);
    atomic_store(&node->next, 0);
    
    while (true) {
        uintptr_t tail_ptr = atomic_load_explicit(&queue->tail, memory_order_acquire);
        queue_node_t *tail = (queue_node_t*)tail_ptr;
        
        uintptr_t next_ptr = atomic_load_explicit(&tail->next, memory_order_acquire);
        
        // Check if tail is still the last node
        if (tail_ptr == atomic_load(&queue->tail)) {
            if (next_ptr == 0) {
                // Try to link new node at the end of the list
                if (atomic_compare_exchange_weak_explicit(&tail->next,
                                                         &next_ptr,
                                                         (uintptr_t)node,
                                                         memory_order_release,
                                                         memory_order_relaxed)) {
                    break; // Enqueue done, now try to swing tail
                }
            } else {
                // Tail was not pointing to the last node
                // Try to swing tail to the next node
                atomic_compare_exchange_weak(&queue->tail, &tail_ptr, next_ptr);
            }
        }
    }
    
    // Try to swing tail to the new node
    uintptr_t tail_ptr = atomic_load(&queue->tail);
    atomic_compare_exchange_weak(&queue->tail, &tail_ptr, (uintptr_t)node);
    
    atomic_fetch_add(&queue->size, 1);
    atomic_fetch_add(&queue->enqueue_count, 1);
    
    return true;
}

// Dequeue operation
void* lockfree_queue_dequeue(lockfree_queue_t *queue) {
    while (true) {
        uintptr_t head_ptr = atomic_load_explicit(&queue->head, memory_order_acquire);
        uintptr_t tail_ptr = atomic_load_explicit(&queue->tail, memory_order_acquire);
        
        queue_node_t *head = (queue_node_t*)head_ptr;
        uintptr_t next_ptr = atomic_load_explicit(&head->next, memory_order_acquire);
        
        // Verify that head is still consistent
        if (head_ptr == atomic_load(&queue->head)) {
            if (head_ptr == tail_ptr) {
                if (next_ptr == 0) {
                    return NULL; // Queue is empty
                }
                
                // Tail is falling behind, try to advance it
                atomic_compare_exchange_weak(&queue->tail, &tail_ptr, next_ptr);
            } else {
                if (next_ptr == 0) {
                    continue; // Inconsistent state, retry
                }
                
                queue_node_t *next = (queue_node_t*)next_ptr;
                void *data = (void*)atomic_load_explicit(&next->data, memory_order_acquire);
                
                // Try to swing head to the next node
                if (atomic_compare_exchange_weak_explicit(&queue->head,
                                                         &head_ptr,
                                                         next_ptr,
                                                         memory_order_release,
                                                         memory_order_relaxed)) {
                    deallocate_queue_node(queue, head);
                    atomic_fetch_sub(&queue->size, 1);
                    atomic_fetch_add(&queue->dequeue_count, 1);
                    return data;
                }
            }
        }
    }
}

// Hash table entry with marked pointers for logical deletion
typedef struct hash_entry {
    atomic_uintptr_t key;
    atomic_uintptr_t value;
    atomic_uintptr_t next; // LSB used as deletion mark
} hash_entry_t;

#define MARK_MASK 1UL
#define PTR_MASK (~MARK_MASK)

static inline hash_entry_t* get_pointer(uintptr_t marked_ptr) {
    return (hash_entry_t*)(marked_ptr & PTR_MASK);
}

static inline bool is_marked(uintptr_t marked_ptr) {
    return (marked_ptr & MARK_MASK) != 0;
}

static inline uintptr_t set_mark(hash_entry_t *ptr) {
    return (uintptr_t)ptr | MARK_MASK;
}

typedef struct {
    atomic_uintptr_t *buckets;
    atomic_size_t bucket_count;
    atomic_size_t size;
    atomic_size_t threshold;
    
    // Resize coordination
    atomic_bool resizing;
    atomic_uintptr_t old_buckets;
    atomic_size_t old_bucket_count;
    
    // Statistics
    atomic_size_t insert_count;
    atomic_size_t delete_count;
    atomic_size_t resize_count;
} lockfree_hashtable_t;

// Hash function (FNV-1a)
uint64_t hash_function(uint64_t key) {
    const uint64_t FNV_OFFSET_BASIS = 14695981039346656037ULL;
    const uint64_t FNV_PRIME = 1099511628211ULL;
    
    uint64_t hash = FNV_OFFSET_BASIS;
    uint8_t *bytes = (uint8_t*)&key;
    
    for (int i = 0; i < sizeof(key); i++) {
        hash ^= bytes[i];
        hash *= FNV_PRIME;
    }
    
    return hash;
}

// Reverse bits for split-ordering
uint64_t reverse_bits(uint64_t value) {
    value = ((value >> 1) & 0x5555555555555555ULL) | ((value & 0x5555555555555555ULL) << 1);
    value = ((value >> 2) & 0x3333333333333333ULL) | ((value & 0x3333333333333333ULL) << 2);
    value = ((value >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((value & 0x0F0F0F0F0F0F0F0FULL) << 4);
    value = ((value >> 8) & 0x00FF00FF00FF00FFULL) | ((value & 0x00FF00FF00FF00FFULL) << 8);
    value = ((value >> 16) & 0x0000FFFF0000FFFFULL) | ((value & 0x0000FFFF0000FFFFULL) << 16);
    value = (value >> 32) | (value << 32);
    
    return value;
}

lockfree_hashtable_t* lockfree_hashtable_create(size_t initial_capacity) {
    lockfree_hashtable_t *table = aligned_alloc(CACHE_LINE_SIZE, sizeof(lockfree_hashtable_t));
    if (!table) return NULL;
    
    size_t bucket_count = 1;
    while (bucket_count < initial_capacity) {
        bucket_count <<= 1;
    }
    
    table->buckets = aligned_alloc(CACHE_LINE_SIZE, bucket_count * sizeof(atomic_uintptr_t));
    if (!table->buckets) {
        free(table);
        return NULL;
    }
    
    for (size_t i = 0; i < bucket_count; i++) {
        atomic_store(&table->buckets[i], 0);
    }
    
    atomic_store(&table->bucket_count, bucket_count);
    atomic_store(&table->size, 0);
    atomic_store(&table->threshold, bucket_count * 3 / 4);
    atomic_store(&table->resizing, false);
    atomic_store(&table->old_buckets, 0);
    atomic_store(&table->old_bucket_count, 0);
    
    return table;
}

// Find operation with logical deletion handling
hash_entry_t* find_entry(lockfree_hashtable_t *table, uint64_t key, 
                        hash_entry_t **prev_ptr) {
    size_t bucket_count = atomic_load(&table->bucket_count);
    size_t bucket = hash_function(key) & (bucket_count - 1);
    uint64_t reversed_key = reverse_bits(key);
    
retry:
    atomic_uintptr_t *prev = &table->buckets[bucket];
    uintptr_t curr_ptr = atomic_load_explicit(prev, memory_order_acquire);
    
    while (true) {
        hash_entry_t *curr = get_pointer(curr_ptr);
        if (!curr) {
            if (prev_ptr) *prev_ptr = (hash_entry_t*)prev;
            return NULL;
        }
        
        uintptr_t next_ptr = atomic_load_explicit(&curr->next, memory_order_acquire);
        
        // Verify the link is still valid
        if (atomic_load(prev) != curr_ptr) {
            goto retry; // Start over
        }
        
        if (is_marked(next_ptr)) {
            // Logically deleted node, help remove it
            if (!atomic_compare_exchange_weak(prev, &curr_ptr, next_ptr & PTR_MASK)) {
                goto retry;
            }
            curr_ptr = next_ptr & PTR_MASK;
        } else {
            uint64_t curr_key = atomic_load(&curr->key);
            uint64_t curr_reversed = reverse_bits(curr_key);
            
            if (curr_reversed >= reversed_key) {
                if (curr_key == key) {
                    if (prev_ptr) *prev_ptr = (hash_entry_t*)prev;
                    return curr;
                } else {
                    if (prev_ptr) *prev_ptr = (hash_entry_t*)prev;
                    return NULL;
                }
            }
            
            prev = &curr->next;
            curr_ptr = next_ptr;
        }
    }
}

// Insert operation
bool lockfree_hashtable_insert(lockfree_hashtable_t *table, uint64_t key, uint64_t value) {
    if (key == 0 || value == 0) return false; // Reserved values
    
    // Check if resize is needed
    if (atomic_load(&table->size) > atomic_load(&table->threshold)) {
        resize_table(table);
    }
    
    hash_entry_t *new_entry = aligned_alloc(CACHE_LINE_SIZE, sizeof(hash_entry_t));
    if (!new_entry) return false;
    
    atomic_store(&new_entry->key, key);
    atomic_store(&new_entry->value, value);
    
    while (true) {
        hash_entry_t *prev, *curr;
        curr = find_entry(table, key, &prev);
        
        if (curr && atomic_load(&curr->key) == key) {
            // Key already exists, update value
            atomic_store(&curr->value, value);
            free(new_entry);
            return true;
        }
        
        atomic_store(&new_entry->next, (uintptr_t)curr);
        
        if (atomic_compare_exchange_weak(&prev->next, (uintptr_t*)&curr, (uintptr_t)new_entry)) {
            atomic_fetch_add(&table->size, 1);
            atomic_fetch_add(&table->insert_count, 1);
            return true;
        }
    }
}

// Delete operation with logical deletion
bool lockfree_hashtable_delete(lockfree_hashtable_t *table, uint64_t key) {
    while (true) {
        hash_entry_t *prev, *curr;
        curr = find_entry(table, key, &prev);
        
        if (!curr || atomic_load(&curr->key) != key) {
            return false; // Key not found
        }
        
        uintptr_t next_ptr = atomic_load(&curr->next);
        
        // Logically delete by marking the next pointer
        if (!atomic_compare_exchange_weak(&curr->next, &next_ptr, set_mark((hash_entry_t*)next_ptr))) {
            continue; // Retry if marking failed
        }
        
        // Physically remove from list
        atomic_compare_exchange_weak(&prev->next, (uintptr_t*)&curr, next_ptr & PTR_MASK);
        
        atomic_fetch_sub(&table->size, 1);
        atomic_fetch_add(&table->delete_count, 1);
        
        // Schedule for safe deletion
        retire_hash_entry(table, curr);
        
        return true;
    }
}

// Resize operation
void resize_table(lockfree_hashtable_t *table) {
    bool expected = false;
    if (!atomic_compare_exchange_strong(&table->resizing, &expected, true)) {
        return; // Another thread is already resizing
    }
    
    size_t old_bucket_count = atomic_load(&table->bucket_count);
    size_t new_bucket_count = old_bucket_count * 2;
    
    atomic_uintptr_t *new_buckets = aligned_alloc(CACHE_LINE_SIZE, 
                                                 new_bucket_count * sizeof(atomic_uintptr_t));
    if (!new_buckets) {
        atomic_store(&table->resizing, false);
        return;
    }
    
    for (size_t i = 0; i < new_bucket_count; i++) {
        atomic_store(&new_buckets[i], 0);
    }
    
    // Save old buckets for migration
    atomic_uintptr_t *old_buckets = table->buckets;
    atomic_store(&table->old_buckets, (uintptr_t)old_buckets);
    atomic_store(&table->old_bucket_count, old_bucket_count);
    
    // Install new buckets
    table->buckets = new_buckets;
    atomic_store(&table->bucket_count, new_bucket_count);
    atomic_store(&table->threshold, new_bucket_count * 3 / 4);
    
    // Migrate entries (this is a simplified version)
    migrate_entries(table, old_buckets, old_bucket_count);
    
    atomic_fetch_add(&table->resize_count, 1);
    atomic_store(&table->resizing, false);
}

// Hazard pointer system for safe memory reclamation
#define MAX_THREADS 64
#define MAX_HAZARD_POINTERS 8

typedef struct hazard_pointer {
    atomic_uintptr_t pointer;
    char padding[CACHE_LINE_SIZE - sizeof(atomic_uintptr_t)];
} hazard_pointer_t;

typedef struct thread_hazards {
    hazard_pointer_t hazards[MAX_HAZARD_POINTERS];
    atomic_uintptr_t retire_list;
    atomic_size_t retire_count;
    int thread_id;
} thread_hazards_t;

static __thread thread_hazards_t *local_hazards = NULL;
static hazard_pointer_t global_hazards[MAX_THREADS][MAX_HAZARD_POINTERS];
static atomic_int next_thread_id = ATOMIC_VAR_INIT(0);

// Initialize thread-local hazard pointers
void initialize_hazard_pointers() {
    if (local_hazards) return;
    
    int thread_id = atomic_fetch_add(&next_thread_id, 1);
    local_hazards = malloc(sizeof(thread_hazards_t));
    local_hazards->thread_id = thread_id;
    
    for (int i = 0; i < MAX_HAZARD_POINTERS; i++) {
        atomic_store(&local_hazards->hazards[i].pointer, 0);
    }
    
    atomic_store(&local_hazards->retire_list, 0);
    atomic_store(&local_hazards->retire_count, 0);
}

// Acquire hazard pointer
void acquire_hazard_pointer(int slot, void *ptr) {
    if (!local_hazards) initialize_hazard_pointers();
    
    atomic_store_explicit(&local_hazards->hazards[slot].pointer,
                         (uintptr_t)ptr, memory_order_release);
}

// Release hazard pointer
void release_hazard_pointer(int slot) {
    if (!local_hazards) return;
    
    atomic_store_explicit(&local_hazards->hazards[slot].pointer,
                         0, memory_order_release);
}

// Check if pointer is protected by any hazard pointer
bool is_hazardous(void *ptr) {
    for (int tid = 0; tid < MAX_THREADS; tid++) {
        for (int hp = 0; hp < MAX_HAZARD_POINTERS; hp++) {
            if (atomic_load(&global_hazards[tid][hp].pointer) == (uintptr_t)ptr) {
                return true;
            }
        }
    }
    return false;
}

// Retire pointer for later deletion
void retire_pointer(void *ptr) {
    if (!local_hazards) initialize_hazard_pointers();
    
    // Add to retire list
    retire_node_t *node = malloc(sizeof(retire_node_t));
    node->ptr = ptr;
    
    uintptr_t old_head;
    do {
        old_head = atomic_load(&local_hazards->retire_list);
        node->next = (retire_node_t*)old_head;
    } while (!atomic_compare_exchange_weak(&local_hazards->retire_list,
                                          &old_head, (uintptr_t)node));
    
    atomic_fetch_add(&local_hazards->retire_count, 1);
    
    // Trigger cleanup if too many retired objects
    if (atomic_load(&local_hazards->retire_count) > 100) {
        cleanup_retired_objects();
    }
}

// CPU optimization techniques
static inline void cpu_relax() {
#ifdef __x86_64__
    __asm__ __volatile__("pause" ::: "memory");
#elif defined(__aarch64__)
    __asm__ __volatile__("yield" ::: "memory");
#else
    __asm__ __volatile__("" ::: "memory");
#endif
}

// Exponential backoff for contention management
typedef struct {
    int current_delay;
    int max_delay;
    int base_delay;
} backoff_t;

void backoff_init(backoff_t *backoff, int base_delay, int max_delay) {
    backoff->current_delay = base_delay;
    backoff->max_delay = max_delay;
    backoff->base_delay = base_delay;
}

void backoff_delay(backoff_t *backoff) {
    for (int i = 0; i < backoff->current_delay; i++) {
        cpu_relax();
    }
    
    backoff->current_delay = (backoff->current_delay < backoff->max_delay) ?
                            backoff->current_delay * 2 : backoff->max_delay;
}

void backoff_reset(backoff_t *backoff) {
    backoff->current_delay = backoff->base_delay;
}

// Lock-free memory allocator for frequently allocated objects
typedef struct free_node {
    struct free_node *next;
} free_node_t;

typedef struct {
    atomic_uintptr_t head;
    size_t object_size;
    size_t alignment;
    atomic_size_t allocated_count;
    atomic_size_t free_count;
} lockfree_allocator_t;

lockfree_allocator_t* create_lockfree_allocator(size_t object_size, size_t alignment) {
    lockfree_allocator_t *allocator = malloc(sizeof(lockfree_allocator_t));
    allocator->object_size = object_size;
    allocator->alignment = alignment;
    atomic_store(&allocator->head, 0);
    atomic_store(&allocator->allocated_count, 0);
    atomic_store(&allocator->free_count, 0);
    
    return allocator;
}

void* lockfree_allocator_alloc(lockfree_allocator_t *allocator) {
    uintptr_t head;
    free_node_t *node;
    
    do {
        head = atomic_load_explicit(&allocator->head, memory_order_acquire);
        node = (free_node_t*)head;
        
        if (!node) {
            // No free objects, allocate new one
            void *ptr = aligned_alloc(allocator->alignment, allocator->object_size);
            if (ptr) {
                atomic_fetch_add(&allocator->allocated_count, 1);
            }
            return ptr;
        }
        
    } while (!atomic_compare_exchange_weak_explicit(&allocator->head,
                                                   &head,
                                                   (uintptr_t)node->next,
                                                   memory_order_release,
                                                   memory_order_relaxed));
    
    atomic_fetch_sub(&allocator->free_count, 1);
    return node;
}

void lockfree_allocator_free(lockfree_allocator_t *allocator, void *ptr) {
    if (!ptr) return;
    
    free_node_t *node = (free_node_t*)ptr;
    uintptr_t head;
    
    do {
        head = atomic_load_explicit(&allocator->head, memory_order_relaxed);
        node->next = (free_node_t*)head;
    } while (!atomic_compare_exchange_weak_explicit(&allocator->head,
                                                   &head,
                                                   (uintptr_t)node,
                                                   memory_order_release,
                                                   memory_order_relaxed));
    
    atomic_fetch_add(&allocator->free_count, 1);
}

#include <pthread.h>
#include <time.h>

// Test framework for lock-free data structures
typedef struct {
    void *data_structure;
    int num_threads;
    int operations_per_thread;
    int test_duration_seconds;
    
    // Test parameters
    float insert_ratio;
    float delete_ratio;
    float lookup_ratio;
    
    // Results
    atomic_size_t total_operations;
    atomic_size_t successful_operations;
    atomic_size_t failed_operations;
    
    // Timing
    struct timespec start_time;
    struct timespec end_time;
    
    // Thread synchronization
    pthread_barrier_t start_barrier;
    atomic_bool test_running;
} test_context_t;

// Thread function for stress testing
void* stress_test_thread(void *arg) {
    test_context_t *ctx = (test_context_t*)arg;
    lockfree_hashtable_t *table = (lockfree_hashtable_t*)ctx->data_structure;
    
    // Wait for all threads to be ready
    pthread_barrier_wait(&ctx->start_barrier);
    
    unsigned int seed = (unsigned int)pthread_self();
    
    while (atomic_load(&ctx->test_running)) {
        float operation_type = (float)rand_r(&seed) / RAND_MAX;
        uint64_t key = rand_r(&seed) % 100000 + 1; // Avoid key 0
        uint64_t value = rand_r(&seed) % 100000 + 1;
        
        bool success = false;
        
        if (operation_type < ctx->insert_ratio) {
            success = lockfree_hashtable_insert(table, key, value);
        } else if (operation_type < ctx->insert_ratio + ctx->delete_ratio) {
            success = lockfree_hashtable_delete(table, key);
        } else {
            hash_entry_t *entry = find_entry(table, key, NULL);
            success = (entry != NULL);
        }
        
        atomic_fetch_add(&ctx->total_operations, 1);
        if (success) {
            atomic_fetch_add(&ctx->successful_operations, 1);
        } else {
            atomic_fetch_add(&ctx->failed_operations, 1);
        }
    }
    
    return NULL;
}

// Run stress test
void run_stress_test(test_context_t *ctx) {
    pthread_t *threads = malloc(ctx->num_threads * sizeof(pthread_t));
    
    // Initialize barrier
    pthread_barrier_init(&ctx->start_barrier, NULL, ctx->num_threads + 1);
    atomic_store(&ctx->test_running, true);
    
    // Record start time
    clock_gettime(CLOCK_MONOTONIC, &ctx->start_time);
    
    // Create threads
    for (int i = 0; i < ctx->num_threads; i++) {
        pthread_create(&threads[i], NULL, stress_test_thread, ctx);
    }
    
    // Start test
    pthread_barrier_wait(&ctx->start_barrier);
    
    // Run for specified duration
    sleep(ctx->test_duration_seconds);
    
    // Stop test
    atomic_store(&ctx->test_running, false);
    clock_gettime(CLOCK_MONOTONIC, &ctx->end_time);
    
    // Wait for threads to complete
    for (int i = 0; i < ctx->num_threads; i++) {
        pthread_join(threads[i], NULL);
    }
    
    pthread_barrier_destroy(&ctx->start_barrier);
    free(threads);
}

// Linearizability checker using operation logs
typedef struct operation_log {
    enum { OP_INSERT, OP_DELETE, OP_LOOKUP } type;
    uint64_t key;
    uint64_t value;
    struct timespec start_time;
    struct timespec end_time;
    bool success;
    int thread_id;
} operation_log_t;

// Simple linearizability check (history-based)
bool check_linearizability(operation_log_t *operations, int count) {
    // Sort operations by start time
    qsort(operations, count, sizeof(operation_log_t), compare_operations);
    
    // Build expected state based on successful operations
    uint64_t *expected_values = calloc(100001, sizeof(uint64_t)); // Key space
    
    for (int i = 0; i < count; i++) {
        operation_log_t *op = &operations[i];
        
        switch (op->type) {
            case OP_INSERT:
                if (op->success) {
                    expected_values[op->key] = op->value;
                }
                break;
                
            case OP_DELETE:
                if (op->success) {
                    expected_values[op->key] = 0;
                }
                break;
                
            case OP_LOOKUP:
                // Check if lookup result matches expected state
                uint64_t expected = expected_values[op->key];
                bool should_find = (expected != 0);
                
                if (op->success != should_find) {
                    printf("Linearizability violation: key %lu, expected %s, got %s\n",
                           op->key, should_find ? "found" : "not found",
                           op->success ? "found" : "not found");
                    free(expected_values);
                    return false;
                }
                break;
        }
    }
    
    free(expected_values);
    return true;
}

// Performance benchmarking
void benchmark_performance(void *data_structure, const char *structure_name) {
    printf("Benchmarking %s:\n", structure_name);
    
    test_context_t ctx = {
        .data_structure = data_structure,
        .num_threads = 8,
        .test_duration_seconds = 10,
        .insert_ratio = 0.4f,
        .delete_ratio = 0.2f,
        .lookup_ratio = 0.4f
    };
    
    atomic_store(&ctx.total_operations, 0);
    atomic_store(&ctx.successful_operations, 0);
    atomic_store(&ctx.failed_operations, 0);
    
    run_stress_test(&ctx);
    
    double elapsed_time = (ctx.end_time.tv_sec - ctx.start_time.tv_sec) +
                         (ctx.end_time.tv_nsec - ctx.start_time.tv_nsec) / 1e9;
    
    size_t total_ops = atomic_load(&ctx.total_operations);
    double throughput = total_ops / elapsed_time;
    
    printf("  Total operations: %zu\n", total_ops);
    printf("  Elapsed time: %.2f seconds\n", elapsed_time);
    printf("  Throughput: %.0f ops/sec\n", throughput);
    printf("  Success rate: %.2f%%\n", 
           100.0 * atomic_load(&ctx.successful_operations) / total_ops);
}