3/11/08

Round FIFO queue in C

An implementation of a round FIFO queue in C. In this example it is used to store strings but can actually be used to store any type of data. User set the size and then inserts or deletes strings from the queue. You can imagine it to be something like this picture where the table is shown and in and out are two pointer . An integer (avl) counts how many cells are used. Red color means that there is data in their and white means that is empty. in points to the next empty cell and out to the next element to be removed. Every cell in a pointer to void (void*) which means that anything can be stored in there (except food, clothes... :-P)Anyway i hope you understood this image because it will be helpful to understand the source code below.

#include <stdio.h>

int N,in,out,avl;
void **table;

/*init queue*/
void fifoinit (int size) {
avl=0; in=0;out=0;
N=size;
table=(void**)malloc(N*sizeof(void*));
}
/*free memmory*/
void fifodestroy() {
int i;
if(!fifoempty()) free(table);
else{
for(i=out;i<in;i++){
free(table[i]);
}
free(table);
}
}
/* empty queue = 1 else 0*/
int fifoempty() {
return(avl==0);
}

/*insert element*/
int fifoenter(void *next) {
if(avl==N) {return(0);}
else {
table[in]=next;
avl++;
in=(in+1)%N;
return(1);
}
}

/*return next element*/
void* fifoget(){
void* get;
if (avl>0) {
get=table[out];
out=(out+1)%N;
avl--;
return(get);
}
}

int main(int argc,char* argv[]) {
int y;
char *p,str[64];
printf(" Give an integer for size: ");
scanf("%d",y);
fifoinit(y); /*init fifo*/

do{
putchar('\n');
printf(" 0: Exit\n");
printf(" 1: Insert string\n");
printf(" 2: Print next string\n");
printf(" Choose one of the above options: ");
scanf("%d",&y);
switch (y) {
case 1 : {
printf(" Insert elements\n\n");
printf(" Give string ");
scanf("%s",str);
p=strdup(str);
if (!(fifoenter((void*) p))) {
free(p);
printf(" Table is full\n");
}
else { printf(" Insert successful\n"); }
break;
}
case 2 : {
printf(" Print next string : ");
if(fifoempty()) {
printf("No string in table\n");
}
else {
p=(char*)fifoget();
printf("%s\n",p);
free(p);
}
break;
}
}
}
while(y!=0);
fifodestroy();
exit(0);
}

4 comments:

Anonymous said...

Thanks - useful stuff. Bert

Jonnie said...

Nice idea. Thanks.

Although there are a few problems here:
a) L54: should be "&y" i.e. "scanf("%d",&y);"
b) fifodestroy() has a memory leak - it doesn't always free all table elements. Specifically L17 "for(i=out;i<in;i++)" does not address the possibility of in<out.

Cheers
Jonnie

Andreas Papadopoulos said...

Thank you very much Jonnie. You are absolutely right! :-)

for(i=out;i<in;i++){
free(table[i]);
}

should be
for(i=0;i<avl;i++){
free(table[(out+i)%N]);
}

Jonnie said...

Hi Andreas

Elegant fix. Thanks.

fyi I stumbled across your examples in my attempt to learn a bit more about threads/semaphores etc in a posix environment. They've been very useful. Big thanks.