C++ Help.. Double linked list

**robwhit** · 02-10-2008

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.

**Elysia** · 02-10-2008

Originally Posted by tabstop

If it's an assignment, Elysia, don't bother the poor guy. His instructor is going to bother him enough.

I know... unfortunately, I do...
So the question was, why are you doing it in the first place (why does the assignment ask you to do it)? That might help find a solution to this whole ordeal.

**garrettw09** · 02-10-2008

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.

**garrettw09** · 02-10-2008

says it cant convert from void* to int.

**tabstop** · 02-10-2008

Originally Posted by garrettw09

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.

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:

Code:

void MoveNext(Node *&current, Node *&previous) {
    Node *temp;
    temp = current->ptr ^ previous;
    previous = current;
    current = temp;
}

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.

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.

**garrettw09** · 02-10-2008

no.. i have to write them all.. but i figured if i could get next, I could get the rest:: prev, insert, etc.

**tabstop** · 02-10-2008

Originally Posted by garrettw09

no.. i have to write them all.. but i figured if i could get next, I could get the rest:: prev, insert, etc.

Note: since we're dealing with pointers and ints, you need not static_cast, but reinterpret_cast. Remember that you will always need that one extra pointer for previous, to walk forward. Good luck.

**garrettw09** · 02-10-2008

error C2296: '^' : illegal, left operand has type 'Node *'

**iMalc** · 02-11-2008

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

**sktrs_kpr** · 02-12-2008

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

**k4m1k4z3** · 02-12-2008

Same problem here. I hope the project gets postponed

**tabstop** · 02-12-2008

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

Code:

reinterpret_cast<int>(one_ptr) ^ reinterpret_cast<int>(other_ptr)

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

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.

**garrettw09** · 02-12-2008

Well I got everything working except for one minor problem.. i dont think he'll really postpone either.. it's the first project..

**sktrs_kpr** · 02-12-2008

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

**tabstop** · 02-12-2008

Originally Posted by sktrs_kpr

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