LocklessQueue

LocklessQueue.swift

//
//  LocklessQueue.swift
//  Famera
//
//  Created by Andrew Pouliot on 11/11/20.
//  Copyright © 2020 Famera. All rights reserved.
//

import Foundation
import CoreMedia

// Simple swift wrapper around a CMSimpleQueue
public class LocklessQueue<Type> {
    
    private let queue: CMSimpleQueue
    
    deinit {
        // Ok this might not be 100% correct yet but I'm going to assume that you are not still trying to dequeue or enqueue while this is running
        var o: Type? = nil
        repeat {
            o = dequeue()
        } while o != nil
    }
    
    // Simple type we can allocate that can store our type
    private struct Box {
        let value: Type
    }
    
    public init(capacity: Int) throws {
        self.queue = try CMSimpleQueue(capacity: capacity)
    }
    
    public var head: Type? {
        if let ptr = queue.head {
            return ptr.assumingMemoryBound(to: Box.self).pointee.value
        } else {
            return nil
        }
    }

    // Returns whether the value was enqueued
    @discardableResult
    public func enqueue(_ value: Type) -> Bool {
        // Make a heap-allocated Box to put in our queue
        let heap = UnsafeMutablePointer<Box>.allocate(capacity: 1)
        heap.initialize(to: Box(value: value))
        do {
            try queue.enqueue(heap)
            return true
        } catch {
            return false
        }
    }
    
    public func dequeue() -> Type? {
        guard let ptr = queue.dequeue() else { return nil }
        let typedPtr = UnsafeMutablePointer(mutating: ptr.assumingMemoryBound(to: Box.self))
        let box = typedPtr.pointee
        typedPtr.deinitialize(count: 1)
        typedPtr.deallocate()
        return box.value
    }
    
    public var capacity: Int {
        return queue.capacity
    }
    
    public var count: Int {
        return queue.count
    }
    
}

LocklessQueueTests.swift

//
//  LocklessQueueTests.swift
//  Famera
//
//  Created by Andrew Pouliot on 11/11/20.
//  Copyright © 2020 Famera. All rights reserved.
//

import XCTest

class LocklessQueueTests: XCTestCase {

    func testBasic() throws {
        let q = try! LocklessQueue<Int>(capacity: 3)
        XCTAssertEqual(q.count, 0)
        q.enqueue(1)
        XCTAssertEqual(q.count, 1)
        let _ = q.dequeue()
        XCTAssertEqual(q.count, 0)
    }

    struct GenericStruct: Equatable {
        let a: Float
        let b: Int
    }
    
    func testStruct() throws {
        let q = try! LocklessQueue<GenericStruct>(capacity: 3)
        XCTAssertEqual(q.count, 0)
        let a = GenericStruct(a: 1, b: 1)
        q.enqueue(a)
        XCTAssertEqual(q.count, 1)
        let b = q.dequeue()
        XCTAssertEqual(a, b)
        XCTAssertEqual(q.count, 0)
    }
    
    struct GenericStructWithClass: Equatable {
        let a: NSObject
    }
    func testStructWithClass() throws {
        let q = try! LocklessQueue<GenericStructWithClass>(capacity: 3)
        XCTAssertEqual(q.count, 0)
        let o = NSObject()
        let a = GenericStructWithClass(a: o)
        q.enqueue(a)
        q.enqueue(a)
        XCTAssertEqual(q.count, 2)
        let b = q.dequeue()
        let _ = q.dequeue()
        XCTAssertEqual(a, b)
        XCTAssertEqual(q.count, 0)

    }
    
    static var objectCount = 0
    
    class TrackedObject {
        init() {
            objectCount += 1
        }
        deinit {
            objectCount -= 1
        }
        func dummy() {}
    }
    
    func testTrackedObject() {
        Self.objectCount = 0
        autoreleasepool {
            var a = TrackedObject()
            a = TrackedObject()
            // Just shut the compiler up about "'a' written to, but never read"
            a.dummy()
        }
        XCTAssertEqual(Self.objectCount, 0)
    }
    
    func testObjectsRemainingInQueueDealloc() {
        Self.objectCount = 0
        var q = try? LocklessQueue<TrackedObject>(capacity: 3)
        q?.enqueue(TrackedObject())
        q?.enqueue(TrackedObject())
        q?.enqueue(TrackedObject())
        
        XCTAssertEqual(Self.objectCount, 3)
        XCTAssertEqual(q!.count, 3)
        
        autoreleasepool {
            let _ = q?.dequeue()
        }
        XCTAssertEqual(Self.objectCount, 2)
        
        q = nil
        XCTAssertEqual(Self.objectCount, 0)
    }
    
    func testPerformance() throws {
        // This is an example of a performance test case.
        self.measure {
            let q = try! LocklessQueue<GenericStruct>(capacity: 3)
            for i in 0 ..< 100_000 {
                q.enqueue(GenericStruct(a: 1, b: i))
                q.enqueue(GenericStruct(a: Float(i), b: 1))
                let _ = q.dequeue()
                let _ = q.dequeue()
            }
        }
    }

}