Thread: Heap management

Hello, I am frustrated over heap management, basically the task is to manage a variable number of FIFO queues with limited memory. There are only 4 functions to manage the queues and 2 error handlers. So far it's proving difficult, I have gotten it work before, but that's only part of the collective functions so if anyone feels like a challenge, help me out a little.

My current code:

Code:

#include <stdlib.h>
#include <stdio.h>

typedef struct tagQ {
  unsigned char* segment;   /* Pointer to allocated memory. */
  size_t size;              /* Size of allocated block. */
  unsigned char* head;      /* Start of FIFO queue. */
  unsigned char* tail;      /* End of FIFO queue. */
} Q;                        /* This is the allocator handle */

static size_t total = 0;    /* Total number of allocator handle in memory. */
static size_t mfree = 2048; /* Total amount of non-occupied memory remain. */

unsigned char data[2048];

void onOutOfMemory(void) {
  exit(1);
}

void onIllegalOperation(void) {
  exit(1);
}
/* Need completion. */
Q* createQ(void) {
  size_t count;               /* Variable for stepping through each handle */
  Q* handle;
  unsigned char* seek;

  count = total;
  seek = data;
  handle = (Q*)seek;
  while(count > 0) {
    seek += sizeof(Q)+handle->size;
    handle = (Q*)seek;
    --count;
  }
  seek += sizeof(Q);                /* Move pointer to here segment starts. */
  handle->segment = seek;           /* Start of segment. */
#ifndef NDEBUG
  handle->size = 1;                 /* Reserved bytes. (debug) */
#else
  handle->size = 8;                 /* Reserved bytes. */
#endif
  handle->head = handle->segment;   /* See comment in deQ on why. */
  handle->tail = handle->segment;   /* Again, see comment in deQ. */

  ++total;
  mfree -= sizeof(Q)+handle->size;
  return handle;
}
/* Require fix. */
void destroyQ(Q* q) {               /* Queue memory is released by joining */
  if(q == NULL) {                   /* the destoryed queue with the smaller */
    return;                         /* adjacent queues. */
  }

  unsigned char* seek;
  Q* h1;
  Q* h2;
  size_t count;

  if(total > 1) {
    seek = data;
    h1 = (Q*)seek;
    count = 0;

    if(h1 == q) {
      h1 = NULL;
    } else {
      while(seek != (unsigned char*)q) {
        h1 = (Q*)seek;
        seek += sizeof(Q)+h1->size;
        ++count;
      }
    }

    ++count;
    if(count < total) {
      seek += sizeof(Q)+q->size;
      h2 = (Q*)seek;                    /* Finding the queue after this queue. */
    } else {                            /* There is no queue after this one... */
      h2 = NULL;
    }

    if(h1 != NULL && h2 != NULL) {      /* Two queues. */
      if(h1->size < h2->size || h1->size == h2->size) {
        h1->size += sizeof(Q)+q->size;
      } else {
        q->head = q->segment;
        q->tail = q->segment;
        while(h2->head != h2->tail) {
          *q->tail = *h2->head;
          ++q->tail;
          ++h2->head;
        }
        q->size += sizeof(Q)+h2->size;
        h2 = q;
      }
    }

    if(h1 == NULL) {             /* No queue before this queue. */
      h1 = q;
      h1->head = h1->segment;
      h1->tail = h1->segment;
      while(h2->head != h2->tail) {
        *h1->tail = *h2->head;
        ++h1->tail;
        ++h2->head;
      }
      h1->size += sizeof(Q)+h2->size;
    }

    if(h2 == NULL) {             /* No queue after this queue. */
      h1->size += sizeof(Q)+q->size;
    }
  }

  q = NULL;
  --total;
  return;
}
/* Need completion. */
void enQ(Q* q, unsigned char byte) {
  if(q == NULL) {
    onIllegalOperation();
  }

  if(q->tail == q->segment+q->size) {
    unsigned char* copy;
    if(q->head != q->segment) {           /* There is space in front. */
      copy = q->segment;
      while(q->head != q->tail) {         /* Copy data over. */
        *copy = *q->head;
        ++copy;
        ++q->head;
      }
      q->tail = copy;
      q->head = q->segment;               /* The head of the queue is back. */
    } else {
      if(mfree > sizeof(Q)+2*q->size) {   /* Enough memory to make another! */
        Q* h1;                            /* Handle of this queue. */
        Q* h2;                            /* Handle of next queue. */
        unsigned char* seek = (unsigned char*)q;
        size_t block = q->size*2-1;

        h1 = q;                           /* Get handle to this queue. */
        seek += sizeof(Q)+h1->size;       /* Move to next queue handle. */
        h2 = (Q*)seek;                    /* The next queue to be merged. */

        h1->size += sizeof(Q)+h2->size;   /* New queue size. */

        q = createQ();                    /* Make another queue. */
        q->size += block;                 /* Increate size. */
        while(h1->head != h1->tail) {     /* Copy data over. */
          *q->tail = *h1->head;
          ++q->tail;
          ++h1->head;
        }

        h1->head = h1->segment;           /* Reset pointer to new start. */
        h1->tail = h1->segment;
        while(h2->head != h2->tail) {     /* Copy queue 2's data over. */
          *h1->tail = *h2->head;
          ++h1->tail;
          ++h2->head;
        }
      } else {
        onOutOfMemory();
      }
    }
  }

  *q->tail = byte;                        /* Add another byte. */
  ++q->tail;
  return;
}
/* Complete. */
unsigned char deQ(Q* q) {
  if(q == NULL) {
    onIllegalOperation();
  }
  unsigned char byte;

  if(q->head == q->tail) {    /* A queue would only be empty if both head and */
    onIllegalOperation();     /* tail are pointing to segment. */
  }

  byte = *q->head;
  ++q->head;
  return byte;
}

int main() {
  Q* q0 = createQ();
  enQ(q0, 0);
  enQ(q0, 1);
  Q* q1 = createQ();
  enQ(q1, 3);
  enQ(q0, 2);
  enQ(q1, 4);
  printf("%d", deQ(q0));
  printf("%d\n", deQ(q0));
  enQ(q0, 5);
  enQ(q1, 6);
  printf("%d", deQ(q0));
  printf("%d\n", deQ(q0));
  destroyQ(q0);
  printf("%d", deQ(q1));
  printf("%d", deQ(q1));
  printf("%d\n", deQ(q1));
  destroyQ(q1);
  getchar();
  return 0;
}