I have this linked list code that I've been using for quite some time now, but until my latest project, it's been giving me some rare but random crashes. So far, I haven't been able to track down the problem but I did find a way to replicate it (at least I think so). This is a C-based linked list, and yes, my game is written in pure C.

What's happening is (from what I understand) that in rare instances, when iterating through the linked list, the current "node" pointer will have a bogus memory address. Here's an example:

void update_smoke()
{
    struct node_t* n = smoke;
    
    if( !smoke )
        return;
    
    while( n != NULL )
    {
        struct smoke_t* s = n->data;
        
        if( s != NULL )
        {
            /* */
            if( ++s->timer > s->anim_speed )
            {
                s->frame++;
                s->timer = 0;
                if( s->frame >= s->max_frame )
                {
                    set_deletion_callback( delete_smoke_func );
                    list_delete( &smoke, s );
                    s = NULL;
                }
            }
        }
        
        n = n->next;
    }
}

This is how I iterate through my linked lists, and I'm currently managing several of them. As I mentioned, I rarely run into problems with it, but when I do, the problem is almost a complete mystery to me.

Let's say smoke is located at 0x000000010008efd3. The first iteration around, the temporary pointer n will be located in the same location. If/when this does crash, then when I check the location of n, It's usually the same address with an offset (i.e. 0xd00000010008efd3). It's always an address absurdly higher than what I originally started with. This only occurs in loops where I am deleting nodes.

This problem always occurs when I am deleting a node from two lists in the same loop. To work around this, I just set a flag to remove the node later in another pass. My assumption is that the same problem is what's causing random crashes. These crashes are so rare and unpredictable, they're hard to track. This one function is a perfect example.

void check_missiles_for_collisions()
{
    struct node_t* n = enemies;
    
    if( !enemies )
        return;
    
    if( !missiles )
        return;
    
    /* Go through the entire list of enemies and check for collisions with the missile */
    
    while( n != NULL )
    {
        struct enemy_t* e = n->data;
        
        if( e != NULL )
        {
            float x1 = e->x-(e->w/2.0f);
            float y1 = e->y-(e->h/2.0f);
            float x2 = e->x+(e->w/2.0f);
            float y2 = e->y+(e->h/2.0f);
            
            struct node_t* mn = missiles;
            
            while( mn != NULL )
            {
                struct missle_t* m = mn->data;
                
                if( m != NULL )
                {
                    if( m->x > x1 && m->x < x2 &&
                       m->y > y1 && m->y < y2 )
                    {
                        /* Subtract the damage and check for a kill */
                        e->energy -= 5;
                        
                        if( e->energy < 1 )
                        {
                            /* If so, delete this enemy, it's spline, and add an explosion */
                            /* Also, add it's score value to the user's score */
                            user.score += e->score_value;
                            add_explosion( e->x, e->y, No );
                            
                            /* Add a small crystal */
                            add_new_crystal( e->x, e->y, Yes );
                            
                            set_deletion_callback( enemy_delete_func );
                            list_delete( &enemies, e );
                            e = NULL;
                        }
                        
                        /* Go ahead and delete this missile too */
            //            set_deletion_callback( missile_deletion_func );
            //            list_delete( &missiles, m );
            //            m = NULL;
                        m->was_used = Yes;
                        
                        break;
                    }
                }
                
                mn = mn->next;
            }
        }
        
        n = n->next;
    }
}

Note where I commented out the part where I delete the missile. If I uncomment this, it will crash later on down the line somewhere, somehow. Once again, I have no idea what's causing this. Apparently, ignoring the problem and using a workaround was NOT a good idea as this is a prime example of how an isolated problem can evolve into a cancer in your game engine.

If it helps, I'm using XCode 4.5.2 (Apple's LLVM compiler) under MacOSX Lion. I assume the problem will remain the same under Windows. Somehow, I assume the current node or the next pointer is getting corrupted.

For those who want to see the linked list code, here it is:

#include <stdio.h>
#include <stdlib.h>
#include "linkedlist.h"


/* linked list head */
//struct node_t* head = NULL;

/* Deletion callback function */
void (*delete_func)(void*);


/* Add a node at the beginning of the list */
void list_add_beginning( struct node_t** head, void* data )
{
	struct node_t* temp;

	temp = ( struct node_t* ) malloc( sizeof( struct node_t ) );
	temp->data = data;

	if( (*head) == NULL )
	{
		(*head) = temp;
		(*head)->next = NULL;
	}
	else
	{
		temp->next = (*head);
		(*head) = temp;
	}
}

/* Add list node to the end */
void list_add_end( struct node_t** head, void* data )
{
	struct node_t* temp1;
	struct node_t* temp2;

	temp1 = (struct node_t*) malloc( sizeof( struct node_t ) );
	temp1->data = data;

	temp2 = (*head);

	if( (*head) == NULL )
	{
		(*head) = temp1;
		(*head)->next = NULL;
	}
	else
	{
		while( temp2->next != NULL )
			temp2 = temp2->next;

		temp1->next = NULL;
		temp2->next = temp1;
	}
}

