Compiler Explorer

Source code

#pragma once

#include <memory>
#include <utility>
#include <iostream>
#include <assert.h>

template <typename T, typename Allocator = std::allocator<T>>
class LinkList {
public:
    struct ListNodeBase {
        ListNodeBase* next = nullptr;
    };

struct ListNode : ListNodeBase {
        T value;
    };

struct ListImpl {
        size_t size = 0;
        ListNodeBase header;
    };

using alloc_traits = std::allocator_traits<Allocator>;
    using node_alloc_traits = typename std::allocator_traits<Allocator>::template rebind_traits<ListNode>;
    using node_alloc_type = typename std::allocator_traits<Allocator>::template rebind_alloc<ListNode>;
    constexpr static auto NoException = typename alloc_traits::is_always_equal();

public:

LinkList() = default;

LinkList(const Allocator& a) : alloc(a) { }

// ----------------------------- const& -----------------------------
    LinkList(const LinkList& other, const Allocator& a) : alloc(a) {
        assign_from_another_list(other);
    }

LinkList(const LinkList& other) 
        : LinkList(other, node_alloc_traits::select_on_container_copy_construction(other.alloc)) 
    { }

LinkList& operator=(const LinkList& other) {
        constexpr auto POCCA = typename alloc_traits::propagate_on_container_copy_assignment();
        if (this != std::addressof(other)) {
            clear();
            if constexpr (POCCA)
                alloc = other.alloc;
            assign_from_another_list(other);
        }
        return *this;
    }

// ------------------------------- && -------------------------------
    LinkList(LinkList&& other, const Allocator& a) noexcept(NoException) : alloc(a) {
        if (other.alloc == a) {
            impl = std::exchange(other.impl, ListImpl());
        } else {
            move_from_another_list(std::move(other));
            // Each object after moving should not be used again, so 
            // this step is not necessary in C++. 
            // Rust may report an error if we use a moved object.
            other.clear(); 
        }
    }

LinkList(LinkList&& other) noexcept(NoException) 
        : impl(std::exchange(other.impl, ListImpl())), alloc(std::move(other.alloc)) {
        assert(other.is_empty_list());
    }

LinkList& operator=(LinkList&& other) noexcept(NoException) {
        constexpr auto POCMA = typename alloc_traits::propagate_on_container_move_assignment();
        if (this != std::addressof(other)) {
            clear();
            if constexpr (POCMA) {
                // Same as LinkList(LinkList&& other)
                alloc = std::move(other.alloc);
                impl = std::exchange(other.impl, ListImpl());
            } else {
                // Same as LinkList(LinkList&& other, const Allocator& a)
                if (alloc == other.alloc) {
                    impl = std::exchange(other.impl, ListImpl());
                } else {
                    move_from_another_list(other);
                    other.clear(); 
                }
            }
        }
        assert(other.is_empty_list() && "We always making other empty.");
        return *this;
    }

~LinkList() {
        // std::cout << "~LinkList Called\n";
        clear();
        assert(is_empty_list());
    }

// ------------------------------- swap -----------------------------
    void swap(LinkList& other) noexcept(NoException) {
        std::swap(impl, other.impl);
        if constexpr (typename alloc_traits::propagate_on_container_swap())
            std::swap(alloc, other.alloc);
    }

// -------------------------- other functions ------------------------

Allocator get_allocator() { return alloc; }

size_t size() const { return impl.size; }

ListNodeBase* first_node() { return impl.header.next; }

// Check whether the list is empty, not only size is 0 but also header.next is null pointer.
    bool is_empty_list() const { return impl.size == 0 && impl.header.next == nullptr; }

template <typename... Args>
    ListNode* emplace_front(Args&&... args) {
        auto node = make_node((Args&&) args...);
        node->next = impl.header.next;
        impl.header.next = node;
        impl.size++;
        return node;
    }

void clear() {
        auto p = impl.header.next;
        while (p) {
            auto q = p->next;
            drop_node(static_cast<ListNode*>(p));
            p = q;
        }
        impl = ListImpl();
    }

void show() const {
        for (auto p = impl.header.next; p; p = p->next) {
            std::cout << static_cast<const ListNode*>(p)->value << ' ';
        }
        std::cout << '\n';
    }

// private:

void assign_from_another_list(const LinkList& other) {
        assert(impl.size == 0 && !impl.header.next && "only for empty list.");
        auto cur = &impl.header;
        for (auto p = other.impl.header.next; p; p = p->next) {
            auto node = make_node(static_cast<ListNode*>(p)->value);
            cur->next = static_cast<ListNodeBase*>(node);
            cur = node;
        }
        impl.size = other.size();
    }

void move_from_another_list(LinkList& other) {
        assert(impl.size == 0 && !impl.header.next && "only for empty list.");
        auto cur = &impl.header;
        for (auto p = other.impl.header.next; p; p = p->next) {
            auto node = make_node(std::move(static_cast<ListNode*>(p)->value));
            cur->next = static_cast<ListNodeBase*>(node);
            cur = node;
        }
        impl.size = other.size();
    }

template <typename... Args>
    ListNode* make_node(Args&&... args) {
        node_alloc_type node_alloc(alloc);
        // C-style: malloc + init
        auto node = node_alloc_traits::allocate(node_alloc, 1);
        node->next = nullptr;
        // T may overload operator&, so we use std::addressof to access the address of value.
        node_alloc_traits::construct(node_alloc, std::addressof(node->value), (Args&&) args...);
        return node;
    }

void drop_node(ListNode* node) {
        node_alloc_type node_alloc(alloc);
        node_alloc_traits::destroy(node_alloc, std::addressof(node->value));
        node_alloc_traits::deallocate(node_alloc, node, 1);
    }

ListImpl impl;
    [[no_unique_address]] Allocator alloc;
};

