bslalg_dequeimputil.h

Go to the documentation of this file.

/// @file bslalg_dequeimputil.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslalg_dequeimputil.h                                              -*-C++-*-
#ifndef INCLUDED_BSLALG_DEQUEIMPUTIL
#define INCLUDED_BSLALG_DEQUEIMPUTIL
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslalg_dequeimputil bslalg_dequeimputil
/// @brief  Provide basic parameters and primitive data structures for deques.
/// @addtogroup bsl
/// @{
/// @addtogroup bslalg
/// @{
/// @addtogroup bslalg_dequeimputil
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslalg_dequeimputil-purpose"> Purpose</a>
/// * <a href="#bslalg_dequeimputil-classes"> Classes </a>
/// * <a href="#bslalg_dequeimputil-description"> Description </a>
///   * <a href="#bslalg_dequeimputil-usage"> Usage </a>
///
/// # Purpose {#bslalg_dequeimputil-purpose}
/// Provide basic parameters and primitive data structures for deques.
///
/// # Classes {#bslalg_dequeimputil-classes}
///
/// -  bslalg::DequeImpUtil: deque parameters and primitive data structures
///
/// @see  bslalg_dequeprimitives, bslalg_arrayprimitives
///
/// # Description {#bslalg_dequeimputil-description}
/// This component provides primitive data structures for
/// implementing a deque knowing only its value type and the number of objects
/// in a block.  Conceptually, a deque is an array of blocks pointers, each
/// block capable of containing a fixed number of objects.  An element in the
/// deque is identified by an iterator that consists of a pointer to the block
/// pointer array, and a pointer to a value.  A deque implementation is
/// parameterized by the `VALUE_TYPE` and a `BLOCK_LENGTH` (fixed number of
/// objects in a block).  `bslalg::DequeImpUtil` provides a namespace for the
/// following types and constants:
/// @code
/// Type                   Short description
/// ----                   -----------------
/// ValueType              An alias for the templatized 'VALUE_TYPE'
/// Block                  An array (of length 'BLOCK_LENGTH') of 'ValueType'
/// BlockPtr               An alias for a pointer to a block
///
/// Constant               Short description
/// --------               -----------------
/// BLOCK_BYTES            Number of bytes in a block
/// BLOCK_ARRAY_PADDING    Number of empty blocks to keep at both ends of the
///                        block array pointer (one on each side).
/// @endcode
///
/// The picture is as follows:
/// @code
/// +-----+-----+-----+-----+-----+-----+-----+-----+
/// |  *  |  *  |  *  |  *  |  *  |  *  |  *  |  *  |  (BlockPtr array)
/// +-----+-----+--|--+--|--+--|--+--|--+-----+-----+
///                |     |     |     |                     Block
///                |     |     |     |  +---+---+---+---+---+---+---+---+
///                |     |     |     `--| V | W | X | Y | Z |   |   |   |
///                |     |     |        +---+---+---+---+---+---+---+---+
///                |     |     |                      Block
///                |     |     |  +---+---+---+---+---+---+---+---+
///                |     |     `--| N | O | P | Q | R | S | T | U |
///                |     |        +---+---+---+---+---+---+---+---+
///                |     |                      Block
///                |     |  +---+---+---+---+---+---+---+---+
///                |     `--| F | G | H | I | J | K | L | M |
///                |        +---+---+---+---+---+---+---+---+
///                |                      Block
///                |  +---+---+---+---+---+---+---+---+
///                `--|   |   |   | A | B | C | D | E |
///                   +---+---+---+---+---+---+---+---+
/// @endcode
/// Depicted above is a deque consisting of an array of eight block pointers,
/// only four actually used to point to blocks of eight elements.  In the first
/// block, the first three elements are uninitialized, and the twenty six
/// elements follow in sequence across the different blocks.  The value of the
/// corresponding deque would be `[ A, B, C, ... X, Y, Z ]`, its logical length
/// 26, and its capacity would be 19 (the minimum number of prepend/append to
/// force a reallocation of the block pointer array).
///
/// ## Usage {#bslalg_dequeimputil-usage}
///
///
/// This component is for use by the `bslalg` package.  Other clients should use
/// the STL deque (in header `<deque>`).
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslalg
 * @{
 */
/** @addtogroup bslalg_dequeimputil
 * @{
 */
 
#include <bslscm_version.h>
 
 
 
namespace bslalg {
 
                           // ==============
                           // class DequeImp
                           // ==============
 
/// This `struct`, parameterized by the `VALUE_TYPE` and a `BLOCK_LENGTH`,
/// provides the various parameters of the deque implementation.
///
/// See @ref bslalg_dequeimputil 
template <class VALUE_TYPE, int BLOCK_LENGTH>
struct DequeImpUtil {
 
    // PUBLIC CONSTANTS
 
    /// Actual number of bytes in a block.
    enum { BLOCK_BYTES         = BLOCK_LENGTH * sizeof(VALUE_TYPE) };
 
    /// Minimum number of (allocated) empty blocks to keep at both ends of
    /// the block array pointer (one on each side of the deque).
    enum { BLOCK_ARRAY_PADDING = 2 };
 
    // PUBLIC TYPES
 
    /// `ValueType` is an alias for the `VALUE_TYPE` provided as first
    /// template parameter to this class.
    typedef VALUE_TYPE  ValueType;
 
    /// A block of one or more data objects.  A deque will be organized as a
    /// sequence of blocks.
    ///
    /// See @ref bslalg_dequeimputil 
    struct Block {
 
        VALUE_TYPE d_data[BLOCK_LENGTH];
    };
 
    /// Pointer to a block.  A deque will own an array of those.
    typedef Block *BlockPtr;
};
 
}  // close package namespace
 
#ifndef BDE_OPENSOURCE_PUBLICATION  // BACKWARD_COMPATIBILITY
// ============================================================================
//                           BACKWARD COMPATIBILITY
// ============================================================================
 
#ifdef bslalg_DequeImpUtil
#undef bslalg_DequeImpUtil
#endif
/// This alias is defined for backward compatibility.
#define bslalg_DequeImpUtil bslalg::DequeImpUtil
#endif  // BDE_OPENSOURCE_PUBLICATION -- BACKWARD_COMPATIBILITY
 
 
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2013 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 ----------------------------------
 
/** @} */
/** @} */
/** @} */