Given an Array, is there an algorithm that can allocate memory out of it?

Question

Hi, I'm doing some graphics programming and I'm using Vertex pools. I'd like to be able to allocate a range out of the pool and use this for drawing.

Whats different from the solution I need than from a C allocator is that I never call malloc. Instead I preallocate the array and then need an object that wraps that up and keeps track of the free space and allocates a range (a pair of begin/end pointers) from the allocation I pass in.

Much thanks.

Answer 1

boost::pool does this for you very nicely!

Answer 2

in general: you're looking for a memory mangager, which uses a (see wikipedia) memory pool (like the boost::pool as answered by TokenMacGuy). They come in many flavours. Important considerations:

• block size (fixed or variable; number of different block sizes; can the block size usage be predicted (statistically)?
• efficiency (some managers have 2^n block sizes, i.e. for use in network stacks where they search for best fit block; very good performance and no fragementation at the cost of wasting memory)
• administration overhead (I presume that you'll have many, very small blocks; so the number of ints and pointers maintainted by the memory manager is significant for efficiency)

In case of boost::pool, I think the simple segragated storage is worth a look. It will allow you to configure a memory pool with many different block sizes for which a best-match is searched for.

Answer 3

Instead I preallocate the array and then need an object that wraps that up and keeps track of the free space and allocates a range (a pair of begin/end pointers) from the allocation I pass in.

That's basically what malloc() does internally (malloc() can increase the size of this "preallocated array" if it gets full, though). So yes, there is an algorithm for it. There are many, in fact, and Wikipedia gives a basic overview. Different strategies can work better in different situations. (E.g. if all the blocks are a similar size, or if there's some pattern to allocation and freeing)

If you have many objects of the same size, look into obstacks.

You probably don't want to write the code yourself, it's not an easy task and bugs can be painful.