Subject: Re: [boost] [pool] an O(1) implementation of object_pool::destroy()
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-02-05 21:32:36
AMDG
Ben Muzal wrote:
> 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.
>
Extra memory is needed because only the free list contains
next pointers. The chunks that are in use do not.
What would be possible is to make object_pool::destroy O(1)
and object_pool::~object_pool O(n log n) by sorting the free list
only on destruction.
In Christ,
Steven Watanabe