xor.cpp

template <typename T>
auto xor_ptr(T* x, T* y) -> T *
{
    return reinterpret_cast<T*>(
        reinterpret_cast<std::uintptr_t>(x) ^ reinterpret_cast<std::uintptr_t>(y)
    );
}

template <typename T>
struct list_node
{
    T value;
    list_node<T> * link = nullptr;
};

template <typename T>
class list
{
public:
    using nodeptr_t = list_node<T> *;

    class iterator
    {
    public:
        using difference_type = ptrdiff_t;
        using value_type = T;

        auto operator*() const -> T &
        {
            return curr->value;
        }

        auto operator++() -> iterator &
        {
            advance();
            return *this;
        }

        auto operator++(int) -> iterator
        {
            auto copy = *this;
            advance();
            return copy;
        }

        auto operator==(const iterator& other) const -> bool
        {
            return prev == other.prev && curr == other.curr;
        }

        auto operator!=(const iterator& other) const -> bool
        {
            return !(*this == other);
        }

        nodeptr_t prev = nullptr;
        nodeptr_t curr = nullptr;
    private:

        void advance()
        {
            nodeptr_t next = xor_ptr(prev, curr->link);

            prev = curr;
            curr = next;
        }
    };

    list(std::size_t count, const T& value)
    {
        for (size_t i = 0; i < count; ++i)
        {
            push_back(value);
        }
    }

    list(std::initializer_list<T> init)
    {
        for (const T& i : init)
        {
            push_back(i);
        }
    }

    ~list() noexcept
    {
        auto it = begin();
        do
        {
            ++it;
            std::cout << "Deleted node{" << it.prev->value << "} at " << it.prev << "\n";
            delete it.prev;
        }
        while(it != end());
    }

    [[nodiscard]] auto size() const noexcept -> std::size_t
    {
        return _size;
    }

    [[nodiscard]] auto empty() const noexcept -> bool
    {
        return size() == 0;
    }

    auto begin() -> iterator
    {
        return {nullptr, _head};
    }

    auto end() -> iterator
    {
        return {_tail, nullptr};
    }

    template <std::convertible_to<T> U>
    void push_back(U&& value)
    {
        push(_tail, std::forward<U>(value));
    }

    template <std::convertible_to<T> U>
    void push_front(U&& value)
    {
        push(_head, std::forward<U>(value));
    }


private:
    std::size_t _size = 0;
    nodeptr_t _head = nullptr;
    nodeptr_t _tail = nullptr;

    template <std::convertible_to<T> U>
    void push(nodeptr_t & end, U&& value)
    {
        auto *node = new list_node<T>{
            .value = std::forward<U>(value),
            .link = nullptr
        };

        if (empty())
        {
            _head = node;
            _tail = node;
            _size = 1;
        }
        else
        {
            // 1. Update link to prev (current tail/head ptr) XOR'd with new (next) node
            end->link = xor_ptr(end->link, node);

            // 2. Update the xor_ptr of the new node
            node->link = end;

            // 3. Update the tail/head pointer
            end = node;

            // 4. Update list size
            ++_size;
        }
    }
};

static_assert(std::forward_iterator<list<int>::iterator>);