/*
 * The ABA problem typically arises in lock-free algorithms that rely on
 * Compare-And-Swap (CAS) operations. This snippet illustrates a conceptual
 * scenario, not necessarily a direct ABA bug, but how a shared pointer's
 * value can change and then revert.
 *
 * Consider a simplified lock-free stack pop operation.
 */

#include <atomic>
#include <memory>
#include <iostream>

// A basic node structure for a stack
struct Node {
    int value;
    Node* next;

    Node(int v) : value(v), next(nullptr) {}
};

std::atomic<Node*> head{nullptr};

void push(int val) {
    Node* new_node = new Node(val);
    new_node->next = head.load();
    while (!head.compare_exchange_weak(new_node->next, new_node));
}

// This 'pop' is conceptually vulnerable to ABA if memory is recycled quickly
// without proper safeguards. (Simplified for illustration, actual pop is more complex)
Node* pop_conceptual_aba_vulnerable() {
    Node* old_head = head.load();
    // In a real scenario, this loop would retry if CAS fails.
    // The ABA problem occurs if another thread pops 'old_head', then pushes a
    // *new* node that happens to occupy the same memory address as 'old_head',
    // before our CAS completes.
    while (old_head && !head.compare_exchange_weak(old_head, old_head->next)) {
        old_head = head.load(); // Reload head if CAS fails
    }
    return old_head; // Caller would then delete this node
}

int main() {
    std::cout << "Illustrating ABA problem's conceptual basis.\n";
    
    // Initial pushes
    push(10);
    push(20);
    push(30);

    Node* node_A = head.load(); // Points to node with value 30
    std::cout << "Initial head value: " << (node_A ? std::to_string(node_A->value) : "nullptr") << " (Address: " << node_A << ")\n";

    // Imagine another thread pops 30, then 20, then pushes 30 again (new node at old address)
    // This is hard to simulate deterministically without multiple threads and careful timing.
    // For demonstration, let's manually simulate the 'A -> B -> A' state change.

    Node* popped_30 = pop_conceptual_aba_vulnerable(); // Pop 30
    if (popped_30) {
        std::cout << "Popped value: " << popped_30->value << " (Address: " << popped_30 << ")\n";
        delete popped_30; // Memory for 30 is now freed
    }

    Node* popped_20 = pop_conceptual_aba_vulnerable(); // Pop 20
    if (popped_20) {
        std::cout << "Popped value: " << popped_20->value << " (Address: " << popped_20 << ")\n";
        delete popped_20; // Memory for 20 is now freed
    }

    // Now, imagine a new node is created that happens to get the same address as 'popped_30'
    // This is the 'A' again, but a *different* logical A.
    // We'll simulate this by pushing a new node and assigning it the address of 'popped_30' for demonstration.
    // In reality, this is non-deterministic memory allocation.
    Node* new_node_at_old_address = new Node(40); // Represents the new node
    // To force the ABA condition, we would need to ensure new_node_at_old_address
    // gets the exact same address as node_A (the original '30' node).
    // This is highly improbable in real allocations but is the core premise of ABA.
    
    // For illustrative purposes, let's assume 'head' was read as original 'node_A' (address X).
    // Then 'node_A' was popped, then another node (node_B) was popped, and then
    // a *new* node (node_C) was pushed which happens to get address X.
    // The original `pop_conceptual_aba_vulnerable` might still attempt `compare_exchange_weak(X, X->next)`
    // where X->next now points to something completely different than what was intended when X was first read.

    std::cout << "\nABA problem's essence: A pointer value 'A' is read, changes to 'B', then reverts to 'A'.\n";
    std::cout << "A Compare-And-Swap (CAS) operation, checking if the value is still 'A', succeeds even though\n";
    std::cout << "the underlying object or state has changed. This leads to incorrect logic.\n";
    
    // Clean up remaining nodes for good practice in a complete example
    Node* current = head.load();
    while (current) {
        Node* next = current->next;
        delete current;
        current = next;
    }

    return 0;
}

/*
 * This code demonstrates a simplified (and buggy) lock-free stack 'pop' operation
 * that is highly susceptible to the ABA problem when memory is aggressively recycled.
 * It uses std::atomic for the head pointer and simulates the conditions where
 * ABA could lead to incorrect pointer updates.
 *
 * To fully observe ABA, one would need multiple threads and specific scheduling,
 * which is non-deterministic. This example focuses on the structure that enables it.
 */

#include <atomic>
#include <thread>
#include <vector>
#include <iostream>
#include <chrono>
#include <stdexcept>