/* Add a new node at a specific position */
void list_add_at( struct node_t** head, void* data, int loc )
{
	int i;
	struct node_t *temp, *prev_ptr, *cur_ptr;

	cur_ptr = (*head);

	if( loc > (list_length( head )+1) || loc <= 0 )
	{
	}
	else
	{
		if( loc == 1 )
		{
			list_add_beginning(head, data);
		}
		else
		{
			for( i = 1; i < loc; i++ )
			{
				prev_ptr = cur_ptr;
				cur_ptr = cur_ptr->next;
			}

			temp = (struct node_t*) malloc( sizeof( struct node_t ) );
			temp->data = data;

			prev_ptr->next = temp;
			temp->next = cur_ptr;
		}
	}
}


/* Returns the number of elements in the list */
int list_length( struct node_t** head )
{
	struct node_t* cur_ptr;
	int count= 0;

	cur_ptr = (*head);

	while( cur_ptr != NULL )
	{
		cur_ptr = cur_ptr->next;
		count++;
	}

	return count;
}


/* Delete a node from the list */
int list_delete( struct node_t** head, void* data )
{
	struct node_t *prev_ptr, *cur_ptr;

	cur_ptr = (*head);

	while( cur_ptr != NULL )
	{
		if( cur_ptr->data == data )
		{
			if( cur_ptr == (*head) )
			{
				(*head) = cur_ptr->next;
				if( delete_func ) delete_func( cur_ptr->data );
				free( cur_ptr );
				return 1;
			}
			else
			{
				prev_ptr->next = cur_ptr->next;
				if( delete_func ) delete_func( cur_ptr->data );
				free( cur_ptr );
				return 1;
			}
		}
		else
		{
			prev_ptr = cur_ptr;
			cur_ptr = cur_ptr->next;
		}
	}

	return 0;
}

/* Deletes a node from the given position */
int list_delete_loc( struct node_t** head, int loc )
{
	struct node_t *prev_ptr, *cur_ptr;
	int i;

	cur_ptr = (*head);

	if( loc > list_length( head ) || loc <= 0 )
	{
	}
	else
	{
		if( loc == 1 )
		{
			(*head) = cur_ptr->next;
			if( delete_func ) delete_func( cur_ptr->data );
			free(cur_ptr);
			return 1;
		}
		else
		{
			for( i = 1; i < loc; i++ )
			{
				prev_ptr = cur_ptr;
				cur_ptr = cur_ptr->next;
			}

			prev_ptr->next = cur_ptr->next;
			if( delete_func ) delete_func( cur_ptr->data );
			free(cur_ptr);
		}
	}

	return 0;
}

/* Deletes every node in the list */
void list_clear( struct node_t** head )
{
	struct node_t* cur_ptr, *temp;

	cur_ptr = (*head);

	while( cur_ptr )
	{
		temp = cur_ptr->next;
		if( delete_func ) delete_func( cur_ptr->data );
		free(cur_ptr);
		cur_ptr = temp;
	}
    
    (*head) = NULL;
}

/* Retrieve data from the selected node */
void* list_get_node_data( struct node_t** head, int loc )
{
	struct node_t* cur_ptr;
	int i = 1;

	cur_ptr = (*head);

	if( loc < 1 )
		return NULL;

	while( i < loc )
	{
		cur_ptr = cur_ptr->next;
		i++;
	}
    
    if( !cur_ptr )
        return NULL;
	
	return cur_ptr->data;
}
		
/* Node deletion callback */
void set_deletion_callback( void (*func)(void*) )
{
	delete_func = func;
}

I've been at this for a while, and have no idea what the problem is or how my pointers keep getting corrupted. Any ideas? Thanks ^^

Shogun

I think the problem here is that your delete function gets rid of the associated node data, so this happens:

1. Program decides to delete s.
2. Program deletes s and its associated node n.
3. Program tries to get the next member of n, but can't because that node has been deleted and can no longer be assumed to hold valid data.

How I would solve this is by moving the line n=n->next; to immediately after the program extracts the element from n, so that n will always be valid when you extract the next member from it.

I think the problem here is that your delete function gets rid of the associated node data, so this happens:

1. Program decides to delete s.
2. Program deletes s and its associated node n.
3. Program tries to get the next member of n, but can't because that node has been deleted and can no longer be assumed to hold valid data.

How I would solve this is by moving the line n=n->next; to immediately after the program extracts the element from n, so that n will always be valid when you extract the next member from it.

Okay, this fixed the problem. I felt so dumb after realizing this, I laughed for about 15 minutes straight. Thanks.

I concur with RulerOfNothing.

My recommendation would be to not delete data from linked list, basically remove this line: if( delete_func ) delete_func( cur_ptr->data );

You mentioned having two lists, if they both point to same data, than linked list code will attempt to delete it twice. First time it will work, second time the result will be undefined.

Normally you would allocate and free resources in same module. Since linked list doesn't allocate data, it wouldn't be freeing it.

I do have multiple lists, but none of them point to the same data though. I have separate lists for things like enemies, enemy/user shoots, missiles, explosions, etc. The delete_func callback is really important since very specific data is allocated within the structure it points to (i.e. textures, sound effects, splines) plus the structure was allocated on the heap as well via malloc(). What I do is create an instance of a structure after allocating it, then add it to the list.

Thanks for the replies, I really appreciate it! ^^

Shogun