Title: C code for Circular Buffer (Queue) is required
Post by: yasir9909 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
Title: Re: C code for Circular Buffer (Queue) is required
Post by: oldvan 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.
Title: Re: C code for Circular Buffer (Queue) is required
Post by: cncbasher 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
Title: Re: C code for Circular Buffer (Queue) is required
Post by: yasir9909 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(); }
Title: Re: C code for Circular Buffer (Queue) is required
Post by: yasir9909 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: #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()*/
Title: Re: C code for Circular Buffer (Queue) is required
Post by: yasir9909 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
Title: Re: C code for Circular Buffer (Queue) is required
Post by: yasir9909 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 /* * 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
Title: Re: C code for Circular Buffer (Queue) is required
Post by: chyun3 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
|