// A basic node structure for a stack
struct Node {
    int value;
    Node* next;

    // Keep track of allocation/deallocation to highlight reuse
    static std::atomic<long> alive_nodes;

    Node(int v) : value(v), next(nullptr) {
        alive_nodes++;
        //std::cout << "Node " << value << " allocated at " << this << " (alive: " << alive_nodes.load() << ")\n";
    }

    ~Node() {
        alive_nodes--;
        //std::cout << "Node " << value << " deallocated from " << this << " (alive: " << alive_nodes.load() << ")\n";
    }
};

std::atomic<long> Node::alive_nodes{0};

std::atomic<Node*> head{nullptr};

// Function to push a node onto the stack
void push(int val) {
    Node* new_node = new Node(val);
    new_node->next = head.load(std::memory_order_relaxed);
    // Loop until CAS succeeds
    while (!head.compare_exchange_weak(new_node->next, new_node, std::memory_order_release, std::memory_order_relaxed)) {
        // If CAS fails, new_node->next has been updated by compare_exchange_weak
        // to the current value of head. We retry with the new head.
    }
}

// Function to pop a node from the stack - VULNERABLE TO ABA
Node* pop_aba_vulnerable() {
    Node* old_head = head.load(std::memory_order_acquire);
    while (old_head != nullptr) {
        Node* next_node = old_head->next; // Read next pointer of current head
        // Attempt to swap head to next_node
        if (head.compare_exchange_weak(old_head, next_node, std::memory_order_release, std::memory_order_relaxed)) {
            return old_head; // Successfully popped
        }
        // If CAS failed, old_head was updated by compare_exchange_weak
        // to the current head, so loop continues with the new head value.
    }
    return nullptr; // Stack is empty
}

// Helper to simulate thread work and potential memory recycling
void simulate_thread_ops(int id, int num_ops) {
    for (int i = 0; i < num_ops; ++i) {
        // Simulate a mix of pushes and pops
        if ((id + i) % 2 == 0) {
            push(id * 100 + i);
            // std::this_thread::sleep_for(std::chrono::milliseconds(1)); // Induce contention
        } else {
            Node* node = pop_aba_vulnerable();
            if (node) {
                // Simulate memory recycling quickly after deallocation
                // In a real system, the OS/allocator reuses memory addresses.
                // We simply delete here, assuming the allocator is 'fast'.
                delete node;
                // std::this_thread::sleep_for(std::chrono::milliseconds(1)); // Induce contention
            }
        }
    }
}

int main() {
    std::cout << "\n--- Demonstrating ABA Vulnerability ---\n";
    std::cout << "Note: The ABA problem is highly non-deterministic and requires specific timings\n";
    std::cout << "to manifest. This code provides the structure that makes it possible.\n\n";

    // Initial pushes to get some elements on the stack
    for (int i = 0; i < 5; ++i) {
        push(i + 1);
    }
    std::cout << "Initial stack state. Head address: " << head.load() << "\n";

    // Create multiple threads that will aggressively push and pop
    const int num_threads = 4;
    const int ops_per_thread = 1000;
    std::vector<std::thread> threads;

    for (int i = 0; i < num_threads; ++i) {
        threads.emplace_back(simulate_thread_ops, i, ops_per_thread);
    }

    for (auto& t : threads) {
        t.join();
    }

    std::cout << "\n--- Simulation Complete ---\n";
    std::cout << "Final stack state. Head address: " << head.load() << "\n";
    std::cout << "Remaining nodes alive: " << Node::alive_nodes.load() << "\n";

    // Clean up any remaining nodes for correctness
    Node* current = head.load();
    while (current) {
        Node* next_node = current->next;
        delete current;
        current = next_node;
    }

    return 0;
}

/*
 * This code demonstrates the Tagged Pointer approach to mitigate the ABA problem.
 * Instead of just storing a pointer, we store a pair of (pointer, counter).
 * The counter is incremented with every logical modification to the pointer,
 * ensuring that even if the pointer value itself cycles back to an old address,
 * the counter value will be different, thus preventing the CAS from succeeding.
 *
 * We use a union or struct to represent the 64-bit tagged pointer for platforms
 * where a native DCAS (double-word compare-and-swap) is available (like some x86_64).
 * For C++, std::atomic<std::pair<T*, unsigned int>> is generally preferred for clarity
 * and portability, but often compiled down to `_Atomic_load_pair` and `_Atomic_compare_exchange_pair`
 * on platforms supporting it, or a mutex-protected emulation otherwise if not lock-free.
 *
 * For platforms without native DCAS (e.g., if std::atomic<std::pair> isn't lock-free),
 * bit manipulation on a single std::atomic<uintptr_t> can be used where the pointer
 * uses lower bits and the tag uses higher bits (requires aligned pointers).
 * We will demonstrate the std::atomic<std::pair<T*, unsigned int>> approach as it's cleaner C++.
 */

