In realtime systems, malloc/free/garbage collection can take a very long time.

For a real-time system I'm doing, I want to have very fast response time, I call malloc/free often.
Traditional malloc/free will fragment memory quickly, and garbage collection will just take
forever.

The solution I've used many times is a bucket allocator, setting pre-defined sizes of memory, and putting them in a queue, or in this case a "bucket". The idea being find the bucket, pull out a entry and return it.

Also something I've found useful is to keep track of busy memory elements as well. That way if I suspect that memory is getting corrupted, I can easily add a tag at the end of the allocation, and run thru the busy memory looking for the corruption. Very useful in debug.

#include 
#include 
#include "include/queue.h"



struct bucket_struct {
       struct entry_struct entry;
       struct queue_struct free_q;
       struct queue_struct busy_q;
       int    size;
       };

struct alloc_struct {
       struct entry_struct entry;
       struct bucket_struct *bucket;
       };

struct queue_struct buckets;

int gkmalloc_init_needed = 1;

void gkmalloc_newbucket(thesize)
int thesize;
{
struct bucket_struct *mybucket;

     mybucket = malloc(sizeof(struct bucket_struct));
     mybucket->free_q.head = NULL;
     mybucket->free_q.tail = NULL;
     mybucket->busy_q.head = NULL;
     mybucket->busy_q.tail = NULL;
     mybucket->entry.next = NULL;
     mybucket->entry.prev = NULL;
     mybucket->size = thesize;
     queue(&buckets, &mybucket->entry);
     return;
}    


void gkmalloc_init(void)
{
    gkmalloc_init_needed = 0;
    buckets.head = NULL;
    buckets.tail = NULL;
    gkmalloc_newbucket(32);
    gkmalloc_newbucket(64);
    gkmalloc_newbucket(128);
    gkmalloc_newbucket(256);
    gkmalloc_newbucket(512);
    gkmalloc_newbucket(1024);
    gkmalloc_newbucket(2048);
    gkmalloc_newbucket(4096);
    gkmalloc_newbucket(8192);
    gkmalloc_newbucket(32768);
    gkmalloc_newbucket(12000000); // Big Buf for jpegs
    return;
}

char *gkmalloc(thesize)
int thesize;
{
struct bucket_struct *mybucket;
struct alloc_struct  *myalloc;
void *ptr;

     if (thesize == 0)
        return(NULL);
     if (gkmalloc_init_needed){
        gkmalloc_init();
        gkmalloc_init_needed = 0;
        }
     mybucket = (struct bucket_struct *)buckets.head;
     while(mybucket->size < thesize){
          if (mybucket == NULL){ // Should never happen
              gkfatal("gkmalloc: Allocation bigger than max bucket");
              return(NULL);
              }
          mybucket = (struct bucket_struct *)mybucket->entry.next;
          }
     myalloc = (struct alloc_struct *)unqueue(&mybucket->free_q);
     if (myalloc == NULL){ // The allocation queue is empty
         // Dynamically allocate from the system
         myalloc = malloc(sizeof(struct alloc_struct) + mybucket->size);
         if (myalloc == NULL){
            gkfatal("gkmalloc: Cannot malloc new buffer");
            return(NULL);
            }
         myalloc->bucket = mybucket;
         }
           
      queue(&mybucket->busy_q, &myalloc->entry);
      ptr = (void *)(myalloc + 1); // Add the size of the header to get Memory After
      return(ptr);
}
       
void gkfree(ptr)
void *ptr;
{
struct bucket_struct *mybucket;
struct alloc_struct  *myalloc;

      if (ptr == NULL){
         gkfatal("gkfree: Bad Free - Null Ptr Passed");
         return;
         }
      myalloc = (struct alloc_struct *)ptr;
      myalloc = myalloc - 1; // Go back to the header info
      mybucket = myalloc->bucket;
      if (mybucket == NULL){
         gkfatal("gkfree: Bad Bucket");
         return;
         }
      queue(&mybucket->free_q,&myalloc->entry);
      return;
}