Skip to content

Instantly share code, notes, and snippets.

@ocrickard
Last active October 2, 2021 15:01
Show Gist options
  • Save ocrickard/d222f9d744fee2ad0fdee53625d42ded to your computer and use it in GitHub Desktop.
Save ocrickard/d222f9d744fee2ad0fdee53625d42ded to your computer and use it in GitHub Desktop.
//: Playground - noun: a place where people can play
import Foundation
import UIKit
import Darwin.os.lock
/**
A threadsafe, non-blocking (on the write side), zero-allocation ring-buffer implementation.
This ring buffer pre-allocates the target type into a contiguous buffer. From one thread you can write to the buffer
with zero heap allocations, and on another thread you can read the buffer.
We use an unfair lock, which is basically a glorified spinlock. This means that the locks are extremely low-cost.
However, we go one step further in this circular buffer, and by default we use trylock.
*/
class RingBuffer<T> {
private let capacity: Int
private let lock: os_unfair_lock_t
private var buffer: UnsafeMutablePointer<T>
/**
Note that these are always incrementing, and then we use the modulus to index into the buffer. On 64-bit phones
this shouldn't ever impact you.
*/
private var readIndex: Int = 0
private var writeIndex: Int = 0
public init(capacity: Int,
initial: T) {
assert(capacity > 0)
self.lock = os_unfair_lock_t.allocate(capacity: 1)
self.lock.initialize(to: os_unfair_lock_s(), count: 1)
self.capacity = capacity
self.buffer = UnsafeMutablePointer<T>.allocate(capacity: capacity)
self.buffer.initialize(to: initial, count: capacity)
}
deinit {
lock.deinitialize(count: 1)
lock.deallocate(capacity: 1)
buffer.deinitialize(count: capacity)
buffer.deallocate(capacity: capacity)
}
/**
Threadsafe read operation from the buffer.
*/
@discardableResult public func read(_ reader: (UnsafePointer<T>) -> ()) -> Status {
os_unfair_lock_lock(lock); defer { os_unfair_lock_unlock(lock) }
if readIndex < writeIndex {
reader(buffer.advanced(by: readIndex % capacity))
readIndex += 1
return .ok
}
return .error(error: ReadError.nothingToRead)
}
@discardableResult public func write(wait: Bool = false, _ writer: (UnsafeMutablePointer<T>) -> ()) -> Status {
if (wait) {
// We've been told we have to wait for the lock to become available, so we block on the lock.
os_unfair_lock_lock(lock)
} else if !os_unfair_lock_trylock(lock) {
// If we don't have to wait, then we just try locking the mutex, and inform the caller if we can't
// achieve the lock. It's then up to the caller to decide if they want to call again with wait = true,
// or if they'd rather just bail and try again later.
return .error(error: WriteError.contention)
}
defer { os_unfair_lock_unlock(lock) }
if writeIndex - readIndex >= capacity {
return .error(error: WriteError.overflow)
} else {
writer(buffer.advanced(by: writeIndex % capacity))
writeIndex += 1
return .ok
}
}
public enum ReadError: Error {
/* There's nothing left to read in the buffer */
case nothingToRead
}
public enum WriteError: Error {
/* We're beyond capacity in the buffer. We have to wait for the reader to catch up. */
case overflow
/* The buffer is busy servicing another thread. Try again later, or call again with wait=true. */
case contention
}
public enum Status {
case ok
case error(error: Error)
}
}
let buffer: RingBuffer<CGRect> = RingBuffer(capacity: 3,
initial: CGRect(x: 0, y: 0, width: 0, height: 0))
buffer.write { (ptr: UnsafeMutablePointer<CGRect>) in
ptr.pointee = CGRect(x: 0, y: 0, width: 1110, height: 10)
}
buffer.write { (ptr: UnsafeMutablePointer<CGRect>) in
ptr.pointee = CGRect(x: 0, y: 0, width: 1110, height: 10)
}
buffer.write { (ptr: UnsafeMutablePointer<CGRect>) in
ptr.pointee = CGRect(x: 0, y: 0, width: 1110, height: 10)
}
buffer.write { (ptr: UnsafeMutablePointer<CGRect>) in
ptr.pointee = CGRect(x: 0, y: 0, width: 1110, height: 10)
}
buffer.read { (ptr: UnsafePointer<CGRect>) in
print("\(ptr.pointee)")
}
buffer.read { (ptr: UnsafePointer<CGRect>) in
print("\(ptr.pointee)")
}
buffer.write { (ptr: UnsafeMutablePointer<CGRect>) in
ptr.pointee = CGRect(x: 2, y: 0, width: 1110, height: 10)
}
buffer.read { (ptr: UnsafePointer<CGRect>) in
print("\(ptr.pointee)")
}
buffer.read { (ptr: UnsafePointer<CGRect>) in
print("\(ptr.pointee)")
}
buffer.read { (ptr: UnsafePointer<CGRect>) in
print("\(ptr.pointee)")
}
struct Arbitrary {
let str: String
let int: Int
}
let buff2: RingBuffer<Arbitrary> = RingBuffer(capacity: 3,
initial: Arbitrary(str: "", int: 0))
buff2.write { (ptr: UnsafeMutablePointer<Arbitrary>) in
ptr.pointee = Arbitrary(str: "hello world", int: 10000)
}
buff2.write { (ptr: UnsafeMutablePointer<Arbitrary>) in
ptr.pointee = Arbitrary(str: "hello world", int: 10000)
}
buff2.read { (ptr: UnsafePointer<Arbitrary>) in
print("\(ptr.pointee)")
}
buff2.read { (ptr: UnsafePointer<Arbitrary>) in
print("\(ptr.pointee)")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment