Thread: Is this safe - linked list with multiple types

  1. #1
    Registered User pronecracker's Avatar
    Join Date
    Oct 2006
    Location
    netherlands
    Posts
    158

    Wink Is this safe - linked list with multiple types

    Hi
    I have a linked list that can store two types of object. It's kinda weird and hackish but it seems to work.
    Code:
    struct Node
    {
        struct Node *pNext;
        struct Node *pPrev;
        int iType;
    };
    struct Type1
    {
        struct Node *pNext;
        struct Node *pPrev;
        int iType;
        
        float f1, f2;
    };
    struct Type2
    {
        struct Node *pNext;
        struct Node *pPrev;
        int iType;
        
        int x, y, z;
    };
    Code:
    struct Node *pRoot;
    When iterating through this list, a struct Node * is used. The object is identified by its iType field, then the pointer is converted to a struct Type1 * or a struct Type2 * to access the other members.

    The deallocation of the linked list happens like this:
    Code:
    void DeleteNode(struct Node *pNode)
    {
        if(pNode->pPrev) pNode->pPrev->pNext = pNode->pNext;
        if(pNode->pNext) pNode->pNext->pPrev = pNode->pPrev;
        free(pNode);
    }    
    void EmptyList()
    {
        while(pRoot->pNext) DeleteNode(pRoot->pNext);
    }
    
    /// here
    EmptyList();
    free(pRoot);
    My question is: doesn't this cause a memory leak? I could imagine that in the DeleteNode() function only the first three members get properly deallocated because the pointer is of type struct Node *.
    Don't call me stupid.

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Code:
    #define type_1		1
    #define type_2		2
    
    struct type1
    {
    	int x, y, z;
    };
    struct type2
    {
    	float f1, f2;
    };
    
    struct Node
    {
    	struct Node *pNext;
    	struct Node *pPrev;
    	int iType;
    	union
    	{
    		struct type1 t1;
    		struct type2 t2;
    	}payload;
    };
    I imagine something like this might work. This is how Microsoft handles the different type of Input events....

    http://msdn2.microsoft.com/en-us/library/ms683499.aspx

  3. #3
    Registered User pronecracker's Avatar
    Join Date
    Oct 2006
    Location
    netherlands
    Posts
    158
    What I use does work certainly, but I was not sure if all of the memory was freed correctly. As the free() function takes a void* parameter, my guess is that the pointer type does not really matter ?
    Don't call me stupid.

  4. #4
    Registered User
    Join Date
    Jan 2007
    Posts
    40
    A common approach to linked lists is to keep the data separate from the linked list, and to keep the linked list open ended in terms of what data it can take in. To do this, we usually use a void pointer (void*). Although a union would work just as well ad-hoc.

  5. #5
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    A union is a little more safer than a void *, but less flexible.

    In terms of actually freeing the memory, I don't believe you're doing it right with your EmptyList() function. I think you're not going through the entire linked list because you're forgetting to set a pointer to the next node upon the end of an iteration.

  6. #6
    Registered User pronecracker's Avatar
    Join Date
    Oct 2006
    Location
    netherlands
    Posts
    158
    Quote Originally Posted by MacGyver View Post
    A union is a little more safer than a void *, but less flexible.

    In terms of actually freeing the memory, I don't believe you're doing it right with your EmptyList() function. I think you're not going through the entire linked list because you're forgetting to set a pointer to the next node upon the end of an iteration.
    DeleteNode should do this, if I understand right?
    Don't call me stupid.

  7. #7
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Before EmptyList():

    Code:
    Root -> element 1 -> element 2 -> element 3 -> NULL
    After EmptyList():

    Code:
    Root -> element 2 -> element 3 -> NULL
    If I'm off on this, I apologize.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by MacGyver View Post
    Before EmptyList():

    Code:
    Root -> element 1 -> element 2 -> element 3 -> NULL
    After EmptyList():

    Code:
    Root -> element 2 -> element 3 -> NULL
    If I'm off on this, I apologize.
    Actually, it's worse than that. In EmptyList pRoot->pNext is never modified. Even if DeleteNode attempted to modify this (which it doesn't), it can't becase the parameter would need to be a pointer pointer anyway.

    Therefore EmptyList is an infinite loop. If you're not seeing an infinite loop, then either:
    pRoot->pNext is NULL to beign with, or
    The function is never being called, or
    Some other code not shown is modifying pRoot->pNext, or
    The code shown does not match the code in your program.
    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"

  9. #9
    Registered User pronecracker's Avatar
    Join Date
    Oct 2006
    Location
    netherlands
    Posts
    158

    Cool

    Actually, it's worse than that.
    Then why does it work?

    Code:
    void DeleteNode(struct Node *pNode)
    {
        if(pNode->pPrev) pNode->pPrev->pNext = pNode->pNext;
        if(pNode->pNext) pNode->pNext->pPrev = pNode->pPrev;
        free(pNode);
    }    
    void EmptyList()
    {
        while(pRoot->pNext) DeleteNode(pRoot->pNext);
    }
    
    /// here
    EmptyList();
    free(pRoot);
    Okay, lets go through this step by step:

    Code:
          ->           ->           ->           ->
    Root     Element1     Element2     Element3     NULL
         <-           <-           <-

    Code:
    while(pRoot->pNext)  // TRUE
    
    DeleteNode( pRoot->pNext )   // pNode = &Element1
    
    if(pNode->pPrev) // TRUE
            pNode->pPrev->pNext = pNode->pNext
    ||
    \/
    Code:
          -------------->           ->           ->
    Root     Element1---> Element2     Element3     NULL
         <-           <-           <-


    Code:
    if(pNode->pNext) // TRUE
            pNode->pNext->pPrev = pNode->pPrev
    ||
    \/
    Code:
          -------------->           ->           ->
    Root <---Element1---> Element2     Element3     NULL
         <--------------           <-


    Code:
    free(pNode)
    ||
    \/
    Code:
         ->           ->           ->
    Root    Element2     Element3     NULL
        <-           <-

    Get the idea?
    Last edited by pronecracker; 05-29-2007 at 08:52 AM.

  10. #10
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Edit: I think I confused myself..... rereading.....

    Edit again: Mmkay, I think you're right. I apologize. Very nicely written empty function.
    Last edited by MacGyver; 05-28-2007 at 12:42 PM.

  11. #11
    Registered User pronecracker's Avatar
    Join Date
    Oct 2006
    Location
    netherlands
    Posts
    158
    Quote Originally Posted by MacGyver
    Very nicely written empty function.
    Thanks didn't even have to debug it, worked immediately

    Quote Originally Posted by iMalc
    In EmptyList pRoot->pNext is never modified. Even if DeleteNode attempted to modify this (which it doesn't), it can't becase the parameter would need to be a pointer pointer anyway.
    nonsense

    Quote Originally Posted by iMalc
    Some other code not shown is modifying pRoot->pNext
    It is shown, it is right there in front of you.


    I think I was most looking for a better way to store multiple types in a linked list.
    Using a void* instead of putting the data directly after the Node members is an option, but is it really better? Both involve a pointer cast.
    Don't call me stupid.

  12. #12
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by pronecracker View Post
    My question is: doesn't this cause a memory leak? I could imagine that in the DeleteNode() function only the first three members get properly deallocated because the pointer is of type struct Node *.
    Nope. Look at the prototype for the free() function. It takes a void *, not a particular type of pointer. free() neither received nor needs the information about the particular type. It "knows" how big the chunk of memory really is.

    I've seen code pretty much identical to this before. On many platforms it works fine. I think using a union would be far safer, though.

  13. #13
    Registered User pronecracker's Avatar
    Join Date
    Oct 2006
    Location
    netherlands
    Posts
    158
    I think using a union would be far safer, though.
    Maybe, but then all the elements are as big as the biggest element type, and I don't like that although it might not make that much a difference.
    Don't call me stupid.

  14. #14
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by pronecracker View Post
    Maybe, but then all the elements are as big as the biggest element type, and I don't like that although it might not make that much a difference.
    As long as the varying elements always come at the end of the struct, this SHOULD be safe. But I question the need to keep various types of data in the same linked list. Why are you doing this?

  15. #15
    Registered User pronecracker's Avatar
    Join Date
    Oct 2006
    Location
    netherlands
    Posts
    158
    Because they are related, they are different kinds of shapes in some sort of drawing program. And they are possibly stored in order from back to front (Z).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  5. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM