#include <kis_lockless_stack.h>

Classes
struct	Node

Public Member Functions
void	clear ()

bool	isEmpty () const

	KisLocklessStack ()

void	mergeFrom (KisLocklessStack< T > &other)

bool	pop (T &value)

void	push (T data)

qint32	size () const

	~KisLocklessStack ()

Private Member Functions
void	cleanUpNodes ()

void	freeList (Node *first)

void	releaseNode (Node *node)

Private Attributes
QAtomicInt	m_deleteBlockers

QAtomicPointer< Node >	m_freeNodes

QAtomicInt	m_numNodes

QAtomicPointer< Node >	m_top

Detailed Description

template<class T>
class KisLocklessStack< T >

Definition at line 23 of file kis_lockless_stack.h.

Constructor & Destructor Documentation

◆ KisLocklessStack()

template<class T >

KisLocklessStack< T >::KisLocklessStack ( )

inline

Definition at line 32 of file kis_lockless_stack.h.

32{ }

◆ ~KisLocklessStack()

template<class T >

KisLocklessStack< T >::~KisLocklessStack ( )

inline

Definition at line 33 of file kis_lockless_stack.h.

                        {
 
        freeList(m_top.fetchAndStoreOrdered(0));
        freeList(m_freeNodes.fetchAndStoreOrdered(0));
    }

References KisLocklessStack< T >::freeList(), KisLocklessStack< T >::m_freeNodes, and KisLocklessStack< T >::m_top.

Member Function Documentation

◆ cleanUpNodes()

template<class T >

void KisLocklessStack< T >::cleanUpNodes ( )

inlineprivate

If we are the only users of the objects is cleanChain, then just free it. Otherwise, push them back into the recycling list and keep them there till another chance comes.

Definition at line 177 of file kis_lockless_stack.h.

                               {
        Node *cleanChain = m_freeNodes.fetchAndStoreOrdered(0);
        if (!cleanChain) return;
 
        if (m_deleteBlockers == 1) {
            freeList(cleanChain);
        } else {
            Node *last = cleanChain;
            while (last->next) last = last->next;
 
            Node *freeTop;
 
            do {
                freeTop = m_freeNodes;
                last->next = freeTop;
            } while (!m_freeNodes.testAndSetOrdered(freeTop, cleanChain));
        }
    }

References KisLocklessStack< T >::freeList(), KisLocklessStack< T >::m_deleteBlockers, KisLocklessStack< T >::m_freeNodes, and KisLocklessStack< T >::Node::next.

◆ clear()

template<class T >

void KisLocklessStack< T >::clear ( )

inline

We are the only owner of top contents. So we can delete it freely.

Definition at line 94 of file kis_lockless_stack.h.

                 {
        // a fast-path without write ops
        if(!m_top) return;
 
        m_deleteBlockers.ref();
 
        Node *top = m_top.fetchAndStoreOrdered(0);
 
        int removedChunkSize = 0;
        Node *tmp = top;
        while(tmp) {
            removedChunkSize++;
            tmp = tmp->next;
        }
        m_numNodes.fetchAndAddOrdered(-removedChunkSize);
 
        while(top) {
            Node *next = top->next;
 
            if (m_deleteBlockers == 1) {
                cleanUpNodes();
                freeList(top);
                next = 0;
            }
            else {
                releaseNode(top);
            }
 
            top = next;
        }
 
        m_deleteBlockers.deref();
    }

References KisLocklessStack< T >::cleanUpNodes(), KisLocklessStack< T >::freeList(), KisLocklessStack< T >::m_deleteBlockers, KisLocklessStack< T >::m_numNodes, KisLocklessStack< T >::m_top, KisLocklessStack< T >::Node::next, and KisLocklessStack< T >::releaseNode().

◆ freeList()

template<class T >

void KisLocklessStack< T >::freeList ( Node * first )

inlineprivate

Definition at line 202 of file kis_lockless_stack.h.

                                      {
        Node *next;
        while (first) {
            next = first->next;
            delete first;
            first = next;
        }
    }

References KisLocklessStack< T >::Node::next.

◆ isEmpty()

template<class T >

bool KisLocklessStack< T >::isEmpty ( ) const

inline

Definition at line 163 of file kis_lockless_stack.h.

                         {
        return !m_numNodes;
    }

References KisLocklessStack< T >::m_numNodes.

◆ mergeFrom()

template<class T >

void KisLocklessStack< T >::mergeFrom ( KisLocklessStack< T > & other )

inline

