I am building an entity system for a video game using doubly linked lists. The nodes (entity) of the linked list is allocated in a special manner; when allocating, a free-list is first searched to see if there exists previously deallocated entities. If an entity exists, it is popped off from the free list and then pushed back into the active entity list with original order maintained. If no such entity exists on the free list, a new entity is allocated from the arena.

Here is the code for reference:

void EntitySpawn(GameState *game)
{
    Entity *entity = EntityAllocate(game);
    EntityManager *entity_manager = &game->entity_manager;
    if(entity->prev)
    {
        Entity *next = entity->prev->next;
        entity->prev->next = entity;
        entity->next = next;
    }

    else
    {
        Entity *active_entities = entity_manager->active_entities;
        if(active_entities)
        {
            active_entities->prev = entity;
        }
        entity->next = active_entities;
        entity_manager->active_entities = entity;
    }

    printf("Allocated Entityn");
    entity_manager->num_entities++;
}

void EntityDestroy(GameState *game, Entity *entity)
{
    EntityManager *entity_manager = &game->entity_manager;
    Entity *active_entities = entity_manager->active_entities;
    
    if(!active_entities || !entity) return;
    
    if(active_entities == entity)
    {
        entity_manager->active_entities = entity->next;
    }

    if(entity->next)
    {
        entity->next->prev = entity->prev;
    }

    if(entity->prev)
    {
        entity->prev->next = entity->next;
    }
    
    EntityDeallocate(game, entity);
    entity_manager->num_entities--;
    printf("Destroyed Entityn");
}

Entity *EntityAllocate(GameState *game)
{
    EntityManager *entity_manager = &game->entity_manager;
    Entity *entity = entity_manager->entity_free_list;
    if(!entity)
    {
        entity = ArenaAllocStruct(game->perma_alloc, Entity);
        memset(entity, 0, sizeof(Entity));
        entity->id = entity_manager->num_entities;
    }

    else
    {
        entity_manager->entity_free_list = entity_manager->entity_free_list->next;
    }

    return entity;
}

void EntityDeallocate(GameState *game, Entity *entity)
{
    EntityManager *entity_manager = &game->entity_manager;
    entity->next = entity_manager->entity_free_list;
    entity_manager->entity_free_list = entity;
}

Although this code works about 90% of the time as expected, sometimes the entity destruction causes unexpected behaviour, including deallocated entities breaking free from the free-list (memory leak), or deallocated entities suddenly creating a cycle, resulting in an infinite loop when printing the linked list.

Here’s an example of a memory leak:

[Before deallocation]

Entity Active List
[16] -> [15] -> [14] -> [13] -> [12] -> [11] -> [10] -> [8] -> [7] -> [6] -> [5] -> [4] -> [3] -> [2] -> [1] -> [0] ->
Entity Free List
[9] ->

[After deallocating '12']

Entity Active List
[16] -> [15] -> [14] -> [11] -> [10] -> [8] -> [7] -> [6] -> [5] -> [4] -> [3] -> [2] -> [1] -> [0] ->
Entity Free List
[12] -> [9] ->

After deallocating the 12th node from the Entity Active List, Entity ’13’ suddenly goes missing. I am trying to find the source of this issue in the code, but I can’t seem to trace the culprit.