Garbage Collection
I have heard that memory fragmentation can be a problem in memory-munching programs, and I have also heard that garbage collection (if that's the correct term) works wonders for it. So, since C++ has no native garbage collector, I'm working on how to write one myself. The design goes thusly:
Syntax check gave me an "OK"; haven't tried a real compile yet.Code:#include <vector> // type used for the "pointers", which are just big long integers as far as the system is concerned typedef unsigned long int MemPtr; // this is a structure to store allocation block entries struct MemoryChunk { MemPtr start; // index into MemoryPile's heap MemPtr length; // length of allocation block // bool active; // may be necessary // functions to fiddle with this inline void quickSet(MemPtr _s, MemPtr _l) { start = _s; length = _l; }; MemoryChunk( MemPtr _s, MemPtr _l) { quickSet(_s,_l); }; }; class MemoryPile { vector<MemoryChunk> blocks; // vector of allocation blocks // for some reason I'm getting "error: ISO C++ forbids declaration of 'vector' with no type" for the above... char * memheap; // pointer to our custom heap MemPtr size; // size of the heap MemPtr nextfree; // next free index point public: MemoryPile(MemPtr _size) { size = _size; memheap = new char[size]; // allocate the heap // initalize vector here? // check for failure here nextfree = 0; }; ~MemoryPile() { delete [] memheap; }; // groups all the allocated blocks together at the beginning of memheap // also erases all MemoryChunks with values {0,0} void Collect_Garbage() { // can't be bothered to type out the algorithm properly ATM // so you get pseudocode /* Iterate through the vector blocks * Erase all blank {0,0} entries * if (blocks[0].start != 0) memmove(memheap, * memheap + blocks[0].start, * blocks[0].length); * Do this for each block i with for (i = 1; i <= blocks.size(); i++): * memmove(memheap + blocks[i-1].start + blocks[i-1].length, * memheap + blocks[i].start, * blocks[i].length); * Do the above with STL iterators */ // rejoice }; // malloc-similar function MemPtr MP_malloc(size_t blocksize) { if (blocksize == 0) return 0; // you can't allocate nothing, silly! /* add something to iterate through to find empty blocks * that are not at end here? requires a bit of redesign... */ if (nextfree + blocksize > size) { // if we're out of memory at end... Collect_Garbage(); // garbage collect and try again if (nextfree + blocksize > size) return 0; // no memory: failure }; MemoryChunk newmem(nextfree, blocksize); // make block blocks.push_back(newmem); // put it into the list return blocks.size(); // return the block index for the pointer }; void MP_free(MemPtr targ) { if (targ > blocks.size()) return; blocks[targ - 1].quickSet(0,0); // set to null for speed /* here we need to * set blocks[targ - 1].active = FALSE if I have created that flag. * see comment in MP_malloc() */ }; // should be an operator overriding new, but I need to resolve issues with that first... // syntax may not be correct... template<typename newType> MemPtr MP_new() { MemPtr targ = MP_malloc(sizeof(newType)); if (targ == 0) return 0; // malloc failure? // CALL CONSTRUCTOR HERE???!!!!11 // I DON'T KNOW HOW TO DO THAT!! /* Should be newType.newType() with dereference(targ) * as an argument of some sort... */ return targ; }; // should be an operator overriding delete, but I need to resolve issues with that first... // syntax may not be correct... template<typename newType> void MP_delete(MemPtr targ) { // maybe the following should do something more drastic instead? if (targ > blocks.size()) return; // do nothing if invalid pointer // CALL DESTRUCTOR HERE???!!!!11 // I DON'T KNOW HOW TO DO THAT!! /* Should be newType.~newType() with dereference(targ) * as an argument of some sort... */ MP_free(targ); }; /* this should really be a template operator * but is a function returning void * for now. * Cast it yourself for now. */ void * dereference(MemPtr targ) { // error checking goes here return (void *)(memheap + blocks[targ - 1]); }; };
The problems are in the bolded lines. In order to implement "new", I need to be able to call the object's constructor manually after assigning it an address myself.
Notice also that valid MemPtr values used to dereference and whatnot are 1 or above, so you can still get a null pointer back if my custom malloc fails. Thus, when dereferencing MemPtr x, you use blocks[x - 1]. If you see me failing to do that somewhere, please tell me.
So, I've bombarded you with code. Comments, questions, and help, please? Thanks.
