Sonsivri
 
*
Welcome, Guest. Please login or register.
Did you miss your activation email?
March 29, 2024, 03:46:48 15:46


Login with username, password and session length


Pages: [1]
Print
Author Topic: C code for Circular Buffer (Queue) is required  (Read 19487 times)
0 Members and 1 Guest are viewing this topic.
yasir9909
Active Member
***
Offline Offline

Posts: 153

Thank You
-Given: 7
-Receive: 107


« on: November 11, 2009, 07:36:33 07:36 »

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
Logged

regards
m.yasir
oldvan
Senior Member
****
Offline Offline

Posts: 372

Thank You
-Given: 154
-Receive: 107


If the van is a Rockin'...


WWW
« Reply #1 on: November 11, 2009, 08:52:36 08:52 »

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.
« Last Edit: November 11, 2009, 08:58:09 08:58 by oldvan » Logged

Give a man a fish and you feed him for a day.
Teach a man to fish and he will sit around in a boat drinking beer all day.
cncbasher
Junior Member
**
Offline Offline

Posts: 91

Thank You
-Given: 107
-Receive: 51


« Reply #2 on: November 11, 2009, 09:12:16 09:12 »

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

 http://frank.circleofcurrent.com/cache/gps_logger.htm
Logged
yasir9909
Active Member
***
Offline Offline

Posts: 153

Thank You
-Given: 7
-Receive: 107


« Reply #3 on: November 12, 2009, 07:31:28 19:31 »

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();
}
Logged

regards
m.yasir
yasir9909
Active Member
***
Offline Offline

Posts: 153

Thank You
-Given: 7
-Receive: 107


« Reply #4 on: November 16, 2009, 10:54:26 10:54 »

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()*/

« Last Edit: November 16, 2009, 10:57:08 10:57 by yasir9909 » Logged

regards
m.yasir
yasir9909
Active Member
***
Offline Offline

Posts: 153

Thank You
-Given: 7
-Receive: 107


« Reply #5 on: November 17, 2009, 11:08:56 11:08 »

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
« Last Edit: November 17, 2009, 11:13:40 11:13 by yasir9909 » Logged

regards
m.yasir
yasir9909
Active Member
***
Offline Offline

Posts: 153

Thank You
-Given: 7
-Receive: 107


« Reply #6 on: November 24, 2009, 10:13:27 10:13 »

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
Logged

regards
m.yasir
chyun3
Junior Member
**
Offline Offline

Posts: 65

Thank You
-Given: 43
-Receive: 6


« Reply #7 on: December 01, 2009, 10:16:56 10:16 »

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
Logged
Pages: [1]
Print
Jump to:  


DISCLAIMER
WE DONT HOST ANY ILLEGAL FILES ON THE SERVER
USE CONTACT US TO REPORT ILLEGAL FILES
ADMINISTRATORS CANNOT BE HELD RESPONSIBLE FOR USERS POSTS AND LINKS

... Copyright 2003-2999 Sonsivri.to ...
Powered by SMF 1.1.18 | SMF © 2006-2009, Simple Machines LLC | HarzeM Dilber MC