Skip to content

Instantly share code, notes, and snippets.

@kareman
Last active July 31, 2020 19:16
Show Gist options
  • Save kareman/931017634606b7f7b9c0 to your computer and use it in GitHub Desktop.
Save kareman/931017634606b7f7b9c0 to your computer and use it in GitHub Desktop.
A standard queue (FIFO - First In First Out) implemented in Swift. Supports simultaneous adding and removing, but only one item can be added at a time, and only one item can be removed at a time. Using the "Two-Lock Concurrent Queue Algorithm" from http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html#tlq, without the locks.
//
// Queue.swift
// NTBSwift
//
// Created by Kåre Morstøl on 11/07/14.
//
// Using the "Two-Lock Concurrent Queue Algorithm" from http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html#tlq, without the locks.
// should be an inner class of Queue, but inner classes and generics crash the compiler, SourceKit (repeatedly) and occasionally XCode.
class _QueueItem<T> {
let value: T!
var next: _QueueItem?
init(_ newvalue: T?) {
self.value = newvalue
}
}
///
/// A standard queue (FIFO - First In First Out). Supports simultaneous adding and removing, but only one item can be added at a time, and only one item can be removed at a time.
///
public class Queue<T> {
typealias Element = T
var _front: _QueueItem<Element>
var _back: _QueueItem<Element>
public init () {
// Insert dummy item. Will disappear when the first item is added.
_back = _QueueItem(nil)
_front = _back
}
/// Add a new item to the back of the queue.
public func enqueue (value: Element) {
_back.next = _QueueItem(value)
_back = _back.next!
}
/// Return and remove the item at the front of the queue.
public func dequeue () -> Element? {
if let newhead = _front.next {
_front = newhead
return newhead.value
} else {
return nil
}
}
public func isEmpty() -> Bool {
return _front === _back
}
}
//
// QueueTests.swift
//
// Created by Kåre Morstøl on 11/07/14.
// Copyright (c) 2014 NotTooBad Software. All rights reserved.
//
import XCTest
import NTBSwift
class QueueTests: XCTestCase {
func testAdd1ToQueue() {
let sut = Queue<String>()
sut.enqueue("1")
}
func testAddSeveralToQueue() {
let sut = Queue<String>()
XCTAssert(sut.isEmpty())
sut.enqueue("1")
sut.enqueue("1")
XCTAssertFalse(sut.isEmpty())
sut.enqueue("1")
sut.enqueue("1")
sut.enqueue("1")
}
func testRemoveOne() {
let sut = Queue<String>()
sut.enqueue("1")
sut.enqueue("")
sut.enqueue("")
sut.enqueue("")
let thefirstone = sut.dequeue()
XCTAssertNotNil(thefirstone)
XCTAssertEqual(thefirstone!, "1")
}
func testRemoveAll() {
let sut = Queue<String>()
sut.enqueue("1")
sut.enqueue("2")
sut.enqueue("3")
sut.enqueue("4")
XCTAssertEqual(sut.dequeue()!, "1")
XCTAssertEqual(sut.dequeue()!, "2")
XCTAssertEqual(sut.dequeue()!, "3")
XCTAssertEqual(sut.dequeue()!, "4")
XCTAssert(sut.isEmpty())
XCTAssertNil(sut.dequeue())
XCTAssertNil(sut.dequeue())
XCTAssert(sut.isEmpty())
}
func testGenerics() {
let sut = Queue<Int>()
sut.enqueue(1)
sut.enqueue(2)
sut.enqueue(3)
sut.enqueue(4)
XCTAssertEqual(sut.dequeue()!, 1)
XCTAssertEqual(sut.dequeue()!, 2)
XCTAssertEqual(sut.dequeue()!, 3)
XCTAssertEqual(sut.dequeue()!, 4)
}
func testAddNil() {
let sut = Queue<Int?>()
sut.enqueue(nil)
XCTAssertNil(sut.dequeue()?)
sut.enqueue(2)
sut.enqueue(nil)
sut.enqueue(4)
XCTAssertEqual(sut.dequeue()!!, 2)
XCTAssertNil(sut.dequeue()?)
XCTAssertEqual(sut.dequeue()!!, 4)
}
func testAddAfterEmpty() {
let sut = Queue<String>()
sut.enqueue("1")
XCTAssertEqual(sut.dequeue()!, "1")
XCTAssertNil(sut.dequeue())
sut.enqueue("1")
sut.enqueue("2")
XCTAssertEqual(sut.dequeue()!, "1")
XCTAssertEqual(sut.dequeue()!, "2")
XCTAssert(sut.isEmpty())
XCTAssertNil(sut.dequeue())
}
func testAddAndRemoveChaotically() {
let sut = Queue<String>()
sut.enqueue("1")
XCTAssertFalse(sut.isEmpty())
XCTAssertEqual(sut.dequeue()!, "1")
XCTAssert(sut.isEmpty())
XCTAssertNil(sut.dequeue())
sut.enqueue("1")
sut.enqueue("2")
XCTAssertEqual(sut.dequeue()!, "1")
XCTAssertEqual(sut.dequeue()!, "2")
XCTAssert(sut.isEmpty())
XCTAssertNil(sut.dequeue())
sut.enqueue("1")
sut.enqueue("2")
XCTAssertEqual(sut.dequeue()!, "1")
sut.enqueue("3")
sut.enqueue("4")
XCTAssertEqual(sut.dequeue()!, "2")
XCTAssertEqual(sut.dequeue()!, "3")
XCTAssertFalse(sut.isEmpty())
XCTAssertEqual(sut.dequeue()!, "4")
XCTAssertNil(sut.dequeue())
XCTAssertNil(sut.dequeue())
}
func testConcurrency() {
let sut = Queue<Int>()
let numberofiterations = 2_000_00
let addingexpectation = expectationWithDescription("adding completed")
let addingqueue = dispatch_queue_create( "adding", DISPATCH_QUEUE_SERIAL)
dispatch_async(addingqueue) {
for i in 1...numberofiterations {
sut.enqueue(i)
}
addingexpectation.fulfill()
}
let deletingexpectation = expectationWithDescription("deleting completed")
let deletingqueue = dispatch_queue_create( "deleting", DISPATCH_QUEUE_SERIAL)
dispatch_async(deletingqueue) {
for (var i=1; i <= numberofiterations; 0) {
if let result = sut.dequeue() {
XCTAssertEqual(result, i)
i++
} else {
println(" pausing deleting for one second")
sleep(CUnsignedInt(1))
}
}
deletingexpectation.fulfill()
}
waitForExpectationsWithTimeout( 600, handler: nil)
}
}
@kareman
Copy link
Author

kareman commented Mar 6, 2015

You're welcome.

It's best to use a while loop when reading values from the queue:

while let value = queue.dequeue()  {
    // do something with 'value'.
}

@kuvark
Copy link

kuvark commented Mar 6, 2015

Thank you so much.

@NicholasSterling
Copy link

Thanks for this. Would you consider adding a comment to the file saying what license(s) it is offered under?

@clayheaton
Copy link

testAddNil() causes problems in Swift 2.0, fyi.

@honghaoz
Copy link

It seems like this queue leaks one Element size of memory? Since an empty queue always hold on one element.

@kareman
Copy link
Author

kareman commented May 24, 2017

@honghaoz when empty it holds one _QueueItem with 'nil' for value. This is to avoid dealing with empty queue every time you add or remove something.

@kareman
Copy link
Author

kareman commented May 26, 2017

This is released under an MIT License

@csujedihy
Copy link

Where are the locks? The first solution in that MIT article uses CAS which is an atomic operation and what is your workaround for that CAS operation?

@kareman
Copy link
Author

kareman commented Jul 31, 2020 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment