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

It doesn't work, simple.

The debugger won't work on this system so I have no way of knowing what happened.

If possible could you check if my logic is correct, I am a newbie programmer but rather competent when writing code so I figure I could fix the problem by myself given time. But it would be much easier if I could get help from better programmers. Such is the case when I will need to optimise these functions.

Problem: It seems to call one of the error handling functions as it enQs, that's why it shuts off the program as soon as it executes, printf didn't do anything. No message.

It does compile without warnings or errors.

Not trying to optimise, just trying to get it to work. Last time I edited this, it worked fine but then there was something wrong with pointers so I fixed it and now it doesn't work.

I'll explain here:

The code to create a queue handle before was like this:

Code:

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

  handle->segment = seek;           /* Start of segment.  I thought this was wrong. */

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

Where seek would be the same location as the handle pointer, and I assigned the memory segment to the same location as the handle, which should be wrong by definition as the handle should be before the segment.

So I added:

Code:

seek += sizeof(Q);

To move the seek pointer to where the reserved memory should start, which is sizeof(Q) from the pointer to the handle, although I might have miscalculated something here...

[memory...]

(Q handle (16 bytes))
[segment pointer] (4 bytes)
[size variable] (4 bytes)
[head pointer] (4 bytes)
[tail pointer] (4 bytes)

So it should be like:
################: handle (16 bytes), seek pointer is at 1st byte
==================
########... : allocated memory pointer to by segment

Where segment should be seek += sizeof(Q).

It's ugly because I use the old coding style, attach else at the end of ifs and no single line braces. What do you mean by poorly commented? Do you want me to comment every detail or what? I could do that.

Problem: It seems to call one of the error handling functions as it enQs, that's why it shuts off the program as soon as it executes, printf didn't do anything. No message.

Nope. In your first call to deQ(q0) you execute this statement ++q->head which causes head and tail to point to same location. Thus, in your next call to deQ(q0), the following is executed and you bail out of the app

Code:

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

Okay, point taken. I've wrote much better comments this time round. I'll post the refreshed piece of code after I try some more methods.

About the head and tail thing however... I think I'll explain here:

[queue handle (16 bytes)][head - tail points to 1st byte][reserved space...]

If I haven't deQ any bytes, head will always point to where segment is pointing to. Now, if I enQ a byte, I move the tail pointer up, why? Because in order to know how many bytes I actually have in the queue, I will need a extra variable, but that would make the handle to large, so (long)tail - (long)head would give me the same effect.

If I had only 1 item, and the reserved size for that handle is exactly one, then the memory would look like this:

[byte 1][free bytes...]

As stated above, tail would be pointing at the byte just after byte 1. When I deQ, I withdraw whatever byte was at head, and move the head pointer up. Now if there is any more attempts to deQ, the function would report an error because there is no more data. When head is pointing at the same location as tail, I would know that there are no more bytes that can be deQ'ed.

As in your statement, if I had only 1 data, and head and tail are both pointing at it, how would I know if the next deQ is valid?