devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

环形缓冲区(ring buffer)，环形队列(ring queue) 原理_环形缓冲队列

作者：IT小白 | 2024-05-21 08:34:37

赞

踩

环形缓冲队列

   环形缓冲区(ring buffer)，环形队列(ring queue) 多用于2个线程之间传递数据，是标准的先入先出(FIFO)模型。一般来说，对于多线程共享数据，需要使用mutex来同步，这样共享数据才不至于发生不可预测的修改/读取，然而，mutex的使用也带来了额外的系统开销，ring buffer/queue 的引入，就是为了有效地解决这个问题，因其特殊的结构及算法，可以用于2个线程中共享数据的同步，而且必须遵循A线程push in，B线程pull out的原则。采用这个机制另外一个用处是A push完数据后可以马上接收另外一个数据,当输入数据快速时不容易造成数据阻塞而丢包.

    当然基于这个模型还可以新增一些功能，如在push前加锁，就可以让多个线程来push数据。

线程 A                       媒介                        线程 B
data in --------> ring buffer/queue -------> data out

===============RingBuffer完整Python测试代码======================= 

  1. class RingBuffer:
  2.     def __init__(self, size_max):
  3.         self.max = size_max + 1
  4.         self.data = [None] * self.max
  5.         self.wrPos = 0
  6.         self.rdPos = 0
  7.  
  8.     def is_ringbuffer_full(self):
  9.         if (self.wrPos + 1) % self.max == self.rdPos:
  10.             return 1
  11.         else:
  12.             return 0
  13.  
  14.     def is_ringbuffer_empty(self):
  15.         if self.wrPos == self.rdPos:
  16.             return 1
  17.         else:
  18.             return 0
  19.  
  20.     # pop up data from rb
  21.     def get(self):
  22.         if self.is_ringbuffer_empty():
  23.             return None
  24.         ret = self.data[self.rdPos]
  25.         self.rdPos = (self.rdPos + 1) % self.max
  26.         return ret
  27.  
  28.     # push data to rb
  29.     def append(self, item):
  30.         if self.is_ringbuffer_full():
  31.             return 0
  32.         self.data[self.wrPos] = item
  33.         self.wrPos = (self.wrPos + 1) % self.max
  34.         return 1
  35.  
  36.  
  37. if __name__ == "__main__":
  38.     rb = RingBuffer(5)
  39.     rb.append(1)
  40.     rb.append(2)
  41.     rb.append(3)
  42.     rb.append(4)
  43.     rb.append(5)
  44.     rb.append(6)
  45.     print(rb.get())  # 输出1
  46.     print(rb.get())  # 输出2
  47.     print(rb.get())  # 输出3
  48.     print(rb.get())  # 输出4
  49.     print(rb.get())  # 输出5
  50.     print(rb.get())  # 输出None，因为buffer已经清空
  51.  
  52.     rb.append("Chinese")  # 重新push
  53.     rb.append("English")
  54.     rb.append("Franch")
  55.     rb.append([10, 20, 30])
  56.  
  57.     print(rb.get())  # 输出 Chinse
  58.     print(rb.get())  # 输出 English
  59.     print(rb.get())  # 输出 Franch
  60.     print(rb.get())  # 输出 [10,20,30]
  61.     print(rb.get())  # 输出None，因为buffer已经清空


