Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualSFCBias

Posted 30 December 2012 - 11:04 PM

As a learning exercise I wrote my own version of several STL components, this allocator generally works however while I was testing particles with it, it crashes after a variable number of iterations with alloc's and dealloc's . I've been playing with the code for ours and I'm sure there's something I'm doing wrong. Perhaps someone can point it out to me.

 

During the loop, I save the address of particles that will need to be dealloc'd in a vector, then later dealloc the pointers.

 


The problem always occurs with a segfault at ln. 76 and happens because the MemChunk's pointers point to memory that looks like it should be NULL but is something like 0x1, 0x5, etc.

 

 

This is the allocator's code

template<class T = void>
class PoolAllocator: public AllocBase<T>
{
public:
	typedef typename AllocBase<T>::AllocType AllocType;
	typedef typename AllocBase<T>::AllocTypePtr AllocTypePtr;

	PoolAllocator(size_t sizeInUnits = 1024) :
			mMemory(NULL), mUsedSize(0), mMaxSize(sizeInUnits), mOffset(
					sizeof(MemChunk) + sizeof(T))
	{
		mMemory = new (std::nothrow) char[mMaxSize * mOffset];
		// mMemory = malloc(mMaxSize * mOffset);
		if (!mMemory)
		{
			//Do something more informational here
			throw std::bad_alloc();
			return;
		}

		for (size_t i = 0; i < mMaxSize; i++)
		{
			MemChunk *pCurUnit = (MemChunk *) ((char *) mMemory + i * mOffset);

			pCurUnit->mPrevChunk = mFreeList.mLast;
			pCurUnit->mNextChunk = NULL;

			if (mFreeList.mLast)
				mFreeList.mLast->mNextChunk = pCurUnit;
			mFreeList.mLast = pCurUnit;

			if (!mFreeList.mFirst)
				mFreeList.mFirst = pCurUnit;
		}

	}

	virtual ~PoolAllocator()
	{
		delete[] mMemory;
	}

	template<typename T1>
	struct rebind
	{
		typedef PoolAllocator<T1> other;
	};

	struct MemChunk
	{
		MemChunk* mNextChunk, *mPrevChunk;
	};

	struct ChunkList
	{
		ChunkList() :
				mFirst(0), mLast(0)
		{
		}
		MemChunk* mFirst, *mLast;
	};

	virtual AllocTypePtr allocate(size_t n, const AllocTypePtr = 0)
	{

		if ((mUsedSize + n) > (mMaxSize))
			_resize((mUsedSize * mOffset) + (mOffset * n) * 2);

		//Get the last chunk of unused memory
		MemChunk* pCurChunk = mFreeList.mLast;

		if (mFreeList.mFirst == pCurChunk)
			mFreeList.mFirst = pCurChunk->mNextChunk;

		//This shouldn't happen, since it's the back of the free list
		if (pCurChunk->mNextChunk)
			pCurChunk->mNextChunk->mPrevChunk = pCurChunk->mPrevChunk;

		//This should only _not_ happen if this is the last available piece of memory
		//When it does, the value of pCurChunk->mNextChunk should be NULL
		if (pCurChunk->mPrevChunk)
			pCurChunk->mPrevChunk->mNextChunk = NULL;

		//Set the new value of the last chunk in the free list
		mFreeList.mLast = pCurChunk->mPrevChunk;

		//Place it at the end of the AllocList
		pCurChunk->mPrevChunk = mAllocList.mLast;
		pCurChunk->mNextChunk = NULL;

		if (mAllocList.mLast)
			mAllocList.mLast->mNextChunk = pCurChunk;

		mAllocList.mLast = pCurChunk;
		if (!mAllocList.mFirst)
			mAllocList.mFirst = pCurChunk;

		mUsedSize += 1;

		return reinterpret_cast<AllocTypePtr>((reinterpret_cast<char*>(pCurChunk) + sizeof(MemChunk)));
	}

	//Returns a pointer to the memory at a specific offset. Do NOT modify this pointer
	inline const AllocTypePtr getPtr(unsigned i) const
	{
		return reinterpret_cast<AllocTypePtr>(reinterpret_cast<char*>(mAllocList.mFirst)
				- (mOffset * i) + sizeof(MemChunk));
	}

