   Mem Heap
  Hi!I have the following peace of code :   template<class T>void GetNextAvail(T *&pThis){//Cannot use more memory than whats//allocatedif(mSize_Left < sizeof(T)){throw "Using more memory than allocated!";return;}mNumLinks++;if(mNumLinks == mTotLinks){mTotLinks += 20;UINT *NewLinks = new UINT[mTotLinks];memcpy(NewLinks, mLinks, sizeof(UINT) * (mNumLinks - 1));delete mLinks;mLinks = NewLinks;}mLinks[mNumLinks] = reinterpret_cast<UINT &>(pThis);//Let the pointer object move to that//memory locationpThis = reinterpret_cast<T*>(mPoint) + mNext_Avail;//Move to endmPoint = mMem + mNext_Avail;//Call its constructor (if it has one)pThis->Init();//Lets specify to point to the next peace of the memorymNext_Avail += sizeof(T);mSize_Left -= sizeof(T);}How can I properly get the size of the object (class) thats passed throught the template, etc.This function will be used for classes(and maybe structs) that has the 2 functions : Init and Destroy.You see I thought of writing a Memory manager that allocates X-amount of memory at the beginning of the program and prepares, stores and removes any peace of data that has to be stroed in memory. Its the same as allocating / deallocating memory dynamically but you don''t waste that time that "new" and "delete" does.Its not finished nor has the bugs worked out of it and this is only 1 function. I''m also going to write a Defrag function that moves the bytes of memory backward and updates the affected pointers to that memory. the defrag can be ran when :* allocated space runs out* the user paused the game* beginning of the loading of a level (or any other time consuming operation)* any other time the programmer wishes to run it.I think that operating memory in this way can reduce File Swapping, which improves performance.What do yah think?   // Last Attacker   \\---=( LA   )=---// LA Extreme   \\ICQ Number :  120585863E-mail:   laextr@icqmail.com
  This is not a new concept, writing a memory pool for objects is common practice (it''s like a private heap).  I recommend using placement new on the returned pointer and not calling special functions like Init.  Do a google on placement new.Your code has a lot of problems with it.  - Shouldn''t this be included in a class instead of a single method?- What is "mSize_Left"?  How is it initialized?  Where is mTotLinks set?- I''m not sure why you''re using UINT instead of bytes to allocate the memory...shouldn''t you be using bytes?- You are doing something very dangerous here:memcpy(NewLinks, mLinks, sizeof(UINT) * (mNumLinks - 1));delete mLinks;Because callers may be using the pointers you returned originally.  If you copy the objects over to the new location, those callers will hold invalid references.  The way I did this is to grow my heap in "pages", leaving memory allocated and only allocating new pages (i.e. for you a page seems to be 20 objects at a time), never deleting old ones.- I would return the pointer from the function, don''t send it in as a input/output parameter...too confusing...;  Misuse of the sizeof() function. To find the size of a type   use...sizeof int; // For example.For a variable/constant, use...sizeof(aIntVar); ;  I only posted that function because I only wanted to know 1 thing! Which was how to determine the correct size of the object that''ll be passed thorugh.I am still working on it and have designed an algorithm to handle these cases like preventing to overwrite existing data, etc. I will also write a proper delete function.This function comes out of the MemHeap class if anyone wants to know.   // Last Attacker   \\---=( LA   )=---// LA Extreme   \\ICQ Number :   120585863E-mail:   laextr@icqmail.com ;  Ok, I think sizeof(T) is the answer to your question...it returns the size of the object IN BYTES.  Change this:UINT *NewLinks = new UINT[mTotLinks];to this:// this allocates enough space for mTotLinks new objects// (BYTE is 8 bits)BYTE* NewLinks = new BYTE[mTotLinks * sizeof(T)]; Does that not work?  I think it is related to the fact that you are using UINT (which is larger than 1 byte on most platforms) instead of BYTE (like I suggested)?As for my other points, did you read and understand them?  You are doing several incorrect things here:- you are copying all your memory to a new region and then deleting the older memory, which invalidates all the pointers you previously handed out- another thing I just realized is that you are using delete instead of delete[] (another memory leak)Regards,Jeff ;  See, the problem with passing in the pointer variable reference is that you may be able to track this specific pointer variable and move its value around when you re-allocate the memory but you can''t prevent this:MyObj* pObj = 0;MemHeap heap;heap.getNextAvailable(pObj);MyObj* pAnotherPtr = pObj;// heap re-allocation here// even if pObj is updated, pAnotherPtr is not// you have a dangling pointer...a big problem!A way to get around this is to roll your own smart pointer class that prevents copying from one pointer to another then and when a reallocation occurs, you can update all your links accordingly.  However, this may be more of a pain than its worth.My approach was to allocate "pages" of objects as raw bytes and just keep track of all the page pointers in my heap.  That way, you never need to delete any memory and worry about dangling pointers, you can just keep allocating more pages.Of course when the heap is destroyed, you would then destroy all the pages.Regards,Jeff ;  Before anyone points out any more problems let me explain!(Although I would like to say thanks for the memcpy of an UINT!)There is a memory allocation function called AllocMem() where you specify how much memory to have at the beginning.To be able to use this memory you create class pointers like :CTest *test;MemHeap.GetNextAvail(test);Now the MemHeap manager will go to the available peace of memory and modify the pointer ''test'' to use that specific peace of memory.I also realised that it you have 2 pointers at 1 peace of memory that the manager can only update the 1 pointer which is passed throuhg (which in this case is ''test''). Besides this is written for 1 pointer use only. If you want to make a mess when using this, its up to you but if you really need 2 pointers pointing at the same peace of memory (which I don''t think is nessasary) you can update the 2nd one often from the first one.The thing about sizeof(T) does not answer my problem, instead it returns 8-bytes instead of the correct size of the class (which in my test class case is 16-bytes, I think without the 8-byte class size).Oh and whats the diff between delete and delete []. Do you call delete [] when you have allocated arrays and delete when you have 1 element like data? (Thanks for showing that, I was starting to write everything with delete instead of delete [])I would also like to know what diff. ''sizeof T'' would do where sizeof(T) fails.Thanks for the response! // Last Attacker   \\---=( LA   )=---// LA Extreme   \\ICQ Number :   120585863E-mail:   laextr@icqmail.com ;quote:Before anyone points out any more problems let me explain!You shouldn't be so defensive about criticism.  We are trying to help you.quote:To be able to use this memory you create class pointers like :CTest *test;MemHeap.GetNextAvail< CTest >(test);Just as an FYI, you should be able to remove the < CTest > argument, since the compiler should figure out the type...quote:Now the MemHeap manager will go to the available peace of memory and modify the pointer 'test' to use that specific peace of memory.Another FYI, it's "piece" of memory, not "peace".quote:...this is written for 1 pointer use only. If you want to make a mess when using this, its up to you but if you really need 2 pointers pointing at the same peace of memory (which I don't think is nessasary)If you are 100% certain that only YOU will EVER be using this class and you will NEVER copy a pointer value, then you're free to do what you want.  I was just commenting that it is not very safe design and you're assumptions are a little naive.quote:The thing about sizeof(T) does not answer my problem, instead it returns 8-bytes instead of the correct size of the class (which in my test class case is 16-bytes, I think without the 8-byte class size).Post your test class definition that you think is 16 bytes.  My suspicion is that your class size is really 8 bytes and not 16, you might be making incorrect assumptions.quote:Oh and whats the diff between delete and delete []. Do you call delete [] when you have allocated arrays and delete when you have 1 element like data?You are correct.  Do a google on "C++ delete operator" to get more information.  quote:I would also like to know what diff. 'sizeof T' would do where sizeof(T) fails.I do not think this makes a difference at all.  I believe Mathematix was mistaken.  However, I could be wrong.  Test it and see.quote:Thanks for the response!You're welcome.Regards,Jeff [edited by - rypyr on February 5, 2004 11:37:37 AM];  Ok here''s what I have so far:main.cpp #include <stdlib.h>#include <stdio.h>#include "MemHeap.h"MemHeap MEM;class Test{public:int mP;int mT;Test() { Init(); };~Test() { Destroy(); };void Init() { mP = 0; mT = 0; };void Destroy() { mP = 0; mT = 0; };};Test *t;Test *p;Test *q;int main(){MEM.AllocMem(sizeof(Test) * 3);MEM.GetNextAvail<Test>(t);MEM.GetNextAvail<Test>(p);printf("t = %d; p = %d; t.p = %d; p.p = %d\n", (__w64)&t, (__w64)&p, t->mP, p->mP);t->mP = 1;p->mP = 2;printf("t = %d; p = %d; t.p = %d; p.p = %d\n", (__w64)&t, (__w64)&p, t->mP, p->mP);MEM.FreeMemItem<Test>(t);MEM.GetNextAvail<Test>(t);t->mP = 5;MEM.GetNextAvail<Test>(q);q->mP = 55;printf("\nt = %d; p = %d; q = %d; \nt.p = %d; p.p = %d; q.p = %d\n", (__w64)&t, (__w64)&p, (__w64)&q, t->mP, p->mP, q->mP);MEM.FreeMemItem<Test>(t);MEM.FreeMemItem<Test>(p);MEM.FreeMemItem<Test>(q);return 0;}MemHeap.cpp #include "MemHeap.h"MemHeap::MemHeap(){mMem = NULL;mDeletedPos = NULL;mLastPos = NULL;mLinks = NULL;mNumLinks = 0;mTotLinks = 0;mSize = 0;mSize_Left = 0;mDeletedSize = 0;mHasDeleted = false;mDefragable = false;}MemHeap::MemHeap(int start_size){if(start_size < 1)start_size = DEFAULT_HEAP_SIZE;if((mMem = new UBYTE[start_size]) == NULL){throw "Not enough memory to allocate Heap of the given amount!";return;}if((mLinks = new UINT*[INIT_LINK_SIZE]) == NULL){throw "Not enough memory to allocate space for the Links List!";return;}mDeletedPos = NULL;mLastPos = mMem;mNumLinks = 0;mTotLinks = INIT_LINK_SIZE;mSize = start_size;mSize_Left = start_size;mDeletedSize = 0;mHasDeleted = false;mDefragable = false;}MemHeap::~MemHeap(){if(mMem)delete [] mMem;if(mLinks)delete [] mLinks;}void MemHeap::AllocMem(int size){//We''re starting fresh.if(mMem)delete [] mMem;if(mLinks)delete [] mLinks;if(size < 1)size = DEFAULT_HEAP_SIZE;if((mMem = new UBYTE[size]) == NULL){throw "Not enough memory to allocate Heap of the given amount!";return;}if((mLinks = new UINT*[INIT_LINK_SIZE]) == NULL){throw "Not enough memory to allocate space for the Links List!";return;}mDeletedPos = NULL;mLastPos = mMem;mNumLinks = 0;mTotLinks = INIT_LINK_SIZE;mSize = size;mSize_Left = size;mDeletedSize = 0;mHasDeleted = false;mDefragable = false;}void MemHeap::FreeMem(){//Lets free and reset everything!if(mMem)delete [] mMem;if(mLinks)delete [] mLinks;mDeletedPos = NULL;mLastPos = NULL;mNumLinks = 0;mTotLinks = 0;mSize = 0;mSize_Left = 0;mDeletedSize = 0;mHasDeleted = false;mDefragable = false;}MemHeap.h #ifndef MEM_HEAP_H#define MEM_HEAP_H#include<stdlib.h>#include<memory.h>typedef unsigned char UBYTE;typedef unsigned int UINT;#define DEFAULT_HEAP_SIZE50#define INIT_LINK_SIZE20//Initial Link List Size#define ADD_LINK_SIZE20//Amount more to add to List Sizeclass MemHeap{private:int mSize;//Current size of Heap (in bytes)int mSize_Left;//Available size left in Heapint mTotLinks;//Total amount of links to holdint mNumLinks;//Current hold of number of linksint mDeletedSize;//The last deleted data sizeUINT **mLinks;UBYTE *mMem;UBYTE *mLastPos;//A position from where we can add dataUBYTE *mDeletedPos;//The last address where data was deletedbool mHasDeleted;//Did we delete something before adding?bool mDefragable;//Is it nessasary to defrag?public:MemHeap();MemHeap(int start_size);~MemHeap();void AllocMem(int size);void FreeMem();//Accessorsbool Defragable() { return mDefragable; };int Size_Current() { return mSize; };//Current Heap Sizeint Size_Left() { return mSize_Left; };//Size Left in Heap//Get next available peace of memorytemplate<class T>void GetNextAvail(T *&pThis){//Cannot use more memory than whats//allocatedif(mSize_Left < sizeof(T)){throw "Using more memory than allocated!";return;}mNumLinks++;//Reached max number of Links to hold?if(mNumLinks >= mTotLinks){//Lets make some moremTotLinks += ADD_LINK_SIZE;//Expand the Links ListUINT **NewLinks = new UINT*[mTotLinks];//Copy all prev. links to NewLinks list.//UINT is 4-bytes as well as a pointer var.memcpy(NewLinks, mLinks, sizeof(UINT) * (mNumLinks));//Delete the old linksdelete [] mLinks;//Assign Links pointer to NewLinksmLinks = NewLinks;}//Store the reference address of pThis in Links List.mLinks[mNumLinks - 1] = reinterpret_cast<UINT *>(&pThis);//Let the pointer object move to that//memory locationpThis = reinterpret_cast<T*>(mLastPos);//Call its constructor (or initializer)pThis->Init();//Lets specify to point to the next peace of the memorymLastPos += sizeof(T);//Reduce avail. size leftmSize_Left -= sizeof(T);}template<class T>void FreeMemItem(T *&pThis){//Call its destructorpThis->Destroy();int i;//Loop through all Linksfor(i = 0; i < mNumLinks; i++){//Matched the reference address?//If so, remove it from Links List.if(mLinks[i] == reinterpret_cast<UINT *>(&pThis)){mDeletedPos = reinterpret_cast<UBYTE *>(pThis);//Get the size that is being deletedmDeletedSize = sizeof(T);mHasDeleted = true;//Lets replace the first index with the last onemLinks[i] = mLinks[mNumLinks - 1];//Was this the last link?if(i == mNumLinks - 1)mLastPos -= sizeof(T);elsemDefragable = true;//Decrement countermNumLinks--;break;}}//Show that this pointer class//points nowherepThis = NULL;//Update mSize_LeftmSize_Left += sizeof(T);}};#endifRemember the memcpy(NewLinks, mLinks, sizeof(UINT) * (mNumLinks)); ?Well it must be UINT because its holding pointers reference addressed, not memory data.I made a couple of modifications.Please tell me what you think.Oh, and I get a memory error at the end of the program.Any ideas?Thanks   // Last Attacker   \\---=( LA   )=---// LA Extreme   \\ICQ Number :  120585863E-mail:   laextr@icqmail.com