LFList.hpp

#include <iostream>
#include <thread>
#include <type_traits>

#include <unistd.h>
#include <cassert>

#include <atomic>

template <typename T, size_t kMaxSize = 4096>
struct LFList {
    using index_t                      = uint32_t;
    static const index_t kInvalidIndex = std::numeric_limits<index_t>::max();

    struct Ref {
        uint32_t version = 0;
        index_t  idx     = 0;
    };

    struct Node {
        std::atomic<index_t> next_idx;
        T                    val;
    };

    LFList() {
        head_ = Ref();
        for (index_t i = 0; i < kMaxSize; i++) {
            data_[i].val      = 0;
            data_[i].next_idx = i + 1;
        }
        // tail_                        = Ref{0, kMaxSize - 1};
        data_[kMaxSize - 1].next_idx = kInvalidIndex;
    }

    index_t push(T val) {
        Ref ref = head_.load();
        Ref next_ref;

        do {
            next_ref = {ref.version + 1, data_[ref.idx].next_idx};
            // assert(next_idx != kInvalidIndex);
        } while (!head_.compare_exchange_weak(ref, next_ref));

        assert(ref.idx != kInvalidIndex);
        assert(ref.idx != 0x12345678);
        assert(data_[ref.idx].next_idx != 0x12345678);

        data_[ref.idx].val = val;
        data_[ref.idx].next_idx = 0x12345678;

        return ref.idx;
    }

    T get(index_t idx) const { return data_[idx].val; }

    T operator[](index_t idx) const { return get(idx); };

    void remove(index_t idx) {
        // Ref ref = tail_.load();

        // assert(data_[idx].next_idx == 0x12345678);

        // data_[ref.idx].next_idx = kInvalidIndex;
        // Ref next_ref            = {ref.version + 1, idx};

        // do { data_[ref.idx].next_idx = idx; } while (!tail_.compare_exchange_weak(ref, next_ref));

        Ref ref = head_.load();

        assert(data_[idx].next_idx == 0x12345678);

        Ref next_ref;

        do {
            data_[idx].next_idx = ref.idx;
            next_ref            = Ref{ref.version + 1, idx};
        } while (!head_.compare_exchange_weak(ref, next_ref));
    }

    void print() {
        for (index_t i = 0; i < std::min(64UL, kMaxSize); i++) { printf("%3d ", data_[i].val); }
        printf("\n");
        for (index_t i = 0; i < std::min(64UL, kMaxSize); i++) { printf("%3d ", data_[i].next_idx); }
        printf("\n");
    }

private:
    alignas(64) std::atomic<Ref> head_;
    // alignas(64) std::atomic<Ref> tail_;
    Node data_[kMaxSize];
};

LFList<int, 1024> list;

void th_func() {
    const size_t cnt = 4;

    size_t idxs[cnt];

    for (int i = 0; i < 1024 * 256 / cnt; i++) {
        // for (size_t j = 0; j < cnt; j++) { idxs[j] = list.push(i); }

        // for (size_t j = 0; j < cnt; j++) { list.remove(idxs[j]); }

        size_t idx = list.push(i);
        list.remove(idx);
    }
}

int main() {
    std::thread th1(th_func);
    std::thread th2(th_func);
    std::thread th3(th_func);

    th1.join();
    th2.join();
    th3.join();

    // constexpr const size_t size = 5;
    // LFList<int, size>      list;

    // LFList<int>::index_t idx1 = list.push(6);
    // LFList<int>::index_t idx2 = list.push(7);
    // LFList<int>::index_t idx3 = list.push(8);

    // list.print();

    // list.remove(idx2);
    // LFList<int>::index_t idx4 = list.push(9);
    // LFList<int>::index_t idx5 = list.push(10);

    // list.print();

    // list.remove(idx3);
    // list.push(11);
    // list.print();

    // list.remove(idx4);
    // list.push(12);

    // list.print();

    return 0;
}