嵌入式C基础——循环队列 ringbuffer 讲解
本期主题:
讲解ARRAY_SIZE的作用以及定义,还有一个踩坑分析
往期链接:
- 数据结构系列——先进先出队列queue
- 数据结构系列——栈 stack
- Linux内核链表
- 零长度数组的使用
- inline的作用
- 嵌入式C基础——ARRAY_SIZE使用以及踩坑分析
目录
- 1. Ringbuffer定义及特点
- 2.ringbuffer实例(rtos实例)
- 2.1 ringbuffer结构体
- 2.2 ringbuffer获取当前长度
- 2.3 ringbuffer put
- 3.根据rtos代码,设计ringbuffer,并测试
1. Ringbuffer定义及特点
Ringbuffer的定义:
环形缓冲区(Ring Buffer),也称为循环缓冲区、环形队列(Ring Queue)或循环队列(Circular Queue),是一种用于在固定大小的存储区域中存储数据的数据结构。
环形缓冲区通常由一个固定大小的数组和两个指针
组成,分别用于指示缓冲区的起始位置和结束位置。数据被顺序地存储在数组中,当到达数组的末尾时,数据会“循环”回到数组的起始位置,实现了环形的存储结构。
Ringbuffer的特点:
环形缓冲区通常用于实现数据在生产者和消费者之间的高效传输,特别是在多线程或多任务环境中。它具有以下特点和优势:
- 高效性: 环形缓冲区采用循环结构,避免了数据的频繁搬移。这使得对于生产者和消费者来说,插入和删除操作的时间复杂度都是 O(1)。
- 固定大小: 环形缓冲区有一个固定的大小,这使得其占用的内存是可控的。当缓冲区已满时,生产者会被阻塞,以免过度生产数据,同时保护消费者不会因为数据积压而失去响应能力。
- 无需动态内存分配: 环形缓冲区一般使用静态数组作为存储空间,无需动态内存分配,因此可以在嵌入式系统等资源受限的环境中使用。
- 循环利用空间: 环形缓冲区的循环结构使得空间可以被循环利用,即使数据已经被消费,存储空间也可以被后续的数据重新利用。
- 并发安全: 当环形缓冲区被多个线程或任务访问时,需要通过互斥锁或其他同步机制来保护共享资源,以确保线程安全。
使用环形缓冲区时,需要注意处理好
生产者和消费者之间的同步和竞态条件
,以及处理好缓冲区空间不足和溢出的情况。同时,还需要考虑如何优雅地处理缓冲区已满和已空时的阻塞与唤醒机制。
2.ringbuffer实例(rtos实例)
ringbuffer比较难处理的一个问题就是 当read_ptr = write_ptr 时,此时并不是很确定ringbuffer是empty还是full,rtos和Linux中的设计使用的是 镜像法,具体的意思是:
镜像扩展位是环形缓冲区中的一个额外的标志位或变量,用于指示缓冲区的填充状态。它通常有两种取值:
- 未填满(Not Full): 表示缓冲区还有空闲空间,可以继续向缓冲区写入数据。
- 填满(Full): 表示缓冲区已经填满,不能再继续向缓冲区写入数据。此时,继续写入数据可能会覆盖已有的数据,造成数据丢失。
使用镜像扩展位,当缓冲区填满时,生产者可以根据镜像扩展位的状态来判断是否继续写入数据。如果缓冲区未填满,生产者可以继续写入数据;如果缓冲区已经填满,则生产者应该等待,直到缓冲区有空间可用。
2.1 ringbuffer结构体
看rtos的实例代码:
struct rt_ringbuffer
{rt_uint8_t *buffer_ptr;/* use the msb of the {read,write}_index as mirror bit. You can see this as* if the buffer adds a virtual mirror and the pointers point either to the* normal or to the mirrored buffer. If the write_index has the same value* with the read_index, but in a different mirror, the buffer is full.* While if the write_index and the read_index are the same and within the* same mirror, the buffer is empty. The ASCII art of the ringbuffer is:** mirror = 0 mirror = 1* +---+---+---+---+---+---+---+|+~~~+~~~+~~~+~~~+~~~+~~~+~~~+* | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||| 0 | 1 | 2 | 3 | 4 | 5 | 6 | Full* +---+---+---+---+---+---+---+|+~~~+~~~+~~~+~~~+~~~+~~~+~~~+* read_idx-^ write_idx-^** +---+---+---+---+---+---+---+|+~~~+~~~+~~~+~~~+~~~+~~~+~~~+* | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||| 0 | 1 | 2 | 3 | 4 | 5 | 6 | Empty* +---+---+---+---+---+---+---+|+~~~+~~~+~~~+~~~+~~~+~~~+~~~+* read_idx-^ ^-write_idx*/rt_uint32_t read_mirror : 1;rt_uint32_t read_index : 31;rt_uint32_t write_mirror : 1;rt_uint32_t write_index : 31;/* as we use msb of index as mirror bit, the size should be signed and* could only be positive. */rt_int32_t buffer_size;
};
结构体中有一个read_mirror和write_mirror,看注释可以知道是表示,read/write的指针是否到了mirror区,并且:
- read_index = write_index, read_mirror和write_mirror不同,此时为FULL
- read_index = write_index, read_mirror和write_mirror相同,此时为EMPTY
2.2 ringbuffer获取当前长度
RTOS中代码:
rt_size_t rt_ringbuffer_data_len(struct rt_ringbuffer *rb)
{switch (rt_ringbuffer_status(rb)){case RT_RINGBUFFER_EMPTY:return 0;case RT_RINGBUFFER_FULL:return rb->buffer_size;case RT_RINGBUFFER_HALFFULL:default:{rt_size_t wi = rb->write_index, ri = rb->read_index;if (wi > ri)return wi - ri;elsereturn rb->buffer_size - (ri - wi);}}
}
有三种情况:
- 当rt_status为空时,len为0
- 当rt_status为满时,len为buffer_size
- 当ringbuffer非空/满时,如果write_index>read_index,那么buffer_size为 wi-ri,否则为 rb->buffer_size - (ri - wi)
2.3 ringbuffer put
put代码如下:
rt_size_t rt_ringbuffer_put(struct rt_ringbuffer *rb,const rt_uint8_t *ptr,rt_uint32_t length)
{rt_uint32_t size;RT_ASSERT(rb != RT_NULL);/* whether has enough space */size = rt_ringbuffer_space_len(rb);/* no space */if (size == 0)return 0;/* drop some data */if (size < length)length = size;if (rb->buffer_size - rb->write_index > length){/* read_index - write_index = empty space */rt_memcpy(&rb->buffer_ptr[rb->write_index], ptr, length);/* this should not cause overflow because there is enough space for* length of data in current mirror */rb->write_index += length;return length;}rt_memcpy(&rb->buffer_ptr[rb->write_index],&ptr[0],rb->buffer_size - rb->write_index);rt_memcpy(&rb->buffer_ptr[0],&ptr[rb->buffer_size - rb->write_index],length - (rb->buffer_size - rb->write_index));/* we are going into the other side of the mirror */rb->write_mirror = ~rb->write_mirror;rb->write_index = length - (rb->buffer_size - rb->write_index);return length;
}
逻辑是:
- 判断剩余空间的size是否足够放下数据,如果不够则需要drop一些数据
- 如果可以直接放,不需要循环回来,那么就直接Memcpy就行
- 如果需要循环回来,write_mirror需要取反
3.根据rtos代码,设计ringbuffer,并测试
代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#include <string.h>
#include "main.h"struct rt_ringbuffer
{rt_uint8_t *buffer_ptr;rt_uint32_t read_mirror : 1;rt_uint32_t read_index : 31;rt_uint32_t write_mirror : 1;rt_uint32_t write_index : 31;rt_int32_t buffer_size;
};enum rt_ringbuffer_state rt_ringbuffer_status(struct rt_ringbuffer *rb)
{if (rb->read_index == rb->write_index){if (rb->read_mirror == rb->write_mirror)return RT_RINGBUFFER_EMPTY;elsereturn RT_RINGBUFFER_FULL;}return RT_RINGBUFFER_HALFFULL;
}int rt_ringbuffer_data_len(struct rt_ringbuffer *rb)
{switch (rt_ringbuffer_status(rb)){case RT_RINGBUFFER_EMPTY:return 0;case RT_RINGBUFFER_FULL:return rb->buffer_size;case RT_RINGBUFFER_HALFFULL:default:{rt_size_t wi = rb->write_index, ri = rb->read_index;if (wi > ri)return wi - ri;elsereturn rb->buffer_size - (ri - wi);}}
}struct rt_ringbuffer *ringbuffer_init(rt_int32_t size)
{struct rt_ringbuffer *rb;rt_uint8_t *pool;rb = (struct rt_ringbuffer *)malloc(sizeof(struct rt_ringbuffer));if (!rb) {printf("rb is null\n");return NULL;}pool = (rt_uint8_t *)malloc(size);if (!pool) {printf("pool is null\n");return NULL;}rb->buffer_ptr = pool;rb->buffer_size = size;rb->read_mirror = rb->read_index = 0;rb->write_mirror = rb->write_index = 0;return rb;
} /** return the size of empty space in rb */
#define rt_ringbuffer_space_len(rb) ((rb)->buffer_size - rt_ringbuffer_data_len(rb))int rt_ringbuffer_put(struct rt_ringbuffer *rb,const rt_uint8_t *ptr,rt_uint32_t length)
{rt_uint32_t size;/* whether has enough space */size = rt_ringbuffer_space_len(rb);/* no space */if (size == 0)return 0;/* drop some data */if (size < length)length = size;if (rb->buffer_size - rb->write_index > length){/* read_index - write_index = empty space */memcpy(&rb->buffer_ptr[rb->write_index], ptr, length);/* this should not cause overflow because there is enough space for* length of data in current mirror */rb->write_index += length;return length;}memcpy(&rb->buffer_ptr[rb->write_index],&ptr[0],rb->buffer_size - rb->write_index);memcpy(&rb->buffer_ptr[0],&ptr[rb->buffer_size - rb->write_index],length - (rb->buffer_size - rb->write_index));/* we are going into the other side of the mirror */rb->write_mirror = ~rb->write_mirror;rb->write_index = length - (rb->buffer_size - rb->write_index);return length;
}int rt_ringbuffer_get(struct rt_ringbuffer *rb,rt_uint8_t *ptr,rt_uint32_t length)
{int size;/* whether has enough data */size = rt_ringbuffer_data_len(rb);/* no data */if (size == 0)return 0;/* less data */if (size < length)length = size;if (rb->buffer_size - rb->read_index > length){/* copy all of data */memcpy(ptr, &rb->buffer_ptr[rb->read_index], length);/* this should not cause overflow because there is enough space for* length of data in current mirror */rb->read_index += length;return length;}memcpy(&ptr[0],&rb->buffer_ptr[rb->read_index],rb->buffer_size - rb->read_index);memcpy(&ptr[rb->buffer_size - rb->read_index],&rb->buffer_ptr[0],length - (rb->buffer_size - rb->read_index));/* we are going into the other side of the mirror */rb->read_mirror = ~rb->read_mirror;rb->read_index = length - (rb->buffer_size - rb->read_index);return length;
}int main(void)
{int ret;struct rt_ringbuffer *rb = NULL;rb = ringbuffer_init(4);if (!rb) {printf("rb init failed\n");return -1;}uint8_t a[4] = {0x1, 0x2, 0x3, 0x4};uint8_t read[4] = { 0 };ret = rt_ringbuffer_put(rb, a, 4);ret = rt_ringbuffer_get(rb, read, 1);for (int i = 0; i < 4; i++) {printf("0x%x\n", read[i]);}ret = rt_ringbuffer_put(rb, a, 4);ret = rt_ringbuffer_get(rb, read, 4);for (int i = 0; i < 4; i++) {printf("0x%x\n", read[i]);}return 0;
}
//main.h
#ifndef __MAIN_H__
#define __MAIN_H__#include <stdio.h>
#include <stdint.h>typedef uint8_t rt_uint8_t;
typedef uint32_t rt_uint32_t;
typedef int32_t rt_int32_t;
typedef int rt_size_t;enum rt_ringbuffer_state
{RT_RINGBUFFER_EMPTY,RT_RINGBUFFER_FULL,/* half full is neither full nor empty */RT_RINGBUFFER_HALFFULL,
};#endif
测试结果:
相关文章:

嵌入式C基础——循环队列 ringbuffer 讲解
本期主题: 讲解ARRAY_SIZE的作用以及定义,还有一个踩坑分析 往期链接: 数据结构系列——先进先出队列queue数据结构系列——栈 stackLinux内核链表零长度数组的使用inline的作用嵌入式C基础——ARRAY_SIZE使用以及踩坑分析 目录 1. Ringbuff…...

【动态规划-状态压缩dp】【蓝桥杯备考训练】:毕业旅行问题、蒙德里安的梦想、最短Hamilton路径、国际象棋、小国王【已更新完成】
目录 1、毕业旅行问题(今日头条2019笔试题) 2、蒙德里安的梦想(算法竞赛进阶指南) 3、最短Hamilton路径(《算法竞赛进阶指南》&模板) 4、国际象棋(第十二届蓝桥杯省赛第二场C A组/B组&#…...

全坚固笔记本丨工业笔记本丨三防笔记本相较于普通笔记本有哪些优势?
三防笔记本和普通笔记本在设计和性能方面存在显著差异,三防笔记本相较于普通笔记本具备以下优势: 三防笔记本通常采用耐磨、耐摔的材料,并具有坚固的外壳设计,能够承受恶劣环境和意外碰撞,有效保护内部组件不受损坏。相…...
机房搬迁方案
一、项目背景 随着XX公司业务的不断扩展,现有的机房设备已经无法满足日益增长的数据处理需求。同时,考虑到现有机房的设施老化及潜在的安全隐患,XX公司决定进行机房搬迁。本次搬迁旨在确保业务连续性、数据安全性以及新机房的高效运营。 二…...

推动科技创新润德生物邀您到场参观2024第13届生物发酵展
参展企业介绍 山东润德生物科技有限公司成立于2014年10月17日,是一家围绕生物制品的研发、生产、营销、国际贸易、技术服务为核心业务的国家高新技术企业,近年来荣获国家制造业单项冠军示范企业、国家级绿色工厂、国家知识产权优势企业、国家工业产品绿…...
如何在JavaScript中提高性能
在JavaScript中提高性能是一个涉及多个方面的任务,包括代码优化、数据结构选择、异步编程、避免全局查找、内存管理等。以下是一些关键的策略和技巧,可以帮助你提高JavaScript代码的性能: 1. 优化循环 使用for循环代替forEach,特…...
外观模式(面子模式)
外观模式 文章目录 外观模式什么是外观模式示例 什么是外观模式 外观模式(Facade),为子系统中的一组接口提供一个一致的界面,此模式定义了一个高层接口,这个接口使得这一子系统更加容易使用 Facade 外观类 知道哪些子系统类负责处理请求,将客…...

蓝桥杯考前复习三
1.约数个数 由乘法原理可以得出: import java.util.*; public class Main{static int mod (int)1e9 7;public static void main(String[] args){Map<Integer,Integer> map new HashMap<>(); //创建一个哈希表Scanner scan new Scanner(System.in);i…...

极客时间: 用 Word2Vec, LangChain, Gemma 模拟全本地检索增强生成(RAG)
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
VBA操作Word
检查word中的字体情况 Sub ListAllFontsInDocument()Dim doc As DocumentDim rng As RangeDim char As RangeDim fontName As StringDim uniqueFonts As Collection 初始化集合用于存储唯一字体名称Set uniqueFonts New Collection 获取当前活动文档Set doc ActiveDocument …...

Linux文件IO(4):目录操作和文件属性获取
目录 1. 前言 2. 函数介绍 2.1 访问目录 – opendir 2.2 访问目录 – readdir 2.3 访问目录 – closedir 2.4 修改文件访问权限 – chmod/fchmod 2.5 获取文件属性 – stat/lstat/fstat 2.5.1 文件属性 – struct stat 2.6 文件类型 – st_mode 3. 代码练习 3.1 要求 3.2 代…...

【C语言】_文件类型,结束判定与文件缓冲区
目录 1. 文本文件和二进制文件 2. 文件读取结束的判定 3. 文件缓冲区 1. 文本文件和二进制文件 根据数据的组织形式,数据文件被称为文本文件或二进制文件; 数据在内存中以二进制的形式存储,如果不加转换地输出到外存,就是二进…...

YOLOV8注意力改进方法:DoubleAttention(附代码)
原论文地址:原论文地址 DoubleAttention网络结构的优点在于,它能够有效地捕获图像中不同位置和不同特征的重要性,从而提高了图像识别和分割的性能。 论文相关内容介绍: 论文摘要:学习捕捉远程关系是图像/视频识别的…...
每日一题 --- 前 K 个高频元素[力扣][Go]
前 K 个高频元素 题目:347. 前 K 个高频元素 给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2]示例 2: 输入: nums [1], k 1 输出: …...

Rust所有权和Move关键字使用和含义讲解,以及Arc和Mutex使用
Rust 所有权规则 一个值只能被一个变量所拥有,这个变量被称为所有者。 一个值同一时刻只能有一个所有者,也就是说不能有两个变量拥有相同的值。所以对应变量赋值、参数传递、函数返回等行为,旧的所有者会把值的所有权转移给新的所有者&#…...

【YOLOV5 入门】——构建自己的数据集模型训练模型检验
一、准备工作 1、数据收集 图片类型数据不用多说;视频类型数据利用opencv进行抽帧保存为一张张图片,这里选取30s的名侦探柯南片段进行试验,确保环境解释器下安装了opencv(我使用的是另一个虚拟环境): im…...

MacBook 访达使用技巧【mac 入门】
快捷键 打开访达搜索窗口默认快捷键【⌥ ⌘ 空格键】可以在键盘【系统偏好设置 -> 键盘->快捷键->聚焦】修改 但是我不会去修改它,因为我不常用访达的搜索窗口,更多的是想快速打开访达文件夹窗口,可以通过第三方软件定义访达的快…...
常见溯源,反溯源,判断蜜罐手段
常见溯源,反溯源,判断蜜罐手段 1.溯源手段2.反溯源手段3.如何判断蜜罐🍯4.案例:MySQL读文件蜜罐 1.溯源手段 IP地址追踪:通过IP地址追踪可以确定攻击者的地理位置和ISP信息等;通过攻击IP历史解析记录/域名…...

蓝桥杯刷题-09-三国游戏-贪心⭐⭐⭐
蓝桥杯2023年第十四届省赛真题-三国游戏 小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵X, Y, Z (一开始可以认为都为 0 )。游戏有 n 个可能会发生的事件,每个事件之间相互独立且最多只会发生一次,当第 i 个事件发生时会分别让 X, Y,…...

Windows编译运行TensorRT-YOLOv9 (C++)
Windows编译运行yolov9-bytetrack-tensorrt(C) 1 基础环境2 编译yolov9-bytetrack-tensorrt(1)下载yolov9-bytetrack-tensorrt源码(2)修改CMakeLists.txt(3)CMake编译 3 yolov9模型转…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...

【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

相关类相关的可视化图像总结
目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系,可直观判断线性相关、非线性相关或无相关关系,点的分布密…...
k8s从入门到放弃之Pod的容器探针检测
k8s从入门到放弃之Pod的容器探针检测 在Kubernetes(简称K8s)中,容器探测是指kubelet对容器执行定期诊断的过程,以确保容器中的应用程序处于预期的状态。这些探测是保障应用健康和高可用性的重要机制。Kubernetes提供了两种种类型…...

理想汽车5月交付40856辆,同比增长16.7%
6月1日,理想汽车官方宣布,5月交付新车40856辆,同比增长16.7%。截至2025年5月31日,理想汽车历史累计交付量为1301531辆。 官方表示,理想L系列智能焕新版在5月正式发布,全系产品力有显著的提升,每…...

新版NANO下载烧录过程
一、序言 搭建 Jetson 系列产品烧录系统的环境需要在电脑主机上安装 Ubuntu 系统。此处使用 18.04 LTS。 二、环境搭建 1、安装库 $ sudo apt-get install qemu-user-static$ sudo apt-get install python 搭建环境的过程需要这个应用库来将某些 NVIDIA 软件组件安装到 Je…...