Hello,

I'm looking for the word(s) to describe a particular concept of the way I want to handle a region of memory, so I can perhaps get a handle on the algorithm required to do it (I have written something, but it seems to fail after six or so relatively small regions are allocated).

Say I have a fairly large fixed-size region of memory. The size is a power of 2, allowing for the region to be visualised as a square in 2D space.

I want to allocate regions of different sizes from this. They can be rectangular in shape, but the length of any side cannot exceed that of the largest free region. The sides are also a power of 2.

The process for allocating a region involves looking at a tree of elements. Each element can be divided into two equally-sized regions if required.

The tree is searched for an element with the same width and height as the requested region.

If the current element is too large, but has children, the search continues by evaluating the child elements.

If the current element is too large, but doesn't have children, the element is split in two. The search continues by evaluating the new child elements.

Also, if two adjacent elements that are subsequently freed can form a larger element, they are merged.

I thought it was an R-tree, but the description doesn't seem to match what I was thinking. Is this more like Binary Space Partitioning (BSP)?

I also suspect that a fair amount of sorting is required for this to be particularly efficient. My current algorithm goes down the first available node chain it can find and so doesn't cluster properly. I suck.