Created
March 13, 2015 20:09
-
-
Save tstellanova/b21c2e26b502459f0a69 to your computer and use it in GitHub Desktop.
Lockfree queue using only C++0x features (g++ 4.6)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * 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