This is my mult-prod/sing-cons lockless FIFO template queue

gistfile1.cpp

/**
 * LinkedFIFO.h - this file defines a multi-producer/single-consumer linked
 *                FIFO queue and is using the compare-and-swap to achieve
 *                the lock-free goal.
 */
#ifndef __LINKEDFIFO_H
#define __LINKEDFIFO_H

// System Headers
#include <stdint.h>
#include <ostream>
#include <string>

// Third-Party Headers
#include <log4cpp/Category.hh>

// Other Headers

// Forward Declarations

// Public Constants

// Public Datatypes

// Public Data Constants


/**
 * This is the main class definition
 */
template <class T> class LinkedFIFO
{
	public:
		/*******************************************************************
		 *
		 *                     Constructors/Destructor
		 *
		 *******************************************************************/
		/**
		 * This is the default constructor that assumes NOTHING - it just
		 * makes a simple queue ready to hold things.
		 */
		LinkedFIFO() :
			mHead(NULL),
			mTail(NULL),
			mSleepDelay(),
			mHowSleepy(0)
		{
			// clear out the sleep timer values
			mSleepDelay.tv_sec = 0;
			// start with my first (empty) node
			mHead = new Node();
			mTail = mHead;
		}


		/**
		 * This is the standard copy constructor that needs to be in every
		 * class to make sure that we control how many copies we have
		 * floating around in the system.
		 */
		LinkedFIFO( const LinkedFIFO<T> & anOther ) :
			mHead(NULL),
			mTail(NULL),
			mSleepDelay(),
			mHowSleepy(0)
		{
			// let the '=' operator do the heavy lifting...
			*this = anOther;
		}


		/**
		 * This is the standard destructor and needs to be virtual to make
		 * sure that if we subclass off this, the right destructor will be
		 * called.
		 */
		virtual ~LinkedFIFO()
		{
			clear();
			// now clean out the last node (empty) in the list
			if (mHead != NULL) {
				delete mHead;
				mHead = NULL;
			}
		}


		/**
		 * When we process the result of an equality we need to make sure
		 * that we do this right by always having an equals operator on
		 * all classes.
		 */
		LinkedFIFO & operator=( LinkedFIFO<T> & anOther )
		{
			if (this != & anOther) {
				/**
				 * Assuming the argument is stable, then we're just going
				 * to walk it, pushing on the values from it in the right
				 * order so they are appended to us.
				 */
				for (Node *n = anOther.mHead->next; n != NULL; n = n->next) {
					if (!push(n->value)) {
						break;
					}
				}
			}
			return *this;
		}


		LinkedFIFO & operator=( const LinkedFIFO<T> & anOther )
		{
			return operator=((LinkedFIFO<T> &)anOther);
		}


		/*******************************************************************
		 *
		 *                        Accessor Methods
		 *
		 *******************************************************************/
		/**
		 * This method takes an item and places it in the queue - if it can.
		 * If so, then it will return 'true', otherwise, it'll return 'false'.
		 */
		bool push( const T & anElem )
		{
			bool		error = false;

			// create a new Node with the provided value
			Node	*me = new Node(anElem);
			if (me == NULL) {
				error = true;
			} else {
				/**
				 * We need to add the new value to the tail and then link it
				 * back into the list. Not too bad.
				 */
				// put in the new tail, and get the old one
				Node	*oldTail = mTail;
				while (!__sync_bool_compare_and_swap(&mTail, oldTail, me)) {
					oldTail = mTail;
				}
				// OK, make sure that the list remains intact
				if (oldTail != NULL) {
					oldTail->next = me;
				}
			}

			return !error;
		}


		/**
		 * This method updates the passed-in reference with the value on the
		 * top of the queue - if it can. If so, it'll return the value and
		 * 'true', but if it can't, as in the queue is empty, then the method
		 * will return 'false' and the value will be untouched.
		 */
		bool pop( T & anElem )
		{
			bool		error = false;

			// if the next guy is NULL, we're empty
			if (__sync_bool_compare_and_swap(&(mHead->next), NULL, NULL)) {
				error = true;
			} else {
				// move the head to the next Node and get the value
				Node	*oldHead = __sync_val_compare_and_swap(&mHead, mHead, mHead->next);
				anElem = mHead->value;
				// if there is an oldHead (should be), delete it now
				if (oldHead != NULL) {
					delete oldHead;
				}
			}

			return !error;
		}


		/**
		 * If there is an item on the queue, this method will return a look
		 * at that item without updating the queue. The return value will be
		 * 'true' if there is something, but 'false' if the queue is empty.
		 */
		bool peek( T & anElem )
		{
			bool		error = false;

			// if the next guy is NULL, we're empty
			if (__sync_bool_compare_and_swap(&(mHead->next), NULL, NULL)) {
				error = true;
			} else {
				// look at the next valid node to get the next value
				anElem = mHead->next->value;
			}

			return !error;
		}


		/**
		 * This method will clear out the contents of the queue so if
		 * you're storing pointers, then you need to be careful as this
		 * could leak.
		 */
		void clear()
		{
			// pretty simple - just pop everything off the queue
			T		v;
			while (pop(v));
		}


		/**
		 * This method will return 'true' if there are no items in the
		 * queue. Simple.
		 */
		bool empty()
		{
			return (__sync_bool_compare_and_swap(&mHead->next, NULL, NULL));
		}


		/**
		 * This method will return the total number of items in the
		 * queue.
		 */
		size_t size() const
		{
			size_t		retval = 0;
			for (Node *n = mHead->next; n != NULL; n = n->next) {
				++retval;
			}
			return retval;
		}


		/*******************************************************************
		 *
		 *                         Utility Methods
		 *
		 *******************************************************************/
		/**
		 * This method will check to see if the queue is empty, and if it
		 * is, it'll sleep a "little bit" and then return to the caller.
		 * The reason for all this is that the queue does not have a blocking
		 * mode, so the only way to service the queue is to poll it. Too
		 * agressive and you're wasing CPU cycles, too passive and you're
		 * wasting time. This tries to strike a nice balance.
		 */
		void sleep( bool aForcedSleep = false )
		{
			/**
			 * If we are empty, and we have a non-zero delay to sleep for,
			 * then do it, but make sure to cap the sleepy index at the size
			 * of the array of sleepy values.
			 */
			if ((aForcedSleep || empty()) &&
				((mSleepDelay.tv_nsec = cSleepy[mHowSleepy++]) != 0)) {
				nanosleep(&mSleepDelay, NULL);
				mHowSleepy = (mHowSleepy > cSleepyMax ? cSleepyMax : mHowSleepy);
			}
		}


		/**
		 * Because there are plenty of times that it's really useful to have
		 * a human-readable version of this instance's data, we're going to
		 * have a common method to give us just that - and this is it.
		 */
		virtual std::string toString() const
		{
			return "<LinkedFIFO>";
		}


		/**
		 * This method checks to see if two queues are equal in their
		 * contents and not their pointer values. This is how you'd likely
		 * expect equality to work.
		 */
		bool operator==( LinkedFIFO<T> & anOther ) const
		{
			bool	equals = true;

			// check to see if he's as sleepy as me :)
			if (equals) {
				equals = (mHowSleepy == anOther.mHowSleepy);
			}

			// next, check the elements for equality
			if (equals) {
				Node	*me = mHead;
				Node	*him = anOther.mHead;
				while (me != NULL) {
					if ((him == NULL) || (me->value != him->value)) {
						equals = false;
						break;
					}
					me = me->next;
					him = him->next;
				}
			}

			return equals;
		}


		/**
		 * This method checks to see if two queues are NOT equal in their
		 * contents and not their pointer values. This is how you'd likely
		 * expect equality to work.
		 */
		bool operator!=( LinkedFIFO<T> & anOther ) const
		{
			return !operator=(anOther);
		}

	private:
		/**
		 * My linked list will be made of these nodes, and I'll make them
		 * with the one-argument constructor that just sets the value and
		 * nulls out the next pointer. Pretty simple.
		 */
		struct Node {
			T		value;
			Node	*next;

			Node() : value(), next(NULL) { }
			Node( const T & aValue ) : value(aValue), next(NULL) { }
			~Node() { }
		};

		/**
		 * We have a very simple structure - a singly-linked list of values
		 * that I'm just going to be very careful about modifying.
		 */
		Node	*volatile mHead;
		Node	*volatile mTail;
		/**
		 * Because this queue will not block until something is there,
		 * we need to make it a little easier on the users of this class
		 * by having a simple sleep() method. Simple, but clever under
		 * the covers. In order to implement this sleeper I need a few
		 * things, and these are it.
		 */
		struct timespec 			mSleepDelay;
		uint8_t					mHowSleepy;
		static int32_t				cSleepy[];
		static uint8_t				cSleepyMax;

		/**
		 * This is the class reference to the logger for this class.
		 * It's pthread-aware, so we should be OK to use it by all the
		 * instances of this class.
		 */
		static log4cpp::Category	& cLog;
};
template <class T> int32_t LinkedFIFO<T>::cSleepy[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 250000, 250000, 250000, 250000, 250000, 250000, 250000, 250000, 250000, 250000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 500000, 750000, 750000, 750000, 750000, 750000, 750000, 750000, 750000, 750000, 750000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 2500000, 2500000, 2500000, 2500000, 2500000, 2500000, 2500000, 2500000, 2500000, 2500000, 5000000, 5000000, 5000000, 5000000, 5000000, 10000000, 10000000, 10000000, 10000000, 10000000, 50000000, 100000000 };
template <class T> uint8_t LinkedFIFO<T>::cSleepyMax = 41;
template <class T> log4cpp::Category & LinkedFIFO<T>::cLog = log4cpp::Category::getInstance("LinkedFIFO<T>");

#endif	// __LINKEDFIFO_H
// vim: set ts=4:

the implement of pop() is wrong.
170 Node *oldHead = __sync_val_compare_and_swap(&mHead, mHead, mHead->next);
171 anElem = mHead->value;
should be
170 Node *oldHead = __sync_val_compare_and_swap(&mHead, mHead, mHead->next);
171 anElem = oldHead->value;

Although fixed, it also exists problem that if FIFO is not empty, pop() may fail because of the case *mHead != mHead .