#include <atomic>
#include <thread>
#include <vector>
#include <iostream>
#include <chrono>
#include <utility> // For std::pair

// A basic node structure for a stack
struct Node {
    int value;
    Node* next;
    Node(int v) : value(v), next(nullptr) {}
};

// Use std::pair to store pointer and tag (counter)
// This will typically be lock-free on 64-bit systems for 64-bit pointers + 32-bit tag,
// effectively acting as a DCAS. Check with is_lock_free().
std::atomic<std::pair<Node*, unsigned int>> head_with_tag{{nullptr, 0}};

void push(int val) {
    Node* new_node = new Node(val);
    std::pair<Node*, unsigned int> old_head_pair = head_with_tag.load(std::memory_order_relaxed);
    
    // Loop until CAS succeeds
    do {
        new_node->next = old_head_pair.first;
        // Increment tag for the new state
        // The tag should logically increment for the *new* head value
        // but here it increments for the *entire* head_with_tag pair.
        // The important part is that the tag changes if old_head_pair.first changes.
        // If 'head_with_tag' changes due to another thread, 'old_head_pair' will be updated
        // by 'compare_exchange_weak', and the new tag will be used in the next iteration.

    } while (!head_with_tag.compare_exchange_weak(
        old_head_pair, // Expected value: current head_with_tag
        {new_node, old_head_pair.second + 1}, // New value: new_node with incremented tag
        std::memory_order_release, std::memory_order_relaxed));
}

Node* pop_aba_fixed_with_tag() {
    std::pair<Node*, unsigned int> old_head_pair = head_with_tag.load(std::memory_order_acquire);
    Node* old_head = old_head_pair.first;

    while (old_head != nullptr) {
        Node* next_node = old_head->next;
        unsigned int new_tag = old_head_pair.second + 1; // Increment tag for the new state
        
        if (head_with_tag.compare_exchange_weak(
            old_head_pair, // Expected: current head_with_tag (pointer AND tag)
            {next_node, new_tag}, // New value: next_node with new tag
            std::memory_order_release, std::memory_order_relaxed)) {
            return old_head; // Successfully popped
        }
        // If CAS fails, old_head_pair is updated by compare_exchange_weak
        // to the current head_with_tag, loop continues with new values.
        old_head = old_head_pair.first;
    }
    return nullptr; // Stack is empty
}

// Helper to push some initial elements
void initial_push() {
    for (int i = 0; i < 5; ++i) {
        push(i + 1);
    }
    std::cout << "Initial stack state (tagged). Head address: " << head_with_tag.load().first 
              << ", Tag: " << head_with_tag.load().second << "\n";
}

// Helper to simulate concurrent pop operations
void concurrent_pop_ops(int id, int num_pops) {
    for (int i = 0; i < num_pops; ++i) {
        Node* node = pop_aba_fixed_with_tag();
        if (node) {
            // std::cout << "Thread " << id << " popped " << node->value << " (Tag: -) from " << node << "\n";
            delete node; // Simulate memory recycling
        } else {
            // std::cout << "Thread " << id << " found stack empty.\n";
        }
        // std::this_thread::sleep_for(std::chrono::microseconds(10));
    }
}

int main() {
    std::cout << "\n--- Demonstrating ABA Mitigation with Tagged Pointers ---\n";
    
    std::cout << "std::atomic<std::pair<Node*, unsigned int>> is lock-free: " 
              << std::atomic<std::pair<Node*, unsigned int>>{}.is_lock_free() << "\n\n";
    
    initial_push();

    const int num_threads = 4;
    const int pops_per_thread = 5;
    std::vector<std::thread> threads;

    for (int i = 0; i < num_threads; ++i) {
        threads.emplace_back(concurrent_pop_ops, i, pops_per_thread);
    }

    for (auto& t : threads) {
        t.join();
    }

    std::cout << "\n--- Simulation Complete ---\n";
    std::cout << "Final stack state (tagged). Head address: " << head_with_tag.load().first 
              << ", Tag: " << head_with_tag.load().second << "\n";

    // Clean up any remaining nodes for correctness
    Node* current_node = head_with_tag.load().first;
    while (current_node) {
        Node* next_node = current_node->next;
        delete current_node;
        current_node = next_node;
    }

    return 0;
}

