Intrusive list

[Marcin Kalicinski]

Hi everybody,

I am creating an intrusive list ('next' and 'prev' pointers are stored
within an object that is in a list). One method of doing that is to inherit
all objects from some class that contains these pointers. However, it is
unacceptable for my problem, because it limits the number of lists the
object can be in to 1. I must have some objects in more than 1 list. Instead
of inheriting, I use aggregation:

class Node { // Node of a list
Node *prev, *next;
}

class SomeObject { // Object that can be in 3 independent lists
Node l1, l2, l3;
}

When I iterate through my list, I get pointer to a Node that is stored
within SomeObject. But I need to get pointer to SomeObject itself. Right now
I'm using nonconforming and ugly way:

#define MEMBER_OFFSET(ClassName, FieldName) int(&(((ClassName
*)0)->FieldName))

ListNode *node;
SomeObject *so = reinterpret_cast<SomeObject *>((char *)node -
MEMBER_OFFSET(SomeObject, l2));

My question is, is there a standard conforming way of doing that? For
example by using pointers to members?

Best regards,
Marcin

 

[Jeff Schwab]

I am creating an intrusive list ('next' and 'prev' pointers are stored
within an object that is in a list).

Why aren't you using std::list?

One method of doing that is to inherit
all objects from some class that contains these pointers. However, it is
unacceptable for my problem, because it limits the number of lists the
object can be in to 1.

How so? C++ supports multiple inheritance.

I must have some objects in more than 1 list. Instead
of inheriting, I use aggregation:

class Node { // Node of a list
Node *prev, *next;
}

class SomeObject { // Object that can be in 3 independent lists
Node l1, l2, l3;
}

When I iterate through my list, I get pointer to a Node that is stored
within SomeObject. But I need to get pointer to SomeObject itself. Right now
I'm using nonconforming and ugly way:

#define MEMBER_OFFSET(ClassName, FieldName) int(&(((ClassName
*)0)->FieldName))

ListNode *node;
SomeObject *so = reinterpret_cast<SomeObject *>((char *)node -
MEMBER_OFFSET(SomeObject, l2));

My question is, is there a standard conforming way of doing that? For
example by using pointers to members?

I don't know of any portable way to get the address of an object given
the address of an arbitrary sub-object.

 

[Karl Heinz Buchegger]

My question is, is there a standard conforming way of doing that? For
example by using pointers to members?

No.
But of course you could add a back pointer from each node
class to the object it links.

class Node {
Node *prev, *next;
SomeObject* TheObject;
}

But honestly, I would change the design.
Declare one container as beeing the master and
holding the objects. All other lists just store
pointers to those objects. This way each object
can be referenced by as many lists as you wish.

 

[Marcin Kalicinski]

Marcin Kalicinski wrote:

Why aren't you using std::list?

Because it is non-intrusive and I need an intrusive list.

How so? C++ supports multiple inheritance.

But I cannot inherit multiple times from the same class.

Marcin

 

[bartek]

Hi everybody,

I am creating an intrusive list ('next' and 'prev' pointers are stored
within an object that is in a list). One method of doing that is to
inherit all objects from some class that contains these pointers.
However, it is unacceptable for my problem, because it limits the
number of lists the object can be in to 1. I must have some objects in
more than 1 list. Instead of inheriting, I use aggregation:

class Node { // Node of a list
Node *prev, *next;
}

class SomeObject { // Object that can be in 3 independent lists
Node l1, l2, l3;
}

When I iterate through my list, I get pointer to a Node that is stored
within SomeObject. But I need to get pointer to SomeObject itself.
Right now I'm using nonconforming and ugly way:

#define MEMBER_OFFSET(ClassName, FieldName) int(&(((ClassName
*)0)->FieldName))

ListNode *node;
SomeObject *so = reinterpret_cast<SomeObject *>((char *)node -
MEMBER_OFFSET(SomeObject, l2));

My question is, is there a standard conforming way of doing that? For
example by using pointers to members?

How about going the other way around?
Instead of "embedding" the node pointer in an object, you could use the
aligned storage* trick to hold the memory and place your object there.

* aligned storage as per boost::aligned_storage, or Alexandrescu's
"Discriminated Unions" article.

Very very very oversimplifying:

template <class T>
class Node {
char m_buffer[sizeof(T)];
Node* m_prev;
Node* m_next;
};

You could plant objects directly into node buffers by using placement
new.

