freelist.h

Go to the documentation of this file.

 
#ifndef _FREE_LIST_CLASS_HEADER_
#define _FREE_LIST_CLASS_HEADER_
 
namespace A_UTILS_NS
{
 
#ifdef A_UTILS_TAGGED_POINTER_AVALIABLE
 
template <class T, class DataType>
class A_UTILS_CAS_ALIGNMENT free_list
{
    private:
        typedef tagged_ptr<T> tTaggedNodePtr;
 
        tTaggedNodePtr m_pFree;
 
        tBool m_bGrow;
 
    public:
 
        free_list(tUInt nReserve = 0, tBool bGrow = tTrue):
            m_bGrow(bGrow)
        {
            // preallocate some nodes
            for (tUInt nNode = 0; nNode < nReserve; ++nNode)
            {
                T* pTmp = new T;
                pTmp->m_pNext = m_pFree;
                m_pFree.Set(pTmp);
            }
        }
 
        ~free_list()
        {
            T* pTmp = m_pFree.GetPtr();
            while (pTmp)
            {
                T* pNext = pTmp->m_pNext.GetPtr();
                delete pTmp;
                pTmp = pNext;
            }
        }
 
        T* GetFreeNode()
        {
            for (;;)
            {
                tTaggedNodePtr pOldTos;
                pOldTos.Set(m_pFree);
 
                if (!pOldTos)
                {
                    if (m_bGrow)
                    {
                        return new T;
                    }
                    else
                    {
                        return nullptr;
                    }
                }
 
                T* pNewTos = pOldTos->m_pNext.GetPtr();
 
                if (m_pFree.CompareAndSwap(pOldTos, pNewTos))
                {
                    return pOldTos.GetPtr();
                }
            }
        }
 
        tVoid AddFreeNode(T* pNode)
        {
            pNode->m_oData = DataType(); // reset value
 
            tTaggedNodePtr pOld;
            do
            {
                pOld.Set(m_pFree);
                pNode->m_pNext.Set(pOld.GetPtr());
            }
            while (!m_pFree.CompareAndSwap(pOld, pNode)); // try insertion until we succeed
        }
 
    private:
        free_list(const free_list& oOther);
};
 
#endif
 
}
 
#endif