1

我有这样的遗留结构：

struct LIST_ENTRY {
    LIST_ENTRY *Flink;
    LIST_ENTRY *Blink;
};
LIST_ENTRY legacyListHead;

以及与这样的列表一起使用的遗留代码。如何从中创建 boost::intrusive::list，例如，我可以使用旧的 C 代码和 boost::list 添加元素？我可以编写节点特征：

struct legacy_node_traits
{
    using node = LIST_ENTRY;
    using node_ptr = node *;
    using const_node_ptr = const node *;

    static node *get_next(const node *n)            {  return n->Flink;  }
    static void set_next(node *n, node *next)       {  n->Flink = next;  }
    static node *get_previous(const node *n)        {  return n->Blink;  }
    static void set_previous(node *n, node *prev)   {  n->Blink = prev;  }
};

但这仅允许您创建一个新的，我只想从旧的创建一种视图。有可能吗？还是我应该找到另一个库/写它？

我想获得的代码示例：

LIST_ENTRY legacyListHead;
...
legacy_push_back(&legacyListHead, &node1);
boost::intrusive::list list{legacyListHead}; // NOT a copy
list.push_back(node2); // node1 -> node2
legacy_push_front(&legacyListHead, &node3); // node3 -> node1 -> node2
4

1 回答 1

1

例如，给定以下遗留列表：

struct LIST_ENTRY {
    LIST_ENTRY *Flink;
    LIST_ENTRY *Blink;
    int value;
};

LIST_ENTRY nodes[3] = {};
auto a = nodes+0;
auto b = nodes+1;
auto c = nodes+2;
*a = { b, c,  13 };
*b = { c, a,  42 };
*c = { a, b, -99 };

节点特征允许您使用算法：

using algo = bi::circular_list_algorithms<legacy_node_traits>;

assert(algo::count(a) == 3);
assert(algo::count(b) == 3);
assert(algo::count(c) == 3);

并且使用价值特征，您可以从节点构造一个列表。在您的情况下，可以从节点特征中轻松推导出值特征：

using List = bi::list<LIST_ENTRY, 
    bi::value_traits<
        bi::trivial_value_traits<legacy_node_traits, bi::normal_link>
    > >;

现在您可以构建一个新列表并使用它：

List l(std::begin(nodes), std::end(nodes)); // CAUTION, see below
for (auto& el : l) {
    std::cout << el.value << "\n";
}

注意：这具有将列表重新排序为数组顺序的副作用，丢失原始链接信息。

如果在 bi::list::splice （只对已经在另一个 bi::list 中的节点上运行）和 circular_list_algorithms::transfer （假设相反）之间有一个组合，那就太好了。可悲的是，这里明显的改进需要访问get_root_nod()哪些是私有的。

您可以保证 bi::list 变体（例如可选的大小跟踪！）的唯一方法是编写一个相当愚蠢的循环，例如：

List from_head(LIST_ENTRY* const head) {
    List l;

    auto it = head->Blink;
    while (it != head) {
        auto next = it->Blink;
        l.push_front(*it); // intrusive, so modifies it->Blink!
        it = next;
    }
    l.push_front(*head);
    return l;
}

从某种意义上说，这很烦人，它似乎要求编译器发出代码以再次建立所有相同的链接。希望非常智能的编译器能够真正看穿这一点并消除无操作代码并不是完全不现实的吗？

完整演示

住在科利鲁

#include <boost/intrusive/trivial_value_traits.hpp>
#include <boost/intrusive/list.hpp>
#include <iostream>

namespace bi = boost::intrusive;

struct LIST_ENTRY {
    LIST_ENTRY *Flink;
    LIST_ENTRY *Blink;
    int value;
};

struct legacy_node_traits
{
    using node = LIST_ENTRY;
    using node_ptr = node *;
    using const_node_ptr = const node *;

    static node *get_next(const node *n)            {  return n->Flink;  }
    static void set_next(node *n, node *next)       {  n->Flink = next;  }
    static node *get_previous(const node *n)        {  return n->Blink;  }
    static void set_previous(node *n, node *prev)   {  n->Blink = prev;  }
};

using List = bi::list<LIST_ENTRY,
      bi::value_traits<
        bi::trivial_value_traits<legacy_node_traits, bi::normal_link>
      > >;

List from_head(LIST_ENTRY* const head) {
    List l;

    auto it = head->Blink;
    while (it != head) {
        auto next = it->Blink;
        l.push_front(*it); // intrusive, so modifies it->Blink!
        it = next;
    }
    l.push_front(*head);
    return l;
}

int main() {
    LIST_ENTRY nodes[3] = {};
    auto a = nodes+0;
    auto b = nodes+1;
    auto c = nodes+2;
    *a = { b, c,  13 };
    *b = { c, a,  42 };
    *c = { a, b, -99 };

    using algo = bi::circular_list_algorithms<legacy_node_traits>;
    {
        assert(algo::count(a) == 3);
        assert(algo::count(b) == 3);
        assert(algo::count(c) == 3);

        algo::reverse(a);
    }

    List l = from_head(c);
    l.check();
    for (auto& el : l)
        std::cout << el.value << std::endl;
}

印刷

-99
42
13

我事先将列表颠倒过来，以确保我们没有发明自己的链接。此外，l.check()检查所有节点/列表不变量。

于 2021-01-29T17:44:16.580 回答