#ifndef _LOCK_FREE_QUEUE_H__ #define _LOCK_FREE_QUEUE_H__ #include // uint32_t #include #include // default Queue size #define LOCK_FREE_Q_DEFAULT_SIZE 65536 // (2^16) // define this macro if calls to "size" must return the real size of the // queue. If it is undefined that function will try to take a snapshot of // the queue, but returned value might be bogus #define _WITH_LOCK_FREE_Q_KEEP_REAL_SIZE // forward declarations for default template values // template class ArrayLockFreeQueueMultipleProducers; /// @brief Lock-free queue based on a circular array /// No allocation of extra memory for the nodes handling is needed, but it has /// to add extra overhead (extra CAS operation) when inserting to ensure the /// thread-safety of the queue when the queue type is not /// ArrayLockFreeQueueSingleProducer. /// /// examples of instantiation: /// ArrayLockFreeQueue q; // queue of ints of default size (65535 - 1) /// // and defaulted to single producer /// ArrayLockFreeQueue q; /// // queue of ints of size (16 - 1) and /// // defaulted to single producer /// ArrayLockFreeQueue q; /// // queue of ints of size (100 - 1) with support /// // for multiple producers /// /// ELEM_T represents the type of elementes pushed and popped from the queue /// Q_SIZE size of the queue. The actual size of the queue is (Q_SIZE-1) /// This number should be a power of 2 to ensure /// indexes in the circular queue keep stable when the uint32_t /// variable that holds the current position rolls over from FFFFFFFF /// to 0. For instance /// 2 -> 0x02 /// 4 -> 0x04 /// 8 -> 0x08 /// 16 -> 0x10 /// (...) /// 1024 -> 0x400 /// 2048 -> 0x800 /// /// if queue size is not defined as requested, let's say, for /// instance 100, when current position is FFFFFFFF (4,294,967,295) /// index in the circular array is 4,294,967,295 % 100 = 95. /// When that value is incremented it will be set to 0, that is the /// last 4 elements of the queue are not used when the counter rolls /// over to 0 /// Q_TYPE type of queue implementation. ArrayLockFreeQueueSingleProducer and /// ArrayLockFreeQueueMultipleProducers are supported (single producer /// by default) template < typename ELEM_T, template class Q_TYPE = ArrayLockFreeQueueMultipleProducers > class LockFreeQueue { public: /// @brief constructor of the class LockFreeQueue(size_t qsize = LOCK_FREE_Q_DEFAULT_SIZE); /// @brief destructor of the class. /// Note it is not virtual since it is not expected to inherit from this /// template ~LockFreeQueue(); /// @brief returns the current number of items in the queue /// It tries to take a snapshot of the size of the queue, but in busy environments /// this function might return bogus values. /// /// If a reliable queue size must be kept you might want to have a look at /// the preprocessor variable in this header file called '_WITH_LOCK_FREE_Q_KEEP_REAL_SIZE' /// it enables a reliable size though it hits overall performance of the queue /// (when the reliable size variable is on it's got an impact of about 20% in time) inline uint32_t size(); /// @brief return true if the queue is full. False otherwise /// It tries to take a snapshot of the size of the queue, but in busy /// environments this function might return bogus values. See help in method /// LockFreeQueue::size inline bool full(); /// @brief push an element at the tail of the queue /// @param the element to insert in the queue /// Note that the element is not a pointer or a reference, so if you are using large data /// structures to be inserted in the queue you should think of instantiate the template /// of the queue as a pointer to that large structure /// @return true if the element was inserted in the queue. False if the queue was full inline bool push(const ELEM_T &a_data); /// @brief pop the element at the head of the queue /// @param a reference where the element in the head of the queue will be saved to /// Note that the a_data parameter might contain rubbish if the function returns false /// @return true if the element was successfully extracted from the queue. False if the queue was empty inline bool pop(ELEM_T &a_data); protected: /// @brief the actual queue. methods are forwarded into the real /// implementation Q_TYPE m_qImpl; private: /// @brief disable copy constructor declaring it private LockFreeQueue(const LockFreeQueue &a_src); }; /// @brief implementation of an array based lock free queue with support for /// multiple producers /// This class is prevented from being instantiated directly (all members and /// methods are private). To instantiate a multiple producers lock free queue /// you must use the ArrayLockFreeQueue fachade: /// ArrayLockFreeQueue q; template class ArrayLockFreeQueueMultipleProducers { // ArrayLockFreeQueue will be using this' private members template < typename ELEM_T_, template class Q_TYPE > friend class LockFreeQueue; private: /// @brief constructor of the class ArrayLockFreeQueueMultipleProducers(size_t qsize = LOCK_FREE_Q_DEFAULT_SIZE); virtual ~ArrayLockFreeQueueMultipleProducers(); inline uint32_t size(); inline bool full(); inline bool empty(); bool push(const ELEM_T &a_data); bool pop(ELEM_T &a_data); /// @brief calculate the index in the circular array that corresponds /// to a particular "count" value inline uint32_t countToIndex(uint32_t a_count); private: size_t Q_SIZE; /// @brief array to keep the elements ELEM_T *m_theQueue; /// @brief where a new element will be inserted std::atomic m_writeIndex; /// @brief where the next element where be extracted from std::atomic m_readIndex; /// @brief maximum read index for multiple producer queues /// If it's not the same as m_writeIndex it means /// there are writes pending to be "committed" to the queue, that means, /// the place for the data was reserved (the index in the array) but /// data is still not in the queue, so the thread trying to read will have /// to wait for those other threads to save the data into the queue /// /// note this is only used for multiple producers std::atomic m_maximumReadIndex; #ifdef _WITH_LOCK_FREE_Q_KEEP_REAL_SIZE /// @brief number of elements in the queue std::atomic m_count; #endif static int m_reference; private: /// @brief disable copy constructor declaring it private ArrayLockFreeQueueMultipleProducers(const ArrayLockFreeQueueMultipleProducers &a_src); }; // include implementation files #include "lock_free_queue_impl.h" #include "lock_free_queue_impl_multiple_producer.h" #endif // _LOCK_FREE_QUEUE_H__