环形缓冲区的实现

朱雀 2022-03-26 17:14 262阅读 0赞

http://blog.csdn.net/wanxiao009/article/details/5519514

环形缓冲区是嵌入式系统中十分重要的一种数据结构，比如在一个视频处理的机制中，环形缓冲区就可以理解为数据码流的通道，每一个通道都对应着一个环形缓冲区，这样数据在读取和写入的时候都可以在这个缓冲区里循环进行，程序员可以根据自己需要的数据大小来决定自己使用的缓冲区大小。

环形缓冲区，顾名思义这个缓冲区是环形的，那么何谓环形这个意思也很好理解，就是用一个指针去访问该缓冲区的最后一个内存位置的的后一位置时回到环形缓冲区的起点。类似一个环一样。这样形容就很好理解了，当然有办法实现了。我在这里采用了2种方式实现了环形缓冲区，一个是用数组的方法，一个是用链表的方法。

数组是一块连续的内存，所以顺序访问时只要根据下标的增加而增加，但是最后一个元素之后需要回到起始位置，这就需要我们对这个地方进行特殊处理。只要最后一个地址访问结束能顺利回到起始地址，这个缓冲区就可以实现。代码如下：

**\[cpp\]**  [view plain][] [copy][view plain] [print][view plain] [?][view plain]

1. /\* File name: ringbuf.c 
2.  \* Author   : wanxiao 
3.  \* Function :Implement a circular buffer,  
4.              you can read and write data in the buffer zone. 
5.  \*/  
6.   
7. \#include <stdio.h>     
8.     
9. \#define MAXSIZE 8     
10.     
11. int ringbuf\[MAXSIZE\];     
12. int readldx=0;  
13. int writeldx=0;  
14.   
15. int next\_data\_handle(int addr)     
16. \{     
17.     return (addr+1) == MAXSIZE ? 0:(addr+1) ;     
18. \}     
19.     
20. int write\_data(int data)  
21. \{  
22.     int i;  
23.     \*(ringbuf+writeldx) = data;  
24.     writeldx = next\_data\_handle(writeldx);  
25.     for(i=0;i<MAXSIZE;i++)  
26.     \{  
27.         printf("%4d",\*(ringbuf+i));  
28.         if(MAXSIZE-1 == i)  
29.             printf("/n");  
30.     \}  
31. \}  
32.   
33. int read\_data()  
34. \{  
35.     printf("read data is : %d/n",\*(ringbuf+readldx));  
36.     readldx = next\_data\_handle(readldx);  
37. \}  
38.     
39. int main(int argc , char \*\*argv)     
40. \{     
41.     int data;     
42.     char cmd;  
43.   
44.     do\{     
45.         printf("select:/nw/t--write/nr/t--read/nq/t--quit/n");     
46.         scanf("%s",&cmd);     
47.     
48.         switch(cmd)     
49.         \{     
50.             case 'w' :     
51.                 printf("please input data:");     
52.                 scanf("%d",&data);     
53.                 write\_data(data);     
54.                 break;     
55.             case 'r' :     
56.                 data = read\_data();     
57.                 break;     
58.             case 'q' :     
59.                 printf("quit/n");     
60.                 break;     
61.             default :     
62.                 printf("Command  error/n");     
63.         \}     
64.     \}while(cmd != 'q');     
65.     return 0;     
66. \}

链表实现，实际上就是一个单向循环链表。这个方法的优点是不需要最后一个元素进行特殊处理，但是实现起来比数组稍微麻烦一点，单思路还是很清晰简单的。代码如下：

**\[cpp\]**  [view plain][] [copy][view plain] [print][view plain] [?][view plain]

1. \#include <stdio.h>  
2. \#include <stdlib.h>  
3.   
4.   
5. typedef struct signal\_loop\_chain  
6. \{  
7.     int data;  
8.     struct signal\_loop\_chain \*next;  
9. \}NODE;  
10.   
11. NODE \*Create\_loop\_chain(int n)  
12. \{  
13.     int i;  
14.     NODE \*head , \*previous , \*current ;  
15.     previous = (NODE \*)malloc(sizeof(NODE));  
16.     if(previous == NULL)  
17.         exit(1);  
18.   
19.     previous->data =0;  
20.     previous->next = NULL;  
21.     head = previous ;  
22.   
23.     for(i=0 ; i<n ; i++)  
24.     \{  
25.         current = (NODE\*)malloc(sizeof(NODE));  
26.         if(current == NULL)  
27.             exit(1);  
28.   
29. //      scanf("%d",¤t->data);  
30.         current->next = head;  
31.         previous->next = current;  
32.         previous = current ;  
33.     \}  
34.     return head ;  
35. \}  
36.   
37. int Show(NODE \*head)  
38. \{  
39.     NODE \*current;  
40.     current = head->next ;  
41.     printf("List:/n");  
42.     while(current != head)  
43.     \{  
44.         printf("%4d",current->data);  
45.         current = current->next;  
46.     \}  
47.     printf("/n");  
48. \}  
49.   
50. int read\_buf(NODE \*head)  
51. \{  
52.     NODE \*current;  
53.     current = head->next;  
54.     while(1)  
55.     \{  
56.         printf("read number is %d/n",current->data);  
57.         current = current->next;  
58.         sleep(1);  
59.     \}  
60.   
61. \}  
62.   
63. int write\_buf(NODE \*head)  
64. \{  
65.     NODE \*current;  
66.     int i = 0;  
67.     current = head->next;  
68.     while(1)  
69.     \{  
70.         current->data = i++;  
71.         printf("write number is %d/n",current->data);  
72.         current = current->next;  
73.         sleep(1);  
74.     \}  
75. \}  
76.   
77. int main(int argc , char \*\*argv)  
78. \{  
79.     int num;  
80.     char cmd;  
81.     NODE \*head;  
82.     printf("please input node\_num /n");  
83.     scanf("%d",&num);  
84.     head = Create\_loop\_chain(num);  
85.     printf("The ringbuf was found/n");  
86.     Show(head);  
87.   
88.     while(1)\{  
89.         printf("please select r or w/n");  
90.         scanf("%c",&cmd);  
91.   
92.         if(cmd == 'r')\{  
93.             read\_buf(head);  
94.             Show(head);  
95.         \}  
96.           
97.         if(cmd == 'w')\{  
98.             write\_buf(head);  
99.             Show(head);  
100.         \}  
101.           
102.     \}  
103.     return 0;  
104. \}

以上都是针对单进程而言。对于系统，尤其是嵌入式Linux系统中，缓冲区的保护机制就变得尤为重要了，因为我们的数据时不停的在读写，内存不停的变化，如果牵扯到多任务（多进程，多线程），我们就需要加锁对其进行保护措施。这里我在链表的实现下加了信号量加以保护。

**\[c-sharp\]**  [view plain][] [copy][view plain] [print][view plain] [?][view plain]

1. \#include <stdio.h>  
2. \#include <stdlib.h>  
3. \#include <pthread.h>  
4. \#include <semaphore.h>  
5.   
6. sem\_t mutex;  
7.   
8. typedef **struct** signal\_loop\_chain  
9. \{  
10.     **int** data;  
11.     **struct** signal\_loop\_chain \*next;  
12. \}NODE;  
13.   
14. NODE \*Create\_loop\_chain(**int** n)  
15. \{  
16.     **int** i;  
17.     NODE \*head , \*previous , \*current ;  
18.     previous = (NODE \*)malloc(**sizeof**(NODE));  
19.     **if**(previous == NULL)  
20.         exit(1);  
21.   
22.     previous->data =0;  
23.     previous->next = NULL;  
24.     head = previous ;  
25.   
26.     **for**(i=0 ; i<n ; i++)  
27.     \{  
28.         current = (NODE\*)malloc(**sizeof**(NODE));  
29.         **if**(current == NULL)  
30.             exit(1);  
31.   
32.         current->next = head;  
33.         previous->next = current;  
34.         previous = current ;  
35.     \}  
36.     **return** head ;  
37. \}  
38.   
39. **int** Show(NODE \*head)  
40. \{  
41.     NODE \*current;  
42.     current = head->next ;  
43.     printf("List:/n");  
44.     **while**(current != head)  
45.     \{  
46.         printf("%4d",current->data);  
47.         current = current->next;  
48.     \}  
49.     printf("/n");  
50. \}  
51.   
52. **int** read\_buf(NODE \*head)  
53. \{  
54.     NODE \*current;  
55.     current = head->next;  
56.     **while**(1)  
57.     \{  
58.         sem\_wait(&mutex);  
59.         printf("read number is %d/n",current->data);  
60.         current = current->next;  
61.         sem\_post(&mutex);  
62.         sleep(2);  
63.     \}  
64.   
65. \}  
66.   
67. **int** write\_buf(NODE \*head)  
68. \{  
69.     NODE \*current;  
70.     **int** i = 0;  
71.     current = head->next;  
72.     **while**(1)  
73.     \{  
74.         sem\_wait(&mutex);  
75.         current->data = i++;  
76.         printf("write number is %d/n",current->data);  
77.         current = current->next;  
78.         sem\_post(&mutex);  
79.         sleep(1);  
80.     \}  
81. \}  
82.   
83. **int** main(**int** argc , **char** \*\*argv)  
84. \{  
85.     **int** num,ret;  
86.     **char** cmd;  
87.     NODE \*head;  
88.     pthread\_t id1,id2;  
89.   
90.     ret = sem\_init(&mutex ,0,1);  
91.     **if**(ret != 0)\{  
92.         perror("sem\_init error");  
93.     \}  
94.     printf("please input node\_num /n");  
95.     scanf("%d",&num);  
96.     head = Create\_loop\_chain(num);  
97.     printf("The ringbuf was found/n");  
98.     Show(head);  
99.   
100.     ret = pthread\_create(&id1,NULL,(**void** \*)write\_buf,head);  
101.     ret = pthread\_create(&id2,NULL,(**void** \*)read\_buf,head);  
102.   
103.     pthread\_join(id1,NULL);  
104.     pthread\_join(id2,NULL);  
105.       
106.   
107.     **return** 0;  
108. \}

