Sign in to follow this  
deffer

pointer _from_ member [c++]

Recommended Posts

Is there any legal way to obtain a pointer to an object, having a poointer to one of its member variables.
struct A : public //...
{
   // ...
   int  m_Member;
   // ...
};

int *pMemb = //...
A *pA = ??? ( pMemb );
I know that there's some pointer twiddling, like below (recall old offsetof macro), but is this reliable?
(A*)(void*)
(
   ((char*)(void*)pMemb) -
      (size_t)( ((char*)(void*)&((A*)0)->m_Member) - ((char*)0) )
)

Share this post


Link to post
Share on other sites
typedef int A::*IntMember;
IntMember member=&A::m_Member;
A a;
A* pa=&a;
(a.*member)=3;
cout<<pa->*member;

try this way :)

Share this post


Link to post
Share on other sites
No, there is no safe, general way to do this in C++.

Pointers to members don't allow you to recover an object; that is, if you have a pointer-to-member-of-A you cannot get the specific A that pointer-to-member-of-A came from, because it didn't come from a specific A. Note that lexchou's example initialized "member" without an instance of A. Furthermore, to do anything useful with a pointer-to-member-of-A you need an A, which is what you want to extract; so pointers-to-members cannot solve the problem.

Without pointers to members, you must rely on disgusting and unsafe (usually undefined-behavior-invoking) pointer trickery that requires the function that is using this trickier pathologically coupled to A (that is, it knows about and relies on A's internal layout without having access to or being a part of A).

For example, given a pointer-to-int that I know "know" points somewhere instance an instance of A, how do I found out where the beginning of A is? I need to know which specific member the pointer points at. I need to know if A has a vtable. I need to know if A is part of an inheritance chain (especially multiple-inheritance).

Why do you think you need to do this?

Share this post


Link to post
Share on other sites
[quote]Original post by jpetrie
No, there is no safe, general way to do this in C++.

... ...[quote]

C++ provides a way to handle the member (function) pointer, and that hides the details like vtable, memory align etcs. just like I wrote up stairs

if you uses code to get the offset of a field like:

#define OFFSET(T,F) ((int)&(((T*)NULL)->F))
cout<<OFFSET(A,m_Member)<<endl;
cout<<OFFSET(A,m_Member2);

and the offset of the field will be valid while you direct access through pointer+offset, because the compiler will handle the right offset via this code no matter what the memory layout is or what cookies the compiler filled.

Share this post


Link to post
Share on other sites
Quote:
Original post by lexchou
C++ provides a way to handle the member (function) pointer, and that hides the details like vtable, memory align etcs. just like I wrote up stairs

if you uses code to get the offset of a field like:

#define OFFSET(T,F) ((int)&(((T*)NULL)->F))
cout<<OFFSET(A,m_Member)<<endl;
cout<<OFFSET(A,m_Member2);

and the offset of the field will be valid while you direct access through pointer+offset, because the compiler will handle the right offset via this code no matter what the memory layout is or what cookies the compiler filled.

Actually, that's not at all legal, as you're playing around with bad pointers (which is strictly prohibited by the standard). How the compiler implements offsetof is an implementation detail that the standard (neither C nor C++ states how it operates, just the result of it, which is simply "an integer constant expression that has type size_t, the value of which is the offset in bytes, to the structure member (designated by member-designator), from the beginning of its structure (designated by type).") does not state, except that it will be a macro and that it can only accept a restricted set of types, specifically, POD structures or POD unions (18.1 -5). Nothing more. If you're class is NOT a POD structure or union, then you cannot use offsetof and expect defined behavior.

Share this post


Link to post
Share on other sites
Well, here's the thing, lexchou.

First, you did not provide a solution to the original question. A pointer-to-member-of-A does not carry with it any information about which specific A it was constructed from, because, again, it was not constructed from a specific A, which means it cannot be used to recover a pointer to A from a regular pointer or a pointer-to-member (which is what the original poster wanted). Your own example illustrates this quite clearly, since you a) construct a pointer-to-member-of-A without a specific instance of A, and b) use that pointer-to-member-of-A on a specific instance of A, failing to solve the original poster's problem.

Second, your follow-up code

#define OFFSET(T,F) ((int)&(((T*)NULL)->F))
cout<<OFFSET(A,m_Member)<<endl;
cout<<OFFSET(A,m_Member2);