	virtual void dealloc(AllocTypePtr ptr, size_t = 0)
	{
		MemChunk *pCurChunk = (MemChunk*) ((char*) ptr - sizeof(MemChunk));

		std::cout << pCurChunk << "\n";
		//Remove the chunk from the AllocList
		if (pCurChunk->mNextChunk)
			pCurChunk->mNextChunk->mPrevChunk = pCurChunk->mPrevChunk;

		if (pCurChunk->mPrevChunk)
			pCurChunk->mPrevChunk->mNextChunk = pCurChunk->mNextChunk;

		if (mAllocList.mLast == pCurChunk)
			mAllocList.mLast = pCurChunk->mPrevChunk;

		if (mAllocList.mFirst == pCurChunk)
			mAllocList.mFirst = pCurChunk->mNextChunk;

		//Put it back on the FreeList
		pCurChunk->mPrevChunk = mFreeList.mLast;
		pCurChunk->mNextChunk = NULL;

		if (mFreeList.mLast)
			mFreeList.mLast->mNextChunk = pCurChunk;

		mFreeList.mLast = pCurChunk;

		if (!mFreeList.mFirst)
			mFreeList.mFirst = pCurChunk;

		mUsedSize -= 1;

	}
protected:

	/*
	 * NOTE: This is a slow operation and can be avoided by preallocating enough memory
	 * to hold your data.
	 */
	void _resize(unsigned size)
	{
		//Simple array reallocation
		size_t newSize = size;
		char* newArr = new (std::nothrow) char[newSize * mOffset];

		for (unsigned counter = 0; counter < mUsedSize; ++counter)
			newArr[counter] = mMemory[counter];

		//memcpy(newArr, mMemory, mMaxSize * mOffset);

		mMaxSize = newSize;

		delete[] mMemory;

		mMemory = newArr;

		//Relink the list
		for (size_t i = 0; i < mMaxSize; i++)
		{
			MemChunk *pCurUnit = (MemChunk *) ((char *) mMemory + i * mOffset);

			pCurUnit->mPrevChunk = mFreeList.mLast;
			pCurUnit->mNextChunk = NULL;

			if (mFreeList.mLast)
				mFreeList.mLast->mNextChunk = pCurUnit;

			mFreeList.mLast = pCurUnit;

			if (!mFreeList.mFirst)
				mFreeList.mFirst = pCurUnit;
		}
	}

protected:
	char* mMemory; //The big chunk of allocated memory from the OS

	ChunkList mFreeList;
	ChunkList mAllocList;

	size_t mUsedSize; //current used size in chunks
	size_t mMaxSize; //peak size in chunks
	size_t mOffset; //The total step in memory from one chunk to another (also equal to the sizeof(MemChunk) + sizeof(T))

};

 

Here is the loop

for (unsigned i = 0; i < mNumParticles; i++)
	{
		// Check particle's lifespan
		//Particle* pTemp = reinterpret_cast<Particle*>(mBuffer) + i;
		Particle* pTemp = mAllocator.getPtr(i);

		if (pTemp->m_Life-- < 0)
		{
			//Keep up with the particles to delete
			m_ParticleList.push_back(pTemp);
			continue;
		}

		// Update particle's position
		pTemp->m_Position.fX += pTemp->m_Velocity.fX;
		pTemp->m_Position.fY += pTemp->m_Velocity.fY;

		glColor3f(float(pTemp->m_Colour.r) / 255, float(pTemp->m_Colour.g) / 255,
				float(pTemp->m_Colour.b) / 255);
		glVertex2fv(pTemp->m_Position.ptr());
	}

	bool clear = false;
	for (unsigned i = 0; i < m_ParticleList.size(); i++)
	{
		Particle* p = m_ParticleList[i];

		mAllocator.destroy(p);
		mAllocator.dealloc(p);

		mNumParticles--;
		clear = true;
	}

	if (clear)
		m_ParticleList.clear();

	// If there are less particles than the maximum allowed create another
	if (mNumParticles < m_MaxParticles)
		createParticles(m_MaxParticles - mNumParticles);

