gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

C/C++ > Pointer problems

#120555 - Rajveer - Sun Mar 04, 2007 6:11 pm

Hi guys, I'm using an octree, and in each node there is a linked list of polygons numbers to test collision against.

Code:
struct polyListNode
{
   int polyNo;
   struct node* polyListNode;
};

struct polyListNode* currentPolyListNode;

struct node
{
   u8 split;
   u8 polyCount;
   f32 maxx, maxy, maxz, minx, miny, minz;
   struct polyListNode* polyList;
   struct node* subnode[8];
};


When trying to go through the linked list of a node, I get a few errors:

Code:
         struct polyListNode* tempPolyList = malloc(sizeof(struct polyListNode));
         tempPolyList = (*noderef)->polyList;
         
         while(tempPolyList->polyListNode != NULL)
         {
            tempPolyList = tempPolyList->polyListNode; **ERROR**
         }


Code:
void addLinkedListNode(struct polyListNode* *currentListNode, int c, int temppolycount)
{
   if((temppolycount - c) == 1)
   {
      return;
   }
   else
   {
      struct polyListNode* tempPolyListNode = malloc(sizeof(struct polyListNode));
      (*currentListNode)->polyListNode = tempPolyListNode; **ERROR**
      addLinkedListNode(&tempPolyListNode, (c + 1), temppolycount);
   }
}


Code:
      currentPolyListNode = correctNode->polyList;
      
      int r = 0;
      if(q != 0)
      {
         for(r = 0; r < q; r++)
         {
            currentPolyListNode = currentPolyListNode->polyListNode; **ERROR**
         }
      }


The warning I am getting is:

warning: assignment from incompatible pointer type

Note: Just to let you know they're all in different functions. The problem seems constant though.

Anybody see what I'm doing wrong? I'm tired and ill and at the moment, I'm blind to the problem!

#120573 - Cearn - Sun Mar 04, 2007 7:36 pm

polyListNode exists in three different contexts: a variable, a struct name and a member name. That's gotta give some friction. Doing a little renaming should help.

As for the code:

rajveer wrote:
Code:
         struct polyListNode* tempPolyList = malloc(sizeof(struct polyListNode));
         tempPolyList = (*noderef)->polyList;
         
         while(tempPolyList->polyListNode != NULL)
         {
            tempPolyList = tempPolyList->polyListNode; **ERROR**
         }

You're alllocating a pointer tempPolyList and then making it point to something else. The allocated space is now unreferenced, causing a memory leak.
The reason why 'tempPolyList = tempPolyList->polyListNode' doesn't work is because the lefthand side is a struct polyListNode and the righthand side a node. These are not the same. I can't be sure what it should be, because everything has the same names. Possibly 'tempPolyList= tempPolyList->polyListNode->polyList;'.

Rajveer wrote:
Code:
void addLinkedListNode(struct polyListNode* *currentListNode, int c, int temppolycount)
{
   if((temppolycount - c) == 1)
   {
      return;
   }
   else
   {
      struct polyListNode* tempPolyListNode = malloc(sizeof(struct polyListNode));
      (*currentListNode)->polyListNode = tempPolyListNode; **ERROR**
      addLinkedListNode(&tempPolyListNode, (c + 1), temppolycount);
   }
}

'struct polyListNode* *currentListNode'. If this is the whole function, you don't need the double pointer -- it only confuses things. 'foo->' is clearer than '(*foo)->'. And again, mismatch between polyListNode and node pointers. Same goes for the third function.

#120574 - gmiller - Sun Mar 04, 2007 7:48 pm

I agree with Cearn about the name confusion. If the top nodes link together with each node having a link list of nodes associated with the top node (the one with polyNo in it) then the top node is miss-defined. If you only need a link list of the nodes that have the combined data then there is no reason to separate them. The way it is laid out is is confusing as to what you intended. Does the "struct node" want a list of associated "nodes" or is there something else you are trying to do?

#120578 - Rajveer - Sun Mar 04, 2007 8:38 pm

Oh god, I told you I was tired and ill, what a stupid mistake with the naming of the polyListNode data structure! I've now changed the datastructure for the polyListNode to:

struct polyListNode
{
int polyNo;
struct polyListNode* nextNode;
};

struct polyListNode* currentPolyListNode;

Thanks guys for pointing it out :)

Basically I was trying to create a linked list of polygon numbers for each octree node, because the number for each octree cannot be preset to a value in my example (and therefore cannot use a simple array). Cheers again.

#120582 - Rajveer - Sun Mar 04, 2007 9:27 pm

Cearn, you said that the code I presented causes a memory leak. If I allocated space for tempPolyListNode and then made it point somewhere else, then the memory leak comes from the space I created for the integer polyNo which is part of the polyListNode data structure? How would I free this part of space and still allow tempPolyListNode point to where I want it to, as two pointers have to be the same type no? (So I'm thinking that I HAVE to assign tempPolyListNode some space in order for it to be of the same type, then point it to somewhere else)

#120586 - gmiller - Sun Mar 04, 2007 10:20 pm

With the way the structure is defined the malloc of polyListNode only gets space enough to hold the int polyNo and a pointer that should point to something of the same type. So this list can only hold polyNo data and a pointer to the next data. I assume this is not what you wanted to do. When you allocate the space with malloc the pointer nextNode will not point to anything that has been allocated. if you want a link list when you allocate the data you have a choice on where in the list you put the new node (even though I think the node is miss defined), you could make it the new head of the list or put it on the end of the list. This will determine how your addLinkListNode should operate.

Could you state what data you think should be in each node so I can see how you logically think it should be. Here is my guess:

Code:

struct polyListNode
{
   int polyNo;
   u8 split;
   u8 polyCount;
   f32 maxx, maxy, maxz, minx, miny, minz;
   struct polyListNode* nextNode;
   struct node subnode[8];
};


In this case each node contains this information and a pointer to the next node with more information on a different polyNo. Of course this is a guess.

#120588 - KayH - Sun Mar 04, 2007 10:21 pm

Hi,

I use for structs something like:
Code:

typedef struct _Poly
{
    int value;
    // some more here
} Poly;

then I can use the "Poly" as a new variable typ without that "struct" everytime, this is much more readable. Of course you can use a better name for "Poly" ... ;-)

Code:

// malloc space on the heap
Poly* pPoly;
pPoly = (Poly*) malloc (sizeof (Poly));

// free them later
free(pPoly), pPoly=NULL;


Additional you should ever test the return value of malloc, if there was not enough space available you get no space and no valid pointer back. Then you get a Null pointer ...
If you ever test the pointer for beeing not Null before you use it, you avoid hard to find issues!
That's why after freeing the space the pointer (pPoly) was set to Null, as you should ever test this(!) you will not use the pointer. Do you see what I mean?

HTH
KaY

#120612 - Rajveer - Mon Mar 05, 2007 12:35 am

Cheers for the replies guys.

@gmiller:
gmiller wrote:
With the way the structure is defined the malloc of polyListNode only gets space enough to hold the int polyNo and a pointer that should point to something of the same type. So this list can only hold polyNo data and a pointer to the next data. I assume this is not what you wanted to do.


Actually thats precisely what I wanted to do :) I've created two separate linked lists. The first is an octree data structure called node (the second data structure defined) which holds information to do with the size of each node, whether its split or not, the number of polygons it holds, and I used to store an array of ints for the polygon numbers. I got rid of that as I dont know how many polygons are to be in each octree node anymore, so I created a second data structure called polyListNode which is simply a linked list of ints, storing only the polygon number. I put a node for the linked list into each octree nodes, but defined it wrong before because...well...I blame it on dopeyness ;) Here's how I should have defined the structures:

Code:
struct polyListNode
{
   int polyNo;
   struct polyListNode* nextNode;
};

struct node
{
   u8 split;
   int polyCount;
   f32 maxx, maxy, maxz, minx, miny, minz;
   struct polyListNode* polyList;
   struct node* subnode[8];
};


@KayH: I've never used a typedef before, does it only do what you said? So instead of having to type "struct poly" you would just type "poly" each time?

Also, good call on testing if malloc worked (I never thought of what you said) but when you made pPoly free, does freeing it not get rid of the pointer, or does it still exist when there is no memory allocated to it?

#120623 - KayH - Mon Mar 05, 2007 1:21 am

Rajveer wrote:
Quote:

@KayH: I've never used a typedef before, does it only do what you said? So instead of having to type "struct poly" you would just type "poly" each time?

Yes, that is what I do (and lot of others too). You give the compiler the possibility to make a typecheck. I would call it: on-the-fly extension of the language. The compiler knows then all about it, as he knows e.g. for double or int. You already use the type "u8"! :-) It is exactly this. Maybe some of the guru's can explain it better. ;-) Or any decent C tutorial.

When the malloc fails, you have not so many option anymore. No space for you means normally also no space for the rest of the program. You should immediately free some resources.
It is more important to check the pointer while your program is running, that means when you try to assign some values.

Freeing only frees the space allocated by malloc! The pointer himself is another variable which get not automatically freed! Freeing it depends on the place where you defined the pointer. If you defined it inside a method, it is normally placed on the stack and will be "freed" when the program leaves the scope of the method. If it is a global pointer variable it is freed when the program ends. If it was "malloced" you now know when it is freed. ;-)

You may also think about reading good tutorials about linked lists. Probably you also often need methods for append, insert, delete one element (from the inner list), exchange two elements and sort the list.

When you often needs this it is possible to code all this one time and use it often for each datatyp you want:

Code:

typedef struct _dLinkedList
{
    void* data; // here you add a link to what you want
    _dLinkedList* prev;
    _dLinkedList* next;
} dLinkedList;


For this new type dLinkedList you implement all the methods you need. In the data pointer you can store a pointer to what you want.

HTH
KaY

#120624 - sajiimori - Mon Mar 05, 2007 1:23 am

Rather than explaining how pointers and dynamic allocation work, I'd suggest picking up a good C book. A few posts on a message board aren't going to give you a comparable level of understanding.

http://www.amazon.com/dp/0672326965

#120681 - gmiller - Mon Mar 05, 2007 2:12 pm

From the data you defined this is what you have.

There is a struct node that can point at a struct polyListNode. The polyListNodes are linked together holding only a PloyNode and the link to the "next" polyListNode. There could be multiple struct nodes that can point to ployListNodes (but no pointers the other way) and then up to 8 other "nodes" linked to a single node. Of course this is reading your data definition. I don't know what else you wanted but the data as defined implies the previous definition.

Code:

struct polyListNode
{
   int polyNo;
   struct polyListNode* nextNode;
};

struct node
{
   u8 split;
   int polyCount;
   f32 maxx, maxy, maxz, minx, miny, minz;
   struct polyListNode* polyList;
   struct node* subnode[8];
};

#121071 - OogyBoogy - Thu Mar 08, 2007 5:29 pm

If you are going to use linked lists, it is far easier to create a seperate Node structure, and include this as the first member of the structures you actualy want to link together.

Code:

typedef struct Node {
    struct Node *next, *previous;
} Node;

typedef struct MyData {
    Node *node;
    /* Add your structure data here... */
} MyData;


This way you can treat any structure as a Node structure simply by typecasting. For instance:

Code:

AddNode (mylist, (Node *) mydata);

_________________
OogyBoogy

#121113 - sgeos - Fri Mar 09, 2007 1:45 am

OogyBoogy wrote:
If you are going to use linked lists, it is far easier to create a seperate Node structure, and include this as the first member of the structures you actualy want to link together.

Clever. I do not recommend this for a beginner.

-Brendan

#121118 - sajiimori - Fri Mar 09, 2007 3:23 am

Yikes, delicate.

Oh, the lengths people will go to to avoid using a basic C++ feature...

#121186 - poslundc - Sat Mar 10, 2007 12:54 am

Oof. Type unsafe.

Good luck if you're working on a team, or if your code has to be maintained/upgraded by others.

I would still prefer void pointers to this method. At least that way the absence of type-safety is upfront and obvious, by virtue of the absence of type.

Dan.

#121190 - tepples - Sat Mar 10, 2007 1:25 am

sajiimori wrote:
Oh, the lengths people will go to to avoid using a basic C++ feature...

Could it have something to do with conflating the perceived overhead of C++ with the known overheads of exceptions, RTTI, and static linked <iostream>, all of which are in the "hello world" executable compiled with Free tools using the default settings?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#121199 - sajiimori - Sat Mar 10, 2007 3:56 am

Yes! =)

Out of curiosity, I just compiled "Hello world" using MinGW, one in C and one in C++, and they were exactly the same size, as long as they both used printf.