C code for Circular Buffer (Queue) is required

[yasir9909]

I want to do data logging for GPS data in serial memory AT24C512 for this purpose,i need to make a circular buffer in serial memory.

Could some body please post the code and algorithm for real-time circular buffer so that data may be stored in circular buffer and may be  read or retrieved at will.

Data need to be continuously stored over circular queue while data is retrieved from queue only on demand

regards
m.yasir

[oldvan]

GOOGLE makes an awesome first resource for such needs.

http://www.google.com/search?q=circular+buffer+example+c

In the list I found this:
http://en.wikipedia.org/wiki/Circular_buffer
Which includes source code and a thorough explanation.

[cncbasher]

also , see the gps logger application here also uses circular buffer techniques

 http://frank.circleofcurrent.com/cache/gps_logger.htm

[yasir9909]

I have got this basic skeleton code for circular buffer that i got from some other community in response to my query,i would like to share this code may be it could be helpful for others like me who need such type of code,also i am posting it here for review by those who deem themselves to be good at coding and algorithm development:

#define BUFFER_SIZE 64
uint8_t buffer[BUFFER_SIZE];
uint8_t buffer_head = 0, buffer_tail = 0;

void put_in_buffer( uint8_t data )
{
buffer[buffer_head] = data;
if( ++buffer_head >= BUFFER_SIZE )
buffer_head = 0;
}

uint8_t available_buffer( void )
{
// This is the hardest part,
// calculating the size of data in buffer.
return( (buffer_head - buffer_tail ) % BUFFER_SIZE );
}

uint8_t get_from_buffer( void )
{
uint8_t data;

data = buffer[buffer_tail];
if( ++buffer_tail >= BUFFER_SIZE )
buffer_tail = 0;

return data;
}

main()
{
uint8_t c;

put_in_buffer( 10 );

// don't read from buffer unless it has data
if( available_in_buffer() )
c = get_from_buffer();
}

[yasir9909]

here is complete working C code for Circular Buffer...

I have got this code from a book of data structures in C.I would like to share this code with this community so that others like me who need this code may take advantage from it:

Code:

#include<conio.h>
#include<process.h>

#define MAX 50

int cqueue_arr[MAX];
int front=-1,rear=-1;
//***Function Prototypes***//
void insert();
void del();
void display();
//************************//

//Function to insert an element to the circular queue
void insert()
{
     int added_item;
     //Checking for overflow condition
     if ((front == 0 && rear == MAX-1) || (front == rear +1))
     {

		//cout<<"\nQueue Overflow \n";
		printf("\nQueue Overflow\n");
		getch();
		return;
     }
     if (front == -1) /*If queue is empty */
     {
		front = 0;
		rear = 0;
     }
     else
     if (rear == MAX-1)/*rear is at last position of queue */
	rear = 0;
     else
	rear = rear + 1;
     //cout<<"\nInput the element for insertion in queue:";
     printf("\nInput the element for insertion in queue:");
     //cin>>added_item;
     scanf("%d",&added_item);
     cqueue_arr[rear] = added_item;
}/*End of insert()*/

