We continue our tour of custom collections with a generic ring buffer.

What is a ring buffer?

A ring buffer (also known as a circular buffer) is a fixed-size buffer that is connected end-to-end. It is similar to a queue in that behaves like a FIFO (First-In-First-Out) buffer. But unlike a queue, it does not grow when the buffer is full. This makes ring buffers very fast and memory efficient.

Ring buffers are ideal for buffering data that arrives at an inconsistent rate, but needs to be presented at a consistent rate. You will see this in action any time you watch or listen to streaming media on the internet: the media player will buffer a few milliseconds to seconds of incoming data, so it can play it back at a steady rate. In media applications, this kind of buffer is also called a jitter buffer since it compensates for jitter.

We use a ring buffer in our grijjy app to buffer audio for playback and recording of voice messages.

An example of a ring buffer may look like this:

This ring buffer has a fixed size of 16 elements (characters in this case). We have just written 11 characters (A – K) to the buffer so there is room for 5 more.

We read from the ring buffer at the read pointer. For example, when we read 2 elements, we will get back characters A and B and advance the read pointer by 2:

The ring buffer now has room for 7 more elements, which we can write to the write pointer. After writing 5 more elements, we will start to overwrite locations that were previously occupied by the A and B characters. For example, after writing 6 more characters, the buffer will look like this:

The previous A spot has been overwritten with a Q, and there is still 1 element available that used to contain the letter B.

A generic ring buffer

Ring buffers can be useful for buffering data of different types. Most commonly, you will find ring buffers that just buffer generic data as a buffer of bytes. But in audio applications for example, it makes more sense to buffer audio samples, which are commonly stored as 16-bit signed integers (Int16 or SmallInt in Delphi) or single-precision floating-point values (Single in Delphi). When audio is stored in interleaved stereo format, each sample can be represented as a record with two values (for the left and right channels).

So why not create a generic ring buffer that can be used with different types? We made one just for you called TgoRingBuffer<T>. You can find it in the unit Grijjy.Collections in the GrijjyFoundation repository.

Using the ring buffer

The API for the ring buffer is fairly simple:

type
  TgoRingBuffer<T: record> = class
  public
    constructor Create(const ACapacity: Integer);

    function Write(const AData: TArray<T>): Integer; overload;
    function Write(const AData: array of T): Integer; overload;
    function Write(const AData: array of T; const AIndex, ACount: Integer): Integer; overload;
    function TryWrite(const AData: array of T): Boolean; overload;
    function TryWrite(const AData: array of T; const AIndex, ACount: Integer): Boolean; overload;

    function Read(var AData: array of T): Integer; overload;
    function Read(var AData: array of T; const AIndex, ACount: Integer): Integer; overload;
    function TryRead(var AData: array of T): Boolean; overload;
    function TryRead(var AData: array of T; const AIndex, ACount: Integer): Boolean; overload;

    property Capacity: Integer read FCapacity;
    property Count: Integer read FCount;
    property Available: Integer read GetAvailable;
  end;

You create a ring buffer by passing the capacity to the constructor. This is the number of elements (of type T) that the ring buffer will hold. The ring buffer will never grow beyond this capacity.

You can retrieve the capacity through the Capacity property. There is also a Count property which returns the number of elements currently in the buffer (available for reading). And finally an Available property that returns the number of available (free) items in the ring buffer (available for writing). All these properties returns the number of elements (of type T), not the number of bytes.

The remainder of the API consists of read and write methods on a couple of variations:

• Every method comes in 2 variations: one where the data is passed as a dynamic array (TArray<T>) and one where the data is passed as an open array (array of T). This gives some flexibility in how you want to use it. The implementation is the same though. We didn’t show all these variations above for brevity.
• The Read methods do not create an array. Instead you pass in a pre-allocated array (which can be static of dynamic).
• Also, there are regular Read and Write methods and TryRead and TryWrite variations. The regular versions try to read (or write) the number of elements you specify, but may read or write fewer elements if not enough elements (or free space) is available. These methods return the actual number of elements that are read (or written). The Try* versions will either try to read (or write) the amount you specify, or fail if not enough elements (or free space) is available. The entire operation either succeeds or fails (as indicated by the returned Boolean value).
• Finally, for every method there is an overload that reads (or writes) only a segment of the array. Here, the AIndex parameter is the start index into the array, and ACount specifies the number of elements to read (or write), starting at AIndex.

Notice that unlike other (generic) collections such as lists, stacks and queues, you don’t work with individual values. Instead, you read or write an array of values. This emphasises that this class is typically used for streaming and/or buffering applications.

Example usage

Let’s say we want to reproduce the example presented above. We need to create a ring buffer containing 16 elements of type Char and write 11 characters (A–K) to it:

var
  RingBuffer: TgoRingBuffer<Char>;
begin
  RingBuffer := TgoRingBuffer<Char>.Create(16);
  RingBuffer.Write(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']);
  ...

The result will be the first image we showed:

We can also show this as a “flat” array (which is actually how the ring buffer is implemented):

We the read two elements to a static array, starting at position 0 of that array:

{ Reserve some space to read data from the ring buffer: }
var
  ReadBuffer: array [0..9] of Char;
  Count: Integer;

{ Read data }
Count := RingBuffer.Read(ReadBuffer, 0, 2);
Assert(Count = 2);

There are 7 positions available now: 5 empty ones and 2 that were previously occupied by A and B. So writing 6 more elements results in this:

Count := RingBuffer.Write(['L', 'M', 'N', 'O', 'P', 'Q']);
Assert(Count = 6);

If we try to write 3 elements now, only 1 will fit:

Count := RingBuffer.Write(['R', 'S', 'T']);
Assert(Count = 1);

At this point, the ring buffer is full and you cannot write to it anymore until you read some data. You can read up to 16 elements (C–R) now.

Usage notes

As you may have spotted from the record constraint in the class declaration, you can only use the ring buffer with value types (such as integer types, character types, floating-point types, enums and records):

type
  TgoRingBuffer<T: record> = class
  ...
  end;

You cannot use a ring buffer with reference types (such as strings or objects).

This makes sense, since a ring buffer is used to buffer data, not objects. With this constraint, we can optimize and simplify the implementation of this class since we don’t have to take reference types into account.

Now you may think: “well, then I will just wrap a reference type in a record”, like this:

type
  TWrappedString = record
    Value: String;
  end;

var
  RingBuffer: TgoRingBuffer<TWrappedString>;

While this will compile, it will raise an assertion at run-time since we check if the type is a managed type in the constructor:

constructor TgoRingBuffer<T>.Create(const ACapacity: Integer);
begin
  Assert(not IsManagedType(T));
  inherited Create;
  ...
end;

The IsManagedType compiler magic function returns True if the given type is a memory-managed type, such as a string or object interface. It also returns True if the type itself is not managed (such as a record), but it contains a managed type (such as the String field in the example above).

On non-ARC platforms, you will still be able to use this “hack” to wrap an object. But this will not work on ARC platforms, since objects are managed there as well.

Wrapping up

That wraps up our discussion of ring buffers.

If you want to expand your collection of Collections some more, then stay tuned for another post in this series.

As always, feel free to share your thoughts and leave a comment.