RingBuffer.swift

//: 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)")
}