//This function will delete an element from the queue
void del()
{
     //Checking for queue underflow
     if (front == -1)
     {
	//cout<<"\nQueue Underflow\n";
	printf("\nQueue Underflow\n");
	return;
     }
     //cout<<"\nElement deleted from queue is:"<<cqueue_arr[front]<<"\n";
     printf("\nElement deleted from queue is:%d",cqueue_arr[front]);
     if (front == rear) /* queue has only one element */
     {
	front = -1;
	rear = -1;
     }
     else
     if(front == MAX-1)
	      front = 0;
     else
	      front = front + 1;
}/*End of del()*/
//Function to display the elements in the queue
void display()
{
     int front_pos = front,rear_pos = rear;
     //Checking whether the circular queue is empty or not
     if (front == -1)
     {
	//cout<<"\nQueue is empty\n";
	printf("\nQueue is empty\n");
	return;
     }
     //Displaying the queue elements
     //cout<<"\nQueue elements:\n";
     printf("\nQueue elements:\n");
     if(front_pos <= rear_pos )
     while(front_pos <= rear_pos)
     {
		     //cout<<cqueue_arr[front_pos]<<", ";
		     printf("%d",cqueue_arr[front_pos]);
		     printf(",");
		     front_pos++;
     }
     else
     {
	 while(front_pos <= MAX-1)
	 {
			 //cout<<cqueue_arr[front_pos]<<", ";
			 printf("%d",cqueue_arr[front_pos]);
			 printf(",");
			 front_pos++;
	 }
	 front_pos = 0;
	 while(front_pos <= rear_pos)
	 {
			 //cout<<cqueue_arr[front_pos]<<", ";
			 printf("%d",cqueue_arr[front_pos]);
			 printf(",");
			 front_pos++;
	 }
     }/*End of else*/
     //cout<<"\n";
     printf("\n");
}/*End of display() */
void main()
{
     int choice;
     //Creating the objects for the class
     //circular_queue co;
     while(1)
     {
	     clrscr();
	     //Menu options
	     //cout <<"\n1.Insert\n";
	     printf("\n1.Insert\n");
	     //cout <<"2.Delete\n";
	     printf("2.Delete\n");
	     //cout <<"3.Display\n";
	     printf("3.Display\n");
	     //cout <<"4.Quit\n";
	     printf("4.Quit\n");
	     //cout <<"\nEnter your choice: ";
	     printf("\nEnter your choice: ");
	     //cin>>choice;
	     scanf("%d",&choice);
	     switch(choice)
	     {
		    case 1:
			insert();
		    break;
		    case 2 :
			del();
			getch();
		    break;
		    case 3:
			display();
			getch();
		    break;
		    case 4:
			exit(1);
		    default:
		    //cout<<"\nWrong choice\n";
			printf("\nWrong choice\n");
			getch();
	      }/*End of switch*/
       }/*End of while*/
}/*End of main()*/

[yasir9909]

Th algorithms for above mentioned C code for Circular Buffer is:


ALGORITHMS

Let Q be the array of some specified size say SIZE. FRONT and REAR are two pointers
where the elements are deleted and inserted at two ends of the circular queue. DATA is
the element to be inserted.

Inserting an element to circular Queue

1. Initialize FRONT = – 1; REAR = 1
2. REAR = (REAR + 1) % SIZE
3. If (FRONT is equal to REAR)
(a) Display “Queue is full�
(b) Exit
4. Else
(a) Input the value to be inserted and assign to variable “DATA�
5. If (FRONT is equal to – 1)
(a) FRONT = 0
(b) REAR = 0
6. Q[REAR] = DATA
7. Repeat steps 2 to 5 if we want to insert more elements
8. Exit

Deleting an element from a circular queue

1. If (FRONT is equal to – 1)
(a) Display “Queue is empty�
(b) Exit
2. Else
(a) DATA = Q[FRONT]
3. If (REAR is equal to FRONT)
(a) FRONT = –1
(b) REAR = –1
4. Else
(a) FRONT = (FRONT +1) % SIZE
5. Repeat the steps 1, 2 and 3 if we want to delete more elements
6. Exit

[yasir9909]

Here is the PIC18F4520 based implementation (in mikroC for PIC) of the Circular Que for the C code posted previously

Code:

  /*
 * Project name:
     CircularQ (Simple implementation of a Circular Queue for PIC18F4520)
 * Copyright:
     m.yasir
 * Description:
     This code demonstrates how to use implement a circular queue on PIC MCU.
     
 * Test configuration:
     MCU:             P18F4520
     Oscillator:      HS, 08.0000 MHz
     Ext. Modules:    -
     SW:              mikroC v8.0
 * NOTES:
     None.
*/

#define MAX 50

unsigned short data = 0,temp=0;
unsigned short recOK;
unsigned int j=0;
unsigned short i;

