On 9/2/06, Andre Krause <post@andre-krause.net> 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<objects.size ();a++)
                       free_objects.push_back(a);
       }
       void push_back(const T& t)
       {
               //assert(!free_objects.empty() && "out of capacity");
               if(free_objects.empty())
               {
                       PR("small object pool full..");
                       PR(objects.size() - free_objects.size());
                       return;
               }

               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