As I said, the above is a huge oversimplification. The buffer should be
properly aligned for holding type T (see Alexandrescu's article on
discriminated unions at http://www.moderncppdesign.com ).

Nonetheless, it's a very interesting technique. It can help get rid of
that one extra level of pointer indirection.

 

[bartek]

How about going the other way around?
Instead of "embedding" the node pointer in an object, you could use the
aligned storage* trick to hold the memory and place your object there.

(...)

Now, looking and what I've posted, I'm finding it difficult to grasp why
the heck I'd want to do it that way... I'm tired I guess... Please
disregard.

 

[John Harrison]

Because it is non-intrusive and I need an intrusive list.


But I cannot inherit multiple times from the same class.

You cannot inherit *directly* multiple times from the same class.

class ListBase
{
ListBase* next;
ListBase* prev;
};

template <int ID>
class BaseWrapper : public ListBase
{
};

class MyClass : public BaseWrapper<1>, public BaseWrapper<2>, public
baseWrapper<3>
{
};

MyClass can be on three different lists.

john

 

[Joaqu?n M? L?pez Mu?oz]

Hi everybody,

I am creating an intrusive list ('next' and 'prev' pointers are stored
within an object that is in a list). One method of doing that is to inherit
all objects from some class that contains these pointers. However, it is
unacceptable for my problem, because it limits the number of lists the
object can be in to 1. I must have some objects in more than 1 list. Instead
of inheriting, I use aggregation:

class Node { // Node of a list
Node *prev, *next;
}

class SomeObject { // Object that can be in 3 independent lists
Node l1, l2, l3;
}

When I iterate through my list, I get pointer to a Node that is stored
within SomeObject. But I need to get pointer to SomeObject itself. Right now
I'm using nonconforming and ugly way:

#define MEMBER_OFFSET(ClassName, FieldName) int(&(((ClassName
*)0)->FieldName))

ListNode *node;
SomeObject *so = reinterpret_cast<SomeObject *>((char *)node -
MEMBER_OFFSET(SomeObject, l2));

My question is, is there a standard conforming way of doing that? For
example by using pointers to members?

You can use multiple inheritance with an extra level of
derivation to avoid ambiguity problems:

template<int N>
class NodeBaseublic Node
{
};

class SomeObject:
public NobeBase<1>,
public NobeBase<2>,
public NobeBase<3>
{
...
};

See what I mean? Now, if given a NodeBase<n>* one can portably
downcast to SomeObject like this:

NodeBase<2> *pn2=...;
SomeObject* po=static_cast<SomeObject*>(pn2);

If instead of a NodeBase<n>* you're provided with a
pointer to Node, then you must know from some other source
which of the inherited Nodes you are referring to:

Node* pn;
//we know we've been passed node #3
SomeObject* po=static_cast<SomeObject*>(
static_cast<NodeBase<3>*>(pn));

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

 

[Peter Koch Larsen]

Hi everybody,

I am creating an intrusive list ('next' and 'prev' pointers are stored
within an object that is in a list). One method of doing that is to inherit
all objects from some class that contains these pointers. However, it is
unacceptable for my problem, because it limits the number of lists the
object can be in to 1. I must have some objects in more than 1 list. Instead
of inheriting, I use aggregation:

class Node { // Node of a list
Node *prev, *next;
}

class SomeObject { // Object that can be in 3 independent lists
Node l1, l2, l3;
}

When I iterate through my list, I get pointer to a Node that is stored
within SomeObject. But I need to get pointer to SomeObject itself. Right now
I'm using nonconforming and ugly way:

#define MEMBER_OFFSET(ClassName, FieldName) int(&(((ClassName
*)0)->FieldName))

ListNode *node;
SomeObject *so = reinterpret_cast<SomeObject *>((char *)node -
MEMBER_OFFSET(SomeObject, l2));

My question is, is there a standard conforming way of doing that? For
example by using pointers to members?

Best regards,
Marcin

I believe that using templates and pointer-to members could do what you want
to. A brief sketch - giving a singly linked list:

template <typename t> struct link
{
t * next;
};

template <typename t,link<t>::*linkmember> class link_iterator
{
link<t> head;
link_iterator operator++() { head = head->next;}
};

struct test
{
link<test> link1;
link<test> link2;
};

link_iterator<test,&test::link1> iter1;
link_iterator<test,&test::link2> iter2;

Just a sketch, but hoping this helps.

/Peter

 

[Peter Koch Larsen]

Hi everybody,

[snip]

#define MEMBER_OFFSET(ClassName, FieldName) int(&(((ClassName
*)0)->FieldName))

ListNode *node;
SomeObject *so = reinterpret_cast<SomeObject *>((char *)node -
MEMBER_OFFSET(SomeObject, l2));

My question is, is there a standard conforming way of doing that? For
example by using pointers to members?

Best regards,
Marcin

I believe that using templates and pointer-to members could do what you want
to. A brief sketch - giving a singly linked list:

template <typename t> struct link
{
t * next;
};

template <typename t,link<t>::*linkmember> class link_iterator
{
link<t> head;
link_iterator operator++() { head = head->next;}
};

This was written five minutes past my mental bedtime. A correct approach
would be:

template <typename t,link<t>::*linkmember> class link_iterator
{
t* head;
link_iterator operator++() { head = head->*linkmember;}
};

/Peter