Memory Management & Embedded Databases
by Andrei Gorine and Konstantin Knizhnik

Example 1:

const int storage::block_chain[32] = { 
     0,  0,  1,  2,  3,  4,  5,  6,  7,  8, 
     9,  9, 10, 10, 10, 10, 11, 11, 11, 11, 
    11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 
    12, 12
};
const int storage::block_size[32] = { 
     16,  16,  24,  32,  40,  48,  56,  64,  72,  80,  
     96,  96, 128, 128, 128, 128, 168, 168, 168, 168, 
    168, 256, 256, 256, 256, 256, 256, 256, 256, 256, 
    256, 256
};



Listing One

template<class T>
class fixed_size_object_allocator { 
  protected:
    T*          free_chain;
  public:
    /* allocate method */       
    T* allocate() {
        T* obj = free_chain;
        if (obj == NULL) {
            obj = new T();
        } else { 
            free_chain = obj->next;
        }
        return obj;
    }
    /* free method */ 
    void free(T* obj) {
        obj->next = free_chain;
        free_chain = obj;
    }
    /* constructor /destructor */ 
    fixed_size_object_allocator() {
        free_chain = NULL;
    }
    ~fixed_size_object_allocator() { 
        T *obj, *next;
        for (obj = free_chain; obj != NULL; obj = next) { 
            next = obj->next;
            delete obj;
        }
    }
};


Listing Two

class BlockAllocator { 
    void* allocate(size_t size) { 
    if (size + sizeof(object_header) <= page_size/2) { 
        int n = block_chain[((size+sizeof(object_header)+7)>>3)-1];
        storage_free_block* bp = hdr->free_block_chain[n];
        if (bp != NULL) { 
        hdr->free_block_chain[n] = bp->next;
        bp->size = size;
        return (object_header*)bp+1;
        }
    }
    // allocate a new block using some external allocator
    return alloc_block(size); 
    }
    void  free(object* obj) { 
    object_header* hp = get_header(obj);
    if (hp->size + sizeof(object_header) <= page_size/2) {
        int n=block_chain[((hp->size+sizeof(object_header)+7)>>3)-1];
        storage_free_block* bp = (storage_free_block*)hp;
        bp->next = hdr->free_block_chain[n];
        hdr->free_block_chain[n] = bp;
    } else {
        // return the block back to the memory pool      
        free_block(hp);
    }
    }
};


Listing Three

class StackAllocator {
   class Segment {
      Segment* next;     // segments are linked in the L1 list
      size_t   size;     // size of a segment     
      char     data[1];  // segment data. The actual size of data is
                         // specified by the new() operator   
      // overloaded new() operator
      void* operator new(size_t fixedSize, size_t dataSize) {
         return new char[fixedSize + dataSize - 1];
      }
      Segment(size_t dataSize, Segment* nextSegm) 
         : size(dataSize), next(nextSegm) {}
    };
    Segment* currSegm; // current segment (top of stack)
    Segment* freeSegm; // list of free segments
    size_t currBase;   // base address of the current segment
    size_t currOffs;   // offset within the current segment
    size_t segmSize;   // the default segment size
    size_t currSize;   // size of the current segment        
public:
    void* allocate(size_t size) {
        if (currOffs + size > currSize) {
        // There is not enough space in the current segment 
            currSize = size > segmSize ? size : segmSize;
            if (freeSegm == NULL || freeSegm->size < currSize) {
                // Create a new segment
                currSeg = new (newSize) Segment(currSize, currSegm);
        } else {
               // get a segment from the free segments list  
               currSegm = freeSegm;    
               freeSegm = freeSegm->next;
        }
        currBase += currSize;
        currSize = currSegm->size;
        currOffs = 0;
     }
     void* ptr = currSegm->data + currOffs;
     currOffs += size;  // adjust the offset
     return ptr;
   }
   // Get the current stack position
   size_t mark() { 
      return currBase + currOffs;
   }
   // Unwind the stack back to the marked position  
   size_t reset(size_t mark) {
        // while (mark does not belong to the current segment)
        while (currBase > mark)  {
        // Return a segment to the list of free segments and move
        // one segment back
        currBase -= currSegm->size;
        Segment* next = currSegm->next;
        currSegm->next = freeSegm;
        freeSegm = currSegm;
        curSegm = next;
    }
    // adjust the offset within the segment  
    currOffs = mark - currBase;   
    currSize = currSegm->size;
    }
    // This is the constructor of stack allocator with the specified
    // default segment size 
    StackAllocator(size_t segmentSize) {
      segmSize = segmentSize;
      currSize = 0;
      currBase = 0;
      currOffs = 0;
      currSegm = NULL;
      freeSegm = NULL;  
    }
    // Stack allocator destructor. It releases all the allocated segments 
    ~StackAllocator() {
        Segment *segm, *next;
        for (segm = freeSegm; segm != NULL; segm = next) { 
           next = segm->next;
           delete segm;
        }
        for (segm = currSegm; segm != NULL; segm = next) { 
            next = segm->next;
            delete segm;
        }
    }    
};