Source code

#pragma once

#include <memory>
#include <utility>
#include <set>
#include <limits>
#include <format>
#include <iostream>

#include <stdlib.h>
#include <string.h>

template <typename T>
struct tracked 
{
    tracked() = default;

tracked(const T& val) : m_val(val) { }

tracked(const tracked& other) 
        : m_val(other.m_val),
          m_num_copies(other.m_num_copies),
          m_num_moves(other.m_num_moves) 
    {
        ++(*m_num_copies);
    }

tracked(tracked&& other) 
        : m_val(std::move(other.m_val)),
          m_num_copies(std::move(other.m_num_copies)),
          m_num_moves(std::move(other.m_num_moves)) 
    {
        ++(*m_num_moves);
    }

tracked& operator=(const tracked& other)
    {
        m_val = other.m_val;
        m_num_copies = other.m_num_copies;
        m_num_moves = other.m_num_moves;
        ++(*m_num_copies);
    }

tracked& operator=(tracked&& other)
    {
        m_val = std::move(other.m_val);
        m_num_copies = std::move(other.m_num_copies);
        m_num_moves = std::move(other.m_num_moves);
        ++(*m_num_moves);
    }

friend bool operator==(const tracked& lhs, const tracked& rhs) 
    {
        return lhs.m_val == rhs.m_val;
    }

const T& val() const { return m_val; }

size_t num_copies() { return *m_num_copies; }
    size_t num_moves() { return *m_num_moves; }

T m_val;
    std::shared_ptr<size_t> m_num_moves = std::make_shared<size_t>(0);
    std::shared_ptr<size_t> m_num_copies = std::make_shared<size_t>(0);
};

enum alloc_spec
{
    PropagateOnCopy = 1,
    PropagateOnMove = 2,
    PropagateOnSwap = 4,
};

struct alloc_state 
{
    size_t m_num_allocs = 0;
    std::set<void*> m_owned;
};

template <bool B>
struct true_or_false : std::conditional<B, std::true_type, std::false_type> { };

template <bool B>
using true_or_false_t = typename true_or_false<B>::type;

template <typename T, 
    int Spec = PropagateOnCopy | PropagateOnMove | PropagateOnSwap>
struct checked_allocator
{
    using value_type = T;

checked_allocator() = default;

checked_allocator(size_t id) : m_id(id) { }

checked_allocator(const checked_allocator&) = default;

checked_allocator& operator=(const checked_allocator& other) = default;

template <typename U>
    checked_allocator(const checked_allocator<U, Spec>& other)
        : m_id(other.m_id), m_state(other.m_state) { }

template <typename U>
    struct rebind { using other = checked_allocator<U, Spec>; };

using propagate_on_container_copy_assignment = true_or_false_t<(Spec & PropagateOnCopy) != 0>;

using propagate_on_container_move_assignment = true_or_false_t<(Spec & PropagateOnMove) != 0>;

using propagate_on_container_swap = true_or_false_t<(Spec & PropagateOnSwap) != 0>;

checked_allocator select_on_container_copy_construction() const 
    {
        if constexpr (Spec & PropagateOnCopy)
            return *this;
        else
            return {}; // return a new allocator which has it's own memory
    }

T* allocate(size_t n)
    {
        T* ptr = std::allocator<T>().allocate(n);
        track_alloc(ptr);
        return ptr;
    }

void deallocate(T* ptr, size_t n) 
    {
        memset(ptr, 0, n * sizeof(T));
        track_dealloc(ptr);
        return std::allocator<T>().deallocate(ptr, n);
    }

friend bool operator==(const checked_allocator& lhs, const checked_allocator& rhs) 
    {
        return lhs.m_id == rhs.m_id;
    }

size_t num_allocs() const { return m_state->m_num_allocs; }

friend void swap(checked_allocator& lhs, checked_allocator& rhs)
    {
        lhs.swap(rhs);
    }

friend std::ostream& operator<<(std::ostream& os, const checked_allocator& a)
    {
        return os << std::format("alloc({})", a.m_id);
    }

void track_alloc(void* ptr)
    {
        auto state = m_state.get();
        ++state->m_num_allocs;
        if (!state->m_owned.insert(ptr).second)
        {
            std::cout << *this;
            std::cout << std::format(" got previously allocated memory: {}", ptr);
        }
    }

void track_dealloc(void* ptr)
    {
        if (m_state->m_owned.erase(ptr) != 1)
        {
            std::cout << *this;
            std::cout << std::format(" deleting memory owned by another allocator: {}", ptr);
        }
    }

size_t m_id = std::numeric_limits<size_t>::max();
    std::shared_ptr<alloc_state> m_state = std::make_shared<alloc_state>();
};

