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

From: Andre Krause (post_at_[hidden])
Date: 2006-09-02 06:06:20

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);
        }

};