Source

dbsdev / sources / utils / threadpool / orig / KMQueue.h

//////////////////////////////////////////////////////////////////////////
// KMThreadPool_Win32.h
//
// Author: Keith Maggio
// Purpose: Our Threadpool Singleton class.
// Free for use and modification.
// Revision 1, September 5th, 2010
//////////////////////////////////////////////////////////////////////////
#ifndef _KM_QUEUE_H_
#define _KM_QUEUE_H_

#include "amp/amp_mutex.h"
using namespace kmp::threading;

namespace kmp{ 
namespace threading{ 
namespace algorithms{

    // Thread-Safe Two-Lock Queue
    // Based on the algorithm presented by Maged M. Michael & Michael L. Scott
    // http://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf
    template<typename TYPE>
    class KMQueue
    {
    private:
        struct tNode
        {
            TYPE element;
            tNode* next;

            tNode(TYPE _elem, tNode* _next) : element(_elem), next(_next)
            {}
            tNode(TYPE _elem) : element(_elem), next(NULL)
            {}
        };

        // Members
        tNode* _head;  // The head acts as a dummy/invalidated pointer. When an item is the head,
                        // then it's scheduled for deletion on the next pop (if it's not the last node
                        // in the queue).
        tNode* _tail;
        amp_mutex_t _headLock;
        amp_mutex_t _tailLock;

        // Deactivated Functions
        KMQueue(KMQueue&)
        {}

        KMQueue& operator = (KMQueue&)
        {}


    public:
        KMQueue()
        {
            amp_mutex_create(&_headLock,AMP_DEFAULT_ALLOCATOR);
            amp_mutex_create(&_tailLock,AMP_DEFAULT_ALLOCATOR);
            tNode* dummy = new tNode(NULL, NULL);
            _head = _tail = dummy;
        }

        ~KMQueue()
        {
            while(pop());
            delete _head;
        }

        bool empty()
        {
            if(_head->next != NULL)
                return false;
            return true;
        }

        void push(TYPE item)
        {
            tNode* node = new tNode(item);
            amp_mutex_lock(_tailLock);
            {
                _tail->next = node;
                _tail = node;
            }
            amp_mutex_unlock(_tailLock);
        }

        TYPE pop()
        {
            tNode* node;
            TYPE value;
            amp_mutex_lock(_headLock);
            {
                node = _head;
                tNode* newHead = node->next;
                if(newHead == NULL)
                {
                    // If only the head is left, then the queue is empty
                    // (Remember, the _head is considered invalidated)
                    amp_mutex_unlock(_headLock);
                    return NULL;
                }
                value = newHead->element;
                _head = newHead;
            }
            amp_mutex_unlock(_headLock);
            delete node;
            return value;

        }

    };
}}}
#endif
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.