C99 has the type intptr_t that you can convert to and from void*.
So
ptr1 = (mypointer_type *)(void*)(( (intptr_t)(void*)ptr2 ) ^ ( (intptr_t)(void*)ptr3 )) ;
dunno if C++ has a similar type.
C99 has the type intptr_t that you can convert to and from void*.
So
ptr1 = (mypointer_type *)(void*)(( (intptr_t)(void*)ptr2 ) ^ ( (intptr_t)(void*)ptr3 )) ;
dunno if C++ has a similar type.
Last edited by robwhit; 02-11-2008 at 12:34 PM.
the bool isnt that big of a deal, Ill just throw in a return true or false in there somewhere.. i just need to worry about how to xor the pointer with the prev pointer which is how you move to the next one (the pointer is really prev xor next, so (prev xor next) xor (prev) = next.
I'm trying to get the current pointer to point to the next element in the list.
says it cant convert from void* to int.
So if you're trying to move to the next, you need to know the address of the previous one. That is, it has to get passed in to your function. You can't just try to make it up, as you did originally. The pseudocode might look something like this:
This would actually change the values of current and previous as side effects, rather than returning the new guy. (I gave it a better name, to try to indicate that current is actually going to change.) I also don't know if that's how you write a reference to a pointer.Code:void MoveNext(Node *¤t, Node *&previous) { Node *temp; temp = current->ptr ^ previous; previous = current; current = temp; }
As for xor'ing, if you can't static_cast into int, or long int (check with the sizeof operator to see which size is appropriate), then things are going to start looking really ugly. If you're only writing the "next" part, then someone has already written the earlier parts (I hope)? How does the code that adds a new node to the list get the xor working?
Failing that, I see either your very own home-grown bitwise operations, or worse, a sudden outgrowth of unions in your future.
no.. i have to write them all.. but i figured if i could get next, I could get the rest:: prev, insert, etc.
error C2296: '^' : illegal, left operand has type 'Node *'
Those of you who haven't been programming for the last decade probably have never heard of the trick mentioned here. The basics of it is that every node stores the xor of the next and prev pointers for each node.
To traverse the list requires an interator to contain two successive node pointers.
Lets call then N1Ptr with xored pointer N02Xor, and N2Ptr with xored pointer N13Xor. N02Xor = N0Ptr xor N2Ptr. N13Xor = N1Ptr xor N3Ptr.
You can traverse the list in one direction by xoring one of the iterator's node pointers with the xor'ed pointer stored in the node.
Say our iterator currently holds N1Ptr and N2Ptr.
To go to N0Ptr we can Xor N2Ptr with N02Xor.
To go to N3Ptr we can Xor N1Ptr with N13Xor.
So you can see, that as long as our iterator contains pointers to TWO successive nodes (normal birectional iterators only need one) then we can traverse the list in both directions, using the space for only one pointer in each node.
Now this probably has no place in modern PC programming. For starters 4 bytes is small change, secondly, it wreaks havoc with garbage collectors!
However it is a great challenge for an assignment, and does have practical application in embedded development. No, probably not even Windows CE type embedded programming. I'm talking really embedded stuff here, like when you only have e.g. 32K of RAM and you could really bennefit from saving 2 bytes per node (yes I'm talking about a near pointer).
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
Hey garrett... its a small net. This is nate from 215.
I've been having basically the same problem... this assignments a bit annoying!
I can't get the two pointers to xor (and i have initialized mine), some good info here but not quite what i was looking for.
well good luck, theres not much time left...
Same problem here. I hope the project gets postponed
Well, C++ is strongly enough typed to make this sort of thing difficult.
As mentioned above, if you have two pointers to nodes, you'll have to do
to make it work. In other words, you pretty much have to forcibly disable the type system of C++, which is the definition of "frowned upon". Remember, don't try this at home, kids! (Unless it's an assignment.)Code:reinterpret_cast<int>(one_ptr) ^ reinterpret_cast<int>(other_ptr)
Edit to add: And I suggest storing that hashed pointer, not as a pointer, but as an int, because it sure as heck doesn't point anywhere, and you don't want to accidentally try and dereference it. Let the type system give you a little bit of protection.
And of course, to recover a pointer you'll have to reinterpret_cast the one pointer to an int, and then wrap the whole expression up in a reinterpret_cast<Node *> to actually follow it.
And also, I suppose you should really make sure sizeof(int)==sizeof(Node *) on your machine, and if it doesn't, adjust accordingly.
Last edited by tabstop; 02-12-2008 at 09:21 PM.
Well I got everything working except for one minor problem.. i dont think he'll really postpone either.. it's the first project..
tabstop - i have been trying to work with the "reinterpret_cast" almost exactly like you stated for about an hour now, i'm convinced it is the only way this is going to work (after a lot of reading!), the only difference is i'm using an unsigned int because we have to use the provided variables and the only "extra" variables we are given are two unsigned ints. I got the code to compile this way but i had a runtime error and the app quit :/
I too hope we get an extension, i've put a LOT of time into this and have very little to show! It sure is a messy messy project!!
I told you not to follow that hashed pointer! No, actually, that's the downside of this thing: you have to have your xor's absolutely correct, because if you follow a hash, or try to unhash with the wrong thing, you're going to end up following a pointer to nowhere. If you have a debugger, you can at least see where you are when it blows up, otherwise you'll have to check all your unhashes to make sure.
Edit to add: And I don't know how you're dealing with the edges of the list, but if you're walking out to the ends, make sure you know how NULL hashes and that you don't try to follow NULL either.