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

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

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 ?

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.

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.

Quote:

---

Originally Posted by MacGyver

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?

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.

Quote:

---

Originally Posted by MacGyver

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.

Quote:

---

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?

Edit: I think I confused myself..... rereading.....

Edit again: Mmkay, I think you're right. I apologize. Very nicely written empty function.

Quote:

---

Originally Posted by MacGyver

Very nicely written empty function.

---

Thanks :p didn't even have to debug it, worked immediately:p

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.

Quote:

---

Originally Posted by pronecracker

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.

Quote:

---

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:p although it might not make that much a difference.

Quote:

---

Originally Posted by pronecracker

Maybe, but then all the elements are as big as the biggest element type, and I don't like that:p 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?

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

Quote:

---

Originally Posted by pronecracker

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

---

I'd suggest storing the objects themselves elsewhere, and keeping a void * pointer to the object inside the node. Functions which operate on nodes would cast the void * to the appropriate type based on the value of iType.

This is basic polymorphism, which is much easier to handle in C++ than in C.

Quote:

---

Originally Posted by brewbuck

This is basic polymorphism, which is much easier to handle in C++ than in C.

---

I know, please don't take my signature too literally:p I sometimes have thoughts like that, because C seems so simple and I sometimes get confused because of all the functionality of C++.

But, why is using a void* safer then what I'm doing now? And what about

Code:

---

union {
Type1 *pType1;
Type2 *pType2;
};

---

Quote:

---

Originally Posted by pronecracker

But, why is using a void* safer then what I'm doing now? And what about

Code:

---

union {
Type1 *pType1;
Type2 *pType2;
};

---

---

I'd say it's safer because it's more likely to work on some screwy compiler. The standard indicates that what you are doing SHOULD work, but I wouldn't count on it. The union thing is fine, too. I do something very similar when writing parsers that build parse trees -- each node of the tree is of type Node, with some code which identifies what kind of node it is, and the data specific to that node type is kept in a field of a union.

If you're going to use a union, no need to use pointers. Just embed the type-specific data directly in there.

Quote:

---

Originally Posted by pronecracker

But, why is using a void* safer then what I'm doing now? And what about

Code:

---

union {
Type1 *pType1;
Type2 *pType2;
};

---

---

Fine details for varying systems.
http://www.open-std.org/jtc1/sc22/wg...24.pdf#page=59

Implementations have existed in which pointers to different types have different representations and/or sizes.
http://c-faq.com/null/machexamp.html