New subject: [pool] why no object-pool with O(1) allocation AND O(1) deallocation?!?

2 Sep 2006

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

};

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

Andre Krause

Leandro Oliveira

tags

participants (2)