the createParticles method calls allocate.


#3SFCBias

Posted 30 December 2012 - 11:00 PM

As a learning exercise I wrote my own version of several STL components, this allocator generally works however while I was testing particles with it, it crashes after a variable number of iterations with alloc's and dealloc's . I've been playing with the code for ours and I'm sure there's something I'm doing wrong. 

 

During the loop, I save the address of particles that will need to be dealloc'd in a vector, then later dealloc the pointers.

 

This is the allocator's code

template<class T = void>
class PoolAllocator: public AllocBase<T>
{
public:
	typedef typename AllocBase<T>::AllocType AllocType;
	typedef typename AllocBase<T>::AllocTypePtr AllocTypePtr;

	PoolAllocator(size_t sizeInUnits = 1024) :
			mMemory(NULL), mUsedSize(0), mMaxSize(sizeInUnits), mOffset(
					sizeof(MemChunk) + sizeof(T))
	{
		mMemory = new (std::nothrow) char[mMaxSize * mOffset];
		// mMemory = malloc(mMaxSize * mOffset);
		if (!mMemory)
		{
			//Do something more informational here
			throw std::bad_alloc();
			return;
		}

		for (size_t i = 0; i < mMaxSize; i++)
		{
			MemChunk *pCurUnit = (MemChunk *) ((char *) mMemory + i * mOffset);

			pCurUnit->mPrevChunk = mFreeList.mLast;
			pCurUnit->mNextChunk = NULL;

			if (mFreeList.mLast)
				mFreeList.mLast->mNextChunk = pCurUnit;
			mFreeList.mLast = pCurUnit;

			if (!mFreeList.mFirst)
				mFreeList.mFirst = pCurUnit;
		}

	}

	virtual ~PoolAllocator()
	{
		delete[] mMemory;
	}

	template<typename T1>
	struct rebind
	{
		typedef PoolAllocator<T1> other;
	};

	struct MemChunk
	{
		MemChunk* mNextChunk, *mPrevChunk;
	};

	struct ChunkList
	{
		ChunkList() :
				mFirst(0), mLast(0)
		{
		}
		MemChunk* mFirst, *mLast;
	};

	virtual AllocTypePtr allocate(size_t n, const AllocTypePtr = 0)
	{

		if ((mUsedSize + n) > (mMaxSize))
			_resize((mUsedSize * mOffset) + (mOffset * n) * 2);

		//Get the last chunk of unused memory
		MemChunk* pCurChunk = mFreeList.mLast;

		if (mFreeList.mFirst == pCurChunk)
			mFreeList.mFirst = pCurChunk->mNextChunk;

		//This shouldn't happen, since it's the back of the free list
		if (pCurChunk->mNextChunk)
			pCurChunk->mNextChunk->mPrevChunk = pCurChunk->mPrevChunk;

		//This should only _not_ happen if this is the last available piece of memory
		//When it does, the value of pCurChunk->mNextChunk should be NULL
		if (pCurChunk->mPrevChunk)
			pCurChunk->mPrevChunk->mNextChunk = NULL;

		//Set the new value of the last chunk in the free list
		mFreeList.mLast = pCurChunk->mPrevChunk;

		//Place it at the end of the AllocList
		pCurChunk->mPrevChunk = mAllocList.mLast;
		pCurChunk->mNextChunk = NULL;

		if (mAllocList.mLast)
			mAllocList.mLast->mNextChunk = pCurChunk;

		mAllocList.mLast = pCurChunk;
		if (!mAllocList.mFirst)
			mAllocList.mFirst = pCurChunk;

		mUsedSize += 1;

		return reinterpret_cast<AllocTypePtr>((reinterpret_cast<char*>(pCurChunk) + sizeof(MemChunk)));
	}

	//Returns a pointer to the memory at a specific offset. Do NOT modify this pointer
	inline const AllocTypePtr getPtr(unsigned i) const
	{
		return reinterpret_cast<AllocTypePtr>(reinterpret_cast<char*>(mAllocList.mFirst)
				- (mOffset * i) + sizeof(MemChunk));
	}

	virtual void dealloc(AllocTypePtr ptr, size_t = 0)
	{
		MemChunk *pCurChunk = (MemChunk*) ((char*) ptr - sizeof(MemChunk));

		std::cout << pCurChunk << "\n";
		//Remove the chunk from the AllocList
		if (pCurChunk->mNextChunk)
			pCurChunk->mNextChunk->mPrevChunk = pCurChunk->mPrevChunk;

		if (pCurChunk->mPrevChunk)
			pCurChunk->mPrevChunk->mNextChunk = pCurChunk->mNextChunk;

		if (mAllocList.mLast == pCurChunk)
			mAllocList.mLast = pCurChunk->mPrevChunk;

		if (mAllocList.mFirst == pCurChunk)
			mAllocList.mFirst = pCurChunk->mNextChunk;

		//Put it back on the FreeList
		pCurChunk->mPrevChunk = mFreeList.mLast;
		pCurChunk->mNextChunk = NULL;

		if (mFreeList.mLast)
			mFreeList.mLast->mNextChunk = pCurChunk;

		mFreeList.mLast = pCurChunk;

		if (!mFreeList.mFirst)
			mFreeList.mFirst = pCurChunk;

		mUsedSize -= 1;

	}
protected:

	/*
	 * NOTE: This is a slow operation and can be avoided by preallocating enough memory
	 * to hold your data.
	 */
	void _resize(unsigned size)
	{
		//Simple array reallocation
		size_t newSize = size;
		char* newArr = new (std::nothrow) char[newSize * mOffset];

		for (unsigned counter = 0; counter < mUsedSize; ++counter)
			newArr[counter] = mMemory[counter];

		//memcpy(newArr, mMemory, mMaxSize * mOffset);

		mMaxSize = newSize;

		delete[] mMemory;

		mMemory = newArr;

		//Relink the list
		for (size_t i = 0; i < mMaxSize; i++)
		{
			MemChunk *pCurUnit = (MemChunk *) ((char *) mMemory + i * mOffset);

			pCurUnit->mPrevChunk = mFreeList.mLast;
			pCurUnit->mNextChunk = NULL;

			if (mFreeList.mLast)
				mFreeList.mLast->mNextChunk = pCurUnit;

			mFreeList.mLast = pCurUnit;

			if (!mFreeList.mFirst)
				mFreeList.mFirst = pCurUnit;
		}
	}

protected:
	char* mMemory; //The big chunk of allocated memory from the OS

	ChunkList mFreeList;
	ChunkList mAllocList;

	size_t mUsedSize; //current used size in chunks
	size_t mMaxSize; //peak size in chunks
	size_t mOffset; //The total step in memory from one chunk to another (also equal to the sizeof(MemChunk) + sizeof(T))

};

 

The problem always occurs with a segfault at ln. 76 and happens because the MemChunk's pointers point to memory that looks like it should be NULL but is something like 0x1, 0x5, etc.

 

Here is the loop

for (unsigned i = 0; i < mNumParticles; i++)
	{
		// Check particle's lifespan
		//Particle* pTemp = reinterpret_cast<Particle*>(mBuffer) + i;
		Particle* pTemp = mAllocator.getPtr(i);

		if (pTemp->m_Life-- < 0)
		{
			//Keep up with the particles to delete
			m_ParticleList.push_back(pTemp);
			continue;
		}

		// Update particle's position
		pTemp->m_Position.fX += pTemp->m_Velocity.fX;
		pTemp->m_Position.fY += pTemp->m_Velocity.fY;

		glColor3f(float(pTemp->m_Colour.r) / 255, float(pTemp->m_Colour.g) / 255,
				float(pTemp->m_Colour.b) / 255);
		glVertex2fv(pTemp->m_Position.ptr());
	}

	bool clear = false;
	for (unsigned i = 0; i < m_ParticleList.size(); i++)
	{
		Particle* p = m_ParticleList[i];

		mAllocator.destroy(p);
		mAllocator.dealloc(p);

		mNumParticles--;
		clear = true;
	}

	if (clear)
		m_ParticleList.clear();

	// If there are less particles than the maximum allowed create another
	if (mNumParticles < m_MaxParticles)
		createParticles(m_MaxParticles - mNumParticles);