=============RingBuffer完整C测试代码[单元素]==========

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct TAG_RING_BUFFER
  5. {
  6.     int wrPos;
  7.     int rdPos;
  8.     int maxCount;
  9. 	int remainCnt;
  10.     char *buffer;
  11. 	
  12. } TagRingBuffer;
  13.  
  14. TagRingBuffer* ringBuffer_init(int size)
  15. {
  16. 	 //Note: (size-1) is full!!
  17. 	TagRingBuffer * rb;
  18.     rb = (TagRingBuffer*)malloc(sizeof(TagRingBuffer));
  19.     if( rb == NULL)
  20.     {
  21.         return NULL;
  22.     }
  23.     rb->buffer = (char*)malloc( size );
  24.     if( rb->buffer == NULL )
  25.     {
  26.         return 0;
  27.     }
  28. 	rb->maxCount = size;
  29. 	rb->wrPos = 0;
  30. 	rb->rdPos = 0;
  31. 	rb->remainCnt = 0;
  32.     return rb;
  33. }
  34.  
  35. void ringBuffer_free(TagRingBuffer* rb)
  36. {
  37. 	if( rb )
  38. 	{
  39. 		if(rb-> buffer)
  40. 		{
  41. 			free( rb-> buffer );
  42. 		}
  43. 		free( rb );
  44. 	}
  45. }
  46.  
  47. int is_ringBuffer_full(TagRingBuffer* rb)
  48. {
  49.   //Note:(MAXCOUNT-1) is full!!
  50. 	if( ( (rb->wrPos)+1)%(rb->maxCount) == rb->rdPos )
  51. 	 return 1;
  52.  
  53.     return 0;
  54. }
  55.  
  56. int is_ringBuffer_empty(TagRingBuffer* rb)
  57. {
  58. 	if( (rb->wrPos) == rb->rdPos ){
  59. 	 return 1;
  60. 	}
  61.  
  62.     return 0;
  63. }
  64.  
  65. int ringBuffer_pop(TagRingBuffer* rb,char *ch)
  66. {  //read
  67. 	if( is_ringBuffer_empty(rb))
  68. 	{
  69. 		return 0;
  70. 	}
  71. 	*ch = rb->buffer[ rb->rdPos ];
  72. 	rb->rdPos =  (rb->rdPos +1)%rb->maxCount;
  73. 	rb->remainCnt --;
  74. 	return 1;
  75. }
  76.  
  77. int ringBuffer_push(TagRingBuffer* rb,char ch)
  78. {  //write
  79. 	if( is_ringBuffer_full(rb))
  80. 	{
  81. 		return 0;
  82. 	}
  83. 	rb->buffer[ rb->wrPos ] = ch;	
  84. 	rb->wrPos =  (rb->wrPos +1)%(rb->maxCount);
  85. 	rb->remainCnt++;
  86. 	return 1;
  87. }
  88.  
  89. int ringBuffer_getRemainCnt(TagRingBuffer* rb)
  90. {
  91. 	return rb->remainCnt;
  92. }
  93.  
  94.  //RingBuffer 测试[单元素]
  95. void main()
  96. {
  97.  
  98. 	printf("----C_BuildTime: %s----\r\n", __TIME__ );
  99. 	
  100.    TagRingBuffer *rb ;
  101.    char ch;
  102.    int retn = 1;
  103.    int remain = 0;
  104.    
  105.    rb = ringBuffer_init(5);
  106.  
  107.    ringBuffer_push(rb,1);
  108.    ringBuffer_push(rb,3);  
  109.    ringBuffer_push(rb,5); 
  110.    ringBuffer_push(rb,7);//effect data
  111.    
  112.    ringBuffer_push(rb,9); //buffer is full
  113.    ringBuffer_push(rb,11);
  114.    ringBuffer_push(rb,13);
  115.    ringBuffer_push(rb,15);
  116.    
  117.    
  118.    for(int i=0;i<10;i++)
  119.    { //测试超出ringbuffer范围的数据
  120. 	 ch = 0;
  121. 	 remain = ringBuffer_getRemainCnt(rb);
  122. 	 retn = ringBuffer_pop(rb,&ch);	 
  123. 	 printf("[%d] out_data=(%d),remain=%d,ret=%d.\n",i,ch,remain,retn  );   
  124.    }	
  125. }

=============RingQueue完整C测试代码[多元素]==========

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. typedef struct TAG_RING_QUEUE
  6. {
  7.     int wrPos;
  8.     int rdPos;
  9.     int maxCount;
  10. 	int remainCnt;
  11.     char**buffer;//storage address
  12. 	
  13. } TagRingQueue;
  14.  
  15. TagRingQueue* ringQueue_init(int size)
  16. {
  17. 	 //Note: (size-1) is full!!
  18. 	TagRingQueue * rb;
  19.     rb = (TagRingQueue*)malloc(sizeof(TagRingQueue));
  20.     if( rb == NULL)
  21.     {
  22.         return NULL;
  23.     }
  24.     rb->buffer = (char**)malloc( size* sizeof(char**) );
  25.     if( rb->buffer == NULL )
  26.     {
  27.         return 0;
  28.     }
  29. 	rb->maxCount = size;
  30. 	rb->wrPos = 0;
  31. 	rb->rdPos = 0;
  32. 	rb->remainCnt = 0;
  33.     return rb;
  34. }
  35.  
  36. void ringQueue_free(TagRingQueue* rb)
  37. {
  38. 	if( rb )
  39. 	{
  40. 		if(rb-> buffer)
  41. 		{
  42. 			free( rb-> buffer );
  43. 		}
  44. 		free( rb );
  45. 	}
  46. }
  47.  
  48. //首字节为长度数据
  49. void ringQueue_free_pt(char*datPoint)
  50. {
  51.     if( (datPoint!=NULL) && ((datPoint-1)!=NULL))
  52.     {
  53.         free(datPoint-1);
  54.     }
  55. }
  56.  
  57. int is_ringQueue_full(TagRingQueue* rb)
  58. {
  59.   //Note:(MAXCOUNT-1) is full!!
  60. 	if( ( (rb->wrPos)+1)%(rb->maxCount) == rb->rdPos )
  61. 	 return 1;
  62.  
  63.     return 0;
  64. }
  65.  
  66. int is_ringQueue_empty(TagRingQueue* rb)
  67. {
  68. 	if( (rb->wrPos) == rb->rdPos ){
  69. 	 return 1;
  70. 	}
  71.  
  72.     return 0;
  73. }
  74.  
  75. //注意:data前1节存数据长度,后面的数据才是本体 
  76. //注意使用完后必须释放指针.
  77. char* ringQueue_pop(TagRingQueue* rb,short *lenOut)
  78. {  //read
  79.     char *buff_pt = NULL;
  80. 	*lenOut = 0;
  81. 	if( is_ringQueue_empty(rb))
  82. 	{
  83. 		return NULL;
  84. 	}
  85. 	buff_pt = (char*)rb->buffer[ rb->rdPos ];
  86. 	rb->rdPos =  (rb->rdPos +1)%rb->maxCount;
  87. 	rb->remainCnt --;
  88. 	if( buff_pt != NULL)
  89. 	{
  90. 		*lenOut = *buff_pt;
  91. 		buff_pt++;
  92. 	}	
  93. 	return buff_pt;//must free after use! NOTE: free(buff_pt-1)
  94. }
  95.  
  96. //注意:data前1字节存数据长度,后面的数据才是本体
  97. int ringQueue_push(TagRingQueue* rb,char *data,short len)
  98. {  //write
  99.     char *buff_pt = NULL;
  100. 	if( is_ringQueue_full(rb))
  101. 	{
  102. 		return 0;
  103. 	}
  104. 	buff_pt = (char*)malloc(len+1);
  105. 	if( buff_pt == NULL )
  106. 	{
  107. 		return -1;//no mem
  108. 	}
  109. 	buff_pt[0] = len; //data第一字节存数据长度
  110. 	memcpy(buff_pt+1,data,len);
  111. 	rb->buffer[ rb->wrPos ] = buff_pt;	
  112. 	rb->wrPos =  (rb->wrPos +1)%(rb->maxCount);
  113. 	rb->remainCnt++;
  114. 	return 1;
  115. }
  116.  
  117. int ringQueue_getRemainCnt(TagRingQueue* rb)
  118. {
  119. 	return rb->remainCnt;
  120. }
  121.  
  122.  
  123. void dump_hex(char *infoStr,char *buf,int len)
  124. {
  125. 	printf("%s(%d)",infoStr,len);
  126. 	for(int i=0;i<len;i++)
  127. 	{
  128. 		printf("%02X ",(unsigned char)buf[i]);
  129. 	}
  130. 	printf("\n");
  131. } 
  132.  
  133. //RingQueue 测试 [多元素]
  134. void main()
  135. {
  136. 	printf("----C_BuildTime: %s----\r\n", __TIME__ );
  137. 	
  138.    TagRingQueue *rb ;
  139.    char data[50];   
  140.    
  141.    rb = ringQueue_init(5);//MAXCOUNT-1=4
  142.  
  143.    char rawDat[]={0x39,0x38,0x03,0x00,0x35,0x00,0x00};
  144.    ringQueue_push(rb,rawDat,sizeof(rawDat)); //test raw data
  145.  
  146.    sprintf(data,"English");
  147.    ringQueue_push(rb,data,strlen(data)+1);
  148.    
  149.    sprintf(data,"USA");
  150.    ringQueue_push(rb,data,strlen(data)+1);    
  151.    
  152.    sprintf(data,"Japan");
  153.    ringQueue_push(rb,data,strlen(data)+1);     
  154.    
  155.    sprintf(data,"India");
  156.    ringQueue_push(rb,data,strlen(data)+1);   
  157.  
  158.    sprintf(data,"Yemen");
  159.    ringQueue_push(rb,data,strlen(data)+1);   
  160.  
  161.  
  162.    char* datOut = NULL;
  163.    short lenOut = 0;
  164.  
  165.    
  166.    for(int i=0;i<10;i++)
  167.    { //测试超出ringQueue范围的数据
  168.         datOut = ringQueue_pop(rb,&lenOut);
  169.         printf("\n[%d] len_out=%d,data=[%s].",i,lenOut,datOut);
  170. 		dump_hex("HEX",datOut,lenOut);
  171.         ringQueue_free_pt(datOut);//must free after use!!
  172.  
  173.    }	
  174. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/601711
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号