bdlcc_fixedqueueindexmanager.h

Go to the documentation of this file.

/// @file bdlcc_fixedqueueindexmanager.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bdlcc_fixedqueueindexmanager.h                                     -*-C++-*-
#ifndef INCLUDED_BDLCC_FIXEDQUEUEINDEXMANAGER
#define INCLUDED_BDLCC_FIXEDQUEUEINDEXMANAGER
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bdlcc_fixedqueueindexmanager bdlcc_fixedqueueindexmanager
/// @brief  Provide thread-enabled state management for a fixed-size queue.
/// @addtogroup bdl
/// @{
/// @addtogroup bdlcc
/// @{
/// @addtogroup bdlcc_fixedqueueindexmanager
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bdlcc_fixedqueueindexmanager-purpose"> Purpose</a>
/// * <a href="#bdlcc_fixedqueueindexmanager-classes"> Classes </a>
/// * <a href="#bdlcc_fixedqueueindexmanager-description"> Description </a>
///   * <a href="#bdlcc_fixedqueueindexmanager-thread-safety"> Thread Safety </a>
///   * <a href="#bdlcc_fixedqueueindexmanager-exception-safety"> Exception safety </a>
///   * <a href="#bdlcc_fixedqueueindexmanager-usage"> Usage </a>
///     * <a href="#bdlcc_fixedqueueindexmanager-example-1-creating-a-thread-safe-queue-of-integers"> Example 1: Creating a Thread-Safe Queue of Integers </a>
///
/// # Purpose {#bdlcc_fixedqueueindexmanager-purpose}
/// Provide thread-enabled state management for a fixed-size queue.
///
/// # Classes {#bdlcc_fixedqueueindexmanager-classes}
///
/// -  bdlcc::FixedQueueIndexManager: state management for a queue
///
/// # Description {#bdlcc_fixedqueueindexmanager-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-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 {#bdlcc_fixedqueueindexmanager-exception-safety}
///
///
/// All methods of the `bdlcc::FixedQueueIndexManager` provide a no-throw
/// exception guarantee, except for the constructor, which is exception neutral.
///
/// ## Usage {#bdlcc_fixedqueueindexmanager-usage}
///
///
/// This section illustrates intended use of this component.
///
/// ### Example 1: Creating a Thread-Safe Queue of Integers {#bdlcc_fixedqueueindexmanager-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:
/// @code
/// /// 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:
/// @endcode
/// Then, we declare the methods of an integer queue:
/// @code
///     // 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;
/// };
/// @endcode
///  Next, we define the constructor, which initializes both the index manager
///  and vector with the supplied capacity:
/// @code
/// // CREATORS
/// IntegerQueue::IntegerQueue(bsl::size_t       capacity,
///                            bslma::Allocator *basicAllocator)
/// : d_indexManager(capacity, basicAllocator)
/// , d_values(capacity, 0, basicAllocator)
/// {
/// }
///
/// IntegerQueue::~IntegerQueue()
/// {
/// }
/// @endcode
/// 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:
/// @code
/// // 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;
/// }
/// @endcode
/// 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:
/// @code
/// // ACCESSORS
/// bsl::size_t IntegerQueue::length() const
/// {
///     return d_indexManager.length();
/// }
///
/// bsl::size_t IntegerQueue::capacity() const
/// {
///     return d_indexManager.capacity();
/// }
/// @endcode
/// Finally, we create an `IntegerQueue`, and push and pop a couple of elements
/// into the queue:
/// @code
/// 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);
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bdl
 * @{
 */
/** @addtogroup bdlcc
 * @{
 */
/** @addtogroup bdlcc_fixedqueueindexmanager
 * @{
 */
 
#include <bdlscm_version.h>
 
#include <bslmt_platform.h>
 
#include <bslma_allocator.h>
#include <bslma_usesbslmaallocator.h>
 
#include <bslmf_nestedtraitdeclaration.h>
 
#include <bsls_atomic.h>
#include <bsls_platform.h>
#include <bsls_performancehint.h>
 
#include <bsl_iosfwd.h>
#include <bsl_cstddef.h>
#include <bsl_cstdlib.h>
 
 
namespace bdlcc {
 
                        // ============================
                        // class FixedQueueIndexManager
                        // ============================
 
/// This class implements a circular buffer of atomic state variables.  These
/// are intended to synchronize access to another (non-atomic) indexed data
/// structure so that the other data structure can be used as a thread-enabled
/// fixed-size queue.
///
/// See @ref bdlcc_fixedqueueindexmanager 
class FixedQueueIndexManager {
 
    // PRIVATE CONSTANTS
    enum {
        k_PADDING =
                   bslmt::Platform::e_CACHE_LINE_SIZE - sizeof(bsls::AtomicInt)
    };
 
    // DATA
    bsls::AtomicInt     d_pushIndex;
                           // index in circular buffer in which the next
                           // element will be pushed (see implementation note
                           // in .cpp)
 
    const char          d_pushIndexPad[k_PADDING];
                           // padding to prevent false sharing
 
    bsls::AtomicInt     d_popIndex;
                           // index in the circular buffer from which the next
                           // element will be popped (see implementation note
                           // in .cpp)
 
    const char          d_popIndexPad[k_PADDING];
                           // padding to prevent false sharing
 
    const bsl::size_t   d_capacity;
                           // maximum number of elements that can be held in
                           // the circular buffer
 
    const unsigned int  d_maxGeneration;
                           // maximum generation count for this object (see
                           // implementation note in the .cpp file for more
                           // detail)
 
    const unsigned int  d_maxCombinedIndex;
                           // maximum combination of index and generation count
                           // that can stored in `d_pushIndex` and `d_popIndex`
                           // of this object (see implementation note in the
                           // .cpp file for more detail)
 
    bsls::AtomicInt    *d_states;
                           // array of index state variables
 
    bslma::Allocator   *d_allocator_p;
                           // allocator, held not owned
 
  private:
    // NOT IMPLEMENTED
    FixedQueueIndexManager(const FixedQueueIndexManager&); // = delete;
    FixedQueueIndexManager& operator=(
                                   const FixedQueueIndexManager&); // = delete;
 
  private:
 
    // PRIVATE ACCESSORS
 
    /// Return the combined index value subsequent to the specified
    /// `combinedIndex`.  Note that a "combined index" is the combination of
    /// generation count and element index held in `d_pushIndex` and
    /// `d_popIndex`, and is defined as:
    /// @code
    /// ('generationCount * d_capacity) + index'.
    /// @endcode
    /// See the implementation note in the .cpp file for more detail.
    unsigned int nextCombinedIndex(unsigned int combinedIndex) const;
 
    /// Return the generation subsequent to the specified `generation`.
    unsigned int nextGeneration(unsigned int generation) const;
 
  public:
    // TRAITS
    BSLMF_NESTED_TRAIT_DECLARATION(FixedQueueIndexManager,
                                   bslma::UsesBslmaAllocator);
 
    // CLASS METHODS
 
    /// Return the difference between the specified `minuend` and the
    /// specified `subtrahend` (typically `minuend - subtrahend`) where
    /// minuend and subtrahend are both "circular values", meaning they are
    /// part of a non-euclidean number line where the value wrap around to 0
    /// at the specified `modulo`.  The difference between two circular
    /// values is the minimum of either the number of increments or the
    /// number of decrements to `subtrahend` that results in `minuend`
    /// (i.e., the minimum "distance" between the points on the number
    /// circle), where increments are a positive difference, and decrements
    /// are a negative difference.  If the number of increments and number
    /// of decrements between `minuend` and `subtrahend` are equal,
    /// `minuend - subtrahend` is returned.  For example, for a hypothetical
    /// compass, [0, 360):
    /// @code
    /// circularDifference(   0, 359, 360) ==    1
    /// circularDifference( 359,   0, 360) ==   -1
    /// circularDifference( 180,   0, 360) ==  180
    /// circularDifference(   0, 180, 360) == -180
    /// @endcode
    /// The behavior is undefined unless `minuend < modulo`,
    /// `subtrahend < modulo`, and `modulo <= INT_MAX + 1`.
    static int circularDifference(unsigned int minuend,
                                  unsigned int subtrahend,
                                  unsigned int modulo);
 
    /// Return the number of representable generations for a circular buffer
    /// of the specified `capacity`.
    static unsigned int numRepresentableGenerations(bsl::size_t capacity);
 
    // PUBLIC CONSTANTS
    enum {
        k_MAX_CAPACITY = 1 << ((sizeof(int) * 8) - 2)
                                    // maximum capacity of an index manager;
                                    // note that 2 bits of `d_pushIndex` are
                                    // reserved for holding the disabled status
                                    // flag, and ensuring that the
                                    // representable number of generation
                                    // counts is at least 2 (see the
                                    // implementation note in the .cpp for more
                                    // details)
 
#ifndef BDE_OMIT_INTERNAL_DEPRECATED
      , e_MAX_CAPACITY = k_MAX_CAPACITY
#endif  // BDE_OMIT_INTERNAL_DEPRECATED
 
    };
 
    // CREATORS
 
    /// Create an index manager for a circular buffer having the specified
    /// maximum `capacity`.  Optionally specify a `basicAllocator` used to
    /// supply memory.  If `basicAllocator` is 0, the currently installed
    /// default allocator is used.  `isEnabled` will be `true` for the newly
    /// created index manager.  The behavior is undefined unless
    /// `0 < capacity` and `capacity <= k_MAX_CAPACITY`.
    explicit
    FixedQueueIndexManager(bsl::size_t       capacity,
                           bslma::Allocator *basicAllocator = 0);
 
    /// Destroy this object.
    ~FixedQueueIndexManager();
 
    // MANIPULATORS
                         // Pushing Elements
 
    /// Reserve the next available index at which to enqueue an element in
    /// an (externally managed) circular buffer; load the specified `index`
    /// with the reserved index and load the specified `generation` with the
    /// current generation of the circular buffer.  Return 0 on success, a
    /// negative value if the queue is disabled, and a positive value if the
    /// queue is full.  If this method succeeds, other threads using this
    /// object may spin on the corresponding index state until
    /// `commitPushIndex` is called using the returned `index` and
    /// `generation` values; clients should call `commitPushIndex` quickly
    /// after this method returns, without performing any blocking
    /// operations.  If this method fails the `generation` and `index` will
    /// be unmodified.  The behavior is undefined if the current thread is
    /// already holding a reservation on either a push or pop index.  Note
    /// that `generation` is necessary for invoking `commitPushIndex` but
    /// should not otherwise be used by the caller; the value reflects the
    /// number of times the `index` in the circular buffer has been used.
    int reservePushIndex(unsigned int *generation, unsigned int *index);
 
    /// Mark the specified `index` as occupied (full) in the specified
    /// `generation`.  The behavior is undefined unless `generation` and
    /// `index` match those returned by a previous successful call to
    /// `reservePushIndex` (that has not previously been committed).
    void commitPushIndex(unsigned int generation, unsigned int index);
 
                         // Popping Elements
 
    /// Reserve the next available index from which to dequeue an element
    /// from an (externally managed) circular buffer; load the specified
    /// `index` with the reserved index and load the specified `generation`
    /// with the current generation of the circular buffer.  Return 0 on
    /// success, and a non-zero value if the queue is empty.  If this method
    /// succeeds, other threads using this object may spin on the
    /// corresponding index state until `commitPopIndex` is called using the
    /// returned `index` and `generation` values; clients should call
    /// `commitPopIndex` quickly after this method returns, without
    /// performing any blocking operations.  If this method fails the
    /// `generation` and `index` will be unmodified.  The behavior is
    /// undefined if the current thread is already holding a reservation on
    /// either a push or pop index.  Note that `generation` is necessary for
    /// invoking `commitPopIndex` but should not otherwise be used by the
    /// caller; the value reflects the of times the `index` in the circular
    /// buffer has been used.
    int reservePopIndex(unsigned int *generation, unsigned int *index);
 
    /// Mark the specified `index` as available (empty) in the generation
    /// following the specified `generation`.  The behavior is undefined
    /// unless `generation` and index' match those returned by a previous
    /// successful call to `reservePopIndex` (that has not previously been
    /// committed).
    void commitPopIndex(unsigned int generation, unsigned int index);
 
                                // Disabled State
 
    /// Mark the queue as disabled.  Future calls to `reservePushIndex` will
    /// fail.
    void disable();
 
    /// Mark the queue as enabled.
    void enable();
 
                               // Exception Safety
 
    /// If the next available index from which an element can be popped is
    /// before the specified `endGeneration` and `endIndex` then reserve
    /// that index for popping and load the specified `disposedGeneration`
    /// and `disposedIndex` with the generation and index of the reserved
    /// cell; otherwise this operation has no effect.  Return 0 if an index
    /// was successfully reserved, and a non-zero value if the current pop
    /// index is at `endIndex` and `endGeneration`.  The behavior is
    /// undefined unless `endGeneration` and `endIndex` refer to a cell that
    /// has been acquired for writing.  Note that this operation is used to
    /// facilitate removing all the elements in a circular buffer if an
    /// exception is thrown between reserving an index for pushing, and
    /// committing that index -- the intended usage is to call
    /// `reservePopIndexForClear` and then `commitPopIndex`, emptying all
    /// the cells up to the index that was reserved for writing, and then
    /// call `abortPushIndexReservation` on the reserved index.
    int reservePopIndexForClear(unsigned int *disposedGeneration,
                                unsigned int *disposedIndex,
                                unsigned int  endGeneration,
                                unsigned int  endIndex);
 
    /// Release the specified `index` and make it available for use in the
    /// generation following the specified `generation`.  The behavior is
    /// undefined unless the calling thread holds a reservation on
    /// `generation` and `index`, and `clearPopIndex` and then
    /// `commitPushIndex` have been repeatedly invoked with `generation` and
    /// `index` as input until no indices remain to clear.  Note that this
    /// operation is used to facilitate removing all the elements in a
    /// circular buffer if an exception is thrown between reserving an index
    /// for pushing, and committing that index.
    void abortPushIndexReservation(unsigned int generation,
                                   unsigned int index);
 
    // ACCESSORS
 
    /// Return `true` if the queue is enabled, and `false` if it is
    /// disabled.
    bool isEnabled() const;
 
    /// Return a snapshot of the number of items in the queue.
    bsl::size_t length() const;
 
    /// Return the maximum number of items that may be stored in the queue.
    bsl::size_t capacity() const;
 
    /// Print a formatted string describing the current state of this object
    /// to the specified `stream`.  If `stream` is not valid on entry, this
    /// operation has no effect.  Note that this method describes the
    /// internal state of the buffer and is provided purely for debugging
    /// purposes.
    bsl::ostream& print(bsl::ostream& stream) const;
};
 
// ============================================================================
//                            INLINE DEFINITIONS
// ============================================================================
 
                        // ----------------------------
                        // class FixedQueueIndexManager
                        // ----------------------------
 
// PRIVATE ACCESSORS
inline
unsigned int FixedQueueIndexManager::nextCombinedIndex(
                                              unsigned int combinedIndex) const
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(d_maxCombinedIndex ==
                                              combinedIndex)) {
        // We have reached the maximum representable combination of index and
        // generation count, so we reset the generation count to 0.
 
        return 0;                                                     // RETURN
    }
 
    return combinedIndex + 1;
 
}
 
inline
unsigned int FixedQueueIndexManager::nextGeneration(
                                                 unsigned int generation) const
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(d_maxGeneration == generation)) {
        return 0;                                                     // RETURN
    }
    return generation + 1;
}
 
// ACCESSORS
inline
bsl::size_t FixedQueueIndexManager::capacity() const
{
    return d_capacity;
}
 
}  // close package namespace
 
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2015 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------
 
/** @} */
/** @} */
/** @} */