the createParticles method calls allocate.


#2SFCBias

Posted 30 December 2012 - 10:58 PM

As a learning exercise I wrote my own version of several STL components, this allocator generally works however while I was testing particles with it, it crashes after a variable number of iterations with alloc's and dealloc's . I've been playing with the code for ours and I'm sure there's something I'm doing wrong. 

 

During the loop, I save the address of particles that will need to be dealloc'd in a vector, then later dealloc the pointers.

 

This is the allocator's code

template<class T = void>
class PoolAllocator: public AllocBase<T>
{
public:
	typedef typename AllocBase<T>::AllocType AllocType;
	typedef typename AllocBase<T>::AllocTypePtr AllocTypePtr;

	PoolAllocator(size_t sizeInUnits = 1024) :
			mMemory(NULL), mUsedSize(0), mMaxSize(sizeInUnits), mOffset(
					sizeof(MemChunk) + sizeof(T))
	{
		mMemory = new (std::nothrow) char[mMaxSize * mOffset];
		// mMemory = malloc(mMaxSize * mOffset);
		if (!mMemory)
		{
			//Do something more informational here
			throw std::bad_alloc();
			return;
		}

		for (size_t i = 0; i < mMaxSize; i++)
		{
			MemChunk *pCurUnit = (MemChunk *) ((char *) mMemory + i * mOffset);

			pCurUnit->mPrevChunk = mFreeList.mLast;
			pCurUnit->mNextChunk = NULL;

			if (mFreeList.mLast)
				mFreeList.mLast->mNextChunk = pCurUnit;
			mFreeList.mLast = pCurUnit;

			if (!mFreeList.mFirst)
				mFreeList.mFirst = pCurUnit;
		}

	}

	virtual ~PoolAllocator()
	{
		delete[] mMemory;
	}

	template<typename T1>
	struct rebind
	{
		typedef PoolAllocator<T1> other;
	};

	struct MemChunk
	{
		MemChunk* mNextChunk, *mPrevChunk;
	};

	struct ChunkList
	{
		ChunkList() :
				mFirst(0), mLast(0)
		{
		}
		MemChunk* mFirst, *mLast;
	};

	virtual AllocTypePtr allocate(size_t n, const AllocTypePtr = 0)
	{

		if ((mUsedSize + n) > (mMaxSize))
			_resize((mUsedSize * mOffset) + (mOffset * n) * 2);

		//Get the last chunk of unused memory
		MemChunk* pCurChunk = mFreeList.mLast;

		if (mFreeList.mFirst == pCurChunk)
			mFreeList.mFirst = pCurChunk->mNextChunk;

		//This shouldn't happen, since it's the back of the free list
		if (pCurChunk->mNextChunk)
			pCurChunk->mNextChunk->mPrevChunk = pCurChunk->mPrevChunk;

		//This should only _not_ happen if this is the last available piece of memory
		//When it does, the value of pCurChunk->mNextChunk should be NULL
		if (pCurChunk->mPrevChunk)
			pCurChunk->mPrevChunk->mNextChunk = NULL;

		//Set the new value of the last chunk in the free list
		mFreeList.mLast = pCurChunk->mPrevChunk;

		//Place it at the end of the AllocList
		pCurChunk->mPrevChunk = mAllocList.mLast;
		pCurChunk->mNextChunk = NULL;

		if (mAllocList.mLast)
			mAllocList.mLast->mNextChunk = pCurChunk;

		mAllocList.mLast = pCurChunk;
		if (!mAllocList.mFirst)
			mAllocList.mFirst = pCurChunk;

		mUsedSize += 1;

		return reinterpret_cast<AllocTypePtr>((reinterpret_cast<char*>(pCurChunk) + sizeof(MemChunk)));
	}

	//Returns a pointer to the memory at a specific offset. Do NOT modify this pointer
	inline const AllocTypePtr getPtr(unsigned i) const
	{
		return reinterpret_cast<AllocTypePtr>(reinterpret_cast<char*>(mAllocList.mFirst)
				- (mOffset * i) + sizeof(MemChunk));
	}