Source code

#include <memory>
#include <memory_resource>

#include <format>
#include <string>
#include <assert.h>

#include "checked_allocator.hpp"
#include "linklist.hpp"

void insert_elemets(auto& list) {

assert(list.size() == 0 && "empty size");
    assert(!list.first_node() && "no node in list");

// insert elements => [1, 2, 3]
    list.emplace_front(3);
    list.emplace_front(2);
    list.emplace_front(1);
 
    assert(list.size() == 3);
}

template <int Spec>
struct Test {

using Alloc = checked_allocator<tracked<int>, Spec>;

using List = LinkList<tracked<int>, Alloc>;

Test() {
        assert(a1 == l1.alloc);
        assert(a2 != l1.alloc);
    }

Alloc a1 = Alloc(1); // id = 1
    List l1 = List(a1);
    Alloc a2 = Alloc(2);

};

// Copy only associate with propagate_on_container_copy_assignment
void test_propagate_on_all_copy_construction() {

using T = Test<0b111>;

T t;
    auto node = t.l1.emplace_front(0);

T::List u(t.l1); // copy ctor

assert(t.l1.alloc.num_allocs() == 2);
    assert(node->value.num_moves() == 0);
    assert(node->value.num_copies() == 1);
}

void test_propagate_on_nocopy_copy_construction() {

using T = Test<PropagateOnMove | PropagateOnSwap>;
    
    T t;
    auto node = t.l1.emplace_front(0);

T::List u(t.l1); // copy ctor

assert(t.l1.alloc.num_allocs() == 1);
    assert(node->value.num_moves() == 0);
    assert(node->value.num_copies() == 1);
    assert(u.get_allocator().num_allocs() == 1);
}

void test_propagate_on_all_copy_assignment() {

using T = Test<0b111>;

T t;
    auto node = t.l1.emplace_front(0);

T::List l2(t.a1);

l2 = t.l1;

assert(t.a1.num_allocs() == 2);
    assert(node->value.num_moves() == 0);
    assert(node->value.num_copies() == 1);
}

void test_propagate_on_nocopy_copy_assignment() {

using T = Test<PropagateOnMove | PropagateOnSwap>;

T t;
    auto node = t.l1.emplace_front(0);

T::List l2(t.a1);

l2 = t.l1;

assert(t.a1.num_allocs() == 2);
    assert(node->value.num_moves() == 0);
    assert(node->value.num_copies() == 1);
}

void test_propagate_on_all_copy_assignment_with_different_alloc() {

using T = Test<0b111>;

T t;
    auto node = t.l1.emplace_front(0);

T::List l2(t.a2);

l2 = t.l1;

assert(t.a1 == l2.get_allocator());
    assert(t.a1.num_allocs() == 2);
    assert(t.a2.num_allocs() == 0);
    assert(node->value.num_moves() == 0);
    assert(node->value.num_copies() == 1);
}

void test_propagate_on_nocopy_copy_assignment_with_different_alloc() {

using T = Test<PropagateOnMove | PropagateOnSwap>;

T t;
    auto node = t.l1.emplace_front(0);

T::List l2(t.a2);

l2 = t.l1;

assert(t.a2 == l2.get_allocator());
    assert(t.a1.num_allocs() == 1);
    assert(t.a2.num_allocs() == 1);
    assert(node->value.num_moves() == 0);
    assert(node->value.num_copies() == 1);
}

// Move only associate with propagate_on_container_move_assignment
void test_propagate_on_all_move_construction() {

using T = Test<0b111>;

T t;
    auto node = t.l1.emplace_front(0);

T::List u(std::move(t.l1)); // copy ctor

assert(t.a1.num_allocs() == 1);
    assert(node->value.num_moves() == 0);
    assert(node->value.num_copies() == 0);
}

