C++ Help.. Double linked list

bool LinkedList::next()
{
Node *prev, *temp;

temp->ptr = static_cast<int>(prev->ptr) ^ static_cast<int>(current->ptr);
prev->ptr = current->ptr;
current->ptr = temp->ptr;
}

I keep getting the error:

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

If this is totally wrong, can you just tell me how to do it, but it needs to be return type bool. The node class is defined as :

Code:

---


class Node
{
  public:

    Node(){}
    ~Node(){}

    // stores the value for the node
    int value;
 
    // stores both the next and previous pointers, combined with the xor operator
    Node *ptr;
};

---

Use code tags for all code.
And tell me, what's this supposed to do?

Code:

---

temp->ptr = static_cast<int>(prev->ptr) ^ static_cast<int>(current->ptr);

---

it is supposed to xor those two pointers on the right and set the left one equal to that

You are trying to assign an int to a pointer. Why are you trying to do that?

ok i dont know how to do it, but I know I need to xor the two pointers on the right and set that to the pointer on the left

XORing pointers might not work on all platforms. Why do you want to XOR the pointers?

It's how you move from each element in the list to the next..

:eek:

Wow. That code is all kinds of wrong. Even if it compiled, it's dead when you access a member of an uninitialized pointer (temp -- and prev for that matter)).

You're going to have to static_cast it back to a Node *, after you static_cast it to an int earlier. I would be surprised to find that the xor of two pointers is also a valid ptr -- and for sure it's not a valid pointer to anything you have.

We can't help you make it Bool, because what is that supposed to mean? Bool only has true and false, you can't return a pointer out of it.

I'm going to be generous and assume that this is an assignment and ye know not what ye do. Xor'ing addresses is an old, antiquated, dirty-even-for-the-time way to squeeze an extra 24 bits (or whatever a pointer was worth on your architecture) out of a node structure. (The penalty was that you always always always needed to have an extra pointer to previous (if you were traveling forward) or to next (if you were traveling backward) to do the xor with and that NULL had to be all bits 0.) The idea that you wouldn't use std::list, or if the assignment is to roll your own, a "normal" doubly linked list, is hard to fathom these days.

yeah it is an assignment.. i need to make a double linked list that only uses one pointer .. im trying to make the next function by xor'ing two pointers together, that is how i was told to do it.. you can start from scratch if you want.. i just have no idea.. and in response to the last thread, I cant static cast it back, because it says i cant static cast it to int in the first place.. any ideas will be welcome.. Thanks..

Quote:

---

Originally Posted by garrettw09

yeah it is an assignment.. i need to make a double linked list that only uses one pointer ..

---

Why would you want to do that? No sane programmer would. If you use only one pointer, use a single linked list.

it saves space.. like 4 bytes per pointer that you don't use i guess.. it's dumb.. but i just need to know how to do it..

4 bytes is nothing. So explain again why you need to do it that way?

it is an assignment.

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

Anyway, you're going to need to be more specific on what you're trying to do. What is your Bool function supposed to test? (And remember, it's a Bool, so it absopositively has to be a yes/no question.)

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.

Quote:

---

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.

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.

Quote:

---

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.

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

Quote:

---

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.

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

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

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.

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

Quote:

---

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.

Quote:

---

Originally Posted by tabstop

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.

---

ah ha... you got me there!

It has been too long since i have done any coding in C++... I sorta wish our first project would have been a little "nicer"!


Well thank you very much folks!