/*
 * This conceptual code illustrates the principles of Hazard Pointers for safe memory reclamation
 * in lock-free data structures, specifically to prevent ABA-related issues during memory reuse.
 * Implementing a full Hazard Pointer manager is complex and typically involves a global or per-thread
 * array of pointers, a garbage collection mechanism, and careful synchronization.
 *
 * This example focuses on the core idea: A thread registers a pointer it's currently observing
 * (making it 'hazardous' to deallocate) before attempting a CAS. If the CAS succeeds, the old
 * node is moved to a 'retired' list, to be deleted only when no other thread declares it 'hazardous'.
 *
 * Note: This is a simplified, incomplete illustration of the *concept* and is NOT a production-ready
 * Hazard Pointer implementation. Real implementations are significantly more involved.
 */

#include <atomic>
#include <thread>
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
#include <mutex>

// --- Simplified Node Structure ---
struct Node {
    int value;
    Node* next;
    Node(int v) : value(v), next(nullptr) {}
};

// --- Simplified Hazard Pointer Manager Concept --- (Highly conceptual)
// In a real system, this would be per-thread or managed globally with more sophistication.
// For illustration, we'll use a global set and a mutex, which makes it NOT lock-free
// for the manager itself, but the *data structure operations* remain conceptually lock-free.

std::set<void*> global_hazard_pointers; // Pointers currently being 'read' by threads
std::mutex hazard_mtx; // Protects access to global_hazard_pointers

void add_hazard(void* ptr) {
    std::lock_guard<std::mutex> lock(hazard_mtx);
    global_hazard_pointers.insert(ptr);
}

void remove_hazard(void* ptr) {
    std::lock_guard<std::mutex> lock(hazard_mtx);
    global_hazard_pointers.erase(ptr);
}

bool is_hazardous(void* ptr) {
    std::lock_guard<std::mutex> lock(hazard_mtx);
    return global_hazard_pointers.count(ptr) > 0;
}

// --- Lock-Free Stack (Hazard Pointer protected POP - CONCEPTUAL) ---
std::atomic<Node*> head{nullptr};

void push(int val) {
    Node* new_node = new Node(val);
    new_node->next = head.load(std::memory_order_relaxed);
    while (!head.compare_exchange_weak(new_node->next, new_node, std::memory_order_release, std::memory_order_relaxed));
}

// A retired list for nodes that are logically removed but not yet safely deallocated
std::vector<Node*> retired_nodes;
std::mutex retired_mtx;

// Pop with Hazard Pointers (Conceptual steps)
Node* pop_with_hazard_pointers_conceptual() {
    Node* old_head = nullptr;
    Node* next_node = nullptr;

    do {
        old_head = head.load(std::memory_order_acquire);
        if (old_head == nullptr) return nullptr;

        // 1. Declare 'old_head' as hazardous (we are observing it)
        add_hazard(old_head);

        // 2. Re-read head. If it changed, our hazard pointer might be stale. Loop.
        //    This check is crucial: if head changed (e.g., to A->B->A and old_head is the *first* A)
        //    then our hazard might be pointing to a different A, but since we re-check, we'll restart
        //    and hazard the new head. If old_head is *still* the current head, then it's safe to proceed.
        if (head.load(std::memory_order_acquire) != old_head) {
            remove_hazard(old_head);
            continue; // Retry the loop
        }

        next_node = old_head->next; // Read next pointer *after* hazarding old_head

        // 3. Attempt CAS. If it succeeds, old_head is logically removed.
    } while (!head.compare_exchange_weak(old_head, next_node, std::memory_order_release, std::memory_order_relaxed));

    // 4. Remove hazard for old_head (no longer observing it directly)
    remove_hazard(old_head);
    
    // 5. Place old_head on a 'retired' list. It will be deleted later by a garbage collector
    //    when no other threads have it as a hazard pointer.
    std::lock_guard<std::mutex> lock(retired_mtx);
    retired_nodes.push_back(old_head);
    // A real system would then periodically scan retired_nodes and global_hazard_pointers
    // to find and delete non-hazardous retired nodes.
    std::cout << "Node " << old_head->value << " logically popped and retired.\n";

    return old_head; // Return the logically popped node
}

