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

Originally Posted by cerr

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...

Originally Posted by dwks

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

Originally Posted by dwks

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!

Originally Posted by iMalc

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

Originally Posted by iMalc

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

Originally Posted by iMalc

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...?