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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
#pragma once
#include <windows.h>
/* lock free stack object
multiple threads can push and pop without locking
note that order is not guaranteed. that is, if Thread 1 calls Insert before Thread 2, Thread 2's item might still make it in before.
since it uses malloc/free for the linked list nodes, it might not be considered truely lock-free.
use LockFreeStack2 if you can assure that you have a 'next' pointer in your class/struct
*/
template <class value_t>
class LockFreeStackNode
{
public:
LockFreeStackNode(value_t _data)
{
data = _data;
next = 0;
}
value_t data;
LockFreeStackNode *next;
};
template <class value_t>
class LockFreeStack
{
public:
LockFreeStack()
{
head = 0;
}
void push(value_t data)
{
LockFreeStackNode<value_t> *new_head = new LockFreeStackNode<value_t>(data);
LockFreeStackNode<value_t> *old_head = 0;
do
{
old_head = (LockFreeStackNode<value_t> *)head;
new_head->next = old_head;
} while (InterlockedCompareExchangePointer((volatile PVOID *)&head, new_head, old_head) != old_head);
}
value_t pop()
{
LockFreeStackNode<value_t> *new_head = 0, *old_head = 0;
do
{
old_head = (LockFreeStackNode<value_t> *)head;
if (old_head)
{
new_head = old_head->next;
}
else
{
new_head = 0;
}
} while (InterlockedCompareExchangePointer((volatile PVOID *)&head, new_head, old_head) != old_head);
value_t ret = old_head?old_head->data:0;
delete old_head;
return ret;
}
bool pop_ref(value_t *val)
{
LockFreeStackNode<value_t> *new_head = 0, *old_head = 0;
do
{
old_head = (LockFreeStackNode<value_t> *)head;
if (old_head)
{
new_head = old_head->next;
}
else
{
new_head = 0;
}
} while (InterlockedCompareExchangePointer((volatile PVOID *)&head, new_head, old_head) != old_head);
if (old_head)
{
*val = old_head->data;
delete old_head;
return true;
}
return false;
}
volatile LockFreeStackNode<value_t> *head;
};
template <class value_t>
class LockFreeStack2
{
public:
LockFreeStack()
{
head = 0;
}
void push(value_t *data)
{
value_t *old_head = 0;
do
{
old_head = head;
data->next = old_head;
} while (InterlockedCompareExchangePointer((volatile PVOID *)&head, data, old_head) != old_head);
}
value_t *pop()
{
value_t *new_head = 0, *old_head = 0;
do
{
old_head = head;
if (old_head)
{
new_head = old_head->next;
}
else
{
new_head = 0;
}
} while (InterlockedCompareExchangePointer((volatile PVOID *)&head, new_head, old_head) != old_head);
return old_head;
}
bool pop_ref(value_t **val)
{
value_t *new_head = 0, *old_head = 0;
do
{
old_head = head;
if (old_head)
{
new_head = old_head->next;
}
else
{
new_head = 0;
}
} while (InterlockedCompareExchangePointer((volatile PVOID *)&head, new_head, old_head) != old_head);
if (old_head)
{
*val = old_head;
return true;
}
return false;
}
volatile value_t *head;
};
|