unsigned char msg01[]="This is a test code for implementation of circular queue\n\r";

unsigned char msg02[]="\nQueue Overflow\n";
unsigned char msg03[]="\nInput the element for insertion in queue:";
unsigned char msg04[]="\nQueue Underflow\n";
unsigned char msg05[]="\nElement deleted from queue is:";
unsigned char msg06[]="\nQueue is empty\n";
unsigned char msg07[]="\nQueue elements:\n";
unsigned char msg08[]="\n1.Insert\n";
unsigned char msg09[]="\n2.Delete\n";
unsigned char msg10[]="\n3.Display\n";
unsigned char msg11[]="\n4.Quit\n";
unsigned char msg12[]="\nEnter your choice: ";//
unsigned char msg13[]="\nWrong choice\n";

int cqueue_arr[MAX];
int front=-1,rear=-1;

//***Function Prototypes***//
void insert();
void del();
void display();
//*************************//

//Function to insert an element to the circular queue
void insert()
{
     //int added_item;
     
     unsigned char added_item;;

     //Checking for overflow condition
     if ((front == 0 && rear == MAX-1) || (front == rear +1))
     {

		      //printf("\nQueue Overflow\n");
          for(j=0;j<sizeof(msg02);j++)
          USART_Write(msg02[j]);                    // send data via USART

		      //getch();
		      while( !(USART_Data_Ready()) );
		      temp = USART_Read();                  // read the received data
		
		      return;
     }
     if (front == -1) /*If queue is empty */
     {
		     front = 0;
		     rear = 0;
     }
     else
     if (rear == MAX-1)/*rear is at last position of queue */
	       rear = 0;
     else
	       rear = rear + 1;

      USART_Write(13);
     //printf("\nInput the element for insertion in queue:");
     for(j=0;j<sizeof(msg03);j++)
     USART_Write(msg03[j]);                     // send data via USART

     //scanf("%d",&added_item);
     while(!( USART_Data_Ready() ));             // wait till data is received
     added_item = USART_Read();                  // read the received data
     cqueue_arr[rear] = added_item;
     USART_Write(added_item);                    // send data via USART
     
     USART_Write(13);
     
}/*End of insert()*/

//This function will delete an element from the queue
void del()
{
     //Checking for queue underflow
     if (front == -1)
     {
         //printf("\nQueue Underflow\n");
	       for(j=0;j<sizeof(msg04);j++)
         USART_Write(msg04[j]);                   // send data via USART
	       return;
     }

     //printf("\nElement deleted from queue is:%d",cqueue_arr[front]);
     for(j=0;j<sizeof(msg05);j++)
     USART_Write(msg05[j]);                    // send data via USART
     

     USART_Write(cqueue_arr[front]);           // send data via USART
     
     if (front == rear) /* queue has only one element */
     {
	       front = -1;
	       rear = -1;
     }
     else
     if(front == MAX-1)
	      front = 0;
     else
	      front = front + 1;
}/*End of del()*/

//Function to display the elements in the queue
void display()
{
     int front_pos = front,rear_pos = rear;
     //Checking whether the circular queue is empty or not
     if (front == -1)
     {

	   //printf("\nQueue is empty\n");
	   for(j=0;j<sizeof(msg06);j++)
     USART_Write(msg06[j]);                    // send data via USART
  
	return;
     }
     //Displaying the queue elements
     //printf("\nQueue elements:\n");
     for(j=0;j<sizeof(msg07);j++)
     USART_Write(msg07[j]);                    // send data via USART

     if(front_pos <= rear_pos )
     while(front_pos <= rear_pos)
     {

		     //printf("%d",cqueue_arr[front_pos]);
		     USART_Write(cqueue_arr[front_pos]);                    // send data via USART
		     //printf(",");
		     USART_Write(',');                    // send data via USART
		     front_pos++;
     }
     else
     {
	 while(front_pos <= MAX-1)
	 {

			 //printf("%d",cqueue_arr[front_pos]);
       USART_Write(cqueue_arr[front_pos]);                    // send data via USART
       //printf(",");
			 USART_Write(',');                    // send data via USART
			 front_pos++;
	 }
	 front_pos = 0;
	 while(front_pos <= rear_pos)
	 {

			 //printf("%d",cqueue_arr[front_pos]);
       USART_Write(cqueue_arr[front_pos]);                    // send data via USART
       //printf(",");
       USART_Write(',');                    // send data via USART
       front_pos++;
	 }
     }/*End of else*/
     //cout<<"\n";
     //printf("\n");
     USART_Write(13);                    // send data via USART
}/*End of display() */


