Inconsistent double pointer (linked list)

Question

I have a game I am working on that uses a linked list for the entities in the game. I have found what I think to be some sort of bug. Note, I'm coding in C. But after this trouble with C pointers I'm thinking about trying C++ techniques.

In my debug testing two projectiles were colliding which blows both of them up. Basically the situation is this:

Starting in Entity's move function: 1) Projectile entity moves 2) Loop through all entities checking collision at this new location 3) If collision, in this case between projectiles, remove both

I pass a double pointer of the entity to the function that does collision. That entity may be removed but I still need to use it for advancing the entity to the next one in the list (in the while loop). If that didn't make sense it is seen as this:

    ENTITY *node;

    while (node)
    {
        ...

        entity_do_collision (&node); // <-- node may be removed in this function

        //Debug
        if (node == global_node)
        {
        }
        else
            node = global_node;

        node = node->next; // <-- pass a double pointer above so this works here
    }

So, I've ran through the code so many times and don't see any illegal operations. The part that gets me is sometimes the double pointer will work and sometimes it won't. I tested using a global entity pointer (that always works) to compare back in my entity move function to test if the node being removed matches what it was set to in the entity remove function.

This description is a little abstract, so let me know if I need to explain more.

score 2 · Answer 1 · edited May 23 '17 at 11:47

There are zillion solutions which would or would not work for your exact problem.

Here are some ideas to start with:

Do not delete objects from the container on collision, but mark them "dead". Clean up "dead" bodies in separate pass after collision detection finished.
Mark them dead on collision, but not delete at all. Just reuse marked nodes for future entities.
Improvement of (2): sort your container, so "dead" entities went to the tail and mark size of the container as it would contain only "living" ones
Improvement of (1), (2), (3): implement some kind of "garbage collection", so "dead" entities would be cleaned up let's say once a second or once a frame or when memory threshold reached.

etc.

Sidenote: You should never use linked lists in 21th's century (an era of hierarchies of caches, prefetching, out-of-order execution and mutithreading), unless you really, really have no other choice and you understand what you are doing. Use arrays by default, swith to something else only if you find it reasonable.

More info:

Bjarne Stroustrup. The C++ Programming Language (4th edition). 2013. ISBN: 978-0-321-56384-2. Chapter 31.6. Advice. page 924: '[2] Use vector as your default container' — jensa, Mar 12 '15 at 12:32
Thanks Drop those are good suggestions. I am a fairly new programmer (hobbyist for 2-3 years) and feel comfortable with C and the "old ways". I want a well programmed project, but I just thought I could use the old techniques if I was careful. However, it would probably be worthwhile to learn the "new ways" that are more reliable and efficient. — sethb411, Mar 12 '15 at 16:42
Do you have any answer in regards to why a double pointer might not be reliably returning the correct address? Or is there not enough information to determine that? — sethb411, Mar 12 '15 at 16:44

joop · Answer 2 · 2015-03-12T17:27:04.900

Original code:

ENTITY *node;

    while (node)
    {
        ...

        entity_do_collision (&node); // <-- node may be removed in this function
        node = node->next;
        /* the function can have changed node's value
        ** but on the next iteration ( on the **value** of node->next)
        ** the original node->next will not be affected!
        */
    }

Sample code using pointer tot pointer:

ENTITY **pp;
for (pp = &global_node; *pp; pp = &(*pp)->next)
    {
        ...

        entity_do_collision (pp); // <-- *pp  (= node) may be removed in this function

        ...
    }

Inconsistent double pointer (linked list)

2 Answers2