项目总结-无锁队列的链表实现

本文主要是介绍项目总结-无锁队列的链表实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先，无锁队列的实现基于原子操作CAS（_sync_vale_compare_and_swap）
GCC下的CAS实现：

bool __sync_bool_compare_and_swap (type *accum, type *dest, type newval){if(*accum==*dest){*dest=newval;return true;}return false;
}
type __sync_val_compare_and_swap (type *ptr, type oldval, type newval){type oldval_tmp=*ptr;if(oldval_tmp==oldval)*ptr=newval;return oldval_tmp;
}

C++11中的CAS实现：(跨平台)

template< class T >
bool atomic_compare_exchange_weak( std::atomic* obj,T* expected, T desired );
template< class T >
bool atomic_compare_exchange_weak( volatile std::atomic* obj,T* expected, T desired );

有了CAS实现方式保证原子操作后，编写队列的尾部添加：

Enqueue(type x){node q=new node;q.value=x;q->next=NULL;p=tail;oldp=p;do{while(p-next!=NULL)p=p->next;}while(CAS(p->next,NULL,q)!=TRUE);CAS(tail,oldp,q);}

同理，队列的头部删除：

Dequeue(){do{p=head;if(p->next==NULL)return ERR_EMPTY_QUEUE;}while(CAS(head,p,p->next)!=true)return p->next->val;
}

这篇关于项目总结-无锁队列的链表实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---