May 282014
 

Java has a very useful class called the BlockingQueue. With a blocking queue, the dequeue operation will block until there is something to be dequeued. A blocking queue is very handy and can be used to solve the classic producer-consumer problem. I needed a similar class in Objective-C, but I could not find one. The following is a simple implementation.

Queue Implementation

The queue is implemented using NSMutableArray. A queue is a FIFO (First In, First Out) data structure, so enqueue adds an object to the end of the array (simple addObject suffices). Dequeue simply returns the first object in the array, and then removes it from the array (items are effectively shifted up a slot after the deletion).

Locking and Thread Synchronization

NSCondition is used for locking and thread synchronization. If you have two threads sharing a resource (the queue in our case), you will have the following code for the producer and the consumer.

The consumer:

[lock lock];
while (!someValueIsTrue) 
{
    [lock wait];
}
// Do protected work (in our case, dequeue)
[lock unlock]

The producer:

[lock lock];
// Do protected work (in our case, enqueue)
someValueIsTrue = true;
[lock signal];  
[lock unlock];

The Implementation

Here is the implementation of enqueue and dequeue. It is very simple and generally follows the pattern above. Remember, queueing and dequeueing must happen on different threads, so I am using a dispatch queue. If you call NSCondition’s lock in the same thread, you will get a deadlock.

- (void)enqueue:(id)object
{
    [_lock lock];
    [_queue addObject:object];
    [_lock signal];
    [_lock unlock];
}

- (id)dequeue
{
    __block id object;
    dispatch_sync(_dispatchQueue, ^{
        [_lock lock];
        while (_queue.count == 0)
        {
            [_lock wait];
        }
        object = [_queue objectAtIndex:0];
        [_queue removeObjectAtIndex:0];
        [_lock unlock];
    });
    
    return object;
}

Source Code and Sample

I hope this has been helpful to someone.

You can find the complete implementation along with sample code in my Github repository.

 Posted by at 3:49 pm

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)