node_pool.hpp

• View this file on GitHub
• Last update: 2025-09-15 19:13:13+08:00
• Include: #include "node_pool.hpp"

Verified with

• test/data_structure/dynamic_sequence_range_affine_range_sum.0.test.cpp
• test/data_structure/dynamic_sequence_range_affine_range_sum.1.test.cpp
• test/data_structure/ordered_set.0.test.cpp
• test/data_structure/ordered_set.1.test.cpp
• test/data_structure/point_set_range_composite.0.test.cpp
• test/data_structure/point_set_range_composite.1.test.cpp
• test/data_structure/range_affine_point_get.0.test.cpp
• test/data_structure/range_affine_point_get.1.test.cpp
• test/data_structure/range_affine_range_sum.0.test.cpp
• test/data_structure/range_affine_range_sum.1.test.cpp
• test/data_structure/range_reverse_range_sum.0.test.cpp
• test/data_structure/range_reverse_range_sum.1.test.cpp
• test/tree/dynamic_tree_vertex_add_path_sum.0.test.cpp
• test/tree/dynamic_tree_vertex_set_path_composite.0.test.cpp
• test/tree/jump_on_tree.0.test.cpp
• test/tree/lca.0.test.cpp

Code

#pragma once

#include <list>
#include <memory>
#include <utility>
#include <vector>

template<typename NodeT> class FixedSizeNodePool {
    std::vector<NodeT> pool;

public:
    explicit FixedSizeNodePool(int n) : pool(n) {}
    NodeT *at(int ind) { return pool.data() + ind; }
    int id(NodeT *a) const { return a - pool.data(); }
    auto get_func() {
        return std::make_pair([this](int ind) { return at(ind); },
                              [this](NodeT *a) { return id(a); });
    }
};

template<typename NodeT> class DynamicSizeNodePool {
    struct Wrapped : public NodeT {
        using NodeT::NodeT;
        typename std::list<Wrapped>::iterator i;
    };
    std::list<Wrapped> used_list;
    std::list<Wrapped> free_list;

public:
    template<typename... Args> NodeT *make(Args &&...arg) {
        if (free_list.empty()) {
            auto &&node = used_list.emplace_back(std::forward<Args>(arg)...);
            node.i      = std::prev(used_list.end());
            return std::addressof(node);
        }
        used_list.splice(used_list.end(), free_list, std::prev(free_list.end()));
        auto &&node = used_list.back();
        node.~NodeT(); // i remains unchanged
        new (std::addressof(node)) NodeT(std::forward<Args>(arg)...);
        return std::addressof(node);
    }
    // this is lazy, if sth. relies on the order of dtor, do NOT use
    void retrieve(NodeT *node) {
        free_list.splice(free_list.end(), used_list, ((Wrapped *)node)->i);
    }
};

#line 2 "node_pool.hpp"

#include <list>
#include <memory>
#include <utility>
#include <vector>

template<typename NodeT> class FixedSizeNodePool {
    std::vector<NodeT> pool;

public:
    explicit FixedSizeNodePool(int n) : pool(n) {}
    NodeT *at(int ind) { return pool.data() + ind; }
    int id(NodeT *a) const { return a - pool.data(); }
    auto get_func() {
        return std::make_pair([this](int ind) { return at(ind); },
                              [this](NodeT *a) { return id(a); });
    }
};

template<typename NodeT> class DynamicSizeNodePool {
    struct Wrapped : public NodeT {
        using NodeT::NodeT;
        typename std::list<Wrapped>::iterator i;
    };
    std::list<Wrapped> used_list;
    std::list<Wrapped> free_list;

public:
    template<typename... Args> NodeT *make(Args &&...arg) {
        if (free_list.empty()) {
            auto &&node = used_list.emplace_back(std::forward<Args>(arg)...);
            node.i      = std::prev(used_list.end());
            return std::addressof(node);
        }
        used_list.splice(used_list.end(), free_list, std::prev(free_list.end()));
        auto &&node = used_list.back();
        node.~NodeT(); // i remains unchanged
        new (std::addressof(node)) NodeT(std::forward<Args>(arg)...);
        return std::addressof(node);
    }
    // this is lazy, if sth. relies on the order of dtor, do NOT use
    void retrieve(NodeT *node) {
        free_list.splice(free_list.end(), used_list, ((Wrapped *)node)->i);
    }
};

Back to top page