Queue implementation in C

This is a discussion on Queue implementation in C within the C Programming forums, part of the General Programming Boards category; HI There, I've written a fifo implementation in C featuring two functions, one is push() and one is pop() to ...

  1. #1
    Registered User
    Join Date
    Dec 2009
    Posts
    37

    Queue implementation in C

    HI There,

    I've written a fifo implementation in C featuring two functions, one is push() and one is pop() to queue up strings i.e. character arrays. The push function would just push the new element onto the end of an array whereas the pop function would always get the element at [0] and shift the whole content one element "down".
    My problem now is that i'm not 100% sure about how i can pop elements off without having a memory leak. My two functions look like this:

    Code:
    int push(char ***list, char *str, int curlen){
    
      char **temp;
      int i=0;
    
      temp = realloc((*list),(curlen+1)*sizeof(*list));
      if (temp==NULL){
        printf("push(): Error reallocating memory for msglist\n");
        for (i=curlen;i>=0;i--) {
          free((*list)[i]);
          QLen--;
        }
        free(list);
        return -1;
      }
      (*list)=temp;
      (*list)[curlen]=malloc (strlen(str)+1);
      strcpy((*list)[curlen],str);
    
      return ++curlen;
    }
    //-------------------------------------------------------
    int pop (char **list, char *outstr, int curlen)
    {
      int j=0;
      char **temp=NULL;
      if (curlen==0) {
        printf("pop(): No element left in list\n");
        outstr="";
        return 0;
      }
    
      strcpy(outstr, list[0]);
    //  temp = realloc(temp,(curlen-1)*sizeof(*list));
      for (j=1; j<curlen; j++){
        temp = realloc(list,(curlen)*sizeof(*list));
        if (temp==NULL){
          printf("pop(): Error reallocating temp memory for msglist\n");
          for (curlen=curlen;curlen>=0;curlen--)
            free(temp[curlen]);
          free(temp);
          return -1;
        }
        temp[j-1]=malloc (strlen(list[j])+1);
        temp[j-1] = list[j];
      }
      //free(list[curlen-1]);
      list=temp;
      /*for(j=curlen-1;j>=0;j++)
        free(temp[j]);*/
      return curlen-1;
    }

  2. #2
    Registered User
    Join Date
    Dec 2009
    Posts
    37
    Quote Originally Posted by cerr View Post
    HI There,

    I've written a fifo implementation in C featuring two functions, one is push() and one is pop() to queue up strings i.e. character arrays. The push function would just push the new element onto the end of an array whereas the pop function would always get the element at [0] and shift the whole content one element "down".
    My problem now is that i'm not 100% sure about how i can pop elements off without having a memory leak. My two functions look like this:

    Code:
    int push(char ***list, char *str, int curlen){
    
      char **temp;
      int i=0;
    
      temp = realloc((*list),(curlen+1)*sizeof(*list));
      if (temp==NULL){
        printf("push(): Error reallocating memory for msglist\n");
        for (i=curlen;i>=0;i--) {
          free((*list)[i]);
          QLen--;
        }
        free(list);
        return -1;
      }
      (*list)=temp;
      (*list)[curlen]=malloc (strlen(str)+1);
      strcpy((*list)[curlen],str);
    
      return ++curlen;
    }
    //-------------------------------------------------------
    int pop (char **list, char *outstr, int curlen)
    {
      int j=0;
      char **temp=NULL;
      if (curlen==0) {
        printf("pop(): No element left in list\n");
        outstr="";
        return 0;
      }
    
      strcpy(outstr, list[0]);
    //  temp = realloc(temp,(curlen-1)*sizeof(*list));
      for (j=1; j<curlen; j++){
        temp = realloc(list,(curlen)*sizeof(*list));
        if (temp==NULL){
          printf("pop(): Error reallocating temp memory for msglist\n");
          for (curlen=curlen;curlen>=0;curlen--)
            free(temp[curlen]);
          free(temp);
          return -1;
        }
        temp[j-1]=malloc (strlen(list[j])+1);
        temp[j-1] = list[j];
      }
      //free(list[curlen-1]);
      list=temp;
      /*for(j=curlen-1;j>=0;j++)
        free(temp[j]);*/
      return curlen-1;
    }
    Something else i'm trying for the pop() function is this:
    Code:
      int i=0;
      
      char **temp;
      printf("DEBUG:list[0]: %s\n",list[0]);
      strcpy(outstr, list[0]);
      temp=malloc((curlen-1)*sizeof(*list));
      
      for (i=1;i<curlen;i++){
        temp[i-1]=malloc (strlen(list[i])+1);
        strcpy(temp[i-1],list[i]);
      }
      memcpy(list,temp,(curlen-1)*sizeof(*list));
      for (i=0;i<curlen-1;i++)
        free (temp[i]);
      free(temp);
    but it doesn't quite seem to work that well yet...

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Code:
    outstr="";
    That won't do what you think it does. It just makes outstr point to the string literal "". You probably want outstr[0] = 0; instead.

    I'm not entirely sure what your question is, but I think I can answer it in a roundabout way. Memory allocation is expensive. Usually, when you're maintaining a vector or a dynamic array or anything similar (like a queue) that uses realloc(), you maintain two sizes: one is how much space you have allocated, and the other is how much space you're using out of that allocated space. Typically you'll allocate a small amount of space to start with, and when you run out, you'll double the size of the array. (When shrinking, you'll halve the size of the array when it becomes less than one-quarter full.) It can be proven that the amortized time of such an algorithm is constant.

    Anyway, you probably don't need to worry about this, because in popping you're shifting every element over and throwing performance out the window anyway.

    I'm not sure what your pop() is trying to do. You can't free some blocks of memory from the beginning of the list. You'd have to shift every element down one, and then free the memory for the last element.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    In regards to your second post: what's wrong with this?
    Code:
    /** Pops an element from the queue given by @a list and @a size.
        
        @return The popped string, or NULL upon error (such as there being an
            empty stack). The caller should free this string with free().
    */
    char *pop(char ***list, int *size) {
        if(!*size) return 0;
        
        char *first = (*list)[0];
        
        memmove(*list, *list + 1, (*size) * sizeof(**list));
        (*size) --;
        (*list) = realloc(*list, (*size) * sizeof(**list));
        
        return first;
    }
    Well, okay, I know what's wrong with it -- it's using triple pointers! Ugh. But I think that's about the simplest way to do it. You see, just like in the last thread you need *** pointers if you're going to update your ** list.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Registered User
    Join Date
    Dec 2009
    Posts
    37
    Quote Originally Posted by dwks View Post
    Code:
    outstr="";
    That won't do what you think it does. It just makes outstr point to the string literal "". You probably want outstr[0] = 0; instead.

    I'm not entirely sure what your question is, but I think I can answer it in a roundabout way. Memory allocation is expensive. Usually, when you're maintaining a vector or a dynamic array or anything similar (like a queue) that uses realloc(), you maintain two sizes: one is how much space you have allocated, and the other is how much space you're using out of that allocated space. Typically you'll allocate a small amount of space to start with, and when you run out, you'll double the size of the array. (When shrinking, you'll halve the size of the array when it becomes less than one-quarter full.) It can be proven that the amortized time of such an algorithm is constant.

    Anyway, you probably don't need to worry about this, because in popping you're shifting every element over and throwing performance out the window anyway.

    I'm not sure what your pop() is trying to do. You can't free some blocks of memory from the beginning of the list. You'd have to shift every element down one, and then free the memory for the last element.
    But then i always have allocated space that stays unused, right?

    I just tried another approach now:
    Code:
      int i=0;
      
      strcpy(outstr, (*list)[0]);  
      for(i=1; i<curlen;i++){
        realloc((*list)[i-1],strlen((*list)[i])+1);
        strcpy((*list)[i-1],(*list)[i]);
      }
      free((*list)[curlen-1]);
      if (curlen==0);
        free((*list));
    But i'm still running into seg faults...
    so now anyhow, if i did try your version,i started with int alloc=2 an then when
    Code:
    if (curlen==alloc) {
    realloc((*list),(alloc*2)*sizeof(*list));
    (*list)[curlen]=malloc (strlen(str)+1);
    strcpy((*list)[curlen],str);
    return ++curlen;
    } else {
    (*list)[curlen]=malloc (strlen(str)+1);
    strcpy((*list)[curlen],str);
    return ++curlen;
    }

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    But then i always have allocated space that stays unused, right?
    Yes -- but that's usually preferable to spending a *long* time by calling realloc() all the time. Seriously -- it's a standard thing to do. For example, C++'s std::vector<> follows this paradigm, having a notion of an allocated size and a used size (which you can manipulate independently, if you're really keen on it).

    Remember that you have a list of pointers to allocated strings. So you can just shift the pointers downwards, no strcpy()'ing required.

    As for the segfaults: that might be because of this extra semicolon.
    Code:
      if (curlen==0);
        free((*list));
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Dec 2009
    Posts
    37
    Quote Originally Posted by dwks View Post
    In regards to your second post: what's wrong with this?
    Code:
    /** Pops an element from the queue given by @a list and @a size.
        
        @return The popped string, or NULL upon error (such as there being an
            empty stack). The caller should free this string with free().
    */
    char *pop(char ***list, int *size) {
        if(!*size) return 0;
        
        char *first = (*list)[0];
        
        memmove(*list, *list + 1, (*size) * sizeof(**list));
        (*size) --;
        (*list) = realloc(*list, (*size) * sizeof(**list));
        
        return first;
    }
    Well, okay, I know what's wrong with it -- it's using triple pointers! Ugh. But I think that's about the simplest way to do it. You see, just like in the last thread you need *** pointers if you're going to update your ** list.
    This one is great! Thanks a lot!

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    There's no reason that a pop of an item from a queue of 10000 items should take ten times longer than a pop of an item from a queue of 1000 items.

    "Schlemiel the painter" is hiding just around the corner.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Dec 2009
    Posts
    37
    Quote Originally Posted by iMalc View Post
    There's no reason that a pop of an item from a queue of 10000 items should take ten times longer than a pop of an item from a queue of 1000 items.

    "Schlemiel the painter" is hiding just around the corner.
    I don't see how this would apply to following code:
    Code:
    char *pop(char ***list, int *size) {
        if(!*size) return 0;
        
        char *first = (*list)[0];
        
        memmove(*list, *list + 1, (*size) * sizeof(**list));
        (*size) --;
        (*list) = realloc(*list, (*size) * sizeof(**list));
        
        return first;
    }

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by cerr View Post
    I don't see how this would apply to following code:
    Code:
    char *pop(char ***list, int *size) {
        if(!*size) return 0;
        
        char *first = (*list)[0];
        
        memmove(*list, *list + 1, (*size) * sizeof(**list));
        (*size) --;
        (*list) = realloc(*list, (*size) * sizeof(**list));
        
        return first;
    }
    Think: How long does a memmove take, relative to the number of items it has to move?
    Why it takes an amount of time proportional to the number of items to move of course! (This is terrible performance-wise)

    Now, If you wish to pop all items off one at a time in a loop, how long will it take?
    That's where the reference to Schlemiel comes from, though in this case he's starting from the furthest point from the paint can.

    You should take more of a circular-buffer type of approach (or other such technique) if you want to actually have any kind of reasonable performance from this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Dec 2009
    Posts
    37
    Quote Originally Posted by iMalc View Post
    You should take more of a circular-buffer type of approach (or other such technique) if you want to actually have any kind of reasonable performance from this.
    Well the performance isn't actually a big issue here as the string gets sent to a central server after the pop and then i'm waiting for an acknowledge before popping the next one off.
    But another question if i have following:
    Code:
    char *popstr;
    char *sendstr[BUFF_SZ];
    popstr=pop(&list, &size);
    strncpy(sendstr, popstr, BUFF_SZ);
    do i need to make a free(popstr); after the srncpy in order to clean up the memory (assuming i'm using above pop function)?

    Thanks

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by cerr View Post
    Well the performance isn't actually a big issue here as the string gets sent to a central server after the pop and then i'm waiting for an acknowledge before popping the next one off.
    But another question if i have following:
    Code:
    char *popstr;
    char *sendstr[BUFF_SZ];
    popstr=pop(&list, &size);
    strncpy(sendstr, popstr, BUFF_SZ);
    do i need to make a free(popstr); after the srncpy in order to clean up the memory (assuming i'm using above pop function)?
    That doesn't make it a total non-issue. Sure the network traffic take a long time but it's a fixed (amortized) amount of time. The pop however will only take less time up to a point. If you get enough items in there then it will eventually take much more time than the network traffic does.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Registered User
    Join Date
    Dec 2009
    Posts
    37
    Quote Originally Posted by iMalc View Post
    That doesn't make it a total non-issue. Sure the network traffic take a long time but it's a fixed (amortized) amount of time. The pop however will only take less time up to a point. If you get enough items in there then it will eventually take much more time than the network traffic does.
    Yup but there's "never" supposed to be more than 1 or 2 elements in this queue because there's always a parallel "popping thread" running...
    I'm more interested in if free(popstr); in above's example would clean up things properly...?

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by cerr View Post
    Yup but there's "never" supposed to be more than 1 or 2 elements in this queue because there's always a parallel "popping thread" running...
    I'm more interested in if free(popstr); in above's example would clean up things properly...?
    OH! In that case it's certainly not an issue. It does beg the question of who not just leave the buffer alone once it's big enough.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 02:55 AM
  3. Queue implementation
    By kolliash in forum C Programming
    Replies: 1
    Last Post: 06-01-2008, 08:25 AM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM

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