pointer _from_ member [c++]

13,220

October 03, 2006 02:52 PM

Quote:
We do know which member we have in mind.
So there should be no information lost in the process.

Well, the compiler knows (some kind of offsetting has got to be stored in the value of a pointer-to-member), but the compiler doesn't provide a standard way to get that offsetting out of there. Nor can you safely cast a pointer-to-member to a regular pointer. The language just plan doesn't support this "features" (and for good reason).

The "bit pattern" is just another word for the value. The value of a pointer is an address, but the format of that address is implementation defined. Memory isn't neccessarily linearly addressable (some machines address is differently), and C++ has to cope with that, so you can't, in turn, expect linearly-addressable-interpretations of a pointer to be valid. Additionally, the standard says that a constant integral expression evaluating to zero shall be converted to the null pointer value at compile time. This means that a, in "int a = 0;" can legally contain, in memory, at run-time, a non-zero value, if the target machine uses a non-zero value for the null pointer. It is possible and it does happen.

The FAQ you quoted is for C. C isn't C++. Are we talking about the same language, here? It doesn't change the validity of the "constant expression of zero is null" statement, but it does change other things.

Doing "math" on pointers that point to different arrays/objects isn't well defined. There's no object at the null pointer value. Thus, the math isn't well defined.

Quote:
The discussion clearly concludes that it is the standard itself that has been mis-worded on that matter. And that we shouldn't be paranoid about it.

It shows a mis-wording, true. But to me, that means one should be as conservative as possible about the issue.

As far as the intrusive list concept, since you're being intrusive, why don't you be just slightly more intrusive and hold a more complicated object in the host class that can be told the information about "which object holds me" so that it can be queried later? There's no reason to muck about with pointers like this.

MaulingMonkey

1,729

October 03, 2006 02:57 PM

Even if there's a standard defined behavior for this, I wouldn't use it.

To get a pointer/reference to the parent one must rely on the following invariants:
1) The pointer must only be to a member of that parent class in the first place.
2) The pointer must only be to that specific member in the first place.

Instead, one shouldn't be storing a pointer to the member in the first place. One should be storing it to the original parent. This enforces the above invariants in a manner that needs effort to circumvent, rather than implicitly relying on them in a manner easily frogotten about (which is enough to accidentally break those invariants).

Instead of:

M * member = ...;
use( member );
T * parent = parent_of_member< & T::specific_member_we_hope_it_is >( member );

Prefer:

T * parent = ...;
use( parent->specific_member_we_know_it_is );
T * parent2 = parent;

It sounds like the original problem may be focused on hacking around the need to refactor <_<