Listing Four

holeSize = 0;
for (int i = 0; i < bitmapSize*8; i++) {
      if (bitmap[i >> 3] & (1 << (i&7)) {
           holeSize = 0;
      } else if (++holeSize >= objBitSize) {
           return (i-holeSize+1)*8*allocationQuantum;
      }
}


Listing Five

static byte const firstHoleSize [] = {
   8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,        
   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,        
   6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
   7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
   6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
};
static byte const lastHoleSize [] = {
   8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
   2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
};
static byte const maxHoleSize [] = {
   8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
   5,4,3,3,2,2,2,2,3,2,2,2,2,2,2,2,4,3,2,2,2,2,2,2,3,2,2,2,2,2,2,2,
   6,5,4,4,3,3,3,3,3,2,2,2,2,2,2,2,4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1,
   5,4,3,3,2,2,2,2,3,2,1,1,2,1,1,1,4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1,
   7,6,5,5,4,4,4,4,3,3,3,3,3,3,3,3,4,3,2,2,2,2,2,2,3,2,2,2,2,2,2,2,
   5,4,3,3,2,2,2,2,3,2,1,1,2,1,1,1,4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1,
   6,5,4,4,3,3,3,3,3,2,2,2,2,2,2,2,4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,1,
   5,4,3,3,2,2,2,2,3,2,1,1,2,1,1,1,4,3,2,2,2,1,1,1,3,2,1,1,2,1,1,0
};

static byte const maxHoleOffset [] = {
   0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,0,1,5,5,5,5,5,5,0,5,5,5,5,5,5,5,
   0,1,2,2,0,3,3,3,0,1,6,6,0,6,6,6,0,1,2,2,0,6,6,6,0,1,6,6,0,6,6,6,
   0,1,2,2,3,3,3,3,0,1,4,4,0,4,4,4,0,1,2,2,0,1,0,3,0,1,0,2,0,1,0,5,
   0,1,2,2,0,3,3,3,0,1,0,2,0,1,0,4,0,1,2,2,0,1,0,3,0,1,0,2,0,1,0,7,
   0,1,2,2,3,3,3,3,0,4,4,4,4,4,4,4,0,1,2,2,0,5,5,5,0,1,5,5,0,5,5,5,
   0,1,2,2,0,3,3,3,0,1,0,2,0,1,0,4,0,1,2,2,0,1,0,3,0,1,0,2,0,1,0,6,
   0,1,2,2,3,3,3,3,0,1,4,4,0,4,4,4,0,1,2,2,0,1,0,3,0,1,0,2,0,1,0,5,
   0,1,2,2,0,3,3,3,0,1,0,2,0,1,0,4,0,1,2,2,0,1,0,3,0,1,0,2,0,1,0,0
};

Listing Six

while (i < bitmap_size)
{
  if (first_hole_size[i] + current_hole_size >= object_bit_size) {
       return offset_of_the_hole;
  } else if (first_hole_size[i] == 8) { 
       current_hole_size += 8;
  } else if (max hole size[i] >= object_bit_size) { 
      return offset_of_max_hole;
  } else {
      current_hole_size = last_hole_size[i];
  }
  i++;
}


4