http://hi.baidu.com/zkheartboy/blog/item/edee1ff74b543321720eecbc.html

环形缓冲区的实现代码

2007-11-15 23:10

<table style="table-layout:fixed; font-family:Arial; background-color:rgb(32,46,51); width:870px"> 
 <tbody> 
 <tr> 
 <td style="word-wrap:break-word; word-break:break-all; visibility:visible!important; zoom:1!important; font-size:12px; line-height:18px"> 
 <div style="word-wrap:break-word; word-break:break-all; visibility:visible!important; zoom:1!important; line-height:19px; overflow-x:hidden; overflow-y:hidden; position:relative!important; margin-top:0px; margin-right:30px; margin-bottom:0px; margin-left:30px"> 
 在通信程序中，经常使用环形缓冲区作为数据结构来存放通信中发送和接收的数据。环形缓冲区是一个先进先出的循环缓冲区，可以向通信程序提供对缓冲区的互斥访问。 
 1、环形缓冲区的实现原理 
 环 形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据，写指针指向环形缓冲区中可写的缓冲区。通过移动读指针和写指针就可以实现缓冲 区的数据读取和写人。在通常情况下，环形缓冲区的读用户仅仅会影响读指针，而写用户仅仅会影响写指针。如果仅仅有一个读用户和一个写用户，那么不需要添加 互斥保护机制就可以保证数据的正确性。如果有多个读写用户访问环形缓冲区，那么必须添加互斥保护机制来确保多个用户互斥访问环形缓冲区。 
 图1、图2和图3是一个环形缓冲区的运行示意图。图1是环形缓冲区的初始状态，可以看到读指针和写指针都指向第一个缓冲区处；图2是向环形缓冲区中添加了一个数据后的情况，可以看到写指针已经移动到数据块2的位置，而读指针没有移动；图3是环形缓冲区进行了读取和添加后的状态，可以看到环形缓冲区中已经添加了两个数据，已经读取了一个数据。 
 <a href="http://www.mcublog.com/blog/uploadfile/2006824204829368.jpg" style="color:rgb(99,219,245); text-decoration:none" rel="nofollow"><img width="540" height="400" src="http://www.mcublog.com/blog/uploadfile/2006824204829368.jpg" alt=""></a> 
 2、实例：环形缓冲区的实现 
 环形缓冲区是数据通信程序中使用最为广泛的数据结构之一，下面的代码，实现了一个环形缓冲区： 
 /*ringbuf .c*/ 
 ＃i nclude&lt;stdio. h&gt; 
 &nbsp;&nbsp;&nbsp;&nbsp;＃i nclude&lt;ctype. h&gt; 
 #define NMAX 8 
 int iput = 0; /*&nbsp;环形缓冲区的当前放人位置&nbsp;*/ 
 int iget = 0; /*&nbsp;缓冲区的当前取出位置&nbsp;*/ 
 int n = 0; /*&nbsp;环形缓冲区中的元素总数量&nbsp;*/ 
 double buffer[NMAX]; 
 /*&nbsp;环形缓冲区的地址编号计算函数，，如果到达唤醒缓冲区的尾部，将绕回到头部。 
 环形缓冲区的有效地址编号为：0到(NMAX-1) 
 */ 
 int addring (int i) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return (i+1) == NMAX ? 0 : i+1; 
 } 
 /*&nbsp;从环形缓冲区中取一个元素&nbsp;*/ 
 double get{void} 
 { 
 cnt pos; 
 if (n&gt;0){ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Pos = iget; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;iget = addring(iget); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n--; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return buffer[pos]; 
 } 
 else { 
 printf(“Buffer is empty\n”); 
 return 0.0; 
 } 
 /*&nbsp;向环形缓冲区中放人一个元素*/ 
 void put(double z) 
 { 
 if (n&lt;NMAX){ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;buffer[iput]=z; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;iput = addring(iput); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n++; 
 } 
 else 
 printf(“Buffer is full\n”); 
 } 
 
 int main{void) 
 { 
 chat opera[5]; 
 double z; 
 do { 
 printf(“Please input p|g|e?”); 
 scanf(“%s”, &amp;opera); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;switch(tolower(opera[0])){ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case ‘p’: /* put */ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(“Please input a float number?”); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf(“%lf”, &amp;z); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;put(z); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break; 
 case ‘g’: /* get */ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;z = get(); 
 printf(“%8.2f&nbsp;from Buffer\n”, z); 
 break; 
 case ‘e’: 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(“End\n”); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break; 
 default: 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(“%s - Operation command error! \n”, opera); 
 }/* end switch */ 
 }while(opera[0] != ’e’); 
 return 0; 
 } 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

设备驱动中环形缓冲区数据存储和读写同步的实现

2007-11-15 23:06

[view plain]: http://blog.csdn.net/wanxiao009/article/details/5519514#