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:
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]);
};
};
Syntax check gave me an "OK"; haven't tried a real compile yet.
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.