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

Subject: [Boost-users] intrusive data structures with custom pointer class
From: Matei David (matei_at_[hidden])
Date: 2014-02-06 17:52:39

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.

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.

Initial solution that doesn't work:

The most important limitation of these 4-byte indirect pointers (say
to a type T) is that if you fully dereference one to T&, you can no
longer reconstruct the indirect pointer (with operator&) in constant
time. I.e. converting a real-pointer to indirect-pointer must be
avoided. Thus, to make methods such as insert(T&) work, I had to roll
out a reference-replacement class in addition to the pointer-replacement
class. This is what I initially tried:

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

Problems:

Even though intrusive data structures are designed with the stated goal
of leaving memory management to the user, intrusive lists&trees do
allocate one extra node object that they use as "header". The code then
takes the address (&) of this node and uses it in comparisons as a
node_ptr. Because of this, my custom traits above could not compile.
The only way I could find to make such containers work for my needs is
basically a hack: define "node" to be a "pointer holder" object
(neither member nor base of "value"), that allocates a "value" struct
from the deque upon construction, that responds to operator& by
returning the held pointer, and that otherwise acts as a value&. From
what I could gather reading the docs, boost::intrusive containers allow
some type of customization via the traits structs. However, I see some
drawbacks:

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.

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.

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.

Questions:

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

static node_ptr uncast(const_node_ptr ptr)
{
  return node_ptr(const_cast<node*>(
    ::boost::intrusive::detail::boost_intrusive_get_pointer(ptr)));
}

So despite all the custom traits structs defining node_ptr and
const_node_ptr, under the hood you have a line of code which assumes
node_ptr can be constructed from node*. This is the expensive
real-pointer to offset-pointer no-no I mentioned earlier.

However, intrusive lists worked just fine in 1.46, which suggests this
was simply a bug.

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.

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?

Many thanks,
M