Definition at line 132 of file kis_lockless_stack.h.

                                               {
        Node *otherTop = other.m_top.fetchAndStoreOrdered(0);
        if (!otherTop) return;
 
        int removedChunkSize = 1;
        Node *last = otherTop;
        while(last->next) {
            removedChunkSize++;
            last = last->next;
        }
        other.m_numNodes.fetchAndAddOrdered(-removedChunkSize);
 
        Node *top;
 
        do {
            top = m_top;
            last->next = top;
        } while (!m_top.testAndSetOrdered(top, otherTop));
 
        m_numNodes.fetchAndAddOrdered(removedChunkSize);
    }

References KisLocklessStack< T >::m_numNodes, KisLocklessStack< T >::m_top, and KisLocklessStack< T >::Node::next.

◆ pop()

template<class T >

bool KisLocklessStack< T >::pop ( T & value )

inline

Test if we are the only delete blocker left (it means that we are the only owner of 'top') If there is someone else in "delete-blocked section", then just add the struct to the list of free nodes.

Definition at line 53 of file kis_lockless_stack.h.

                       {
        bool result = false;
 
        m_deleteBlockers.ref();
 
        while(1) {
            Node *top = (Node*) m_top;
            if(!top) break;
 
            // This is safe as we ref'ed m_deleteBlockers
            Node *next = top->next;
 
            if(m_top.testAndSetOrdered(top, next)) {
                m_numNodes.deref();
                result = true;
 
                value = top->data;
 
                if (m_deleteBlockers == 1) {
                    cleanUpNodes();
                    delete top;
                }
                else {
                    releaseNode(top);
                }
 
                break;
            }
        }
 
        m_deleteBlockers.deref();
 
        return result;
    }

References KisLocklessStack< T >::cleanUpNodes(), KisLocklessStack< T >::Node::data, KisLocklessStack< T >::m_deleteBlockers, KisLocklessStack< T >::m_numNodes, KisLocklessStack< T >::m_top, KisLocklessStack< T >::Node::next, KisLocklessStack< T >::releaseNode(), and value().

◆ push()

template<class T >

void KisLocklessStack< T >::push ( T data )

inline

Definition at line 39 of file kis_lockless_stack.h.

                      {
        Node *newNode = new Node();
        newNode->data = data;
 
        Node *top;
 
        do {
            top = m_top;
            newNode->next = top;
        } while (!m_top.testAndSetOrdered(top, newNode));
 
        m_numNodes.ref();
    }

References KisLocklessStack< T >::Node::data, KisLocklessStack< T >::m_numNodes, KisLocklessStack< T >::m_top, and KisLocklessStack< T >::Node::next.

◆ releaseNode()

template<class T >

void KisLocklessStack< T >::releaseNode ( Node * node )

inlineprivate

Definition at line 169 of file kis_lockless_stack.h.

                                        {
        Node *top;
        do {
            top = m_freeNodes;
            node->next = top;
        } while (!m_freeNodes.testAndSetOrdered(top, node));
    }

References KisLocklessStack< T >::m_freeNodes, and KisLocklessStack< T >::Node::next.

◆ size()

template<class T >

qint32 KisLocklessStack< T >::size ( ) const

inline

This is impossible to measure the size of the stack in highly concurrent environment. So we return approximate value! Do not rely on this value much!

Definition at line 159 of file kis_lockless_stack.h.

                        {
        return m_numNodes;
    }

References KisLocklessStack< T >::m_numNodes.

Member Data Documentation

◆ m_deleteBlockers

template<class T >

QAtomicInt KisLocklessStack< T >::m_deleteBlockers

private

Definition at line 218 of file kis_lockless_stack.h.

◆ m_freeNodes

template<class T >

QAtomicPointer<Node> KisLocklessStack< T >::m_freeNodes

private

Definition at line 216 of file kis_lockless_stack.h.

◆ m_numNodes

template<class T >

QAtomicInt KisLocklessStack< T >::m_numNodes

private

Definition at line 219 of file kis_lockless_stack.h.

◆ m_top

template<class T >

QAtomicPointer<Node> KisLocklessStack< T >::m_top

private

Definition at line 215 of file kis_lockless_stack.h.

The documentation for this class was generated from the following file:

libs/global/kis_lockless_stack.h

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ KisLocklessStack()

◆ ~KisLocklessStack()

Member Function Documentation

◆ cleanUpNodes()

◆ clear()

◆ freeList()

◆ isEmpty()

◆ mergeFrom()

◆ pop()

◆ push()

◆ releaseNode()

◆ size()

Member Data Documentation

◆ m_deleteBlockers

◆ m_freeNodes

◆ m_numNodes

◆ m_top