C++ Help.. Double linked list

This is a discussion on C++ Help.. Double linked list within the C++ Programming forums, part of the General Programming Boards category; C99 has the type intptr_t that you can convert to and from void*. So ptr1 = (mypointer_type *)(void*)(( (intptr_t)(void*)ptr2 ) ...

  1. #16
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    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.

  2. #17
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,020
    Quote Originally Posted by tabstop View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #18
    Registered User
    Join Date
    Feb 2008
    Posts
    12
    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.

  4. #19
    Registered User
    Join Date
    Feb 2008
    Posts
    12
    says it cant convert from void* to int.

  5. #20
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by garrettw09 View Post
    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.

  6. #21
    Registered User
    Join Date
    Feb 2008
    Posts
    12
    no.. i have to write them all.. but i figured if i could get next, I could get the rest:: prev, insert, etc.

  7. #22
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by garrettw09 View Post
    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.

  8. #23
    Registered User
    Join Date
    Feb 2008
    Posts
    12
    error C2296: '^' : illegal, left operand has type 'Node *'

  9. #24
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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"

  10. #25
    Registered User
    Join Date
    Feb 2008
    Posts
    3
    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...

  11. #26
    Registered User
    Join Date
    Feb 2008
    Posts
    1
    Same problem here. I hope the project gets postponed

  12. #27
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.
    Last edited by tabstop; 02-12-2008 at 09:21 PM.

  13. #28
    Registered User
    Join Date
    Feb 2008
    Posts
    12
    Well I got everything working except for one minor problem.. i dont think he'll really postpone either.. it's the first project..

  14. #29
    Registered User
    Join Date
    Feb 2008
    Posts
    3
    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!!

  15. #30
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by sktrs_kpr View Post
    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.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked List Problem
    By Shiggins in forum C++ Programming
    Replies: 4
    Last Post: 03-10-2009, 08:15 AM
  2. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 06:46 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21