Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
lockfree queue without hazard pointer
#ifndef LOCKFREE_QUEUE
#define LOCKFREE_QUEUE
#include "atomics.h"
#include <unistd.h> // usleep
#include <stdlib.h> // rand
namespace lockfree{
template<typename T>
class queue{
private:
class Node{
public:
const T mValue;
Node* mNext;
Node(const T& v):mValue(v),mNext(NULL){}
Node():mValue(),mNext(NULL){};
private:
Node(const Node&);
Node& operator=(const Node&);
};
Node *mHead,*mTail;
// uncopyable
queue(const queue&);
queue& operator=(const queue&);
public:
queue():mHead(new Node()),mTail(mHead){ } // sentinel node
void enq(const T& v){
const Node* const node = new Node(v);
while(1){
const Node* const last = mTail;
const Node* const next = last->mNext;
if(last != mTail){ continue; }
if(next == NULL){
if(compare_and_set(&last->mNext, next, node)){
compare_and_set(&mTail, last, node);
return;
}
}else{
compare_and_set(&mTail, last, next);
}
}
}
bool deq(T* value){ // it returns false if there is nothing to deque.
while(1){
const Node* const first = mHead;
const Node* const last = mTail;
const Node* const next = first->mNext;
if(first != mHead){ continue;}
if(first == last){
if(next == NULL){
return false;
}
compare_and_set(&mTail,last,next);
}else{
*value = next->mValue;
if(compare_and_set(&mHead, first, next)){
delete first;
return true;
}
}
}
}
bool deq_delete(){ // it destroys dequed item. but fast.
while(1){
const Node* const first = mHead;
const Node* const last = mTail;
const Node* const next = first->mNext;
if(first != mHead){ continue;}
if(first == last){
if(next == NULL){
return false;
}
compare_and_set(&mTail,last,next);
}else{
if(compare_and_set(&mHead, first, next)){
delete first;
return true;
}
}
}
}
bool empty() const{
return mHead->mNext == NULL;
}
bool size() const{
const Node* it = mHead;
int num;
while(it != NULL){
it = it->mNext;
num++;
}
return num-1;
}
~queue(){
while(deq_delete());
delete mHead;
}
};
}; // namepace lockfree
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment