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;
}