Last active
September 18, 2018 13:54
-
-
Save z64/415d1813f06b6ae91896408f6d26558c to your computer and use it in GitHub Desktop.
An optimized fixed size ring buffer implementation in Crystal. Designed for quick in-memory storage and serialization of recent event history in web applications
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require "json" | |
# Optimized implementation of a fixed sized ring buffer that exposes | |
# a simple and "safe" API of `#push` and `#to_a`. `#push`ing to a full | |
# buffer erases the oldest member. | |
# | |
# ``` | |
# # Create a new buffer of Int32, with size 3 | |
# buffer = StaticRingBuffer(Int32, 3).new | |
# buffer.push(1) | |
# buffer.push(2) | |
# buffer.push(3) | |
# buffer.push(4) | |
# buffer.to_a # => [2, 3, 4] | |
# ``` | |
class StaticRingBuffer(T, N) | |
def initialize | |
@buffer = Pointer(T?).malloc(N) { nil } | |
@write_index = 0 | |
end | |
# Push a new element into the buffer | |
def push(elem : T) | |
@buffer[@write_index] = elem | |
@write_index = (@write_index + 1) % N | |
end | |
# Yields each element of the buffer | |
def each | |
N.times do |i| | |
index = (@write_index + i) % N | |
if value = @buffer[index] | |
yield value | |
end | |
end | |
end | |
# Returns a copy of the current buffer as an `Array(T)` | |
def to_a : Array(T) | |
arr = Array(T).new(N) | |
each { |e| arr << e } | |
arr | |
end | |
# Serializes this buffer to a `JSON::Builder` | |
def to_json(builder : JSON::Builder) | |
builder.array do | |
each { |e| e.to_json(builder) } | |
end | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require "spec" | |
require "./static_ring_buffer" | |
describe StaticRingBuffer do | |
it "acts as a fixed size ring buffer" do | |
buffer = StaticRingBuffer(Int32, 3).new | |
buffer.push(1) | |
buffer.push(2) | |
buffer.push(3) | |
buffer.push(4) | |
buffer.to_a.should eq [2, 3, 4] | |
end | |
it "serializes to JSON" do | |
arr = [1, 2, 3] | |
buffer = StaticRingBuffer(Int32, 3).new | |
arr.each { |i| buffer.push(i) } | |
buffer.to_json.should eq arr.to_json | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require "./static_ring_buffer" | |
record(Message, id : Int32, content : String) { include JSON::Serializable } | |
buffer = StaticRingBuffer(Message, 3).new | |
messages = { | |
Message.new(1, "a"), | |
Message.new(2, "b"), | |
Message.new(3, "c"), | |
Message.new(4, "d"), | |
Message.new(5, "e"), | |
} | |
messages.each do |message| | |
buffer.push(message) | |
# puts buffer.to_a | |
puts buffer.to_json | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
[{"id":1,"content":"a"}] | |
[{"id":1,"content":"a"},{"id":2,"content":"b"}] | |
[{"id":1,"content":"a"},{"id":2,"content":"b"},{"id":3,"content":"c"}] | |
[{"id":2,"content":"b"},{"id":3,"content":"c"},{"id":4,"content":"d"}] | |
[{"id":3,"content":"c"},{"id":4,"content":"d"},{"id":5,"content":"e"}] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment