LockFreeQueue/lockfree_queue.h at master · lanyutc/LockFreeQueue · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#ifndef _LOCKFREE_QUEUE_
#define _LOCKFREE_QUEUE_

#include <atomic>
#include <map>

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
#define LOCKFREE_CACHELINE_BYTES 64

using namespace std;

template <typename T>
class LFqueue
{
public:
	LFqueue()
	{
		node *n = new node();
		head_.store((unsigned long)n, memory_order_relaxed);
		tail_.store((unsigned long)n, memory_order_release);
	}

	struct node {
		T data;
		atomic_ulong next;

		node(T const &v) : data(v)
		{
			next.store((unsigned long)0, memory_order_release);
		}

		node()
		{
		}
	};


public:
	bool isLockFree() const
	{
		return head_.is_lock_free() && tail_.is_lock_free();
	}

	bool push(T const &t)
	{
		node *n = new node(t);

		if (!n) return false;

		for (;;) {

			unsigned long tail = tail_.load(memory_order_acquire);

			node *tNext   = nextNodePtr(tail_);
			node *tailPtr = nodePtr(tail_);

			unsigned long tail2= tail_.load(memory_order_acquire);
			if (likely(tail == tail2)) {

				if (tNext == 0) {
					unsigned long next = 0;
					if (tailPtr->next.compare_exchange_weak(next, (unsigned long)n)) {
						tail_.compare_exchange_strong(tail, (unsigned long)n);
						return true;
					}
				} else {
					tail_.compare_exchange_strong(tail, (unsigned long)tNext);
				}

			}
		}
	}

	bool pop(T &ret)
	{
		for (;;) {
			unsigned long head = head_.load(memory_order_acquire);
			unsigned long tail = tail_.load(memory_order_acquire);

			node *hNext   = nextNodePtr(head_);
			node *headPtr = nodePtr(head_);

			unsigned long head2= head_.load(memory_order_acquire);
			if (likely(head == head2)) {

				if (head == tail) {
					if (hNext == 0) return false;

					tail_.compare_exchange_strong(tail, (unsigned long)hNext);
				} else {
					if (hNext == 0) continue;

					ret = hNext->data;
					if (head_.compare_exchange_weak(head, (unsigned long)hNext)) {
						delete headPtr;
						return true;
					}
				}

			}
		}
	}

private:
	node *nodePtr(const atomic_ulong &a)
	{
		return reinterpret_cast<node *>(a.load(memory_order_acquire));
	}

	node *nextNodePtr(const atomic_ulong &a)
	{
		node *n = nodePtr(a);
		if (n) {
			return nodePtr(n->next);
		}
		return 0;
	}

private:
	atomic_ulong head_;
	static const int PaddingSize = LOCKFREE_CACHELINE_BYTES - sizeof(unsigned long);
	char padding1[PaddingSize];
	atomic_ulong tail_;
	char padding2[PaddingSize];
};


#endif