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

Subject: Re: [Boost-users] intrusive data structures with custom pointer class
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2014-02-07 16:00:23

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<node*>(
>      ::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