LocklessQueue.h

Go to the documentation of this file.

#ifndef __LDK_LOCKLESSQUEUE_HH__
#define __LDK_LOCKLESSQUEUE_HH__

//   Copyright (C) 2003-2006 Lorien Dunn.
//
//   Contact: loriendunn AT users DOT sourceforge DOT net
//
//   This software is provided 'as-is', without any express or implied warranty.
//   In no event will the authors be held liable for any damages arising from
//   the use of this software.
//
//   Permission is granted to anyone to use this software for any purpose,
//   including commercial applications, and to alter it and redistribute it
//   freely, subject to the following restrictions:
//
//   1. The origin of this software must not be misrepresented; you must not
//   claim that you wrote the original software. If you use this software in a
//   product, an acknowledgment in the product documentation would be
//   appreciated but is not required.
//
//   2. Altered source versions must be plainly marked as such, and must not be
//   misrepresented as being the original software.
//
//   3. This notice may not be removed or altered from any source distribution.
//


#include "LDK/Exceptions.h"
#include "LDK/Atomic.h"
#include <memory.h>

namespace LDK
{
template <class T>
class LocklessQueue
{
    struct QType
    {
        AtomicCount mHead;
        AtomicCount mTail;
        T* mBuffer;
        Atomic<bool> mOverflow;

        inline QType(size_t size) : mHead(0),
         mTail(0),
         mBuffer(NULL),
         mOverflow(false)
        {
            mBuffer = reinterpret_cast<T*>(malloc(sizeof(T)*size));
            if(!mBuffer)
                throw LDK_BADALLOC_ERROR;
        }

        inline ~QType()
        {
            if(mBuffer)
                ::free(mBuffer);
        }

        inline const T* operator[](size_t idx) const
        {
            return &mBuffer[idx];
        }

        inline T* operator[](size_t idx)
        {
            return &mBuffer[idx];
        }
    };

    QType* mQueue;
    const size_t mSize;

public:
    inline LocklessQueue(size_t size) : mQueue(NULL),
     mSize(size+1) //+1 because full == overflow
    {
        mQueue = new QType(mSize);
    }

    inline ~LocklessQueue()
    {
        if(mQueue)
            delete mQueue;
    }

    inline void enqueue(const T& msg)
    {
        size_t tail = mQueue->mTail;
        memcpy((*mQueue)[tail], &msg, sizeof(T));
        tail++;
        if(tail == mSize)
            tail = 0;
        if(tail == mQueue->mHead)
        {
            mQueue->mOverflow = true;
            throw LDK_LENGTH_ERROR("LocklessQueue overflow");
        }
        mQueue->mTail = tail;
    }

    inline void enqueue(const T* msg)
    {
        enqueue(*msg);
    }

    inline void dequeue(T& msg)
    {
        if(mQueue->mOverflow)
        {
            mQueue->mOverflow = false;
            return;
        }

        size_t head = mQueue->mHead; //make sure this is written after access

        if(head == mQueue->mTail)
            throw LDK_LENGTH_ERROR("LocklessQueue empty");
        memcpy(&msg, (*mQueue)[head], sizeof(T));
        head++;
        if(head == mSize)
            head = 0;
        mQueue->mHead = head;
    }

    inline void dequeue(T* msg)
    {
        dequeue(*msg);
    }

    inline bool full() const
    {
        size_t tail = mQueue->mTail + 1;
        if(tail == mSize)
            tail = 0;
        return (tail == mQueue->mHead);
    }

    inline bool empty() const
    {
        return (mQueue->mHead == mQueue->mTail);
    }

    inline const T* peek() const
    {
        size_t head = mQueue->mHead;
        if(head == mQueue->mTail)
            return NULL;
        return (*mQueue)[head];
    }

    inline void clear()
    {
        mQueue->mTail = 0;
        mQueue->mHead = 0;
        mQueue->mOverflow = 0;
    }
};

}//namespace LDK

#endif //__LDK_LOCKLESSQUEUE_HH__

---