Re: [Boost-users] intrusive data structures with custom pointer class

El 06/02/2014 23:52, Matei David escribió:

Hi,

I would like to use some boost::intrusive data structures (lists and trees) in a project I'm working on, but I ran into trouble trying to customize the existing classes to my needs. I decided to post my problem here, in case somebody knowledgeable of boost::intrusive *implementation details* can assist me. Thank you in advance.

Hi Meti, You have a lot of questions, I hope I can answer most of them.

Background:

In the project I'm working on, I need to manage a large number of objects in memory. The data is dynamic, so I need to be able to alloc&dealloc objects, in addition to keeping the objects in various lists&trees (for which I'm trying to use boost::intrusive). The RAM usage is large (think, >100GB), but the number of objects is smaller than 2^32. So one thing I'd like to do is to replace 8-byte raw pointers with 4-byte offsets into a deque. Doing this would solve the alloc/dealloc part. However, I now need to customize boost::intrusive containers to work with these 4-byte offsets instead of raw pointers.

I guess the deque is a global object, right. What do you mean with "offset" into a deque? It's the offset passed to "deque::operator[]"?

- Given a type T, I rolled out pointer-replacement class Ptr<T> which holds a 4-byte int, and upon operator*, it produces a Ref<T> object. - A reference-replacement Ref<T> class similarly holds a 4-byte int, it implements operator& which produces the associated Ptr<T> object, and it also provides an operator T& () conversion which dereferences the object from the deque. - With these, I tried a custom traits struct looking like this: value_type = node := T node_ptr = pointer := Ptr<T> reference := Ref<T>

Boost.Intrusive models (or tries to model) a pointer type that can be modeled with std::pointer_traits (more precisely boost::intrusive::pointer_traits). In that model the reference type must be a type that implements the dot operator. Sadly in C++ there is no way to implement a class that overloads this operator. That's why your pseudo-reference type will not work.

A. The traits classes seem to be there to support 2 existing customization types, namely the situation where "node" is a base class of "value" (implementing "base hooks") and the situation where "node" is a member of "value" (implementing "member hooks"). My situation represents a 3rd customization type.

You can use function_hook, the hook does not need to be a member or base class.

B. Even though the traits classes allow one to specify pointer types, it's possible (?) that under the hood the classes were designed to support only raw pointers and smart pointers, not the indirect offset-like pointers I need.

See previous answer about supported reference types.

Given A&B, it seems to me that in my customization I would need 2 different hacks. In the interest of code stability, I started wondering whether it is feasible to adapt existing boost::intrusive data to my needs (my first instinct) as opposed to simply rolling out my own rbtree.

I don't know the impact of supporting smart reference types. It might be impossible, I haven't tried it.

0. Obviously: Have you seen a similar situation being dealt with before? Maybe there's an existing solution out there. My reluctance to rolling out my own intrusive rbtrees is due to the fact I'd have to test them, as opposed to using a known implementation.

1. Are boost::intrusive data structures supposed to support custom pointer classes (neither real pointers nor smart pointers)? For instance, in 1.46 I found this code in boost/intrusive/detail/tree_algorithms.hpp

Yes, boost::interprocess::offset_ptr (but a raw reference can be converted to a smart pointer easily).

static node_ptr uncast(const_node_ptr ptr) { return node_ptr(const_cast( ::boost::intrusive::detail::boost_intrusive_get_pointer(ptr))); } However, intrusive lists worked just fine in 1.46, which suggests this was simply a bug.

This was fixed in recent Boost releases using pointer_traits to implement this function. You can customize pointer_traits to implement your own version.

2. Can you point me to an example of defining and using custom pointer class with boost::intrusive? To enable compilation (of lists only) in 1.46, I had to customize std::iterator_traits (that part I understood), but then also boost::pointer_to_other and boost::intrusive::detail::smart_ptr_type. Even though the code compiled, I don't know what those are doing exactly, so I'm weary of them.

See the example in libs/intrusive/example/doc_offset_ptr.cpp and boost/interprocess/offset_ptr.hpp. See the most recent boost version for fixed bugs. A dumb smart pointer is used in boost intrusive tests, and it's found in libs/intrusive/test/smart_ptr.hpp, but it's a bit oudated. Anyway I think pointer requirements for Boost.Intrusive might no be correctly specified and it might require some fixes. Recent versions uses pointer_traits, and I recommend you this approach.

3. In 1.55, I have a few more pages of errors, I think mainly due to these pointer customization issues I don't fully understand. Something seems to have changed from 1.46 to 1.55. Is there a reference about what changed? Or is there a portable way of rolling out such a custom pointer class?

pointer_traits was specified and all code was ported to use this customization point. The reference type is assumed to be a raw reference (as there is no way to overload operator dot to implement a working smart reference). The only why to use Boost.Intrusive would be to implement a smart pointer (of any pointee type) that can be fastly obtained from raw reference. If this is your case, Boost.Intrusive might already have all that you need. If you need a "smart reference", then Boost.Intrusive is not prepared for this and I don't know how many effort would require adding support for this (even if this approach is feasible). The problem with "node" objects embedded in the container could be solved with an option that allows external allocation of these nodes. Best, Ion