is not reliable; in fact, it is guaranteed to produce undefined behavior. Just because it might work in practice doesn't mean it is correct. Even it were correct, it still does not answer the original poster's question since it provides you with (what you hope to be) a byte offset from the beginning of an object of type A to a given member of A; but this is not the data that the original poster has.

Let's examine the ways you've created undefined behavior.

First and foremost, you've relied upon the value-representation (i.e., the bits) of a pointer being well-defined as byte addresses. They are not. The standard explictly states that the value representation is up to the implementation, and thus unreliable.

Second, you assume that the null pointer is 0. It isn't, neccessarily. A constant integral expression that evaluates to zero will be converted to the null pointer value, but that value is implementation defined and need not neccessarily have an all-zero bit pattern. It could easily, in some places, be a segment:offset style form with the bitpattern (0x77770000), perhaps, in which case your offset will be quite amusing. And useless as an offset.

Finally, you deference null. The standard draft I have here is wishy-washy on this at the moment; a number of places indicate that dereferencing null is undefined, but the definition of unary operator * does not, as you might expect. Supposedly this was cleared up for the 2003 draft, or will be cleared up for the 0x draft -- the resolution I'm looking at was dated 2000, and I don't have a newer copy of the standard handy so I can't be sure.. However, the proposed clarification is that the dereference is legal... but the subsequent use of the value is undefined. And you use the value. So either way, you've done something naughty.

I will reiterate. Given a pointer to a type, and only a pointer to a type, you cannot safely and sanely discover if what is pointed to is a member of a type A, nor can you recover a pointer to the containing instance of type A even if you make the assumption that what is pointed to is a member.

...and the fact that one would need to do so indicates a design flaw.

Share this post


Link to post
Share on other sites
Quote:
Original post by jpetrie
For example, given a pointer-to-int that I know "know" points somewhere instance an instance of A, how do I found out where the beginning of A is? I need to know which specific member the pointer points at. I need to know if A has a vtable. I need to know if A is part of an inheritance chain (especially multiple-inheritance).


Why is that?
I'm not attempting to count the offset on my fingers, addding sizes of preceeding members, or something that crazy.

Do I need to know any of such stuff when doing:
A * pA = ...;
int* pMemb = &pA->m_Member;

Even when A is stuffed with padding/vtables/hidden-pointers-to-whatever, that code is realiable, and is just adding some offset to (&a).
Event when A is polymorfically some B, that has multiple inheritance and what-not, does that code need to care about it? Not a bit. (a) is a perfectly good instance of A for all the compiler cares at that moment.

If I can do this operation safely anywhere, why can't I do the exact reverse?
int *pMemb = ...;
A *pA = something<A, &A::m_Member>(pMemb);


Quote:
Original post by jpetrie
Why do you think you need to do this?

I'm creating an intrusive container. Just for practice and my own curiosity, so don't go nuts. [grin]

So what's exactly bad in the code I originally provided?

Quote:
Original post by jpetrie
Finally, you deference null. The standard draft I have here is wishy-washy on this at the moment; a number of places indicate that dereferencing null is undefined, but the definition of unary operator * does not, as you might expect. Supposedly this was cleared up for the 2003 draft, or will be cleared up for the 0x draft -- the resolution I'm looking at was dated 2000, and I don't have a newer copy of the standard handy so I can't be sure.. However, the proposed clarification is that the dereference is legal... but the subsequent use of the value is undefined. And you use the value. So either way, you've done something naughty.


Which chapter?

Share this post


Link to post
Share on other sites
Quote:
Original post by jpetrie
Well, here's the thing, lexchou.
... ...

*Thanks for your reply, hehe
the first reply of this post is my solution to the original question o(>_<)o

>>First, you did not provide a solution to the original question. A pointer-to-member-of-A does not carry with it any information about which specific A it was constructed from, because, again, it was not constructed from a specific A, which means it cannot be used to recover a pointer to A from a regular pointer or a pointer-to-member (which is what the original poster wanted). Your own example illustrates this quite clearly, since you a) construct a pointer-to-member-of-A without a specific instance of A, and b) use that pointer-to-member-of-A on a specific instance of A, failing to solve the original poster's problem.
*A pointer-to-member-of-A indeed does not carry with any information about the struct A's instance, but, it is the meta data just like in Delphi's RTTI, .net's reflection, that can be used with a struct's instance to access the concrete member, although it is a naughty way.


