A free list is a data structure that keeps track of computer memory addresses that are ready to be used by a running program using dynamic memory allocation. When a program must allocate space from the heap, it’s necessary to create a list. A linked list, for example, might be as simple as a single linked list. Alternatively, a sort tree or other more complex data structure can be used to organize the information. “Manually managing the free list” is an overused phrase that shouldn’t apply to every language. Most high-level computer programming languages manage the free list automatically.
When a software program needs room to store data while it runs, the underlying operating system must give it. The free list contains the addresses of memory blocks where new memory can be allocated. The locations of memory blocks that may be utilized are kept in the free list. The amount of requested memory must be available in one or more of these blocks for the allocation to succeed. When a pointer to an acceptable memory location is provided, that element from the list is deleted.
It’s possible to de-allocate a program’s memory after it has been used. This entails returning the pointer to the memory block on the free list, where it will be available for future allocations. Because the list is empty or because there are no available memory blocks big enough to fulfill the request of the program, memory allocation might fail.
Free List in Video Game Development
When you are designing a video game, the free list data structure is an incredibly useful tool. The free list contains all of the memory allocations in use by your program and has two important properties: it’s dynamic and helps to reduce the amount of time required to track down memory allocations.
To create a new object in a video game, for example, one can just add it to the tail end of this heap without having to worry about how much storage space will be needed or whether there is room for that allocation at that particular moment in time.
This means that you can design games with more complicated structures than if you were using other types of data structures because when allocated objects are no longer used they don’t take up any additional space on your hard drive.
The biggest benefit to dynamically allocated memory is that you can allocate objects without knowing how large they will be in advance. For example, an OpenGL surface mesh has a vertex array and index array which make up the bulk of its size. One doesn’t know how many triangles or indices that particular piece of geometry contains until it’s loaded into your graphics card.
If all allocations took place using fixed block sizes (like C language malloc), only the original developer would know this information ahead of time and could prepare space for them before actually making them visible in your game. But by using free lists, one can create surface meshes during runtime with no concern about arbitrary limits being imposed on their use by the program itself or external factors, such as the hard drive or video memory.
If you are interested in learning more about free lists, it is highly recommended that you look at this page for more information on how they function and some of their applications.
On the other hand, if you would like to read a book with many examples, I found this one to be very helpful when writing my current game engine. The author explains everything in great detail and does not assume any existing programming knowledge, making it an easy read even for beginners!
