Intrusive list

Discussion in 'C++' started by Marcin Kalicinski, May 17, 2004.

  1. 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
    Marcin Kalicinski, May 17, 2004
    #1
    1. Advertising

  2. Marcin Kalicinski

    Jeff Schwab Guest

    Marcin Kalicinski wrote:

    > 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.
    Jeff Schwab, May 17, 2004
    #2
    1. Advertising

  3. Marcin Kalicinski wrote:
    >
    > 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.

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, May 17, 2004
    #3
  4. Uzytkownik "Jeff Schwab" <> napisal w wiadomosci
    news:...
    > Marcin Kalicinski wrote:
    >
    > Why aren't you using std::list?


    Because it is non-intrusive and I need an intrusive 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.


    But I cannot inherit multiple times from the same class.

    Marcin
    Marcin Kalicinski, May 17, 2004
    #4
  5. Marcin Kalicinski

    bartek Guest

    "Marcin Kalicinski" <> wrote in
    news:c8ajcp$e5d$:

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

    --
    :: bartekd [at] o2 [dot] pl
    bartek, May 17, 2004
    #5
  6. Marcin Kalicinski

    bartek Guest

    bartek <> wrote in
    news:Xns94ECCA968D16Cbartekdqwertyuiopo2p@153.19.251.200:

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

    --
    :: bartekd [at] o2 [dot] pl
    bartek, May 17, 2004
    #6
  7. "Marcin Kalicinski" <> wrote in message
    news:c8ao8j$b75$...
    >
    > Uzytkownik "Jeff Schwab" <> napisal w wiadomosci
    > news:...
    > > Marcin Kalicinski wrote:
    > >
    > > Why aren't you using std::list?

    >
    > Because it is non-intrusive and I need an intrusive 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.

    >
    > 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
    John Harrison, May 17, 2004
    #7
  8. "Marcin Kalicinski" <> wrote in message news:<c8ajcp$e5d$>...
    > 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 NodeBase:public 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
    Joaqu?n M? L?pez Mu?oz, May 17, 2004
    #8
  9. "Marcin Kalicinski" <> skrev i en meddelelse
    news:c8ajcp$e5d$...
    > 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, May 17, 2004
    #9
  10. "Peter Koch Larsen" <> skrev i en meddelelse
    news:eM7qc.164603$...
    >
    > "Marcin Kalicinski" <> skrev i en meddelelse
    > news:c8ajcp$e5d$...
    > > 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

    >
    > 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, May 18, 2004
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sabyasachi Basu

    Non-intrusive object serialization

    Sabyasachi Basu, Mar 7, 2004, in forum: C++
    Replies:
    1
    Views:
    616
    Claudio Puviani
    Mar 7, 2004
  2. Charles Hartman

    intrusive posts

    Charles Hartman, Mar 24, 2005, in forum: Python
    Replies:
    0
    Views:
    306
    Charles Hartman
    Mar 24, 2005
  3. Pradeep

    Intrusive pointer problem

    Pradeep, Oct 5, 2005, in forum: C++
    Replies:
    6
    Views:
    547
    Maxim Yegorushkin
    Oct 5, 2005
  4. Pradeep
    Replies:
    1
    Views:
    291
    Jim Langston
    Oct 19, 2005
  5. Steven T. Hatton
    Replies:
    2
    Views:
    1,495
    Steven T. Hatton
    Nov 30, 2006
Loading...

Share This Page