[boost] [pool] an O(1) implementation of object_pool::destroy()

Subject: [boost] [pool] an O(1) implementation of object_pool::destroy()
From: Ben Muzal (bmuzal_at_[hidden])
Date: 2009-02-05 20:56:51

I was looking at object_pool and noticed that there is a way to make
object_pool::destroy() an O(1) operation instead of an O(n) operation.

If I understand the problem correctly, object_pool::destroy() is O(n)
because it keep the free list sorted. It keeps the free list sorted so
that object_pool::~object_pool() runs in O(n) time instead of in
O(n^2) time. However, I believe there is an implementation of
object_pool::~object_pool() that will run in O(n) time without
requiring a sorted free list.

My suggestion is that ~object_pool() could use a mark-sweep strategy:
It would first step through the free list and mark each free chunk as
such. It would then go back and examine each chunk in the pool and
call the destructor on the ones not marked as free. The each chunk's
'next' pointer could be used to store the marked-as-free flag so that
no extra memory is needed.

This may be related to Ticket #290.

A similar mark-sweep method could be used for pool::release_memory().
The free list would have to be reconstructed afterworlds but that is
also easy. Just step back through all of the chunks and connect the
ones that are marked as free.

While I am on the subject of the pool library, I would also like to
see a pool constructor that allows the user to set the initial size of
the pool and whether or not the pool was allowed to grow. This would
be very useful for the memory limited, real time environments in which
memory pools are popular.

Any thoughts on these suggestions?

If asked, I could help work on an implementation.
--Ben