Handmade Network»Forums
11 posts
Confused about free list in Episode 57
Edited by baublebeard on Reason: clearer title

I'm having trouble understanding Casey's explanation of his free list in the "world" struct with the variable "firstFree". Whenever the first block in the hash table gets emptied and it's next block gets copied into it, he has the next pointer of what is now the firstBlock point to "firstFree" in the "world" struct. Then "firstFree" points back to the new first block. What is this doing? I think I'm just misunderstanding what "firstFree" is representing.

Gaurav Gautam
98 posts
Confused about free list in Episode 57
Edited by Gaurav Gautam on
if(Chunk)
{
   world_entity_block *FirstBlock = &Chunk->FirstBlock;
   for(world_entity_block *Block = FirstBlock;
       Block;
       Block = Block->Next)
   {
       for(uint32 Index = 0;
           Index < Block->EntityCount;
           ++Index)
       {
           if(Block->LowEntityIndex[Index] == LowEntityIndex)
           {
              Assert(FirstBlock->EntityCount > 0);
              Block->LowEntityIndex[Index] =
                   FirstBlock->LowEntityIndex[--FirstBlock->EntityCount];
              
              // At this point the first block is empty and needs to be reclaimed 
              if(FirstBlock->EntityCount == 0)
              {
                 // If the firstblock has a next block because otherwise you don't need to reclaim it
                 if(FirstBlock->Next)
                 {
                    // make a fresh pointer to the next block of first
                    world_entity_block *NextBlock = FirstBlock->Next;
                    // copy the contents of the next block into the first block
                    *FirstBlock = *NextBlock;
                             
                    // Set the next block into the list of free blocks       
                    NextBlock->Next = World->FirstFree;
                    // Set the head of freeblocks to be this block
                    World->FirstFree = NextBlock;
                  }
              }

              Block = 0;
              break;
           }
        }    
    }
}

Explained with images it goes like this. So from right to left imagine that the green line is your memory:

  1. make a pointer N.B. (in pink) to the next of the first block F.B.
  2. Copy all contents of N.B. to the memory of F.B. This will also copy the next pointer of N.B. to F.B. (sorry for bad drawing), and now both N.B. and F.B. have next pointers pointed to the unnamed next block of the next block as pictured.
  3. Move the next pointer of the N.B. to the firstfreeblock which is basically a collection of memory laying around to be used later
  4. Update the first free pointer (F.F.) to be this N.B.

So you end up with the next block's contents in the first block and the nextblock itself becomes discarded.

So clever! I might be wrong though as I'm new to this stuff as well.

WhatsApp Image 2022-10-10 at 23.15.10.jpeg

11 posts
Confused about free list in Episode 57

Thanks for the help! It was mainly what firstFree was supposed to be that was messing me up. I kept thinking it was just one block getting clobbered and not a chain of free blocks.

11 posts
Confused about free list in Episode 57

Just for anyone coming to this post in the future, Casey gives a brief explanation of whats going on in the Q&A of episode 60. guatam1168's explanation is essentially the same so both are good!