The One With D

Policy-based Free List

One of the reasons I was experimenting with policies earlier (1, 2) was to implement a policy-based free list I had seen in Game Programming Gems 5 in an article by Nathan Mefford of Firaxis (1.11 Improving Freelists with Policy Based Design). I’m fairly satisfied with the implementation I put together.

The implementation uses two policies as suggested in the article, one to determine how the free list should grow (the Growth Policy) and another to determine how it objects should be stored, allocated, and managed (the Allocation Policy). By default, I added two Growth policies and two Allocation policies to the freelist module. The allocation policies both store objects in a dynamic array and grow the array by manipulating its length property. The only difference between the two is how they handle object that are returned to the free list when it is full.

The two Growth policies can be combined with the two Allocation policies to cover most of the situations I could think of that I would most commonly want. I thought of several corner cases, but I didn’t implement default policies for those. If I need them later I can implement them separately on a case-by-case basis.

The module is part of a D game engine I am working on (who isn’t these days?), but having seen some talk about free lists over in the DSource forums I decided to release it here. While I will ultimately release the full engine under a BSD License, I am releasing the free list implementation in it’s current state into public domain. If you use it, be sure to add a module statement to the file to fit your project. For this release, I declared “module freelist;”. That leaves a potential for name collisions, so you should put it in your own package heirarchy. Change the name, change the implementation, do whatever you want with it. It’s public domain. Also, it hasn’t been fully tested. I tested an earlier version exhaustively, but made some heavy changes to it since. If you find any bugs in the documenation or the source, let me know if you want. I’m not supporting this release in any way, but bug fixes will help the version I evolve as part of my engine project.

Download freelist.d. I hope you find it useful.