// --- Main for conceptual demonstration ---
int main() {
    std::cout << "\n--- Hazard Pointers: Conceptual Demonstration ---\n";
    std::cout << "Hazard Pointers solve ABA by delaying memory reclamation.\n\n";

    push(10);
    push(20);
    push(30);

    std::cout << "Initial head: " << head.load() << "\n";

    // Simulate multiple threads popping
    const int num_threads = 2;
    const int num_pops_per_thread = 2;
    std::vector<std::thread> threads;

    for(int i = 0; i < num_threads; ++i) {
        threads.emplace_back([i, num_pops_per_thread](){
            for(int j = 0; j < num_pops_per_thread; ++j) {
                Node* node = pop_with_hazard_pointers_conceptual();
                // In a real system, the caller would not delete the node directly here.
                // The memory manager handles actual deallocation.
                // We simply acknowledge the logical pop.
                if(node) { 
                    // std::cout << "Thread " << i << " handled node " << node->value << "\n";
                }
            }
        });
    }

    for(auto& t : threads) {
        t.join();
    }

    std::cout << "\n--- Post-Pop State ---\n";
    std::cout << "Final head: " << head.load() << "\n";
    
    // In a real system, a dedicated thread or periodic check would clean up retired_nodes
    // based on whether they are still hazardous.
    std::cout << "\nRetired nodes (pending safe deletion):\n";
    std::lock_guard<std::mutex> lock(retired_mtx);
    for(Node* node : retired_nodes) {
        std::cout << " - Value: " << node->value << " at " << node << "\n";
        // For this conceptual example, we'll just delete them at the end if not hazardous
        // A real system would check against global_hazard_pointers first.
        delete node;
    }
    retired_nodes.clear();
    
    std::cout << "Remaining elements on stack: (should be 0 or 1 if 5 pops happened and 3 pushes)\n";
    // Manually clean up any remaining nodes for strict correctness in this example
    Node* current = head.load();
    while(current) {
        Node* next_node = current->next;
        delete current;
        current = next_node;
    }

    return 0;
}

/*
 * This section focuses on conceptual best practices rather than executable code.
 * The principles discussed here guide the design and implementation of robust
 * lock-free systems to inherently avoid or mitigate issues like ABA.
 */

// No executable code for this section, as it discusses architectural and design principles.
// We instead provide comments on what robust code *would* entail.

/*
// Example of a conceptual lock-free queue with careful memory management (pseudo-code):

struct Node { /* ... */ };

// Custom allocator/deleter for lock-free structures
// Manages a pool of nodes to reduce reliance on global allocator
// and control reuse, potentially integrating a tagged pointer or hazard pointer system.
class LockFreeAllocator {
public:
    Node* allocate() {
        // Acquire a node from a pre-allocated pool or a custom recycled list.
        // Ensure that nodes are sufficiently 'aged' or tagged to prevent immediate ABA.
        // If a recycling mechanism is used, it must be ABA-safe.
        return new Node(); // Simplified
    }

    void deallocate(Node* node) {
        // Do NOT immediately delete. Place on a 'to-be-reclaimed' list.
        // A background thread or a 'quiescent state' mechanism will eventually delete it.
        // This is where Hazard Pointers or RCU principles are applied.
        delete node; // Simplified; real systems use complex reclamation.
    }
};

// Example of a lock-free data structure leveraging Tagged Pointers
struct TaggedPointer {
    Node* ptr;
    unsigned int tag;
};

std::atomic<TaggedPointer> head_tagged{ {nullptr, 0} };

void safe_push(int val) {
    Node* new_node = LockFreeAllocator().allocate();
    new_node->value = val;
    
    TaggedPointer old_head_tagged = head_tagged.load();
    do {
        new_node->next = old_head_tagged.ptr;
        // Ensure atomic update of both pointer and tag
    } while (!head_tagged.compare_exchange_weak(
        old_head_tagged,
        {new_node, old_head_tagged.tag + 1}
    ));
}

Node* safe_pop() {
    TaggedPointer old_head_tagged = head_tagged.load();
    Node* popped_node = nullptr;

    do {
        if (old_head_tagged.ptr == nullptr) return nullptr;
        popped_node = old_head_tagged.ptr;
        // Ensure atomic update of both pointer and tag
    } while (!head_tagged.compare_exchange_weak(
        old_head_tagged,
        {popped_node->next, old_head_tagged.tag + 1}
    ));

    // The 'popped_node' is now logically removed. It should NOT be deleted here.
    // Instead, it's handed to the LockFreeAllocator for safe reclamation.
    LockFreeAllocator().deallocate(popped_node);
    return popped_node;
}

// Key takeaways:
// 1. Decouple logical removal from physical deallocation.
// 2. Utilize Tagged Pointers for pointer integrity.
// 3. Implement robust memory reclamation (Hazard Pointers, RCU, Epoch-based). 
// 4. Thorough testing with stress loads and memory sanitizers.
*/