void main()
{

     //int choice;
     unsigned char choice;

     USART_init(57600);                     // initialize USART module

     for(j=0;j<sizeof(msg01);j++)
     USART_Write(msg01[j]);                                       // (8 bit, 19200 baud rate, no parity bit...)

     while (1) {

                  ////Menu options
                  //printf("\n1.Insert\n");
                  for(j=0;j<sizeof(msg08);j++)
                  USART_Write(msg08[j]);              // send data via USART
                  
                  USART_Write(13);                    // send CR via USART


	                //printf("2.Delete\n");
	                for(j=0;j<sizeof(msg09);j++)
                  USART_Write(msg09[j]);              // send data via USART

                  USART_Write(13);                    // send CR via USART


	                //printf("3.Display\n");
	                for(j=0;j<sizeof(msg10);j++)
                  USART_Write(msg10[j]);              // send data via USART

                  USART_Write(13);                    // send CR via USART
                  

	                //printf("4.Quit\n");
	                for(j=0;j<sizeof(msg11);j++)
                  USART_Write(msg11[j]);              // send data via USART

                  USART_Write(13);                    // send CR via USART


	                //printf("\nEnter your choice: ");
	                for(j=0;j<sizeof(msg12);j++)
                  USART_Write(msg12[j]);              // send data via USART

                  USART_Write(13);                    // send CR via USART


	                //scanf("%d",&choice);

	                while(!( USART_Data_Ready() ));     // wait till data is received
                  choice = USART_Read();              // read the received data

                  USART_Write(13);                    // send data via USART
	                switch(choice)
	                {
		                     case '1':
			                        insert();
		                     break;
		                     case '2' :
			                        del();
			                        //getch();
			                        while(!( USART_Data_Ready() ));       // wait till data is received
                              temp = USART_Read();                  // read the received data
		                     break;
		                     case '3':
			                        display();
			                        //getch();
			                        while(!( USART_Data_Ready() ));       // wait till data is received
                              temp = USART_Read();                  // read the received data
		                     break;
		                     case '4':
			                        //exit(1);
			                        break;
		                     default:

			                   //printf("\nWrong choice\n");
                         for(j=0;j<sizeof(msg13);j++)
                         USART_Write(msg13[j]);                    // send data via USART

                         //getch();
                         while(!( USART_Data_Ready() ));           // wait till data is received
                         temp = USART_Read();                      // read the received data

	                }/*End of switch*/
                  /*
                  if (USART_Data_Ready()) {         // if data is received
                  i = USART_Read();                 // read the received data
                  USART_Write(i);                   // send data via USART
                  */
                  /*
                  while(!( USART_Data_Ready() ));    // wait till data is received
                  i = USART_Read();                  // read the received data
                  USART_Write(i);                    // send data via USART
                  */
               } // end of main while loop

}//~!

The circuit schematic is also attached with this post.


I would post the version developed for GPS later,so that others may utilize this code if they need some help on circular queue

[chyun3]

Maybe you can refer to the AVR application notes:

AVR101: High Endurance EEPROM Storage
http://www.atmel.com/dyn/resources/prod_documents/doc2526.pdf

AVR104: Buffered Interrupt Controlled EEPROM Writes
http://www.atmel.com/dyn/resources/prod_documents/doc2540.pdf

Thanks
Chyun3