rcu

---

1. Reader-Writer Lock Implementation

#include <atomic>
#include <mutex>

class RCU {
public:
    void lock_for_reading() {
        ++readers_;
    }

    void unlock_after_reading() {
        --readers_;
    }

    void lock_for_writing() {
        while (readers_.load() != 0) {}
        ++writers_;
    }

    void unlock_after_writing() {
        --writers_;
    }

private:
    std::atomic<int> readers_{0};
    std::atomic<int> writers_{0};
};

2. Reference Counting with RCU

#include <atomic>

struct Node {
    Node* next;
    int value;
    std::atomic<int> ref_count;
};

void insert_node(Node* node) {
    // ...
    ++node->ref_count;
}

void remove_node(Node* node) {
    while (node->ref_count != 0) {}
    // ...
}

3. Concurrent Queue with RCU

#include <atomic>
#include <list>

struct Node {
    Node* next;
    int value;
};

class RCUQueue {
public:
    void enqueue(int value) {
        auto* node = new Node{nullptr, value};
        tail_->store(node, std::memory_order_release);
        tail_ = node;
        ++size_;
    }

    int dequeue() {
        while (true) {
            auto* head = head_.load(std::memory_order_acquire);
            auto* next = head->next;
            if (head == tail_.load(std::memory_order_acquire)) {
                return -1; // queue is empty
            }

            if (head_->compare_exchange_weak(head, next, std::memory_order_release)) {
                // successfully removed the head
                head->next = nullptr;
                --size_;
                return head->value;
            }
        }
    }

private:
    std::atomic<Node*> head_{nullptr};
    std::atomic<Node*> tail_{nullptr};
    std::atomic<int> size_{0};
};

4. Concurrent Map with RCU

#include <atomic>
#include <unordered_map>

class RCUMap {
public:
    void put(const std::string& key, int value) {
        auto* new_entry = new std::pair<const std::string, int>(key, value);
        auto old_entry = map_.load(std::memory_order_acquire);
        while (!map_.compare_exchange_weak(old_entry, new_entry, std::memory_order_release)) {}
    }

    int get(const std::string& key) {
        auto old_entry = map_.load(std::memory_order_acquire);
        auto it = old_entry->find(key);
        if (it == old_entry->end()) {
            return -1;
        }
        return it->second;
    }

private:
    std::atomic<std::unordered_map<std::string, int>*> map_{nullptr};
};

5. Time-Stamped Vector with RCU

#include <atomic>
#include <vector>

class TSVector {
public:
    void push_back(int value) {
        timestamp_.store(++timestamp_, std::memory_order_release);
        data_.push_back(value);
    }

    int get_at(int timestamp) {
        auto snapshot = data_[snapshot].load(std::memory_order_acquire);
        auto current_timestamp = timestamp_.load(std::memory_order_acquire);
        return snapshot < current_timestamp ? -1 : data_[snapshot];
    }

private:
    std::atomic<int> timestamp_{0};
    std::vector<std::atomic<int>> data_;
};

6. Lock-Free Stack with RCU

#include <atomic>

class LockFreeStack {
public:
    void push(int value) {
        auto* new_top = new Node{value, top_.load(std::memory_order_release)};
        while (!top_.compare_exchange_weak(new_top->next, new_top, std::memory_order_release)) {}
    }

    int pop() {
        while (true) {
            auto* top = top_.load(std::memory_order_acquire);
            if (top == nullptr) {
                return -1; // stack is empty
            }

            auto* next = top->next;
            if (top_->compare_exchange_weak(top, next, std::memory_order_release)) {
                // successfully popped the top
                return top->value;
            }
        }
    }

private:
    struct Node {
        int value;
        std::atomic<Node*> next;
    };

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

7. Non-Blocking Skip List with RCU

#include <atomic>
#include <vector>

class NBSkipList {
public:
    void insert(int value) {
        // ...
    }

    bool contains(int value) {
        // ...
    }

