Component bdlcc_fixedqueueindexmanager [Package bdlcc]

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

Namespaces
namespace	bdlcc

---

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:

  class IntegerQueue {
      // This class provides a fully thread-safe queue of integers with a
      // fixed maximum capacity.

      // 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
      explicit IntegerQueue(bsl::size_t       capacity,
                            bslma::Allocator *basicAllocator = 0);
          // Create a queue capable of holding up to the specified
          // 'capacity' number of integer values.

      ~IntegerQueue();
          // Destroy this queue.

      // MANIPULATORS
      int tryPushBack(int value);
          // 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 tryPopFront(int *result);
          // 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.

      // ACCESSORS
      bsl::size_t length() const;
          // Return a snapshot of the number of elements currently in this
          // queue.

      bsl::size_t capacity() const;
          // Return the maximum number of elements that this queue can hold.
  };

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);