Heap management

This is a discussion on Heap management within the C Programming forums, part of the General Programming Boards category; Hello, I am frustrated over heap management, basically the task is to manage a variable number of FIFO queues with ...

  1. #1
    C++ Newbie
    Join Date
    Nov 2005
    Posts
    49

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

  2. #2
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    What is your question exactly ?
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  3. #3
    C++ Newbie
    Join Date
    Nov 2005
    Posts
    49
    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.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Frost Drake
    It doesn't work, simple.
    What's "doesn't work" mean?
    Quote Originally Posted by Frost Drake
    The debugger won't work on this system so I have no way of knowing what happened.
    You do, you're just too ........ing lazy. Add some printf statements to your code and watch what it does. You know you can actually print out the values of variables!

    Quote Originally Posted by Frost Drake
    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.
    I find your code ugly to read, and poorly commented.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Remember, "Premature optimization is the root of all evil" (Knuth). Get the code right first, before you try anything funny with it.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  6. #6
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Look, if you want people to help you, you'll have to be more specific. What exactly doesn't work ? What have you tried to fix it ?

    I'm sorry to break it to you, but no one here wants to read through all your code to understand what it does, or what it's doing wrong. When you point us in the direction of the problem, then we can give you an idea on how to solve it.

    I don't mean to put this harshly, but it's important that this be clear to you.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  7. #7
    C++ Newbie
    Join Date
    Nov 2005
    Posts
    49
    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.

  8. #8
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,059
    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. */
        }

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    The reason I state poor commenting, is things like the above quote. Why? Why is your queue considered empty if they both point to the same thing? If you have one entry, the head and tail should both point at it. Not past it. Clearly getting your points across are what comments are for. You don't describe your queue any place. You don't describe your reasoning for anything. It's just not good commenting. Obviously I can look at your code above, and see that you're saying it's illegal for head and tail to point to the same node. Why though? That's wrong, or clearly it should be. Or else you need to describe your queue more.

    Poor comments.


    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    C++ Newbie
    Join Date
    Nov 2005
    Posts
    49
    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?

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You could get the same effect by simply having a variable hold the size of the queue, but it would be less confusing in nature. Typically the tail points to the last element, not past it.


    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,541
    > static size_t total = 0; /* Total number of allocator handle in memory. */
    > static size_t mfree = 2048; /* Total amount of non-occupied memory remain. */
    Why aren't these inside your Q struct?
    What if you have more than one Q? - all hell breaks loose.

    Start with simple tests like
    Code:
      Q* q0 = createQ();
      destroyQ(q0);
    and
    Code:
      Q* q0 = createQ();
      enQ(q0, 0);
      printf("%d", deQ(q0));
      destroyQ(q0);
    I mean if you can't create and destroy a Q without doing anything, then even trying to debug add and remove is just a waste of effort.

    Use the debugger to single-step through the code one line at a time, and examine the state of things as you go.

    Draw out on paper what you expect to happen (run the code in your head). When what actually happens is different to what you think should happen, you've found a bug.

    Lather, rinse and repeat.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  13. #13
    C++ Newbie
    Join Date
    Nov 2005
    Posts
    49
    Quote Originally Posted by Salem
    > static size_t total = 0; /* Total number of allocator handle in memory. */
    > static size_t mfree = 2048; /* Total amount of non-occupied memory remain. */
    Why aren't these inside your Q struct?
    What if you have more than one Q? - all hell breaks loose.

    Start with simple tests like
    Code:
      Q* q0 = createQ();
      destroyQ(q0);
    and
    Code:
      Q* q0 = createQ();
      enQ(q0, 0);
      printf("%d", deQ(q0));
      destroyQ(q0);
    I mean if you can't create and destroy a Q without doing anything, then even trying to debug add and remove is just a waste of effort.

    Use the debugger to single-step through the code one line at a time, and examine the state of things as you go.

    Draw out on paper what you expect to happen (run the code in your head). When what actually happens is different to what you think should happen, you've found a bug.

    Lather, rinse and repeat.
    If I place them inside the Q struct, the compiler jumps at me and gives me: syntax error before "static".

    If I had more than one queue, the createQ function will forward a seek pointer to the end of the previous Q and create a new Q there by casting and returning the handle.

    createQ and destroyQ seems to work fine, I've got debugging fprintfs everywhere to print out the address of each created queue and making sure that there is no conflict. No error reported from these two functions and the addresses of the assigned pointers check out also.

    So I think there is something wrong with enQ and deQ. I'm willing to take judgement on this one though.

    I've drawn out the plans about 10+ times, visualised everytime I modified the code and also put on paper what I would expect. Hell, I've even drawn memory diagrams about what should be where and more...

    I know there is a bug, because the result isn't what I expected, but I just can't find it.

    Here the current last bit of code: Please help, I have no idea what's wrong. I will be as today move this project onto my offline computer which is much faster and better. So I won't be able to post updated code, but I can assure you it would be well documented like you suggested. Also testing can be done faster on the other computer and the debugger works there as well. Salem I will follow your advice and just try get createQ and destroyQ done first.

    Damn I guess my type of commenting sucks, I see why you guys say it's ugly, those comments are blurring me as well. I'll start writing STL style comments now.

    Thanks alot, I wish you can keep to this thread and suggest ways I can improve though, don't worry about the harsh tone, as long it's good advice, I don't mind. Thank you.

    ~Frost
    Attached Files Attached Files
    Last edited by Frost Drake; 10-15-2006 at 10:52 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. heap
    By George2 in forum Windows Programming
    Replies: 2
    Last Post: 11-10-2007, 10:49 PM
  2. Suggestions on this C style code
    By Joelito in forum C Programming
    Replies: 11
    Last Post: 06-07-2007, 03:22 AM
  3. Do you know...
    By davejigsaw in forum C++ Programming
    Replies: 1
    Last Post: 05-10-2005, 10:33 AM
  4. heap question
    By mackol in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 04:03 AM
  5. heap memory management
    By jdinger in forum C++ Programming
    Replies: 4
    Last Post: 04-27-2002, 10:23 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21