	virtual void dealloc(AllocTypePtr ptr, size_t = 0)
	{
		MemChunk *pCurChunk = (MemChunk*) ((char*) ptr - sizeof(MemChunk));

		std::cout << pCurChunk << "\n";
		//Remove the chunk from the AllocList
		if (pCurChunk->mNextChunk)
			pCurChunk->mNextChunk->mPrevChunk = pCurChunk->mPrevChunk;

		if (pCurChunk->mPrevChunk)
			pCurChunk->mPrevChunk->mNextChunk = pCurChunk->mNextChunk;

		if (mAllocList.mLast == pCurChunk)
			mAllocList.mLast = pCurChunk->mPrevChunk;

		if (mAllocList.mFirst == pCurChunk)
			mAllocList.mFirst = pCurChunk->mNextChunk;

		//Put it back on the FreeList
		pCurChunk->mPrevChunk = mFreeList.mLast;
		pCurChunk->mNextChunk = NULL;

		if (mFreeList.mLast)
			mFreeList.mLast->mNextChunk = pCurChunk;

		mFreeList.mLast = pCurChunk;

		if (!mFreeList.mFirst)
			mFreeList.mFirst = pCurChunk;

		mUsedSize -= 1;

	}
protected:

	/*
	 * NOTE: This is a slow operation and can be avoided by preallocating enough memory
	 * to hold your data.
	 */
	void _resize(unsigned size)
	{
		//Simple array reallocation
		size_t newSize = size;
		char* newArr = new (std::nothrow) char[newSize * mOffset];

		for (unsigned counter = 0; counter < mUsedSize; ++counter)
			newArr[counter] = mMemory[counter];

		//memcpy(newArr, mMemory, mMaxSize * mOffset);

		mMaxSize = newSize;

		delete[] mMemory;

		mMemory = newArr;

		//Relink the list
		for (size_t i = 0; i < mMaxSize; i++)
		{
			MemChunk *pCurUnit = (MemChunk *) ((char *) mMemory + i * mOffset);

			pCurUnit->mPrevChunk = mFreeList.mLast;
			pCurUnit->mNextChunk = NULL;

			if (mFreeList.mLast)
				mFreeList.mLast->mNextChunk = pCurUnit;

			mFreeList.mLast = pCurUnit;

			if (!mFreeList.mFirst)
				mFreeList.mFirst = pCurUnit;
		}
	}

protected:
	char* mMemory; //The big chunk of allocated memory from the OS

	ChunkList mFreeList;
	ChunkList mAllocList;

	size_t mUsedSize; //current used size in chunks
	size_t mMaxSize; //peak size in chunks
	size_t mOffset; //The total step in memory from one chunk to another (also equal to the sizeof(MemChunk) + sizeof(T))

};

 

The problem always occurs with a segfault at ln. 76 and happens because the MemChunk's pointers point to memory that looks like it should be NULL but is something like 0x1, 0x5, etc.

 

Here is the loop

for (unsigned i = 0; i < mNumParticles; i++)
	{
		// Check particle's lifespan
		//Particle* pTemp = reinterpret_cast<Particle*>(mBuffer) + i;
		Particle* pTemp = mAllocator.getPtr(i);

		if (pTemp->m_Life-- < 0)
		{
			//Keep up with the particles to delete
			m_ParticleList.push_back(pTemp);
			continue;
		}

		// Update particle's position
		pTemp->m_Position.fX += pTemp->m_Velocity.fX;
		pTemp->m_Position.fY += pTemp->m_Velocity.fY;

		glColor3f(float(pTemp->m_Colour.r) / 255, float(pTemp->m_Colour.g) / 255,
				float(pTemp->m_Colour.b) / 255);
		glVertex2fv(pTemp->m_Position.ptr());
	}

	bool clear = false;
	for (unsigned i = 0; i < m_ParticleList.size(); i++)
	{
		Particle* p = m_ParticleList[i];

		mAllocator.destroy(p);
		mAllocator.dealloc(p);

		mNumParticles--;
		clear = true;
	}

	if (clear)
		m_ParticleList.clear();

	// If there are less particles than the maximum allowed create another
	if (mNumParticles < m_MaxParticles)
		createParticles(m_MaxParticles - mNumParticles);

the createParticles method calls allocate.


