Garbage Collection

This is a discussion on Garbage Collection within the C++ Programming forums, part of the General Programming Boards category; I have heard that memory fragmentation can be a problem in memory-munching programs, and I have also heard that garbage ...

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    28

    Question 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:

    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.

  2. #2
    Registered User
    Join Date
    Mar 2005
    Posts
    28
    It'd be really, really nice if someone could address this problem:
    Code:
    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...
    // blah blah blah //
    };
    It's really not related to the big problem and should be simple to solve, so if you know the answer to just that bit, I'd like it quickly, even if you don't have an answer to my new/delete problem immediately or ever...

  3. #3
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,699
    >> I'd like it quickly...
    I guess you've waited long enough - others probably won't agree.

    std::vector<MemoryChunk> blocks;
    and
    placement new

    Read 11.14 as well.

    gg

  4. #4
    Registered User
    Join Date
    Mar 2005
    Posts
    28
    Codeplug, why are you such a genius? It's disgusting. Thanks.

  5. #5
    Registered User
    Join Date
    Mar 2005
    Posts
    28

    Question

    Is it possible to do something functionally similar to the following?
    Code:
    inline MemPtr operator new(size_t _size, MemoryPile &from) {
         return from.MP_malloc(_size);
    };
    The program demands that "new" return void *, but I want something that is functionally the same as "new" but returns a MemPtr instead. Then *MemPtr will be overridden to use the dereference(MemPtr) command created above to dereference the MemPtr through the MemoryPile it is associated with. Does that make sense?

    I have a similar problem with operator delete; the compiler demands that it take a void * as the first argument, and I want it to take a MemPtr.

    Or am I trying to twist the C++ language too far out of shape in the first place?
    Last edited by Orborde; 05-11-2005 at 12:20 AM. Reason: Add more info

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. garbage collection enabled c++
    By manav in forum C++ Programming
    Replies: 42
    Last Post: 02-15-2008, 01:42 PM
  2. Garbage Collection is not so complicated
    By Nalpdii in forum C Programming
    Replies: 2
    Last Post: 10-08-2007, 12:34 AM
  3. C++ Garbage Collection
    By vaibhav in forum C++ Programming
    Replies: 1
    Last Post: 11-27-2005, 10:26 AM
  4. SDL: Garbage collection (?) screwing me
    By Brian in forum Game Programming
    Replies: 4
    Last Post: 05-08-2005, 10:13 AM
  5. garbage collection
    By joed in forum C Programming
    Replies: 4
    Last Post: 04-01-2004, 01:47 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21