Class: FixedSizeBuffer

Inherits:
Object
  • Object
show all
Defined in:
lib/fixed_size_buffer.rb,
lib/fixed_size_buffer/version.rb

Overview

A ring buffer with a fixed capacity

Principal of Operation

A ring buffer is a continuously writable and continuously readable data structure that is contained in a fixed amount of memory. It can be conceptualized as writing values around a circular array. As we write, we move clockwise around the circle, and reading trails around in the same direction.

If the reader catches up to the writer, the buffer is empty. If the writer wraps around and catches up to the reader, the buffer is full. In our case, we allow the writer to continue writing to a full buffer, which causes the oldest values to be dropped.

Implementation

This ring buffer is implemented as a fixed-size array. We also maintain a read index and a write index. These are the positions where the next read or write will occur. We increase the write pointer by one each time we write to the buffer. We also increase the read pointer by one every time we read.

The buffer is considered empty if the read and write pointers are in the same position. In this state, reading will not move the read pointer, and nil will be returned.

An empty buffer of capacity 3.

       rw
|  |  |  |  |

The buffer is considered full if the write pointer is in the position immediately before the read pointer. In this state, writing will overwrite the next position, which will be the oldest value in the buffer. Writing in this state will also move the read pointer forward so that the next read will continue from the next-oldest value.

A full buffer of capacity 3. Note that the 2 here is already considered overwritten.

      w   r
| 5 | 2 | 3 | 4 |

Another full buffer with the same values but in a wrapped-around position.

  r           w
| 3 | 4 | 5 | 2 |

Notice that the array for this buffer has one extra position. This is used to differentiate between an empty buffer (read/write pointers in same position), and a full buffer (write pointer just before read pointer). The value in-between the read and write pointers for a full buffer will not be read.

Constant Summary collapse

VERSION =

The current FixedSizeBuffer gem version

'0.1.2'

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(capacity) ⇒ FixedSizeBuffer

Create a new empty FixedSizeBuffer

Start state

 rw
|  |  |  |  |

Parameters:

  • capacity (Integer) —

    The number of items this buffer can hold



74
75
76
77
78
79
 
# File 'lib/fixed_size_buffer.rb', line 74

def initialize(capacity)
  @capacity = capacity
  @buffer = Array.new(capacity + 1)
  @read = 0
  @write = 0
end

Instance Attribute Details

#capacity ⇒ Object (readonly)

The capacity given to new



62
63
64
 
# File 'lib/fixed_size_buffer.rb', line 62

def capacity
  @capacity
end

Class Method Details

.version ⇒ Object 



7
8
9
 
# File 'lib/fixed_size_buffer/version.rb', line 7

def self.version
  Gem::Version.new(VERSION)
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


136
137
138
139
 
# File 'lib/fixed_size_buffer.rb', line 136

def empty?
  # When empty, the read and write pointers will be in the same place.
  @read == @write
end

#full? ⇒ Boolean

Is the buffer full?

A full buffer does not prevent writes, but it does mean that the next write will overwrite an unread value.

Returns:

  • (Boolean) —

    True if the buffer is full



130
131
132
133
134
 
# File 'lib/fixed_size_buffer.rb', line 130

def full?
  # When full, the write pointer will be one less than the read pointer
  # (mod buffer size).
  (@write + 1) % @buffer.size == @read
end

#peek ⇒ Object?

Read a value from the buffer without consuming it

Like #read, this will return nil when the buffer is empty, so check #empty if you need to distinguish between the two states.

Returns:

  • (Object, nil) —

    The value that was read, or nil if empty



102
103
104
105
106
 
# File 'lib/fixed_size_buffer.rb', line 102

def peek
  return nil if empty?

  @buffer[@read]
end

#read ⇒ Object?

Read one value from the buffer

The value will be "consumed", meaning it will no longer be readable. If the buffer is empty, this will return nil, so if it matters, check empty? before calling read.

Returns:

  • (Object, nil) —

    The value that was read, or nil if empty



88
89
90
91
92
93
94
 
# File 'lib/fixed_size_buffer.rb', line 88

def read
  return nil if empty?

  value = @buffer[@read]
  @read = (@read + 1) % @buffer.size
  value
end

#size ⇒ Integer

The number of unread items

Returns:

  • (Integer) —

    The buffer size



144
145
146
147
148
149
150
 
# File 'lib/fixed_size_buffer.rb', line 144

def size
  if @write >= @read
    @write - @read
  else
    @buffer.size - @read + @write
  end
end

#to_a ⇒ Array<Object>

Get an array of all the unread items in the buffer

Unlike #read, this does not consume buffer items

Returns:

  • (Array<Object>) —

    An array having length of #size



157
158
159
160
161
162
163
 
# File 'lib/fixed_size_buffer.rb', line 157

def to_a
  if @write >= @read
    @buffer[@read...@write]
  else
    @buffer[@read...@buffer.size] + @buffer[0...@write]
  end
end

#write(value) ⇒ void

This method returns an undefined value.

Write one value to the buffer

Write a value to thee buffer

Parameters:

  • value (Object) —

    The value to write



114
115
116
117
118
119
120
121
122
 
# File 'lib/fixed_size_buffer.rb', line 114

def write(value)
  @buffer[@write] = value

  # If the buffer is full before a write, we drop the oldest value by
  # moving the read pointer as well
  @read = (@read + 1) % @buffer.size if full?
  @write = (@write + 1) % @buffer.size
  nil
end