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

From: Leandro Oliveira (leandro.lao_at_[hidden])
Date: 2006-09-04 01:04:31

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 <post_at_[hidden]> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>