#1SFCBias

Posted 30 December 2012 - 10:58 PM

As a learning exercise I wrote my own version of several STL components, this allocator generally works however while I was testing particles with it, it crashes after a variable number of iterations with alloc's and dealloc's . I've been playing with the code for ours and I'm sure there's something I'm doing wrong. 

 

During the loop, I save the address of particles that will need to be dealloc'd in a vector, then later dealloc the pointers.

 

This is the allocator's code

template<class T = void>
class PoolAllocator: public AllocBase<T>
{
public:
	typedef typename AllocBase<T>::AllocType AllocType;
	typedef typename AllocBase<T>::AllocTypePtr AllocTypePtr;

	PoolAllocator(size_t sizeInUnits = 1024) :
			mMemory(NULL), mUsedSize(0), mMaxSize(sizeInUnits), mOffset(
					sizeof(MemChunk) + sizeof(T))
	{
		mMemory = new (std::nothrow) char[mMaxSize * mOffset];
		// mMemory = malloc(mMaxSize * mOffset);
		if (!mMemory)
		{
			//Do something more informational here
			throw std::bad_alloc();
			return;
		}

		for (size_t i = 0; i < mMaxSize; i++)
		{
			MemChunk *pCurUnit = (MemChunk *) ((char *) mMemory + i * mOffset);

			pCurUnit->mPrevChunk = mFreeList.mLast;
			pCurUnit->mNextChunk = NULL;

			if (mFreeList.mLast)
				mFreeList.mLast->mNextChunk = pCurUnit;
			mFreeList.mLast = pCurUnit;

			if (!mFreeList.mFirst)
				mFreeList.mFirst = pCurUnit;
		}

	}

	virtual ~PoolAllocator()
	{
		delete[] mMemory;
	}

	template<typename T1>
	struct rebind
	{
		typedef PoolAllocator<T1> other;
	};

	struct MemChunk
	{
		MemChunk* mNextChunk, *mPrevChunk;
	};

	struct ChunkList
	{
		ChunkList() :
				mFirst(0), mLast(0)
		{
		}
		MemChunk* mFirst, *mLast;
	};

	virtual AllocTypePtr allocate(size_t n, const AllocTypePtr = 0)
	{

		if ((mUsedSize + n) > (mMaxSize))
			_resize((mUsedSize * mOffset) + (mOffset * n) * 2);

		//Get the last chunk of unused memory
		MemChunk* pCurChunk = mFreeList.mLast;

		if (mFreeList.mFirst == pCurChunk)
			mFreeList.mFirst = pCurChunk->mNextChunk;

		//This shouldn't happen, since it's the back of the free list
		if (pCurChunk->mNextChunk)
			pCurChunk->mNextChunk->mPrevChunk = pCurChunk->mPrevChunk;

		//This should only _not_ happen if this is the last available piece of memory
		//When it does, the value of pCurChunk->mNextChunk should be NULL
		if (pCurChunk->mPrevChunk)
			pCurChunk->mPrevChunk->mNextChunk = NULL;

		//Set the new value of the last chunk in the free list
		mFreeList.mLast = pCurChunk->mPrevChunk;

		//Place it at the end of the AllocList
		pCurChunk->mPrevChunk = mAllocList.mLast;
		pCurChunk->mNextChunk = NULL;

		if (mAllocList.mLast)
			mAllocList.mLast->mNextChunk = pCurChunk;

		mAllocList.mLast = pCurChunk;
		if (!mAllocList.mFirst)
			mAllocList.mFirst = pCurChunk;

		mUsedSize += 1;

		return reinterpret_cast<AllocTypePtr>((reinterpret_cast<char*>(pCurChunk) + sizeof(MemChunk)));
	}

	//Returns a pointer to the memory at a specific offset. Do NOT modify this pointer
	inline const AllocTypePtr getPtr(unsigned i) const
	{
		return reinterpret_cast<AllocTypePtr>(reinterpret_cast<char*>(mAllocList.mFirst)
				- (mOffset * i) + sizeof(MemChunk));
	}

