嵌入式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模型转…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
云原生周刊:k0s 成为 CNCF 沙箱项目
开源项目推荐 HAMi HAMi(原名 k8s‑vGPU‑scheduler)是一款 CNCF Sandbox 级别的开源 K8s 中间件,通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度,为容器提供统一接口,实现细粒度资源配额…...

小智AI+MCP
什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析:AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github:https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...

5. TypeScript 类型缩小
在 TypeScript 中,类型缩小(Narrowing)是指根据特定条件将变量的类型细化为更具体的过程。它帮助开发者编写更精确、更准确的代码,确保变量在运行时只以符合其类型的方式进行处理。 一、instanceof 缩小类型 TypeScript 中的 in…...

LSTM-XGBoost多变量时序预测(Matlab完整源码和数据)
LSTM-XGBoost多变量时序预测(Matlab完整源码和数据) 目录 LSTM-XGBoost多变量时序预测(Matlab完整源码和数据)效果一览基本介绍程序设计参考资料 效果一览 基本介绍 普通的多变量时序已经用腻了,审稿人也看烦了&#…...

Ansys Maxwell:线圈和磁体的静磁 3D 分析
本博客展示了如何在 Ansys Maxwell 中执行静磁 3D 分析,以计算载流线圈和永磁体之间相互作用产生的扭矩。在这个例子中,线圈中的电流产生一个沿 Y 轴指向的磁场,而永磁体沿 X 轴被磁化。这种配置导致围绕 Z 轴的扭矩。分步工作流程包括构建几…...
Three.js + Vue3 加载GLB模型项目代码详解
本说明结合 src/App.vue 代码,详细解释如何在 Vue3 项目中用 three.js 加载并显示 glb 模型。 1. 依赖与插件导入 import {onMounted, onUnmounted } from vue import * as THREE from three import Stats from stats.js import {OrbitControls } from three/examples/jsm/co…...

6.8 note
paxos算法_初步感知 Paxos算法保证一致性主要通过以下几个关键步骤和机制: 准备阶段 - 提议者向所有接受者发送准备请求,请求中包含一个唯一的编号。 - 接受者收到请求后,会检查编号,如果编号比它之前见过的都大,就会承…...
C++ vector容器存储对象和存储指针的区别(vector对象、vector指针)(存储指针时推荐使用智能指针)
文章目录 **1. 内存管理**- **存储对象**:- **存储指针**: **2. 生命周期控制**- **存储对象**:- **存储指针**: **3. 性能差异**- **存储对象**:- **存储指针**: **4. 使用场景**- **选择存储对象的情况**…...