Circular buffer

Circular buffer

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

前言:

circular buffercyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams.

Uses

The useful property of a circular buffer is that it does not need to have its elements shuffled around [又一次排列]when one is consumed. (If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.) In other words, the circular buffer is well-suited[很合适] as a FIFO [先进先出]buffer while a standard, non-circular buffer is well suited as a LIFO [后进后出]buffer.

Circular buffering makes a good implementation strategy for a queue that has fixed maximum size. Should a maximum size be adopted [被採用]for a queue, then a circular buffer is a completely ideal implementation; all queue operations are constant time. However, expanding a circular buffer requires shifting memory, which is comparatively[相对来说] costly. For arbitrarily expanding queues[可任意扩展的], a linked list approach[链表] may be preferred instead.

[本文作者franklin注解]环形buffer 应用于固定的块场合,一旦固定,这块内存就是专用,所以,不具备扩展性.

In some situations, overwriting [可覆盖性]circular buffer can be used, e.g. in multimedia. If the buffer is used as the bounded [有界性,有限制] buffer in the producer-consumer problem then it is probably desired for the producer (e.g., an audio generator) to overwrite old data if the consumer (e.g., the sound card) is unable to momentarily keep up. Also, the LZ77 family of lossless data compression algorithms operates on the assumption that strings seen more recently in a data stream are more likely to occur soon in the stream. Implementations store the most recent data in a circular buffer.

How it works

A circular buffer first starts empty and of some predefined length. For example, this is a 7-element buffer:

Circular buffer - empty.svg

Assume that a 1 is written into the middle of the buffer (exact starting location does not matter in a circular buffer):

Circular buffer - XX1XXXX.svg

Then assume that two more elements are added — 2 & 3 — which get appended after the 1:

Circular buffer - XX123XX.svg

If two elements are then removed from the buffer, the oldest values inside the buffer are removed. The two elements removed, in this case, are 1 & 2, leaving the buffer with just a 3:

Circular buffer - XXXX3XX.svg

If the buffer has 7 elements then it is completely full:

Circular buffer - 6789345.svg

A consequence of the circular buffer is that when it is full and a subsequent write is performed, then it starts overwriting the oldest data. In this case, two more elements — A & B — are added and they overwrite the 3 & 4:

[本文作者franklin注解][当环形buffer满的时候,兴许写入数据将覆盖前面数据]

Circular buffer - 6789AB5.svg

Alternatively[或者], the routines that manage the buffer could prevent overwriting the data and return an error or raise[根本就是设计成不能写入] an exception. Whether or not data is overwritten is up to the semantics of the buffer routines or the application using the circular buffer.

Finally, if two elements are now removed then what would be returned is not 3 & 4 but 5 & 6 because A & B overwrote the 3 & the 4 yielding the buffer with:

Circular buffer - X789ABX.svg


Circular buffer mechanics

What is not shown in the example above is the mechanics of how the circular buffer is managed.

Start/end pointers (head/tail)[edit]

Generally, a circular buffer requires four pointers:

  • one to the actual buffer in memory
  • one to the buffer end in memory (or alternately[取代]: the size of the buffer)
  • one to point to the start of valid data (or alternately: amount of data written to the buffer)
  • one to point to the end of valid data (or alternately: amount of data read from the buffer)

Alternatively[或者], a fixed-length buffer with two integers to keep track of indices can be used in languages that do not have pointers.

[没有指针也能够的]

Taking a couple of examples from above. (While there are numerous[庞大的] ways to label the pointers and exact semantics[精确到语意]can vary, this is one way to do it.)

This image shows a partially[部分] full buffer:

Circular buffer - XX123XX with pointers.svg

This image shows a full buffer with two elements having been overwritten:

Circular buffer - 6789AB5 with pointers.svg

What to note about the second one is that after each element is overwritten then the start pointer is incremented as well.

Difficulties

Full / Empty Buffer Distinction

A small disadvantage of relying on pointers or relative indices of the start and end of data is, that in the case the buffer is entirely full, both pointers point to the same element:

Circular buffer - 6789AB5 full.svg

This is exactly the same situation as when the buffer is empty:

Circular buffer - 6789AB5 empty.svg

[最常见的问题是,buffer的满和空的判别]

To solve this confusion there are a number of solutions:

Always Keep One Slot Open [最简单有效的解决的方法就是保持最后一个单元不写]

This design always keeps one slot unallocated. A full buffer has at most (\text{size}-1) slots. If both pointers refer to the same slot, the buffer is empty. If the end (write) pointer refers to the slot preceding the one referred to by the start (read) pointer, the buffer is full.

The advantage is:

  • The solution is simple and robust.

The disadvantages are:

  • One slot is lost, so it is a bad compromise when the buffer size is small or the slot is big or is implemented in hardware.
  • The full test requires a modulo operation

ref:

http://en.wikipedia.org/wiki/Circular_buffer

http://lmax-exchange.github.io/disruptor/

http://www.cnblogs.com/shanyou/archive/2013/02/04/2891300.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116759.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 软件测试常用的黑盒测试方法有哪些,简述什么是黑盒测试方法(最常用的黑盒测试方法)…[通俗易懂]

    软件测试常用的黑盒测试方法有哪些,简述什么是黑盒测试方法(最常用的黑盒测试方法)…[通俗易懂]黑盒(又叫功能测试、数据驱动测试):1.黑盒测试发现错误类型:功能错误和遗漏界面错误数据库错误性能错误初始化和终止错误2.黑盒测试:程序外部接口进行的3.黑盒测试就是根据功能需求来设计测试用例,验证软件是否按照预期要求工作。4.黑盒测试技术主要有等价类划分法、边界值法、判定表法、因果图法、场景法等。5.等价类划分法测试技术是依据软件系统输入集合、输出集合或操作集合实现功能的相同性为依据,对其进行的…

  • 使用html css实现180箭头旋转,纯CSS实现箭头旋转「建议收藏」

    使用html css实现180箭头旋转,纯CSS实现箭头旋转「建议收藏」无标题文档b{position:absolute;right:10px;top:7px;width:0;height:0;border-width:4px4px;border-style:solid;border-color:#666#f5f5f5#f5f5f5;font-size:0;line-height:0;-webkit-transition:-webkit-transform.2…

  • c++ uint32_t_int32和uint32

    c++ uint32_t_int32和uint32文章目录使用int64_t形式代替基本类型使用原因stdint.h源码int32_t和uint32_t的区别size_t在不同机器中定义不同:参考文档使用int64_t形式代替基本类型我们都知道,C语言的基本类型就char,short,int等。但是我们在看其他源码时经常碰到int32_t,int8_t这种形式的定义,他们是什么呢。其实他们就是基本类型的typedef重定义。也就是不同平台下,使用以下名称可以保证固定长度。1字节int8_t——char2字节int1

  • 一叶知秋,一个 LED 就能入门 Linux 内核「建议收藏」

    一叶知秋,一个 LED 就能入门 Linux 内核「建议收藏」简单点灯最近项目上需要用到LED子系统,在嵌入式Linux里面点个灯还是比较简单的,只要在某个灯对应的目录里,向相应文件写入特定值,就可以让LED亮/灭/闪烁。#echo1>/sys/class/leds/green/brightness//点亮LED#echo0>/sys/class/leds/green/brightness//熄灭LED#echoheartbeat>/sys/class/leds/green/trigger//

  • SpringBoot—–SpringBoot序列化Long转String「建议收藏」

    SpringBoot—–SpringBoot序列化Long转String「建议收藏」

  • goland 激活2021【2021.10最新】

    (goland 激活2021)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号