cat::FIFO::Queue< T > Class Template Reference

#include <LocklessFIFO.hpp>

List of all members.

Public Member Functions
T *	Dequeue ()
T *	DequeueWait ()
void	Enqueue (T *data)
void	FixList (Ptr< T > tail, Ptr< T > head)
	Queue ()
	~Queue ()
Private Attributes
Ptr< T >	Head
Ptr< T >	Tail

---

Detailed Description

template<class T>
class cat::FIFO::Queue< T >

Definition at line 105 of file LocklessFIFO.hpp.

---

Constructor & Destructor Documentation

template<class T >

cat::FIFO::Queue< T >::Queue

(

)

Definition at line 175 of file LocklessFIFO.hpp.

References cat::Singleton< RegionAllocator >::ii, and cat::FIFO::Node< T >::value.

    {
#if defined(CAT_OS_WINDOWS)
        hEvent = CreateEvent(NULL, FALSE, FALSE, NULL);
#endif

        Node<T> *node = new (RegionAllocator::ii) Node<T>;
        node->value = 0;

        Head.ptr = Tail.ptr = node;
    }

template<class T >

cat::FIFO::Queue< T >::~Queue

(

)

Definition at line 188 of file LocklessFIFO.hpp.

References cat::RegionAllocator::Delete(), cat::Singleton< RegionAllocator >::ii, and cat::FIFO::Node< T >::next.

    {
        // Destroy objects that are still queued
        for (Node<T> *next, *ptr = Head.ptr; ptr; ptr = next)
        {
            next = ptr->next.ptr;

            if (ptr->value)
                RegionAllocator::ii->Delete(ptr->value);
            RegionAllocator::ii->Delete(ptr);
        }

#if defined(CAT_OS_WINDOWS)
        CloseHandle(hEvent);
#endif
    }

---

Member Function Documentation

template<class T >

T * cat::FIFO::Queue< T >::Dequeue

(

)

Definition at line 254 of file LocklessFIFO.hpp.

References cat::FIFO::CAS2(), cat::RegionAllocator::Delete(), cat::Singleton< RegionAllocator >::ii, cat::FIFO::Node< T >::next, cat::FIFO::Ptr< T >::ptr, T, cat::FIFO::Ptr< T >::tag, and cat::FIFO::Node< T >::value.

    {
        Ptr<T> tail, head, firstNodePrev;
        Node<T> *nd_dummy;
        T *val;

        for (;;)
        {
            head = Head;
            tail = Tail;
            firstNodePrev = head.ptr->prev;
            val = head.ptr->value;

            if (head == Head)
            {
                if (val != 0)
                {
                    if (tail != head)
                    {
                        if (firstNodePrev.tag != head.tag)
                        {
                            FixList(tail, head);
                            continue;
                        }
                    }
                    else
                    {
                        nd_dummy = new (RegionAllocator::ii) Node<T>;
                        nd_dummy->value = 0;
                        nd_dummy->next.ptr = tail.ptr;
                        nd_dummy->next.tag = tail.tag + 1;

                        Ptr<T> new_tail;
                        new_tail.ptr = nd_dummy;
                        new_tail.tag = tail.tag + 1;

                        if (CAS2(Tail, tail, new_tail))
                        {
                            head.ptr->prev.ptr = nd_dummy;
                            head.ptr->prev.tag = tail.tag;
                        }
                        else
                        {
                            RegionAllocator::ii->Delete(nd_dummy);
                        }

                        continue;
                    }

                    Ptr<T> new_head;
                    new_head.ptr = firstNodePrev.ptr;
                    new_head.tag = head.tag + 1;

                    if (CAS2(Head, head, new_head))
                    {
                        RegionAllocator::ii->Delete(head.ptr);
                        return val;
                    }
                }
                else
                {
                    if (tail.ptr == head.ptr)
                        return 0;

                    if (firstNodePrev.tag != head.tag)
                    {
                        FixList(tail, head);

                        continue;
                    }

                    Ptr<T> new_head;
                    new_head.ptr = firstNodePrev.ptr;
                    new_head.tag = head.tag + 1;

                    CAS2(Head, head, new_head);
                }
            }
        }
    }

template<class T >

T * cat::FIFO::Queue< T >::DequeueWait

(

)

Definition at line 236 of file LocklessFIFO.hpp.

References T.

    {
        for (;;)
        {
            // Attempt to dequeue a message
            // If we won the race to service the message, then return it
            T *retval = Dequeue();
            if (retval) return retval;

#if defined(CAT_OS_WINDOWS)
            // If the sychronization wait fails (handle closed), abort with 0
            if (WaitForSingleObject(hEvent, INFINITE) != WAIT_OBJECT_0)
                return 0;
#endif
        }
    }

template<class T >

void cat::FIFO::Queue< T >::Enqueue

(

T *

data

)

Definition at line 206 of file LocklessFIFO.hpp.

References cat::FIFO::CAS2(), cat::Singleton< RegionAllocator >::ii, cat::FIFO::Node< T >::next, cat::FIFO::Ptr< T >::ptr, cat::FIFO::Ptr< T >::tag, and cat::FIFO::Node< T >::value.

    {
        Ptr<T> tail;
        Node<T> *nd = new (RegionAllocator::ii) Node<T>;
        nd->value = val;

        for (;;)
        {
            tail = Tail;
            nd->next.ptr = tail.ptr;
            nd->next.tag = tail.tag + 1;

            Ptr<T> new_tail;
            new_tail.ptr = nd;
            new_tail.tag = tail.tag + 1;

            if (CAS2(Tail, tail, new_tail))
            {
                tail.ptr->prev.ptr = nd;
                tail.ptr->prev.tag = tail.tag;
                break;
            }
        }

#if defined(CAT_OS_WINDOWS)
        SetEvent(hEvent);
#endif
    }

template<class T >

void cat::FIFO::Queue< T >::FixList	(	Ptr< T >	tail,
		Ptr< T >	head
	)

Definition at line 336 of file LocklessFIFO.hpp.

References cat::FIFO::Ptr< T >::ptr, and cat::FIFO::Ptr< T >::tag.

    {
        Ptr<T> curNode, curNodeNext, nextNodePrev;

        curNode = tail;

        while (head == Head && curNode != head)
        {
            curNodeNext = curNode.ptr->next;

            if (curNodeNext.tag != curNode.tag)
                return;

            nextNodePrev = curNodeNext.ptr->prev;

            if (nextNodePrev.ptr != curNode.ptr || nextNodePrev.tag != curNode.tag - 1)
            {
                curNodeNext.ptr->prev.ptr = curNode.ptr;
                curNodeNext.ptr->prev.tag = curNode.tag - 1;
            }

            curNode.ptr = curNodeNext.ptr;
            curNode.tag = curNode.tag - 1;
        }
    }

---

Member Data Documentation

template<class T >

Ptr<T> cat::FIFO::Queue< T >::Head [private]

Definition at line 108 of file LocklessFIFO.hpp.

template<class T >

Ptr<T> cat::FIFO::Queue< T >::Tail [private]

Definition at line 108 of file LocklessFIFO.hpp.

---

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

• LocklessFIFO.hpp