Quote:Original post by deffer
struct ilist_node{  ilist_node *prev;  ilist_node *next;};struct A{  // ...  ilist_node  m_Node;  // ...};typedef  ilist<A, &A::m_Node>  my_list;
And here's the problem with dereferencing an iterator (being a wrapped ilist_node*, additionally templated with <A, &A::m_Node>) - getting A* from ilist_node*.

Normally I see intrusive schemes like such implemented with a is-a relationship:

struct A : ilist_node {    //...};(ilist_node*) => (A*) is just a simple cast then:static_cast< A* >( ilist_node_pointer );

Of course, I'm presuming this iterator belongs to a templated class ala:

template < typename T >class intrusive_list {    //...};

In which case templating the intrusive_list iterator makes the above cast un-necessary in the first place:

template < typename T >class intrusive_list_iterator {    T * node;    intrusive_list_iterator & operator++(int) {        node = node->next;        return *this;    }    intrusive_list_iterator & operator--(int) {        node = node->prev;        return *this;    }    //...};template < typename T >class intrusive_list {    typedef intrusive_list_iterator< T > iterator;    //...};

(note: You don't even necessairly have to use inheritence! We're assuming next/prev are (T*) though - which may involve templating the node "interface" we inherit)

The only sane reason that comes to mind that's problematic with the is-a scheme is if you want your object to be on multiple lists. Having a single type for both lists is asking for trouble anyways in the first place - and if we use a tagging scheme, the is-a method still works:

template < typename T , typename tag >struct intrusive_tagged_list_node {    T * prev;    T * next;};template < typename T , typename tag >struct intrusive_tagged_list_iterator {    T * node;    intrusive_tagged_list_iterator & operator++(int) {        intrusive_tagged_list_node< T , tag > * tagged_node = node;        node = tagged_node->next;        return *this;    }    intrusive_tagged_list_iterator & operator--(int) {        intrusive_tagged_list_node< T , tag > * tagged_node = node;        node = tagged_node->prev;        return *this;    }    //...};template < typename tag , typename T /* implicit */ >intrusive_tagged_list_iterator< T , tag > get_iterator_of( T & object ) {    intrusive_tagged_list_iterator< T , tag > iterator;    iterator.node = object;    return iterator;}template < typename T >class intrusive_tagged_list {    typedef intrusive_tagged_list_iterator< T > iterator;    //...};struct objects_list_tag {};struct renderables_list_tag {};class example    : public intrusive_tagged_list_node< example , objects_list_tag >    , public intrusive_tagged_list_node< example , renderables_list_tag >{    //...};void test_example() {    example foo;    //...    intrusive_tagged_list_iterator< example , objects_list_tag > i1 = get_iterator_of< objects_list_tag >( foo );    intrusive_tagged_list_iterator< example , renderables_list_tag > i2 = get_iterator_of< renderables_list_tag >( foo );    i1 = i2; //Thanks to tagging, this is a type mismatch rather than preperation for grevious invocations of undefined runtime behaviors.    //note: We could define sane conversion operators to the above too, thanks to the tagging system.    ++i1; //automatically uses the objects_list_tag-ed next    ++i2; //automatically uses the renderables_list_tag-ed next    //...}

[Edited by - MaulingMonkey on October 3, 2006 3:57:19 PM]

deffer

755

Author

October 03, 2006 04:40 PM

Quote:Original post by jpetrie
The "bit pattern" is just another word for the value. The value of a pointer is an address, but the format of that address is implementation defined. Memory isn't neccessarily linearly addressable (some machines address is differently), and C++ has to cope with that, so you can't, in turn, expect linearly-addressable-interpretations of a pointer to be valid.

That sounds very, very depressing...

Quote:Original post by jpetrie
The FAQ you quoted is for C. C isn't C++. Are we talking about the same language, here?

Heh, I didn't even notice...

Quote:Original post by jpetrie
As far as the intrusive list concept, since you're being intrusive, why don't you be just slightly more intrusive and hold a more complicated object in the host class that can be told the information about "which object holds me" so that it can be queried later? There's no reason to muck about with pointers like this.

Hm... clearly that would be a solution. With some additional cost, but it would work.

Quote:Original post by MaulingMonkey
Instead, one shouldn't be storing a pointer to the member in the first place. One should be storing it to the original parent. This enforces the above invariants in a manner that needs effort to circumvent, rather than implicitly relying on them in a manner easily frogotten about (which is enough to accidentally break those invariants).

I already have such an implementation working. But it has a flaw - I don't have a way of representing an end() iterator.

A std::list has an additional node allocated (without the "data" member contructed, only with prev/next pointers initialized). Using a similar implementation in the intrusive scheme I would have to allocate and construct a T instance, just to have a valid ilist_node to represent end(). That is, of course, unacceptable.
So instead, I tried to link ilist_node-s together directly, with no regard to where they come from (ilist_node would not be templated). Then I could be having an ilist_node instance in the ilist<..> as a member and voila! The only thing left was the dereferencing operator, that would transform ilist_node* to T*. Now I see that as potentially problematic, indeed.

Quote:Original post by MaulingMonkey
Normally I see intrusive schemes like such implemented with a is-a relationship:
[...]

Yikes!
I haven't thought of that.
Arrrrgh!

That seems like the soulution here. I will begin the implementation immediately.

To sum things up:

I tried to inverse the pointer-to-member operator, which apparently cannot be done.
The static_cast, on the other hand, may provide similar functionality, and it already works both ways.

MaulingMonkey

1,729

October 03, 2006 05:43 PM

Quote:Original post by deffer
A std::list has an additional node allocated (without the "data" member contructed, only with prev/next pointers initialized). Using a similar implementation in the intrusive scheme I would have to allocate and construct a T instance, just to have a valid ilist_node to represent end(). That is, of course, unacceptable.

Point. You *will* have to break the type system in one way or another. I guess that means an upcast during dereferencing from the header to the templated node type.

Which means a checked iterator implementation for debug mode might be a good idea as well :)

deffer

755

Author

October 03, 2006 06:39 PM

Quote:Original post by MaulingMonkey
You *will* have to break the type system in one way or another. I guess that means an upcast during dereferencing from the header to the templated node type.

Not really, me thinks.
The only push_front/push_back/insert I have take a reference to the actual class (as opposed to taking list_node<Tag>&). So I only upcast what I myself downcasted before. 100% legit.

And the implementation itself.

/////////////////////////////////namespace intrusive/////////////////////////////////{   template< typename Tag >   class list_node   {      typedef list_node<Tag>  this_type;   public:      this_type* prev;      this_type* next;   };   template< typename T, typename Tag >   class list;   /////////////////////////////////   namespace _list_detail   /////////////////////////////////   {      template< typename T, typename Tag >      class const_iter      {         typedef const_iter<T,Tag>  this_type;         typedef list<T,Tag>  list_type;         typedef list_node<Tag>  node_type;         friend class list_type;      public:         typedef std::bidirectional_iterator_tag  iterator_category;         typedef T  value_type;         typedef int  difference_type;         typedef const T*  const_pointer;         typedef const_pointer  pointer;         typedef const T&  const_reference;         typedef const_reference  reference;      public:         const_iter() : curr(0) {};         const_iter(node_type* p) : curr(p) {};      public:         reference  operator*(void) const         {   return *static_cast<pointer>(curr); };         pointer  operator->(void) const         {   return static_cast<pointer>(curr); };      public:         this_type& operator++()         {            curr = curr->next;            return *this;         };         this_type operator++(int)         {            this_type tmp = *this;            ++(*this);            return tmp;         };         this_type& operator--()         {            curr = curr->prev;            return *this;         };         this_type operator--(int)         {            this_type tmp = *this;            --(*this);            return tmp;         };         bool operator==(const this_type & it) const         {   return curr == it.curr; };         bool operator!=(const this_type & it) const         {   return !(*this == it); };      protected:         node_type* curr;      };      template< typename T, typename Tag >      class iter         : public const_iter<T,Tag>      {         typedef iter<T,Tag>  this_type;         typedef const_iter<T,Tag>  base_type;         typedef list<T,Tag>  list_type;         typedef list_node<Tag>  node_type;         friend class list_type;      public:         typedef T  value_type;         typedef int  difference_type;         typedef T*  pointer;         typedef T&  reference;      public:         iter() {};         iter(node_type* p) : base_type(p) {};      public:         reference  operator*(void) const         {   return *static_cast<pointer>(curr); };         pointer  operator->(void) const         {   return static_cast<pointer>(curr); };      public:         this_type& operator++()         {            ++(*(base_type*)this);            return *this;         };         this_type operator++(int)         {            this_type tmp = *this;            ++(*this);            return tmp;         };         this_type& operator--()         {            --(*(base_type*)this);            return *this;         };         this_type operator--(int)         {            this_type tmp = *this;            --(*this);            return tmp;         };      };   /////////////////////////////////   }; // (namespace _list_detail)   /////////////////////////////////   template< typename T, typename Tag >   class list   {      typedef list<T,Tag>  this_type;      typedef list_node<Tag>  node_type;   public:      typedef _list_detail::const_iter<T,Tag>  const_iterator;      typedef _list_detail::iter<T,Tag>  iterator;      typedef size_t  size_type;      typedef T  value_type;      typedef int  difference_type;      typedef T*  pointer;      typedef const T*  const_pointer;      typedef T&  reference;      typedef const T&  const_reference;   private:      static node_type & _Node(T & t)      {   return static_cast<node_type&>(t); };      static const node_type & _Node(const T & t)      {   return static_cast<const node_type&>(t); };   public:      list()         : m_cnt(0)      {         m_EndNode.prev = &m_EndNode;         m_EndNode.next = &m_EndNode;      };      list(const this_type & o)         : m_cnt(0)      {         m_EndNode.prev = &m_EndNode;         m_EndNode.next = &m_EndNode;         //assert(o.empty());         ignore_unused_variable_warning(o);      };      ~list()      {         //clear();      };   private:      this_type & operator=(const this_type & o);   private:      node_type  m_EndNode;      size_t  m_cnt;   public:      iterator  begin()      {   return iterator(m_EndNode.next); };      const_iterator  begin() const      {   return const_iterator(m_EndNode.next); };      iterator  end()      {   return iterator(&m_EndNode); };      const_iterator  end() const      {   return const_iterator(&m_EndNode); };   public:      bool  empty() const      {   return m_cnt == 0; };      size_type  size() const      {   return m_cnt; };   public:      reference  front()      {   return *begin(); };      const_reference  front() const      {   return *begin(); };      reference  back()      {   return *--end(); };      const_reference  back() const      {   return *--end(); };   public:      void push_front(T & t)      {         node_type & curr = _Node(t);         curr.prev = &m_EndNode;         curr.next = m_EndNode.next;         m_EndNode.next->prev = &curr;         m_EndNode.next = &curr;         m_cnt++;      };      void pop_front()      {         node_type & curr = *m_EndNode.next;         m_EndNode.next = curr.next;         m_EndNode.next->prev = &m_EndNode;         m_cnt--;      };      void push_back(T & t)      {         node_type & curr = _Node(t);         curr.next = &m_EndNode;         curr.prev = m_EndNode.prev;         m_EndNode.prev->next = &curr;         m_EndNode.prev = &curr;         m_cnt++;      };      void pop_back()      {         node_type & curr = *m_EndNode.prev;         m_EndNode.prev = curr.prev;         m_EndNode.prev->next = &m_EndNode;         m_cnt--;      };   public:      void insert(iterator before, T & t)      {         node_type & curr = _Node(t);         node_type & bef = *before.curr;         curr.next = &bef;         curr.prev = bef.prev;         bef.prev = &curr;         curr.prev->next = &curr;         m_cnt++;      };      iterator  erase(iterator it)      {         node_type & curr = *it.curr;         node_type & aft = *curr.next;         curr.next->prev = curr.prev;         curr.prev->next = curr.next;         m_cnt--;         return iterator(&aft);      };      void  clear()      {         m_cnt = 0;         m_EndNode.prev = &m_EndNode;         m_EndNode.next = &m_EndNode;      };      void  swap(this_type & other)      {         std::swap(m_EndNode.prev, other.m_EndNode.prev);         std::swap(m_EndNode.next, other.m_EndNode.next);         std::swap(m_cnt, other.m_cnt);      };   public:      void  remove(T & t)      {         erase(iterator(&_Node(t)));      };      template<class _Pr1>      void remove_if(_Pr1 _Pred)      {   // erase each element satisfying _Pr1         iterator _Last = end();         for (iterator _First = begin(); _First != _Last; )            if (_Pred(*_First))               _First = erase(_First);            else               ++_First;      };   };   template<class T, typename Tag > inline   void swap(list<T, Tag>& _Left, list<T, Tag>& _Right)   {   // swap _Left and _Right lists      _Left.swap(_Right);   }   template<class T, typename Tag > inline   bool operator==(const list<T, Tag>& _Left, const list<T, Tag>& _Right)   {   // no element could be on two different list at once.      return (&_Left) == (&_Right);   }   template<class T, typename Tag > inline   bool operator!=(const list<T, Tag>& _Left, const list<T, Tag>& _Right)   {         return (!(_Left == _Right));   }/////////////////////////////////}; // (namespace intrusive)/////////////////////////////////

MaulingMonkey

1,729

October 03, 2006 08:03 PM

Quote:Original post by deffer
So I only upcast what I myself downcasted before.

That's still "breaking" the type system by my count (circumventing it's type safety features in one small way). A necessary evil if you will.

NotAYakk

876

October 04, 2006 11:14 AM

Remember what "undefined behaviour" means -- it means the compiler can do whatever the hell it wants. Sometimes you get what you want when you run undefined behaviour -- but on a different system or a different compiler, you have no guarantees.

Want to see a psychotic architecture in which what you are using doesn't work?

Segmented memory -- a memory address is two different integers.

The top integer is the "segment" and the bottom integer is the "offset".

Now, segments overlap.

So, take a structure:

struct example {  virtual void example_is_not_a_pod() { return; };  int foo;  int bar;  double sna;};example* ex = new example();double * s = &(ex->sna);

ex might equal (0x00010000).
s might equal (0x00020000). -- the compiler gave you a different segment! Why? Why not! You are getting a pointer into a non-POD struct, so the only guarantee you get is that *s will change sna.

(int)s - offsetof( example, sna ) then equals 0x0001FFF8 -- a pointer utterly unrelated to ex, pointing to the completely wrong chunk of memory.

Compilers are free to lay out non-POD structures however they want. It might be useful for them to seperately allocate the data-segment of a class, and give the class a pointer to the data-segment -- in which case the distance between the class pointer and the pointer to the member changes randomly with each instance of the class!

The C++ standard gave the compiler writers this freedom to make it easier for them to innovate. In exchange, if you want to know the layout of memory in a struct, you are forced to use POD structs.

pointer _from_ member [c++]

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

pointer _from_ member [c++]

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines