bdlc_flathashtable_groupcontrol.h

Go to the documentation of this file.

/// @file bdlc_flathashtable_groupcontrol.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bdlc_flathashtable_groupcontrol.h                                  -*-C++-*-
#ifndef INCLUDED_BDLC_FLATHASHTABLE_GROUPCONTROL
#define INCLUDED_BDLC_FLATHASHTABLE_GROUPCONTROL
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bdlc_flathashtable_groupcontrol bdlc_flathashtable_groupcontrol
/// @brief  Provide inquiries to a flat hash table group of control values.
/// @addtogroup bdl
/// @{
/// @addtogroup bdlc
/// @{
/// @addtogroup bdlc_flathashtable_groupcontrol
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bdlc_flathashtable_groupcontrol-purpose"> Purpose</a>
/// * <a href="#bdlc_flathashtable_groupcontrol-classes"> Classes </a>
/// * <a href="#bdlc_flathashtable_groupcontrol-description"> Description </a>
///   * <a href="#bdlc_flathashtable_groupcontrol-usage"> Usage </a>
///
/// # Purpose {#bdlc_flathashtable_groupcontrol-purpose}
/// Provide inquiries to a flat hash table group of control values.
///
/// # Classes {#bdlc_flathashtable_groupcontrol-classes}
///
/// -  bdlc::FlatHashTable_GroupControl: flat hash table group control inquiries
///
/// # Description {#bdlc_flathashtable_groupcontrol-description}
/// This component implements the class,
/// `bdlc::FlatHashTable_GroupControl`, that provides query methods to a group
/// of flat hash table control values.  Note that the number of entries in a
/// group control and the inquiry performance is platform dependant.
///
/// The flat hash map/set/table data structures are inspired by Google's
/// flat_hash_map CppCon presentations (available on youtube).  The
/// implementations draw from Google's open source `raw_hash_set.h` file at:
/// https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal.
///
/// ## Usage {#bdlc_flathashtable_groupcontrol-usage}
///
///
/// There is no usage example for this component since it is not meant for
/// direct client use.
/// @}
/** @} */
/** @} */
 
/** @addtogroup bdl
 * @{
 */
/** @addtogroup bdlc
 * @{
 */
/** @addtogroup bdlc_flathashtable_groupcontrol
 * @{
 */
 
#include <bdlscm_version.h>
 
#include <bsls_assert.h>
#include <bsls_byteorder.h>
#include <bsls_platform.h>
 
#include <bsl_cstddef.h>
#include <bsl_cstdint.h>
#include <bsl_cstring.h>
 
#if defined(BSLS_PLATFORM_CPU_SSE2)
#include <immintrin.h>
#include <emmintrin.h>
#endif
 
 
namespace bdlc {
 
                     // ================================
                     // class FlatHashTable_GroupControl
                     // ================================
 
/// This class provides methods for making inquires to the data of a group
/// control loading during construction.
class FlatHashTable_GroupControl
{
  public:
    // TYPES
#if defined(BSLS_PLATFORM_CPU_SSE2)
    typedef __m128i       Storage;
#else
    typedef bsl::uint64_t Storage;
#endif
 
  private:
    // CLASS DATA
    static const bsl::uint64_t k_MULT          = 0x0101010101010101ull;
    static const bsl::uint64_t k_DEFLATE       = 0x0002040810204081ull;
    static const int           k_DEFLATE_SHIFT = 56;
    static const bsl::uint64_t k_MSB_MASK      = 0x8080808080808080ull;
 
    // DATA
    Storage d_value;  // efficiently cached value for inquiries
 
    // PRIVATE ACCESSORS
 
    /// Return a bit mask of the `k_SIZE` entries that have the specified
    /// `value`.  The bit at index `i` corresponds to the result for
    /// `data[i]`.
    bsl::uint32_t matchRaw(bsl::uint8_t value) const;
 
  private:
    // NOT IMPLEMENTED
    FlatHashTable_GroupControl();
    FlatHashTable_GroupControl(const FlatHashTable_GroupControl&);
    FlatHashTable_GroupControl& operator=(const FlatHashTable_GroupControl&);
 
  public:
    // PUBLIC CLASS DATA
    static const bsl::uint8_t k_EMPTY  = 0x80;  // = 0b10000000
    static const bsl::uint8_t k_ERASED = 0xC0;  // = 0b11000000
    static const bsl::size_t  k_SIZE   = sizeof(Storage);
 
    // CREATORS
 
    /// Create a group control query object using the specified `data`.  The
    /// bytes of `data` have no alignment requirement.  
    /// 
    /// \pre The behavior is undefined   unless `data` has at least `k_SIZE` bytes available.
    explicit FlatHashTable_GroupControl(const bsl::uint8_t *data);
 
     ~FlatHashTable_GroupControl() = default;
        // Destroy this object.
 
    // ACCESSORS
 
    /// Return a bit mask of the `k_SIZE` entries that are empty or erased.
    /// The bit at index `i` corresponds to the result for `data[i]`.
    bsl::uint32_t available() const;
 
    /// Return a bit mask of the `k_SIZE` entries that are in use (i.e., not
    /// empty or erased).  The bit at index `i` corresponds to the result
    /// for `data[i]`.
    bsl::uint32_t inUse() const;
 
    /// Return a bit mask of the `k_SIZE` entries that have the specified
    /// `value`.  The bit at index `i` corresponds to the result for `data[i]`.  
    /// 
    /// \pre The behavior is undefined   unless `0 == (0x80 & value)`.
    bsl::uint32_t match(bsl::uint8_t value) const;
 
    /// Return `true` if this group control was never full (i.e., has a
    /// value that is empty, but not erased).
    bool neverFull() const;
};
 
// ============================================================================
//                             INLINE DEFINITIONS
// ============================================================================
 
                     // --------------------------------
                     // class FlatHashTable_GroupControl
                     // --------------------------------
 
// PRIVATE ACCESSORS
inline
bsl::uint32_t FlatHashTable_GroupControl::matchRaw(bsl::uint8_t value) const
{
#if defined(BSLS_PLATFORM_CPU_SSE2)
    return _mm_movemask_epi8(_mm_cmpeq_epi8(
                                       _mm_set1_epi8(static_cast<char>(value)),
                                       d_value));
#else
    Storage t = d_value ^ (k_MULT * value);
 
    t = t | (t << 4);
    t = t | (t << 2);
    t = t | (t << 1);
 
    return static_cast<bsl::uint32_t>(
                         (((~t) & k_MSB_MASK) * k_DEFLATE) >> k_DEFLATE_SHIFT);
#endif
}
 
// CREATORS
inline
FlatHashTable_GroupControl::FlatHashTable_GroupControl(
                                                      const bsl::uint8_t *data)
{
#if defined(BSLS_PLATFORM_CPU_SSE2)
    d_value = _mm_loadu_si128(static_cast<const Storage *>(
                                             static_cast<const void *>(data)));
#else
    bsl::memcpy(&d_value, data, k_SIZE);
    d_value = BSLS_BYTEORDER_HOST_U64_TO_LE(d_value);
#endif
}
 
// ACCESSORS
inline
bsl::uint32_t FlatHashTable_GroupControl::available() const
{
#if defined(BSLS_PLATFORM_CPU_SSE2)
    return _mm_movemask_epi8(d_value);
#else
    return static_cast<bsl::uint32_t>(
                      ((d_value & k_MSB_MASK) * k_DEFLATE) >> k_DEFLATE_SHIFT);
#endif
}
 
inline
bsl::uint32_t FlatHashTable_GroupControl::inUse() const
{
#if defined(BSLS_PLATFORM_CPU_SSE2)
    return (~available()) & 0xFFFF;
#else
    return (~available()) & 0xFF;
#endif
}
 
inline
bsl::uint32_t FlatHashTable_GroupControl::match(bsl::uint8_t value) const
{
    BSLS_ASSERT_SAFE(0 == (value & 0x80));
 
    return matchRaw(value);
}
 
inline
bool FlatHashTable_GroupControl::neverFull() const
{
    return 0 != matchRaw(k_EMPTY);
}
 
}  // close package namespace
 
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2020 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 ----------------------------------
 
/** @} */
/** @} */
/** @} */