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