Re: [Boost-users] [pool] why no object-pool with O(1) allocation AND O(1) deallocation?!?

4 Sep 2006


      You can specify an allocator for your pool. See:
http://www.boost.org/libs/pool/doc/interfaces/user_allocator.html
This way, you can have O(1) time for deallocation, using the technique you
described, and you won't need to create (and test) your own pool class
template.
HTH,
Leandro Oliveira


On 9/2/06, Andre Krause  wrote:
...
dear boost users, boost offers in lib pool the class object_pool.
as is stated in the docs, it allows for allocation with O(1) but
deallocation need O(n) time. i suppose it has to search the internal
list for the position of the object ro be freed.
but this could be speed up a lot by using a stack of free objects. if
one would like to allocate an object, a pointer to a free memory cell is
popped from the stack, if the object should  be returned / freed to the
pool, that objects pointer is pushed onto the stack.
of course this causes memory overhead, but, for example if one would
like to implement a really large pool of small objects for a particle
system, then O(n) deallocation is prohibitive.
so my question is why boost does not offer an alternative version of
object_pool with both O(1) alloc and dealloc ?
below is my version of a stack based object pool with O(1) both alloc
and dealloc. i really do not like my implementation, but i did not know
how to do better...
template<class T> class Smallobjects_Pool
{
protected:
       class Node // a node of a double linked list
       {
       public:
               Node() {prev=next=NULL; idx=-1; }
               Node* prev;
               Node* next;
               int idx;        // index to the objects - vector
               T obj;
       };
       //Node* next(int cur) { return objects[cur].next;}
       //Node* root() { return _root; }
       //Node* last() { return _last; }
protected:
       Node* _root;
       Node* _last;
       vector<Node> objects;
       vector<int>  free_objects;
public:
       T & operator[](int i){return objects[i].obj;}
       bool empty() { return _root == NULL;}
       Smallobjects_Pool(int initial_size)
       {
               _root=NULL;
               _last=NULL;
               objects.resize(initial_size);
               free_objects.reserve(initial_size);
               for(unsigned int a=0;a
Node* new_obj = &(objects[free_objects.back()]);
               new_obj->idx = free_objects.back();
               free_objects.pop_back();
if(_root==NULL)
               {
                       _root=new_obj;
                       new_obj->prev=NULL;
                       new_obj->next=NULL;
               }
               else
               {
                       _last->next=new_obj;
                       new_obj->prev=_last;
                       new_obj->next=NULL;
               }
_last=new_obj;
new_obj->obj = t;
       }
class iterator
       {
       //protected:
       public:
               Node* i;
       public:
               iterator(Node* _i) : i(_i) {}
               ~iterator() {}
               iterator& operator=(const iterator& other)      { i =
other.i;
return(*this); } // The assignment and relational operators are
straightforward
               bool operator==(const iterator& it)             { return(i
== it.i); }
               bool operator!=(const iterator& it)             { return(i
!= it.i); }
iterator& operator++()  { assert(i && "increment on null
pointer"); i =
i->next; return(*this); }               // Update my state such that I
refer to the
next element in the SQueue.
               //Iterator& operator++(int) { Iterator tmp(*this);
++(*this);
return(tmp);}
               T& operator*()  { return   i->obj;  }   // Return a
reference to the
value in the node.  I do this instead of returning by value so a caller
can update the value in the node directly.
               T* operator->() { return &(i->obj); }   // Return the
address of the
value referred to.
       };
iterator begin()        { return(iterator(_root));}
       iterator end()          { return(iterator( NULL));}
       iterator erase(iterator i)
       {
assert(i.i!=NULL && "cannot free null pointer.");
free_objects.push_back(i.i->idx);
if(i.i == _last)
               {
                       if(i.i->prev != NULL)
                               _last = i.i->prev;
                       _last->next=NULL;
                       return NULL;
               }
if(i.i == _root)
               {
                       _root = i.i->next;
                       _root->prev=NULL;
                       return _root;
               }
i.i->prev->next = i.i->next;
               i.i->next->prev = i.i->prev;
               return iterator(i.i->next);
       }
};
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users