How to create boost::intrusive::list from an already existing legacy list?

Question

I have a legacy structure like this:

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

And legacy code that works with a list like this. How to create boost::intrusive::list from it, so that I could, for example, add elements using the old C code and using the boost::list? I can write node traits:

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

But this only allows you to create a new one, and I just want to create a kind of view from the old one. Is it possible at all? Or should I find another library/write it?

An example of the code I want to get:

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

What doesn't work, *exactly*, when you use your traits? What.code do you want to work? — Yakk - Adam Nevraumont, Jan 29 '21 at 13:42
Are you talking about [function hooks](https://www.boost.org/doc/libs/1_75_0/doc/html/intrusive/function_hooks.html)? — Caleth, Jan 29 '21 at 15:27
Caleth How can function hooks help me when working with a legacy list? — Igor Pugachev, Jan 30 '21 at 16:34

sehe · Answer 1 · 2021-01-29T21:01:31.377

Given, say, the following legacy list:

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

The node traits allow you to use the algos:

using algo = bi::circular_list_algorithms<legacy_node_traits>;

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

And using value traits you can construct a list from the nodes. In your case the value traits can be trivially deduced from the node traits:

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

Now you could construct a NEW list and use it:

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

CAUTION: This has the side effect of reordering the list to the array order, losing the original link information.

It would be nice if there was a combination mid-way between bi::list::splice (which only operates on nodes already in another bi::list) and circular_list_algorithms::transfer (which assumes the opposite). Sadly, the obvious improvement here requires accessing the get_root_nod() which is private.

The only way in which you can guarantee bi::list variants (such as the optional size tracking!) is to write a rather dumbish loop like:

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

This is annoying in the sense that it seems to ask the compiler to emit code to establish all the same links again. It's not completely unrealistic to hope that a Very Smart Compiler might actually see through this and eliminate the no-op code?

Full Demo

Live On Coliru

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

Prints

-99
42
13

I've reversed the list beforehand to make doubly sure we didn't invent our own links. Also, l.check() check all node/list invariants.

I had fallen into a trap with my [first attempt](https://stackoverflow.com/posts/65959319/revisions) so I gave it another go after dinner. This time I got it right (according to me and ubsan/asan) :) — sehe, Jan 29 '21 at 21:03
Thank you! This is not exactly what I want, but still very useful. If the algorithms were not free functions, but a class method, that would be great. In my case, such an legacy list may be an OS list (NetBufferList, for example), and I need to make changes exactly to it. And yes, `bi::list::splice` is essentially what I want, but for legacy list. The solution seems to be very close, but nothing fits perfectly :( It may not be possible to do this with boost::intrusive. — Igor Pugachev, Jan 30 '21 at 16:22
It is definitely possibly as an extension to the library, but you'll have to manage the learning curve of **all** the combination of generic options that it supports to make sure you address all invariants. I would probably do a feature request and keep this manual approximation in the mean time. — sehe, Jan 30 '21 at 16:52
If you feel brave you can do the work and contribute a pull request for such a feature, however, I feel there might be scepsis because it's an interface that's easy to use wrong. Still, I'd love to see it, personally — sehe, Jan 30 '21 at 16:54

How to create boost::intrusive::list from an already existing legacy list?

1 Answers1

Full Demo