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>
    > >;

これで、NEW リストを作成して使用できます。

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 に答える