Skip to content

Instantly share code, notes, and snippets.

@tstellanova
Created March 13, 2015 20:09
Show Gist options
  • Save tstellanova/b21c2e26b502459f0a69 to your computer and use it in GitHub Desktop.
Save tstellanova/b21c2e26b502459f0a69 to your computer and use it in GitHub Desktop.
Lockfree queue using only C++0x features (g++ 4.6)
/**
* A lock-free queue for sharing messages across threads
* Requires C++0x but nothing later (as many current such things do)
* ref: Herb Sutter, "A Corrected One-Producer, One-Consumer Lock-Free Queue"
* http://www.drdobbs.com/parallel/writing-lock-free-code-a-corrected-queue/210604448
*/
template <typename T>
class LockFreeQueue {
private:
/**
* inner container for the type we're interested in
*/
struct Node {
Node( T val ) : value(val), next(nullptr) { }
T value;
Node* next;
};
Node* first;///< for producer only
atomic<Node*> divider, last;///< shared
public:
LockFreeQueue() {
// create an empty Node to separate
// consumer and producer "sides" of the list
first = divider = last = new Node( T() );
}
~LockFreeQueue() {
// release the list
while( first != nullptr ) {
Node* tmp = first;
first = tmp->next;
delete tmp;
}
}
void Produce( const T& t ) {
last->next = new Node(t);// add the new item
last = last->next; // publish it
while( first != divider ) { // trim unused nodes
Node* tmp = first;
first = first->next;
delete tmp;
}
}
bool Consume( T& result ) {
if( divider != last ) { // if queue is nonempty
result = divider->next->value;// C: copy it back
divider = divider->next;// D: publish that we took it
return true;//report success
}
return false;//report empty
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment