Now let me just say that I know this solution is far from ideal and also that I've read very little on the subject. I'm curious to see what I can come up with myself
A singly linked list of these is managed (it's not an STL list):
When an allocation request is made, the list is searched for a MemBlock_t that is marked as free (mFree) and whose size exactly matches the requested amount (in bytes). If no such block exists, a new one is created, setup and linked in.Code:struct MemBlock_t { bool mFree; MemBlock_t* mNext; size_t mSize; char* mData; };
Calling the free function searches the list for the correct block (more on that in a mo') and simply marks it as free.
Yeah, the searching during a free... at the moment I've got it simply comparing the pointer passed with the mData of each block. It's working fine so far and in all of the tests I've run, but would it be better to allocate 4 extra bytes at the start of each mData block and write a UID there (unsigned long), then use that to compare? Help me out here.
The destructor for the CMemory object iterates the list and destroys each node. Later on I'll have it throw out a warning if any of the blocks were marked as !mFree too.
Oh and yeah, I'm not going to keep all of this code in the ctor / dtor when I put it into my engine (this is a seperate project so I can work on this object alone ) - I'll write Initialise() / Shutdown()'s.
I did want to work it so that if a block larger than the request is found, it's split and two new blocks are constructed in it's place - is it worth doing that? It's no trouble, but I'm worried about fragmentation.
Then again, with the current method, I'm thinking that there could well be a helluva lot of blocks unused a lot of the time, but then again I could write a CollectGarbage() function to free the mData of any blocks marked as mFree. CollectGarbage() wouldn't actually remove them from the list though, just make it so that if the block is chosen to satisfy a request later on, the allocator needs to allocate it again. Should take the edge off the memory usage, right?
Anyway I'm starting to ramble - take a look at it all. Feel free to shoot me some constructive criticism. You can use it if you want, too ( make sure you tell me so I get that warm fuzzy feeling )
Memory.h
Memory.cppCode:#pragma once struct MemoryState_t { unsigned long mTotalAllocated; unsigned long mBlockCount; }; class CMemory { public: CMemory(); ~CMemory(); void* MemAlloc( size_t bytes ); void* MemAllocZero( size_t bytes ); void MemFree( void* ptr ); MemoryState_t GetMemoryState(); void DumpMemoryBlocks(); private: struct MemBlock_t { bool mFree; MemBlock_t* mNext; size_t mSize; char* mData; }; MemBlock_t* mBlocksHead; };
EDIT (I knew I'd forget something): According to _CrtDumpMemoryLeaks(), this is completely leak-less. Just FYI for anyone thinking of using itCode:#include "stdafx.h" #include "Memory.h" //////// // ctor / dtor // dtor: Walk the list and free all mData memory if t'was allocated, then the node itself. // CMemory::CMemory() { MemBlock_t* dummy = NULL; mBlocksHead = dummy; } CMemory::~CMemory() { MemBlock_t* walk = mBlocksHead; MemBlock_t* temp = NULL; while ( walk ) { if ( walk->mData ) { delete[] walk->mData; std::cout << "Just freed " << static_cast<unsigned>( walk->mSize ) << " bytes of data\n"; } temp = walk->mNext; delete walk; walk = temp; } } //////// // MemAlloc // Scan the block list for a block that's big enough to satisy @bytes. // If no allocated block can satisfy @bytes, // a new block of the correct size is allocated. // void* CMemory::MemAlloc( size_t bytes ) { MemBlock_t* walk = mBlocksHead; // Scan for big enough block while ( walk ) { if ( walk->mSize == bytes && walk->mFree ) { // Perfect match. Clear the data and return a pointer to it. memset( walk->mData, 0, walk->mSize ); return static_cast<void*>( walk->mData ); } walk = walk->mNext; } // If we get here, no block can satisfy @bytes // so allocate a new one and link it in MemBlock_t* block = new MemBlock_t; if ( !block ) return NULL; block->mData = new char[bytes]; block->mFree = false; block->mSize = bytes; // Link it in block->mNext = mBlocksHead; mBlocksHead = block; return static_cast<void*>( block->mData ); } void* CMemory::MemAllocZero( size_t bytes ) { return NULL; } //////// // MemFree // Finds the block associated with @ptr and marks it // as free. // void CMemory::MemFree( void* ptr ) { MemBlock_t* walk = mBlocksHead; MemBlock_t* temp = NULL; bool found = false; // Find it and mark it while ( walk ) { if ( walk->mData == ptr ) { found = true; printf( "Found it\n" ); walk->mFree = true; } walk = walk->mNext; } if ( !found ) { // Even though ptr could be a naked pointer ( and valid ) // if it's not in the block list, it's invalid as far as this // manager is concerned std::cout << "\nMemFree: Invalid pointer given\n"; // Would probably be an exception in the engine } } MemoryState_t CMemory::GetMemoryState() { MemoryState_t state; MemBlock_t* walk = mBlocksHead; unsigned long totalSz = 0; unsigned long blocks = 0; memset( &state, 0, sizeof(MemoryState_t) ); while ( walk ) { totalSz += static_cast<unsigned long>( walk->mSize ); blocks++; walk = walk->mNext; } state.mBlockCount = blocks; state.mTotalAllocated = totalSz; return state; } void CMemory::DumpMemoryBlocks() { MemBlock_t* walk = mBlocksHead; while ( walk ) { printf( "\nBlock Data\n\n" ); printf( "Size: %d\n", walk->mSize ); printf( "Data: %s\n", walk->mData ); walk = walk->mNext; } }