Skip to content

Instantly share code, notes, and snippets.

@inspirit
Created June 12, 2015 23:04
Show Gist options
  • Save inspirit/4e765241f6ece6c17ea3 to your computer and use it in GitHub Desktop.
Save inspirit/4e765241f6ece6c17ea3 to your computer and use it in GitHub Desktop.
Objective-C LinkedBlockingQueue
#import <Foundation/Foundation.h>
@interface LinkedBlockingQueue : NSObject
{
// NOP
}
@property(nonatomic, readonly) NSUInteger count;
@property(nonatomic, readonly) NSUInteger freeCount;
- (void)enqueue:(id)object;
- (id)dequeue;
- (void)clear;
@end
#import <libkern/OSAtomic.h>
#import "LinkedBlockingQueue.h"
@interface QueueItem : NSObject
@end
@interface QueueItem()
{
@public
id value;
QueueItem* next;
}
+ (instancetype)create;
+ (instancetype)createWithValue:(id)val;
@end
@implementation QueueItem
+ (instancetype)create
{
QueueItem *obj = [[[self class] alloc] init];
return obj;
}
+ (instancetype)createWithValue:(id)val
{
QueueItem *obj = [[[self class] alloc] initWithValue:val];
return obj;
}
- (instancetype) init
{
self = [super init];
if (self) {
value = nil;
next = nil;
}
return self;
}
- (instancetype) initWithValue:(id)val
{
self = [super init];
if (self) {
value = val;
next = nil;
}
return self;
}
@end
@interface LinkedBlockingQueue()
{
QueueItem* _front;
QueueItem* _back;
QueueItem* _freeListFront;
QueueItem* _freeListBack;
OSSpinLock _freeListFrontLock;
OSSpinLock _freeListBackLock;
OSSpinLock _frontLock;
OSSpinLock _backLock;
NSUInteger _count;
NSUInteger _freeCount;
}
- (void)clearFreeList;
@end
@implementation LinkedBlockingQueue
- (id)init
{
self = [super init];
if (self)
{
_front = _back = [QueueItem create];
_frontLock = OS_SPINLOCK_INIT;
_backLock = OS_SPINLOCK_INIT;
_count = 0;
// free list
_freeListFront = _freeListBack = [QueueItem create];
_freeListFrontLock = OS_SPINLOCK_INIT;
_freeListBackLock = OS_SPINLOCK_INIT;
_freeCount = 0;
}
return self;
}
- (void)dealloc
{
[self clear];
[self clearFreeList];
}
- (QueueItem*)makeQueueItem:(id)object
{
OSSpinLockLock(&_freeListFrontLock);
QueueItem* node = _freeListFront;
QueueItem* newhead = node->next;
if(newhead)
{
_freeListFront = newhead;
_freeCount--;
OSSpinLockUnlock(&_freeListFrontLock);
node->value = object;
node->next = nil;
return node;
}
OSSpinLockUnlock(&_freeListFrontLock);
return [QueueItem createWithValue:object];
}
- (void)recycleQueueItem:(QueueItem*)item
{
OSSpinLockLock(&_freeListBackLock);
item->next = nil;
item->value = nil;
_freeListBack->next = item;
_freeListBack = item;
_freeCount++;
OSSpinLockUnlock(&_freeListBackLock);
}
- (void)clearFreeList
{
OSSpinLockLock(&_freeListFrontLock);
QueueItem* newhead = nil;
while ((newhead = _freeListFront->next)) {
_freeListFront->value = nil;
_freeListFront->next = nil;
_freeListFront = newhead;
_freeCount--;
}
OSSpinLockUnlock(&_freeListFrontLock);
}
- (void)enqueue:(id)object
{
//QueueItem* node = [QueueItem createWithValue:object];
QueueItem* node = [self makeQueueItem:object];
OSSpinLockLock(&_backLock);
_back->next = node;
_back = node;
_count++;
OSSpinLockUnlock(&_backLock);
}
- (id)dequeue
{
id value = nil;
OSSpinLockLock(&_frontLock);
QueueItem* node = _front;
QueueItem* newhead = node->next;
if(newhead)
{
value = newhead->value;
_front = newhead;
_count--;
OSSpinLockUnlock(&_frontLock);
[self recycleQueueItem:node];
return value;
}
OSSpinLockUnlock(&_frontLock);
return value;
}
- (void)clear
{
id node = nil;
while((node = [self dequeue])) {
// NOP
}
}
- (NSUInteger)count
{
return _count;
}
- (NSUInteger)freeCount
{
return _freeCount;
}
@end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment