【数据结构及算法】环形缓冲区（ring buffer）实现原理及代码实现（C语言）

朱雀 2023-03-12 10:52 23阅读 0赞

# 0x00前言 #

文章中的文字可能存在语法错误以及标点错误，请谅解；

如果在文章中发现代码错误或其它问题请告知，感谢！

运行环境：Linux version 2.6.35-22-generic (buildd@rothera) (gcc version 4.4.5 (Ubuntu/Linaro 4.4.4-14ubuntu4) )

# 0x01环形缓冲区简介 #

环形缓冲区（ring buffer）也称作循环缓冲区（cyclic buffer）、圆形队列（circular queue）、圆形缓冲区（circular buffer）。环形缓冲区并不是指物理意义上的一个首尾相连成“环”的缓冲区，而是逻辑意义上的一个环，因为内存空间是线性结构，所以实际上环形缓冲区仍是一段有长度的内存空间，是一个先进先出功能的缓冲区，具备实现通信进程对该缓冲区的互斥访问功能。

环形缓冲区在逻辑上示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg_size_16_color_FFFFFF_t_70]  
环形缓冲区实际在内存空间内示意图：  
![在这里插入图片描述][20200515133521264.jpg]

环形缓冲区的长度是固定的，在使用该缓冲区时，不需要将所有的数据清除，只需要调整指向该缓冲区的pHead、pValidWrite和pTail指针位置即可。pValidWrite指针最先指向pHead指针位置（环形缓冲区开头位置），数据从pValidWrite指针处开始存储，每存储一个数据，pValidWrite指针位置向后移动一个长度 ，随着数据的添加，pValidWrite指针随移动数据长度大小个位置。当pValidWrite指向pTail尾部指针，pValidWrite重新指向pHead指针位置（折行处理），并且覆盖原先位置数据内容直到数据存储完毕。

环形缓冲区的好处是可以减少内存分配继而减少系统的开销，减少内存碎片数量，有利于程序长期稳定的运行（当然，也可以使用内存池机制达到同样的目的）。

# 0x02 实现原理 #

一般构建一个环形缓冲区需要一段连续的内存空间以及4个指针：  
pHead指针：指向内存空间中的首地址；  
pTail指针：指向内存空间的尾地址；  
pValidRead：指向内存空间存储数据的起始位置（读指针）；  
pValidWrite：指向内存空间存储数据的结尾位置（写指针）。

当申请完内存以及指针定义完毕后，环形缓冲区说明及使用如下：  
1.该段内存空间的长度是Len = pTail-pHead；  
2.pValidRead是读数据的起始位置，当读取完N数据之后要移动N个单位长度的偏移，当有addlen长度的数据要存入到环形缓冲区，若addlen + pValidWrite > pTail时，pValidWrite将存入len1 = pTail - pValidWrite个数据长度，然后pValidWrite回到pHead位置，将剩下的len2 = addlen - len1个数据从pHead开始存储并覆盖到原来的数据内容。  
3.pValidWrite是写数据的起始位置，当存入N个数据之后要移动N个单位长度的偏移，pValidRead是读数据的起始位置，当读取N个数据之后要移动N个单位长度的偏移。当要addlen长度的数据要从环形缓冲区读取，若addlen + pValidRead > pTail时，pValidRead 将读取len1 = pTail - pValidRead 个数据长度，然后pValidRead 回到pHead位置，将剩下的len2 = addlen - len1个数据从pHead开始读取完毕。  
![在这里插入图片描述][20200515142802115.jpg]

# 0x03 代码示例 #