void test_propagate_on_all_move_assignment() {

using T = Test<0b111>;

T t;
    auto node = t.l1.emplace_front(0);

T::List u(t.a1); // copy ctor

u = std::move(t.l1);

assert(u.get_allocator() == t.a1);
    assert(t.a1.num_allocs() == 1);
    assert(node->value.num_moves() == 0);
    assert(node->value.num_copies() == 0);
}

void test_propagate_on_nomove_move_assignment() {

using T = Test<PropagateOnCopy | PropagateOnSwap>;

T t;
    auto node = t.l1.emplace_front(0);

T::List u(t.a1); // copy ctor

u = std::move(t.l1);

assert(u.get_allocator() == t.a1);
    assert(t.a1.num_allocs() == 1);
    assert(node->value.num_moves() == 0);
    assert(node->value.num_copies() == 0);
}

void test_propagate_on_all_move_assignment_with_different_alloc() {

using T = Test<0b111>;

T t;
    auto node = t.l1.emplace_front(0);

T::List u(t.a2); // copy ctor

u = std::move(t.l1);

assert(u.get_allocator() == t.a1);
    assert(t.a1.num_allocs() == 1);
    assert(t.a2.num_allocs() == 0);
    assert(node->value.num_moves() == 0);
    assert(node->value.num_copies() == 0);
}

void test_propagate_on_nomove_move_assignment_with_different_alloc() {

using T = Test<PropagateOnCopy | PropagateOnSwap>;

T t;
    auto node = t.l1.emplace_front(0);

T::List u(t.a2); // copy ctor

u = std::move(t.l1);

auto node1 = static_cast<T::List::ListNode*>(u.first_node());

assert(u.get_allocator() == t.a2);
    assert(t.a1.num_allocs() == 1);
    assert(t.a2.num_allocs() == 1);
    assert(node1->value.num_moves() == 1);
    assert(node1->value.num_copies() == 0);
}

// Swap
void test_propagate_on_all_swap() {

using T = Test<PropagateOnCopy | PropagateOnSwap>;

T t;
    auto node = t.l1.emplace_front(0);
    
    T::List l2(t.a2);

l2.swap(t.l1);

// Swap alloc
    assert(t.a1 == l2.get_allocator());
    assert(t.a2 == t.l1.get_allocator());

assert(1 == t.a1.num_allocs());
    assert(0 == t.a2.num_allocs());
    assert(0 == node->value.num_moves());
    assert(0 == node->value.num_copies());
}

int main(int argc, char const *argv[]) {

test_propagate_on_all_copy_construction();
    test_propagate_on_nocopy_copy_construction();
    
    test_propagate_on_all_copy_assignment();
    test_propagate_on_nocopy_copy_assignment();
    test_propagate_on_all_copy_assignment_with_different_alloc();
    test_propagate_on_nocopy_copy_assignment_with_different_alloc();

test_propagate_on_all_move_construction();
    
    test_propagate_on_all_move_assignment();
    test_propagate_on_nomove_move_assignment();
    test_propagate_on_all_move_assignment_with_different_alloc();
    test_propagate_on_nomove_move_assignment_with_different_alloc();

test_propagate_on_all_swap();

std::cout << "OK\n";
    return 0;
}

// -------------------- std::allocator --------------------------------

using Allocator = std::allocator<int>;
using AllocTraits = std::allocator_traits<Allocator>;

// std::allocator是一个空类，
// 采用::operator new申请内存，::operator delete释放内存。
static_assert(std::is_empty_v<Allocator>);

static_assert(!AllocTraits::propagate_on_container_copy_assignment());
// https://www.appsloveworld.com/cplus/100/205/why-does-stdallocator-require-propagate-on-container-move-assignment-to-be-true
static_assert(AllocTraits::propagate_on_container_move_assignment());
static_assert(!AllocTraits::propagate_on_container_swap());
static_assert(AllocTraits::is_always_equal());

// ---------------- std::pmr::polymorphic_allocator -------------------
using PmrAllocator = std::pmr::polymorphic_allocator<int>;
using PmrAllocTraits = std::allocator_traits<PmrAllocator>;

// std::pmr::polymorphic_allocator内部有一个memory_resource*，内存方面的操作都是由
// 该字段完成。

static_assert(!PmrAllocTraits::propagate_on_container_copy_assignment());
static_assert(!PmrAllocTraits::propagate_on_container_move_assignment());
static_assert(!PmrAllocTraits::propagate_on_container_swap());
static_assert(!PmrAllocTraits::is_always_equal());

Source code