You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
283 lines
8.8 KiB
283 lines
8.8 KiB
/*
|
|
* Copyright 2002-2019 Intel Corporation.
|
|
*
|
|
* This software and the related documents are Intel copyrighted materials, and your
|
|
* use of them is governed by the express license under which they were provided to
|
|
* you ("License"). Unless the License provides otherwise, you may not use, modify,
|
|
* copy, publish, distribute, disclose or transmit this software or the related
|
|
* documents without Intel's prior written permission.
|
|
*
|
|
* This software and the related documents are provided as is, with no express or
|
|
* implied warranties, other than those that are expressly stated in the License.
|
|
*/
|
|
|
|
// <COMPONENT>: atomic
|
|
// <FILE-TYPE>: component public header
|
|
|
|
#ifndef ATOMIC_FIXED_LIFO_HPP
|
|
#define ATOMIC_FIXED_LIFO_HPP
|
|
|
|
#include "util/numberbits.hpp"
|
|
#include "atomic/config.hpp"
|
|
#include "atomic/lifo-ctr.hpp"
|
|
#include "atomic/nullstats.hpp"
|
|
|
|
|
|
namespace ATOMIC {
|
|
|
|
|
|
/*! @brief Last-in-first-out queue with pre-allocated elements.
|
|
*
|
|
* A LIFO queue that is thread safe and safe to use from signal handlers. It uses
|
|
* compare-and-swap operations to maintain atomicity rather than locking.
|
|
* This ensures that queue operations are safe even if a signal interrupts an
|
|
* operation and the signal handler accesses the same queue. The queue also
|
|
* statically allocates all of its data, so operations on the queue will never
|
|
* attempt to dynamically allocate memory.
|
|
*
|
|
* @param OBJECT Type of the object which each queue element holds.
|
|
* @param Capacity Maximum number of objects that the queue can hold.
|
|
* @param CounterBits The queue contains a counter which is used to maintain atomicity.
|
|
* (See LIFO_CTR for more information.)
|
|
* @param STATS Type of an object that collects statistics. See NULLSTATS for a model.
|
|
*
|
|
* @par Example:
|
|
* \code
|
|
* #include "atomic/fixed-lifo.hpp"
|
|
*
|
|
* struct MyElement
|
|
* {
|
|
* unsigned _myMember;
|
|
* };
|
|
*
|
|
* ATOMIC::FIXED_LIFO<MyElement, 128> Queue;
|
|
*
|
|
* void Foo()
|
|
* {
|
|
* MyElement el;
|
|
* Queue.Push(el); // Pushes a copy of 'el'
|
|
* Queue.Pop(&el); // Assigns 'el' to a copy of the popped element
|
|
* }
|
|
* \endcode
|
|
*/
|
|
template<typename OBJECT, unsigned int Capacity, unsigned int CounterBits=32, typename STATS=NULLSTATS>
|
|
class /*<UTILITY>*/ FIXED_LIFO
|
|
{
|
|
public:
|
|
/*!
|
|
* Construct a new (empty) queue. This method is NOT atomic.
|
|
*/
|
|
FIXED_LIFO(STATS *stats=0) : _activeQueue(&_elementHeap, stats), _freeQueue(&_elementHeap, stats)
|
|
{
|
|
ClearNonAtomic();
|
|
}
|
|
|
|
/*!
|
|
* Set the statistics collection object. This method is NOT atomic.
|
|
*
|
|
* @param[in] stats The new statistics collection object.
|
|
*/
|
|
void SetStatsNonAtomic(STATS *stats)
|
|
{
|
|
_activeQueue.SetStatsNonAtomic(stats);
|
|
_freeQueue.SetStatsNonAtomic(stats);
|
|
}
|
|
|
|
/*!
|
|
* Initialize to empty queue. This method is NOT atomic.
|
|
*/
|
|
void ClearNonAtomic()
|
|
{
|
|
unsigned int i = 0;
|
|
for (i = 0; i+1 < Capacity; i++)
|
|
_elementHeap._elements[i]._next = &_elementHeap._elements[i+1];
|
|
_elementHeap._elements[i]._next = 0;
|
|
|
|
_activeQueue.AssignNonAtomic(0);
|
|
_freeQueue.AssignNonAtomic(&_elementHeap._elements[0]);
|
|
}
|
|
|
|
/*!
|
|
* Copy all the elements from one queue into another. This method is NOT atomic,
|
|
* so the caller must ensure that neither the copied-to queue nor the copied-from
|
|
* queue are accessed from another thread.
|
|
*
|
|
* @param src The queue to copy.
|
|
*
|
|
* @return Returns a reference to the copied-to queue.
|
|
*/
|
|
FIXED_LIFO& operator=(const FIXED_LIFO &src)
|
|
{
|
|
unsigned int i;
|
|
|
|
// Link all of our _elements[] into a list.
|
|
//
|
|
for (i = 0; i < Capacity-1; i++)
|
|
_elementHeap._elements[i]._next = &_elementHeap._elements[i+1];
|
|
_elementHeap._elements[i]._next = 0;
|
|
|
|
// Copy each allocated element from 'src' into our list.
|
|
//
|
|
i = 0;
|
|
for (const ELEMENT *element = src._activeQueue.Head(); element; element = element->_next)
|
|
_elementHeap._elements[i++]._obj = element->_obj;
|
|
if (i > 0)
|
|
_elementHeap._elements[i-1]._next = 0;
|
|
ATOMIC_CHECK_ASSERT(i <= Capacity);
|
|
|
|
// Set up the active and free queues.
|
|
//
|
|
if (i > 0)
|
|
_activeQueue.AssignNonAtomic(&_elementHeap._elements[0]);
|
|
else
|
|
_activeQueue.AssignNonAtomic(0);
|
|
|
|
if (i < Capacity)
|
|
_freeQueue.AssignNonAtomic(&_elementHeap._elements[i]);
|
|
else
|
|
_freeQueue.AssignNonAtomic(0);
|
|
|
|
return *this;
|
|
}
|
|
|
|
/*!
|
|
* Push an object onto the head of the queue.
|
|
*
|
|
* @param[in] userObj The object to insert.
|
|
*
|
|
* @return Returns TRUE on success, FALSE if the queue's capacity would be exceeded.
|
|
*/
|
|
bool Push(const OBJECT &userObj)
|
|
{
|
|
ELEMENT *element = _freeQueue.Pop();
|
|
if (!element)
|
|
return false;
|
|
|
|
element->_obj = userObj;
|
|
|
|
_activeQueue.Push(element);
|
|
return true;
|
|
}
|
|
|
|
/*!
|
|
* Pop object off the head of the queue.
|
|
*
|
|
* @param[out] userObj Receives the object.
|
|
*
|
|
* @return Returns TRUE if there is an object to pop. Returns FALSE if the queue is empty.
|
|
*/
|
|
bool Pop(OBJECT *userObj)
|
|
{
|
|
ELEMENT *element = _activeQueue.Pop();
|
|
if (!element)
|
|
return false;
|
|
|
|
*userObj = element->_obj;
|
|
|
|
_freeQueue.Push(element);
|
|
return true;
|
|
}
|
|
|
|
/*!
|
|
* Tells whether the queue is empty.
|
|
*
|
|
* @return Returns TRUE if the queue contains no elements.
|
|
*/
|
|
bool Empty() const
|
|
{
|
|
const ELEMENT *head = _activeQueue.Head();
|
|
return (head == 0);
|
|
}
|
|
|
|
/*!
|
|
* Atomically, remove all the elements from the queue and copy them into an STL
|
|
* (or STL-like) container. The head of the queue is pushed onto the container
|
|
* first, then the next element of the queue, etc.
|
|
*
|
|
* @param[in,out] container The container which receives the queue elements.
|
|
* The container must implement the "push_back" method
|
|
* with the normal STL semantics.
|
|
*
|
|
* @return The number of elements copied to \a container.
|
|
*/
|
|
template<typename Container> unsigned MoveToContainer(Container *container)
|
|
{
|
|
unsigned count = 0;
|
|
|
|
ELEMENT *element = _activeQueue.Clear();
|
|
while (element)
|
|
{
|
|
container->push_back(element->_obj);
|
|
ELEMENT *next = element->_next;
|
|
_freeQueue.Push(element);
|
|
element = next;
|
|
count++;
|
|
}
|
|
|
|
return count;
|
|
}
|
|
|
|
/*!
|
|
* Copy pointers to each element in the queue to a container. The elements
|
|
* themselves remain in the queue afterwards. The element at the head of the
|
|
* queue is copied to element 0 of the container, etc.
|
|
*
|
|
* This method is NOT atomic. The caller must ensure that there are no
|
|
* insertions or deletions while this method is active. Moreover, the caller
|
|
* can only safely dereference the resulting pointers so long as the queue
|
|
* remains unmodified.
|
|
*
|
|
* @param[in,out] container The container which receives pointers to the
|
|
* queue elements. The container must implement the
|
|
* "push_back" method with the normal STL semantics.
|
|
*/
|
|
template<typename Container> void CopyPointersToContainerNonAtomic(Container *container) const
|
|
{
|
|
const ELEMENT *element = _activeQueue.Head();
|
|
while (element)
|
|
{
|
|
container->push_back(&element->_obj);
|
|
element = element->_next;
|
|
}
|
|
}
|
|
|
|
private:
|
|
struct ELEMENT
|
|
{
|
|
ELEMENT * volatile _next;
|
|
OBJECT _obj;
|
|
};
|
|
|
|
struct ELEMENT_HEAP
|
|
{
|
|
UINT32 Index(const ELEMENT *element) const
|
|
{
|
|
if (!element)
|
|
return 0;
|
|
return (element - _elements) + 1;
|
|
}
|
|
|
|
ELEMENT *Pointer(UINT32 iElement)
|
|
{
|
|
if (!iElement)
|
|
return 0;
|
|
return &_elements[iElement-1];
|
|
}
|
|
|
|
ELEMENT _elements[Capacity];
|
|
};
|
|
|
|
ELEMENT_HEAP _elementHeap;
|
|
|
|
static const UINT32 CapacityBits = UTIL::NUMBER_BITS<Capacity>::count;
|
|
|
|
// _activeQueue is a list of objects that are "in" the FIXED_LIFO. _freeQueue is a list
|
|
// of unused ELEMENT's.
|
|
//
|
|
LIFO_CTR<ELEMENT, ELEMENT_HEAP, CapacityBits, CounterBits, UINT64, STATS> _activeQueue;
|
|
LIFO_CTR<ELEMENT, ELEMENT_HEAP, CapacityBits, CounterBits, UINT64, STATS> _freeQueue;
|
|
};
|
|
|
|
} // namespace
|
|
#endif // file guard
|