本段代码改自参考文档1中的代码:

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<assert.h>
    
    #define BUFF_MAX_LEN 16
    #define VOS_OK 0
    #define VOS_ERR -1
    
    char *pHead = NULL;			//环形缓冲区首地址
    char *pValidRead = NULL;	//已使用环形缓冲区首地址
    char *pValidWrite = NULL;	//已使用环形缓冲区尾地址
    char *pTail = NULL;			//环形缓冲区尾地址
    
    //环形缓冲区初始化
    void InitRingBuff()
    { 
    	if(NULL == pHead)
    	{ 
    		pHead = (char *)malloc(BUFF_MAX_LEN * sizeof(char));
    	}
    	
    	memset(pHead, 0 , sizeof(BUFF_MAX_LEN));
    	
    	pValidRead = pHead;
    	pValidWrite = pHead;
    	pTail = pHead + BUFF_MAX_LEN;  
    }
    
    //环形缓冲区释放
    void FreeRingBuff()
    { 
    	if(NULL != pHead)
    	{ 
    		free(pHead);
    	}
    }
    
    //向缓冲区写数据
    int WriteRingBuff(char *pBuff, int AddLen)
    { 
    	if(NULL == pHead)
    	{ 
    		printf("WriteRingBuff:RingBuff is not Init!\n");
    		return VOS_ERR;
    	}
    
    	if(AddLen > pTail - pHead)
    	{ 
    		printf("WriteRingBuff:New add buff is too long\n");	
    		return VOS_ERR;
    	}
    	
    	//若新增的数据长度大于写指针和尾指针之间的长度
    	if(pValidWrite + AddLen > pTail)
    	{ 
    		int PreLen = pTail - pValidWrite;
    		int LastLen = AddLen - PreLen;
    		memcpy(pValidWrite, pBuff, PreLen);	
    		memcpy(pHead, pBuff + PreLen, LastLen);
    		
    		pValidWrite = pHead + LastLen;	//新环形缓冲区尾地址
    	}
    	else
    	{ 
    		memcpy(pValidWrite, pBuff, AddLen);	//将新数据内容添加到缓冲区
    		pValidWrite += AddLen;	//新的有效数据尾地址
    	}
    	return VOS_OK;
    }
    
    //从缓冲区读数据
    int ReadRingBuff(char *pBuff, int len)
    { 
    	if(NULL == pHead)
    	{ 
    		printf("ReadRingBuff:RingBuff is not Init!\n");
    		return VOS_ERR;
    	}
    	if(len > pTail - pHead)
    	{ 
    		printf("ReadRingBuff:Read buff size is too long\n");	
    		return VOS_ERR;
    	}
    	if(0 == len)
    	{ 
    		return VOS_OK;
    	}
    	if(pValidRead + len > pTail)
    	{ 
    		int PreLen = pTail - pValidRead;
    		int LastLen = len - PreLen;
    		memcpy(pBuff, pValidRead, PreLen);
    		memcpy(pBuff + PreLen, pHead, LastLen);
    		
    		pValidRead = pHead + LastLen;
    	}
    	else
    	{ 
    		memcpy(pBuff, pValidRead, len);
    		pValidRead += len;
    	}
    	
    	return len;
    }
    
    int main()
    { 
    	char c;
    	int len;
    	int readLen;
    	char readBuffer[10];
    	int i = 0;
    	
    	InitRingBuff();
    	
    	printf("Please enter a character\n");
    	
    	while(1)
    	{ 
    		c=getchar();
    		
    		switch(c)
    		{ 
    			case 'Q':
    				goto exit;
    			break;
    			
    			case 'R':
    				readLen = ReadRingBuff(readBuffer,10);
    				printf("ReadRingBufflen:%d\n",readLen);
    				if(readLen > 0)
    				{ 
    					for(i = 0;i < readLen;i++)
    					{ 
    						printf("%c ",(char)readBuffer[i]);
    					}
    					printf("\n");
    				}
    			break;
    			
    			default :
    				if(c!='\n') WriteRingBuff((char*)&c,1);
    			break;
    		}
    	};
    	
    exit:
    	FreeRingBuff();
    
        return 0;
    }

运行结果：  
![在这里插入图片描述][20200520142821871.png]

这段代码示例中，我们每次从缓冲区只是读取10个长度的数据，可以看到基本实现了环形缓冲区的功能，但是要注意的是，如果我们需要从环形缓冲区中读取指定长度或者对环形缓冲区读取以及写入的长度大于缓冲区长度那么就需要在此代码基础上进行进一步的逻辑修改。

以上。

参考文档：  
1.[https://blog.csdn.net/maowentao0416/article/details/81984269][https_blog.csdn.net_maowentao0416_article_details_81984269]  
2.h[ttps://www.cnblogs.com/youngjum/p/12188780.html][ttps_www.cnblogs.com_youngjum_p_12188780.html]  
3.[https://blog.csdn.net/baidu\_39486224/article/details/83212844][https_blog.csdn.net_baidu_39486224_article_details_83212844]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg_size_16_color_FFFFFF_t_70]: /images/20230312/8f022a604f20446e8d196435488a93b8.png
[20200515133521264.jpg]: /images/20230312/45f7999dde3f44569c25a7c87d5ebf21.png
[20200515142802115.jpg]: /images/20230312/44c30aa05b0b4b37a4c09392f50c8ebc.png
[20200520142821871.png]: /images/20230312/f19e564ec2384237a105f474cd6e84fa.png
[https_blog.csdn.net_maowentao0416_article_details_81984269]: https://blog.csdn.net/maowentao0416/article/details/81984269
[ttps_www.cnblogs.com_youngjum_p_12188780.html]: https://www.cnblogs.com/youngjum/p/12188780.html
[https_blog.csdn.net_baidu_39486224_article_details_83212844]: https://blog.csdn.net/baidu_39486224/article/details/83212844