    int get(int index) {
        // ...
    }

private:
    struct Node {
        std::atomic<int> value;
        std::vector<std::atomic<Node*>> next;
    };
};

8. Concurrent Linked List with RCU

#include <atomic>

class RCUList {
public:
    void insert_after(Node* prev, int value) {
        auto* new_node = new Node{value, prev->next.load(std::memory_order_release)};
        while (!prev->next.compare_exchange_weak(new_node->next, new_node, std::memory_order_release)) {}
    }

    void remove(Node* node) {
        while (true) {
            auto* next = node->next.load(std::memory_order_acquire);
            if (node->next.compare_exchange_weak(next, next->next, std::memory_order_release)) {
                // successfully removed the node
                return;
            }
        }
    }

private:
    struct Node {
        int value;
        std::atomic<Node*> next;
    };
};

9. Concurrent Binary Tree with RCU

#include <atomic>

class RCUBinaryTree {
public:
    void insert(int value) {
        // ...
    }

    bool contains(int value) {
        // ...
    }

private:
    struct Node {
        std::atomic<int> value;
        std::atomic<Node*> left;
        std::atomic<Node*> right;
    };
};

10. Concurrent Hash Table with RCU

#include <atomic>
#include <unordered_map>

class RCUHashTable {
public:
    void put(const std::string& key, int value) {
        // ...
    }

    int get(const std::string& key) {
        // ...
    }

private:
    struct Entry {
        int value;
        std::atomic<Entry*> next;
    };

    std::unordered_map<std::string, Entry*> table;
};

11. Concurrent Graph with RCU

#include <atomic>
#include <unordered_map>

class RCUGraph {
public:
    void add_edge(int src, int dst) {
        // ...
    }

    std::vector<int> get_neighbors(int vertex) {
        // ...
    }

private:
    struct Vertex {
        std::atomic<Vertex*> next;
        int value;
    };

    std::unordered_map<int, Vertex*> vertices;
};

12. Concurrent Bloom Filter with RCU

#include <atomic>
#include <bitset>

class RCUBloomFilter {
public:
    void insert(const std::string& key) {
        // ...
    }

    bool contains(const std::string& key) {
        // ...
    }

private:
    std::atomic<std::bitset<256>> filter;
};

13. Concurrent Set with RCU

#include <atomic>
#include <unordered_set>

class RCUSet {
public:
    void insert(int value) {
        // ...
    }

    bool contains(int value) {
        // ...
    }

private:
    std::unordered_set<int> set;
};

14. Concurrent Counter with RCU

#include <atomic>

class RCUCounter {
public:
    void increment() {
        ++value_;
    }

    int get() {
        return value_.load(std::memory_order_acquire);
    }

private:
    std::atomic<int> value_{0};
};

15. Concurrent Queue with Multiple Readers and Single Writer (MRWS)

#include <atomic>
#include <list>

class MRWSQueue {
public:
    void enqueue(int value) {
        auto* node = new Node{nullptr, value};
        tail_->store(node, std::memory_order_release);
        tail_ = node;
        ++size_;
    }

    int dequeue() {
        while (true) {
            auto* head = head_.load(std::memory_order_acquire);
            auto* next = head->next;
            if (head == tail_.load(std::memory_order_acquire)) {
                return -1; // queue is empty
            }

            if (head_->compare_exchange_weak(head, next, std::memory_order_release)) {
                // successfully removed the head
                head->next = nullptr;
                --size_;
                return head->value;
            }
        }
    }

private:
    struct Node {
        Node* next;
        int value;
    };

    std::atomic<Node*> head_{nullptr};
    std::atomic<Node*> tail_{nullptr};
    std::atomic<int> size_{0};
};

16. Concurrent Queue with Graceful Shutdown

#include <atomic>
#include <list>

class ShutdownQueue {
public:
    void enqueue(int value) {
        lock_.lock();
        tail_->store(value, std::memory_order_release);
        tail_ = tail_->next;
        ++size_;
        lock_.unlock();
    }

