bdlcc_fixedqueueindexmanager

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Thread Safety
  • Exception safety
  • Usage
    • Example 1: Creating a Thread-Safe Queue of Integers

Purpose

Provide thread-enabled state management for a fixed-size queue.

Classes

• bdlcc::FixedQueueIndexManager: state management for a queue

Description

This component implements a lock-free mechanism for managing the indices of a circular buffer of elements to facilitate the implementation of a fixed-size thread-enabled single-ended queue. A bdlcc::FixedQueueIndexManager is supplied the size of a circular buffer on construction, and provides the methods to reserve indices for enqueing and dequeing elements in that buffer. The actual buffer is held in some other (external) data structure managed by the user of this component.

This component is not itself a general-purpose queue data structure. For example, no user data of any kind is stored in this data structure (it is not a queue of integers), and successful invocation of certain methods (reservePopIndex, reservePushIndex) obligates the caller to invoke a corresponding method (commitPopIndex, commitPushIndex respectively); otherwise, other threads may "spin" indefinitely with severe performance consequences.

Thread Safety

bdlcc::FixedQueueIndexManager is fully thread-safe, meaning that all non-creator operations on an object can be safely invoked simultaneously from multiple threads.

Exception safety

All methods of the bdlcc::FixedQueueIndexManager provide a no-throw exception guarantee, except for the constructor, which is exception neutral.

Usage

This section illustrates intended use of this component.

Example 1: Creating a Thread-Safe Queue of Integers

In the following example we create a simple thread-safe queue of integers using a bdlcc::FixedQueueIndexManager to synchronize the queue operations.

We start by declaring the data members of an IntegerQueue, a vector of integers, to hold the values in the queue, and an index manager to ensure thread-safe access to the indices of the vector:

/// This class provides a fully thread-safe queue of integers with a
/// fixed maximum capacity.
class IntegerQueue {
 
    // DATA
    bdlcc::FixedQueueIndexManager d_indexManager;  // manages `d_values`
                                                   // indices
 
    bsl::vector<int>              d_values;        // maintains values
 
  private:
    // Not implemented:
    IntegerQueue(const IntegerQueue&);
 
  public:

Then, we declare the methods of an integer queue:

    // CREATORS
 
    /// Create a queue capable of holding up to the specified
    /// `capacity` number of integer values.
    explicit IntegerQueue(bsl::size_t       capacity,
                          bslma::Allocator *basicAllocator = 0);
 
    /// Destroy this queue.
    ~IntegerQueue();
 
    // MANIPULATORS
 
    /// Attempt to push the specified `value` onto the back of this
    /// queue.  Return 0 on success, and a non-zero value if this queue
    /// is full.
    int tryPushBack(int value);
 
    /// Attempt to remove an element from the front of this queue and
    /// load the removed value into the specified `result`.  Return 0
    /// on success, and a non-zero value otherwise.
    int tryPopFront(int *result);
 
    // ACCESSORS
 
    /// Return a snapshot of the number of elements currently in this
    /// queue.
    bsl::size_t length() const;
 
    /// Return the maximum number of elements that this queue can hold.
    bsl::size_t capacity() const;
};

Next, we define the constructor, which initializes both the index manager and vector with the supplied capacity:

// CREATORS
IntegerQueue::IntegerQueue(bsl::size_t       capacity,
                           bslma::Allocator *basicAllocator)
: d_indexManager(capacity, basicAllocator)
, d_values(capacity, 0, basicAllocator)
{
}
 
IntegerQueue::~IntegerQueue()
{
}

Now, we define tryPushBack and tryPopFront, which use the index manager to reserve an index in the vector, operate on that index, and then commit that index back to the index manager:

// MANIPULATORS
int IntegerQueue::tryPushBack(int value)
{
    unsigned int generation, index;
    if (0 == d_indexManager.reservePushIndex(&generation, &index)) {
        d_values[index] = value;
        d_indexManager.commitPushIndex(generation, index);
        return 0;                                                 // RETURN
    }
    return -1;
}
 
int IntegerQueue::tryPopFront(int *result)
{
    unsigned int generation, index;
    if (0 == d_indexManager.reservePopIndex(&generation, &index)) {
        *result = d_values[index];
        d_indexManager.commitPopIndex(generation, index);
        return 0;                                                 // RETURN
    }
    return -1;
}

Notice that because none of these operations allocate memory, we do not need to add code to ensure exception safety.

Then, we define the accessors to the integer queue:

// ACCESSORS
bsl::size_t IntegerQueue::length() const
{
    return d_indexManager.length();
}
 
bsl::size_t IntegerQueue::capacity() const
{
    return d_indexManager.capacity();
}

Finally, we create an IntegerQueue, and push and pop a couple of elements into the queue:

IntegerQueue intQueue(2);
int rc = intQueue.tryPushBack(1);
assert(0 == rc);
 
rc = intQueue.tryPushBack(2);
assert(0 == rc);
 
rc = intQueue.tryPushBack(3);
assert(0 != rc);
 
assert(2 == intQueue.length());
 
int result;
 
rc = intQueue.tryPopFront(&result);
assert(0 == rc);
assert(1 == result);