[boost] pool allocation

Subject: [boost] pool allocation
From: Stefan Strasser (strasser_at_[hidden])
Date: 2009-09-23 21:55:21

I took a closer look at Boost.Pool today to replace some default allocation of 
small objects.

what I found there was a little disappointing, at least for my use case.

the object_pool has 2 major downsides:
 - no dynamic block allocation
 - destroying one(!) object is O(N), with N being the number of unused objects 
in the pool

so I wrote some code for my own use. I'm not suggesting this code should be 
added to boost, but something like it.

struct A{
...
};

{
  pool<A,100> pool;
  A *a;
  for(int c=0;c<250;++c){
    a=pool.new_(); // O(1)
  }
  pool.delete_(a); //O(1), destructs
} //destruction of 249 objects, O(N)

this allocates 3 memory blocks.
but it also has one pointer memory overhead per object, to achieve constant 
time deletion.
but you can use that pointer while the object is in use, which was what lead 
to this code: I needed to store unused boost.intrusive nodes:

struct A : intrusive::[s]list_base_hook<>{
...
};

{
  [s]list_pool<A,[s]list_base_hook<>,100> pool;
  //same as above  
}

this has no memory overhead, as the list hook can be used by the pool.

here's the code: 
http://www.boostpro.com/vault/index.php?action=downloadfile&filename=intrusive_pool.hpp&directory=Memory&