    int dequeue() {
        while (true) {
            auto* head = head_.load(std::memory_order_acquire);
            auto* next = head->next;
            if (head == tail_.load(std::memory_order_acquire)) {
                if (shutdown_) {
                    return -1; // queue is empty and shutdown has occurred
                } else {
                    return -2; // queue is empty and shutdown has not occurred
                }
            }

            if (head_->compare_exchange_weak(head, next, std::memory_order_release)) {
                // successfully removed the head
                head->next = nullptr;
                --size_;
                return head->value;
            }
        }
    }

    void shutdown() {
        lock_.lock();
        shutdown_ = true;
        lock_.unlock();
    }

private:
    struct Node {
        Node* next;
        int value;
    };

    std::atomic<Node*> head_{nullptr};
    std::atomic<Node*> tail_{nullptr};
    std::atomic<int> size_{0};
    std::atomic<bool> shutdown_{false};
    std::mutex lock_;
};

17. Concurrent Queue with Batched Processing

#include <atomic>
#include <list>
#include <vector>

class BatchedQueue {
public:
    void enqueue(int value) {
        lock_.lock();
        tail_->store(value, std::memory_order_release);
        tail_ = tail_->next;
        ++size_;
        lock_.unlock();
    }

    int dequeue() {
        while (true) {
            auto* head = head_.load(std::memory_order_acquire);
            auto* next = head->next;
            if (head == tail_.load(std::memory_order_acquire)) {
                return -1; // queue is empty
            }

            if (head_->compare_exchange_weak(head, next, std::memory_order_release)) {
                // successfully removed the head
                head->next = nullptr;
                --size_;
                return head->value;
            }
        }
    }

    std::vector<int> dequeue_batch(int batch_size) {
        lock_.lock();
        std::vector<int> batch;
        for (int i = 0; i < batch_size; i++) {
            auto* head = head_.load(std::memory_order_acquire);
            auto* next = head->next;
            if (head == tail_.load(std::memory_order_acquire)) {
                break;
            }

            if (head_->compare_exchange_weak(head, next, std::memory_order_release)) {
                // successfully removed the head
                head->next = nullptr;
                --size_;
                batch.push_back(head->value);
            }
        }
        lock_.unlock();
        return batch;
    }

private:
    struct Node {
        Node* next;
        int value;
    };

    std::atomic<Node*> head_{nullptr};
    std::atomic<Node*> tail_{nullptr};
    std::atomic<int> size_{0};
    std::mutex lock_;
};

18. Concurrent Queue with Reader-Writer Locks

#include <atomic>
#include <condition_variable>
#include <list>
#include <mutex>

class RWLockQueue {
public:
    void enqueue(int value) {
        std::lock_guard<std::mutex> lock(writer_lock_);
        tail_->store(value, std::memory_order_release);
        tail_ = tail_->next;
        ++size_;
        writer_cv_.notify_all();
    }

    int dequeue() {
        std::unique_lock<std::mutex> lock(reader_lock_);
        while (head_ == tail_.load(std::memory_order_acquire)) {
            reader_cv_.wait(lock);
        }
        auto* head = head_.load(std::memory_order_acquire);
        auto* next = head->next;
        head_->compare_exchange_weak(head, next, std::memory_order_release);
        return head->value;
    }

private:
    struct Node {
        Node* next;
        int value;
    };

    std::atomic<Node*> head_{nullptr};
    std::atomic<Node*> tail_{nullptr};
    std::atomic<int> size_{0};
    std::mutex reader_lock_;
    std::mutex writer_lock_;
    std::condition_variable writer_cv_;
    std::condition_variable reader_cv_;
};

19. Concurrent Queue with Wait-Free Read

#include <atomic>
#include <list>

class WaitFreeReadQueue {
public:
    void enqueue(int value) {
        auto* new_tail = new Node{value, tail_.load(std::memory_order_release)};
        while (!tail_.compare_exchange_weak(new_tail->next, new_tail, std::memory_order_release)) {}
    }

