Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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)
}
}
@kuvark

This comment has been minimized.

Copy link

@kuvark kuvark commented Mar 6, 2015

Is there any usage of Queue in for loop?

I need to get values with for loop, can you advice sth?

@kareman

This comment has been minimized.

Copy link
Owner Author

@kareman 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

This comment has been minimized.

Copy link

@kuvark kuvark commented Mar 6, 2015

Thank you so much.

@NicholasSterling

This comment has been minimized.

Copy link

@NicholasSterling NicholasSterling commented May 29, 2015

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

@clayheaton

This comment has been minimized.

Copy link

@clayheaton clayheaton commented Aug 5, 2015

testAddNil() causes problems in Swift 2.0, fyi.

@honghaoz

This comment has been minimized.

Copy link

@honghaoz honghaoz commented Aug 14, 2016

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

@kareman

This comment has been minimized.

Copy link
Owner Author

@kareman 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

This comment has been minimized.

Copy link
Owner Author

@kareman kareman commented May 26, 2017

This is released under an MIT License

@csujedihy

This comment has been minimized.

Copy link

@csujedihy csujedihy commented Jul 11, 2017

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

This comment has been minimized.

Copy link
Owner Author

@kareman kareman commented Jul 31, 2020

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