>>Second, your follow-up code
*may be the code I wrote is wrong, but this trick used in many places, the first place I saw it is in Matthew Wilson's <Imperfect C++> #- -

>>is not reliable; in fact, it is guaranteed to produce undefined behavior. Just because it might work in practice doesn't mean it is correct. Even it were correct, it still does not answer the original poster's question since it provides you with (what you hope to be) a byte offset from the beginning of an object of type A to a given member of A; but this is not the data that the original poster has.

*hehe, i thought if i have an offset of a member in a struct, i can access the member in any instance of that kind of struct. the post's title is pointer_from_member, and the pointer_from_member=pointer_of_struct+offset_to_member, that's what I though.



>>First and foremost, you've relied upon the value-representation (i.e., the bits) of a pointer being well-defined as byte addresses. They are not. The standard explictly states that the value representation is up to the implementation, and thus unreliable.
*I relied on a POD type, that's because the poster used a POD type #-_-

>> Second, you assume that the null pointer is 0. It isn't, neccessarily. A constant integral expression that evaluates to zero will be converted to the null pointer value, but that value is implementation defined and need not neccessarily have an all-zero bit pattern. It could easily, in some places, be a segment:offset style form with the bitpattern (0x77770000), perhaps, in which case your offset will be quite amusing. And useless as an offset.
*haha, I'm wrong #-_-, i've never been programming in that sorts of platform, just heard of it before


>>Finally, you deference null. The standard draft I have here is wishy-washy on this at the moment; a number of places indicate that dereferencing null is undefined, but the definition of unary operator * does not, as you might expect. Supposedly this was cleared up for the 2003 draft, or will be cleared up for the 0x draft -- the resolution I'm looking at was dated 2000, and I don't have a newer copy of the standard handy so I can't be sure.. However, the proposed clarification is that the dereference is legal... but the subsequent use of the value is undefined. And you use the value. So either way, you've done something naughty.
*even though I deferenced a null pointer, but that just a syntax form, actually I didn't access the memory arround the null pointer, just let the compiler translate that to an offset.

Share this post


Link to post
Share on other sites
Quote:

Why is that?
I'm not attempting to count the offset on my fingers, addding sizes of preceeding members, or something that crazy.

Do I need to know any of such stuff when doing:
A * pA = ...;
int* pMemb = &pA->m_Member;
Even when A is stuffed with padding/vtables/hidden-pointers-to-whatever, that code is realiable, and is just adding some offset to (&a).
Event when A is polymorfically some B, that has multiple inheritance and what-not, does that code need to care about it? Not a bit. (a) is a perfectly good instance of A for all the compiler cares at that moment.


When you compute pMemb, you are taking the address of an instance of pA->m_mMember, which means A is a complete type and that the compiler has all of the information available to it (size of A, location of potential v-table, et cetera), and you also know where pA is, so the compiler can calculate everything it needs. Now, you want to do something like:

void recover_object_from_member_pointer(int *memberPtr)
{
A *theA = owner_from_member_of< A >(memberPtr);

// do something with theA...
}


correct? We want where A starts. We know where our member pointer is. What we don't know is the offset of the member from the start of an instance of A (i.e., if A had two int members, which one is memberPtr pointing to?), so we have too many unknowns in our equation. If we knew the offset, we could solve, but we don't know the offset because offsetof is for POD types, so in general, we cannot extract that information, so in general, we cannot solve the problem.

In other words, we've lost information by not knowing where the A instance starts, and the language does not provide us with the functionality to safely recover that lost information.

Quote:

I'm creating an intrusive container.

How do you mean "intrusive"? Can you clarify that? Any definition I can think of
doesn't require you to be doing what you want to be doing.

Quote:

So what's exactly bad in the code I originally provided?

The same problems that lexchou's OFFSET sample has.

Quote:

Which chapter?

The draft I was referring to mentioned that dereferencing null is undefined in the section on references (decl.ref) where it discusses null references. The section on unary operators (expr.unary.op) is where unary * is discussed and where it does not state that indirection through null is illegal, as you might expect. The 2000 discussion on active issues where the proposed clarification was discussed is here. Again, I am unclear whether or not this clarification was adopted into the 2003 standard, if it was delayed until 0x, or if it was rejected. I don't have access to a new copy of the standard where I am at the moment. However, whether or not the indirection yeilds undefined behavior, the rest of the code snippet produces it, so it's somewhat of a non-issue.