    int dequeue() {
        while (true) {
            auto* head = head_.load(std::memory_order_acquire);
            auto* next = head->next;
            if (head == tail_.load(std::memory_order_acquire)) {
                return -1; // queue is empty
            }

            if (head_->compare_exchange_weak(head, next, std::memory_order_release)) {
                // successfully removed the head
                return head->value;
            }
        }
    }

private:
    struct Node {
        Node* next;
        int value;
    };

    std::atomic<Node*> head_{nullptr};
    std::atomic<Node*> tail_{nullptr};
};

20. Concurrent Queue with Lock-Free Insertion

#include <atomic>
#include <list>

class LockFreeInsertQueue {
public:
    void enqueue(int value) {
        auto* new_node = new Node{value, nullptr};
        while (true) {
            auto* tail = tail_.load(std::memory_order_acquire);
            auto* next = tail->next.load(std::memory_order_acquire);
            if (tail == tail_.load(std::memory_order_acquire)) {
                if (next == nullptr) {
                    // queue is empty, try to insert at the head
                    if (tail_->next.compare_exchange_weak(next, new_node, std::memory_order_release)) {
                        tail_ = new_node;
                        return;
                    }
                } else {
                    // queue is not empty, try to insert at the tail
                    if (tail_->compare_exchange_weak(tail, next, std::memory_order_release)) {
                        next->next.store(new_node, std::memory_order_release);
                        tail_ = new_node;
                        return;
                    }
                }
            }
        }
    }

    int dequeue() {
        while (true) {
            auto* head = head_.load(std::memory_order_acquire);
            auto* next = head->next;
            if (head == tail_.load(std::memory_order_acquire)) {
                return -1; // queue is empty
            }

            if (head_->compare_exchange_weak(head, next, std::memory_order_release)) {
                // successfully removed the head
                return head->value;
            }
        }
    }

private:
    struct Node {
        Node* next;
        int value;
    };

    std::atomic<Node*> head_{nullptr};
    std::atomic<Node*> tail_{nullptr};
};

21. Concurrent Queue with Lock-Free Deletion

#include <atomic>
#include <list>

class LockFreeDeleteQueue {
public:
    void enqueue(int value) {
        auto* new_node = new Node{value, nullptr};
        tail_->store(new_node, std::memory_order_release);
        tail_ = new_node;
        ++size_;
    }

    int dequeue() {
        while (true) {
            auto* head = head_.load(std::memory_order_acquire);
            auto* next = head->next;
            if (head == tail_.load(std::memory_order_acquire)) {
                return -1; // queue is empty
            }

            if (head_->compare_exchange_weak(head, next, std::memory_order_release)) {
                // successfully removed the head
                head->next = nullptr;
                --size_;
                return head->value;
            }
        }
    }

private:
    struct Node {
        Node* next;
        int value;
    };

    std::atomic<Node*> head_{nullptr};
    std::atomic<Node*> tail_{nullptr};
    std::atomic<int> size_{0};
};

22. Concurrent Queue with Wait-Free Enqueue and Dequeue

#include <atomic>
#include <list>

class WaitFreeQueue {
public:
    void enqueue(int value) {
        auto* new_node = new Node{value, nullptr};
        tail_.store(new_node, std::memory_order_release);
        if (head_.load(std::memory_order_acquire) == nullptr) {
            head_.store(new_node, std::memory_order_release);
        }
    }

    int dequeue() {
        while (true) {
            auto* head = head_.load(std::memory_order_acquire);
            auto* next = head->next;
            if (head == tail_.load(std::memory_order_acquire)) {
                return -1; // queue is empty
            }

            if (head_->compare_exchange_weak(head, next, std::memory_order_release)) {
                // successfully removed the head
                return head->value;
            }
        }
    }

private:
    struct Node {
        Node* next;
        int value;
    };

    std::atomic<Node*> head_{nullptr};
    std::atomic<Node*> tail_{nullptr};
};

23. Concurrent Stack with RCU

#include <atomic>

class RCU