1 /*
2  *  Copyright (c) 2010 Dmitry Kazakov <dimula73@gmail.com>
3  *
4  *  References:
5  *    * Maged M. Michael, Safe memory reclamation for dynamic
6  *      lock-free objects using atomic reads and writes,
7  *      Proceedings of the twenty-first annual symposium on
8  *      Principles of distributed computing, July 21-24, 2002,
9  *      Monterey, California
10  *
11  *    * Idea of m_deleteBlockers is taken from Andrey Gulin's blog
12  *      https://users.livejournal.com/-foreseer/34284.html
13  *
14  *  This program is free software; you can redistribute it and/or modify
15  *  it under the terms of the GNU General Public License as published by
16  *  the Free Software Foundation; either version 2 of the License, or
17  *  (at your option) any later version.
18  *
19  *  This program is distributed in the hope that it will be useful,
20  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
21  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
22  *  GNU General Public License for more details.
23  *
24  *  You should have received a copy of the GNU General Public License
25  *  along with this program; if not, write to the Free Software
26  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
27  */
28 
29 #ifndef __KIS_LOCKLESS_STACK_H
30 #define __KIS_LOCKLESS_STACK_H
31 
32 #include <QAtomicPointer>
33 
34 template<class T>
35 class KisLocklessStack
36 {
37 private:
38     struct Node {
39         Node *next;
40         T data;
41     };
42 
43 public:
KisLocklessStack()44     KisLocklessStack() { }
~KisLocklessStack()45     ~KisLocklessStack() {
46 
47         freeList(m_top.fetchAndStoreOrdered(0));
48         freeList(m_freeNodes.fetchAndStoreOrdered(0));
49     }
50 
push(T data)51     void push(T data) {
52         Node *newNode = new Node();
53         newNode->data = data;
54 
55         Node *top;
56 
57         do {
58             top = m_top;
59             newNode->next = top;
60         } while (!m_top.testAndSetOrdered(top, newNode));
61 
62         m_numNodes.ref();
63     }
64 
pop(T & value)65     bool pop(T &value) {
66         bool result = false;
67 
68         m_deleteBlockers.ref();
69 
70         while(1) {
71             Node *top = (Node*) m_top;
72             if(!top) break;
73 
74             // This is safe as we ref'ed m_deleteBlockers
75             Node *next = top->next;
76 
77             if(m_top.testAndSetOrdered(top, next)) {
78                 m_numNodes.deref();
79                 result = true;
80 
81                 value = top->data;
82 
83                 /**
84                  * Test if we are the only delete blocker left
85                  * (it means that we are the only owner of 'top')
86                  * If there is someone else in "delete-blocked section",
87                  * then just add the struct to the list of free nodes.
88                  */
89                 if (m_deleteBlockers == 1) {
90                     cleanUpNodes();
91                     delete top;
92                 }
93                 else {
94                     releaseNode(top);
95                 }
96 
97                 break;
98             }
99         }
100 
101         m_deleteBlockers.deref();
102 
103         return result;
104     }
105 
clear()106     void clear() {
107         // a fast-path without write ops
108         if(!m_top) return;
109 
110         m_deleteBlockers.ref();
111 
112         Node *top = m_top.fetchAndStoreOrdered(0);
113 
114         int removedChunkSize = 0;
115         Node *tmp = top;
116         while(tmp) {
117             removedChunkSize++;
118             tmp = tmp->next;
119         }
120         m_numNodes.fetchAndAddOrdered(-removedChunkSize);
121 
122         while(top) {
123             Node *next = top->next;
124 
125             if (m_deleteBlockers == 1) {
126                 /**
127                  * We  are the only owner of top contents.
128                  * So we can delete it freely.
129                  */
130                 cleanUpNodes();
131                 freeList(top);
132                 next = 0;
133             }
134             else {
135                 releaseNode(top);
136             }
137 
138             top = next;
139         }
140 
141         m_deleteBlockers.deref();
142     }
143 
mergeFrom(KisLocklessStack<T> & other)144     void mergeFrom(KisLocklessStack<T> &other) {
145         Node *otherTop = other.m_top.fetchAndStoreOrdered(0);
146         if (!otherTop) return;
147 
148         int removedChunkSize = 1;
149         Node *last = otherTop;
150         while(last->next) {
151             removedChunkSize++;
152             last = last->next;
153         }
154         other.m_numNodes.fetchAndAddOrdered(-removedChunkSize);
155 
156         Node *top;
157 
158         do {
159             top = m_top;
160             last->next = top;
161         } while (!m_top.testAndSetOrdered(top, otherTop));
162 
163         m_numNodes.fetchAndAddOrdered(removedChunkSize);
164     }
165 
166     /**
167      * This is impossible to measure the size of the stack
168      * in highly concurrent environment. So we return approximate
169      * value! Do not rely on this value much!
170      */
size()171     qint32 size() const {
172         return m_numNodes;
173     }
174 
isEmpty()175     bool isEmpty() const {
176         return !m_numNodes;
177     }
178 
179 private:
180 
releaseNode(Node * node)181     inline void releaseNode(Node *node) {
182         Node *top;
183         do {
184             top = m_freeNodes;
185             node->next = top;
186         } while (!m_freeNodes.testAndSetOrdered(top, node));
187     }
188 
cleanUpNodes()189     inline void cleanUpNodes() {
190         Node *cleanChain = m_freeNodes.fetchAndStoreOrdered(0);
191         if (!cleanChain) return;
192 
193         /**
194          * If we are the only users of the objects is cleanChain,
195          * then just free it. Otherwise, push them back into the
196          * recycling list and keep them there till another
197          * chance comes.
198          */
199         if (m_deleteBlockers == 1) {
200             freeList(cleanChain);
201         } else {
202             Node *last = cleanChain;
203             while (last->next) last = last->next;
204 
205             Node *freeTop;
206 
207             do {
208                 freeTop = m_freeNodes;
209                 last->next = freeTop;
210             } while (!m_freeNodes.testAndSetOrdered(freeTop, cleanChain));
211         }
212     }
213 
freeList(Node * first)214     inline void freeList(Node *first) {
215         Node *next;
216         while (first) {
217             next = first->next;
218             delete first;
219             first = next;
220         }
221     }
222 
223 
224 private:
225     Q_DISABLE_COPY(KisLocklessStack)
226 
227     QAtomicPointer<Node> m_top;
228     QAtomicPointer<Node> m_freeNodes;
229 
230     QAtomicInt m_deleteBlockers;
231     QAtomicInt m_numNodes;
232 };
233 
234 #endif /* __KIS_LOCKLESS_STACK_H */
235 
236