Continuously growing header list
Growing the header list is O(1) but will cause holes when headers are in state FREE_BLOCK (for later compacting) or UNUSED. Since handle is mapped 1:1 with header, they cannot be compacted. Scanning the list to find a free header to use in malloc() would take O(n) time
According to http://jfdube.wordpress.com/2012/01/13/memory-management-part-4-allocators-overhead-waste-and-fragmentation/, the overhead is 8-24 bytes per chunk. I'm up to 20 bytes right now.
Could the address of the header be cached in the handle for as long as compact hasn't happened yet? Then, when the compact happens, all handles are updated according to the new value. Caching the address with the integer requires actual storage somewhere, and we're back to square one with actual lookup having to be done. Rats.
A hash function mapping <handle-integer> to <header> in O(1) that is rewritten on each compact? See http://burtleburtle.net/bob/hash/doobs.html for more on hashes -- has a thorough discussion. Also Paul Hsieh's quick hash used in WebKit: http://www.azillionmonkeys.com/qed/hash.html
To consider: to get rid of the extra integer, is it possible to combine the handle and memory block addresses and use that to adress, and update the handle according to an invariant, e.g. that only one will ever be moved at a time, or similar?
Don't grow the header list, don't scan
Since we don't care about any particular order of the headers, only the entire table remains compact, getting any header is fine.
Therefore, use the fact that UNUSED headers don't use their pointer field to keep track of memory blocks, to instead maintain a header free list by using the pointer as the next pointer! Requires two pointers: one to keep track of the start and the end of the free list. New headers are grabbed from the start and appended to the end. If no free list, then grow list as before.
At the compact() step, all FREE_BLOCK headers turn into UNUSED and inserted to the free list.