Quote:

the first reply of this post is my solution to the original question o(>_<)o

But it doesn't answer the original question. A pointer-to-member-of-A doesn't help. Your example created a pointer-to-member-of-A, created a new instance of A, and used that pointer-to-member-of-A to access a field of the new A. That's not what the original poster wanted, which was to user a pointer that happened to point to a member of A and recover the address of the specific A that contains that address.

Quote:

hehe, i thought if i have an offset of a member in a struct, i can access the member in any instance of that kind of struct. the post's title is pointer_from_member, and the pointer_from_member=pointer_of_struct+offset_to_member, that's what I though.

While true, "pointer from member" can be interpreted in a variety of ways, and the way you've interpreted it here is not the way that the original poster wanted it interpreted.

Quote:

I relied on a POD type, that's because the poster used a POD type #-_-

The type of the pointed-to object doesn't matter, POD or not. The bit-pattern of the pointer itself is not guaranteed to be in a form for which your math is valid (again, it could be a segment:offset form)

Quote:

even though I deferenced a null pointer, but that just a syntax form, actually I didn't access the memory arround the null pointer, just let the compiler translate that to an offset.

It is still going to produce undefined behavior. You can't argue with the standard.

Share this post


Link to post
Share on other sites
Quote:
Original post by jpetrie
Now, you want to do something like:

void recover_object_from_member_pointer(int *memberPtr)
{
A *theA = owner_from_member_of< A >(memberPtr);

// do something with theA...
}


correct?


Nope. It should be:

A *theA = owner_from_member_of<A, &A::m_member>(memberPtr);

template<typename T, typename TMemb, TMemb T::* Member>
T* owner_from_member_of(TMemb * ptr)
{
T *t = ...
return t;
};


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

Quote:
Original post by jpetrie
Quote:

I'm creating an intrusive container.

How do you mean "intrusive"? Can you clarify that? Any definition I can think of
doesn't require you to be doing what you want to be doing.


For example, in standard list, we have a list node, which is implemented somewhat like this:

template<typename T>
struct list_node
{
list_node<T> *prev;
list_node<T> *next;
T Data;
};


So dereferencing an iterator (being a wrapped list_node<T>*) is a matter of applying pointer_to_member operator (&list_node<T>::Data) on the list_node pointer.

Whereas in an intrusive list, we are keeping prev/next pointers inside the class T.


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

Quote:
Original post by jpetrie
Quote:

So what's exactly bad in the code I originally provided?

The same problems that lexchou's OFFSET sample has.


That is:

Quote:
Original post by jpetrie
First and foremost, you've relied upon the value-representation (i.e., the bits) of a pointer being well-defined as byte addresses. They are not. The standard explictly states that the value representation is up to the implementation, and thus unreliable.


I don't get it. Really, I don't.

Quote:
Original post by jpetrie
Second, you assume that the null pointer is 0. It isn't, neccessarily. A constant integral expression that evaluates to zero will be converted to the null pointer value, but that value is implementation defined and need not neccessarily have an all-zero bit pattern. It could easily, in some places, be a segment:offset style form with the bitpattern (0x77770000), perhaps, in which case your offset will be quite amusing. And useless as an offset.


My version does not assume it. Accoording to this FAQ:
Quote:
According to the language definition, an ``integral constant expression with the value 0'' in a pointer context is converted into a null pointer at compile time

So I get the actual conversion from the compiler. I'm not doing any tricks to actually get _zero_ pointer.

Quote:
Original post by jpetrie
Finally, you deference null.[...]


Quote:
Original post by jpetrie
Quote:

Which chapter?

[...]


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.

Additionally, the following code compiles just fine on VS2005:

struct A
{
virtual ~A(void) {};
// insert anything
int m_Member;
// insert some more
};

template<int N>
struct blah
{
char space[N];
};

blah< (int) ( ((char*)(void*)&((A*)0)->m_Member) - ((char*)0) ) > bb;


(It doesn't compile on gcc 3.4.6 nor gcc 4.1.1[sad])

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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)
/////////////////////////////////

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this