	virtual void dealloc(AllocTypePtr ptr, size_t = 0)
	{
		MemChunk *pCurChunk = (MemChunk*) ((char*) ptr - sizeof(MemChunk));

		std::cout << pCurChunk << "\n";
		//Remove the chunk from the AllocList
		if (pCurChunk->mNextChunk)
			pCurChunk->mNextChunk->mPrevChunk = pCurChunk->mPrevChunk;

		if (pCurChunk->mPrevChunk)
			pCurChunk->mPrevChunk->mNextChunk = pCurChunk->mNextChunk;

		if (mAllocList.mLast == pCurChunk)
			mAllocList.mLast = pCurChunk->mPrevChunk;

		if (mAllocList.mFirst == pCurChunk)
			mAllocList.mFirst = pCurChunk->mNextChunk;

		//Put it back on the FreeList
		pCurChunk->mPrevChunk = mFreeList.mLast;
		pCurChunk->mNextChunk = NULL;

		if (mFreeList.mLast)
			mFreeList.mLast->mNextChunk = pCurChunk;

		mFreeList.mLast = pCurChunk;

		if (!mFreeList.mFirst)
			mFreeList.mFirst = pCurChunk;

		mUsedSize -= 1;

	}
protected:

	/*
	 * NOTE: This is a slow operation and can be avoided by preallocating enough memory
	 * to hold your data.
	 */
	void _resize(unsigned size)
	{
		//Simple array reallocation
		size_t newSize = size;
		char* newArr = new (std::nothrow) char[newSize * mOffset];

		for (unsigned counter = 0; counter < mUsedSize; ++counter)
			newArr[counter] = mMemory[counter];

		//memcpy(newArr, mMemory, mMaxSize * mOffset);

		mMaxSize = newSize;

		delete[] mMemory;

		mMemory = newArr;

		//Relink the list
		for (size_t i = 0; i < mMaxSize; i++)
		{
			MemChunk *pCurUnit = (MemChunk *) ((char *) mMemory + i * mOffset);

			pCurUnit->mPrevChunk = mFreeList.mLast;
			pCurUnit->mNextChunk = NULL;

			if (mFreeList.mLast)
				mFreeList.mLast->mNextChunk = pCurUnit;

			mFreeList.mLast = pCurUnit;

			if (!mFreeList.mFirst)
				mFreeList.mFirst = pCurUnit;
		}
	}

protected:
	char* mMemory; //The big chunk of allocated memory from the OS

	ChunkList mFreeList;
	ChunkList mAllocList;

	size_t mUsedSize; //current used size in chunks
	size_t mMaxSize; //peak size in chunks
	size_t mOffset; //The total step in memory from one chunk to another (also equal to the sizeof(MemChunk) + sizeof(T))

};

 

The problem always occurs with a segfault at ln. and happens because the MemChunk's pointers point to memory that looks like it should be NULL but is something like 0x1, 0x5, etc.

 

Here is the loop

for (unsigned i = 0; i < mNumParticles; i++)
	{
		// Check particle's lifespan
		//Particle* pTemp = reinterpret_cast<Particle*>(mBuffer) + i;
		Particle* pTemp = mAllocator.getPtr(i);

		if (pTemp->m_Life-- < 0)
		{
			//Keep up with the particles to delete
			m_ParticleList.push_back(pTemp);
			continue;
		}

		// Update particle's position
		pTemp->m_Position.fX += pTemp->m_Velocity.fX;
		pTemp->m_Position.fY += pTemp->m_Velocity.fY;

		glColor3f(float(pTemp->m_Colour.r) / 255, float(pTemp->m_Colour.g) / 255,
				float(pTemp->m_Colour.b) / 255);
		glVertex2fv(pTemp->m_Position.ptr());
	}

	bool clear = false;
	for (unsigned i = 0; i < m_ParticleList.size(); i++)
	{
		Particle* p = m_ParticleList[i];

		mAllocator.destroy(p);
		mAllocator.dealloc(p);

		mNumParticles--;
		clear = true;
	}

	if (clear)
		m_ParticleList.clear();

	// If there are less particles than the maximum allowed create another
	if (mNumParticles < m_MaxParticles)
		createParticles(m_MaxParticles - mNumParticles);

the createParticles method calls allocate.


PARTNERS