chromium/third_party/angle/src/common/bitset_utils.h

//
// Copyright 2015 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// bitset_utils:
//   Bitset-related helper classes, such as a fast iterator to scan for set bits.
//

#ifndef COMMON_BITSETITERATOR_H_
#define COMMON_BITSETITERATOR_H_

#include <stdint.h>

#include <array>

#include "common/angleutils.h"
#include "common/debug.h"
#include "common/mathutil.h"
#include "common/platform.h"

namespace angle
{
// Given x, create 1 << x.
template <typename BitsT, typename ParamT>
constexpr BitsT Bit(ParamT x)
{ … }

// Given x, create (1 << x) - 1, i.e. a mask with x bits set.
template <typename BitsT, typename ParamT>
constexpr BitsT BitMask(ParamT x)
{ … }

template <size_t N, typename BitsT, typename ParamT = std::size_t>
class BitSetT final
{ … };

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT>::BitSetT() : … { … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT>::BitSetT(BitsT value) : … { … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT>::BitSetT(std::initializer_list<ParamT> init) : … { … }

template <size_t N, typename BitsT, typename ParamT>
constexpr bool BitSetT<N, BitsT, ParamT>::operator==(const BitSetT &other) const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr bool BitSetT<N, BitsT, ParamT>::operator!=(const BitSetT &other) const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr bool BitSetT<N, BitsT, ParamT>::operator[](ParamT pos) const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr bool BitSetT<N, BitsT, ParamT>::test(ParamT pos) const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr bool BitSetT<N, BitsT, ParamT>::all() const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr bool BitSetT<N, BitsT, ParamT>::any() const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr bool BitSetT<N, BitsT, ParamT>::none() const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr std::size_t BitSetT<N, BitsT, ParamT>::count() const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr bool BitSetT<N, BitsT, ParamT>::hasGaps() const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator&=(const BitSetT &other)
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator|=(const BitSetT &other)
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator^=(const BitSetT &other)
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator~() const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator&=(BitsT value)
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator|=(BitsT value)
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator^=(BitsT value)
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator<<(std::size_t pos) const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator<<=(std::size_t pos)
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator>>(std::size_t pos) const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator>>=(std::size_t pos)
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::set()
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::set(ParamT pos, bool value)
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::reset()
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::reset(ParamT pos)
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::flip()
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::flip(ParamT pos)
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr ParamT BitSetT<N, BitsT, ParamT>::first() const
{ … }

template <size_t N, typename BitsT, typename ParamT>
constexpr ParamT BitSetT<N, BitsT, ParamT>::last() const
{ … }

template <size_t N, typename BitsT, typename ParamT>
BitSetT<N, BitsT, ParamT>::Iterator::Iterator(const BitSetT &bits) : … { … }

template <size_t N, typename BitsT, typename ParamT>
ANGLE_INLINE typename BitSetT<N, BitsT, ParamT>::Iterator &
BitSetT<N, BitsT, ParamT>::Iterator::operator++()
{ … }

template <size_t N, typename BitsT, typename ParamT>
bool BitSetT<N, BitsT, ParamT>::Iterator::operator==(const Iterator &other) const
{ … }

template <size_t N, typename BitsT, typename ParamT>
bool BitSetT<N, BitsT, ParamT>::Iterator::operator!=(const Iterator &other) const
{ … }

template <size_t N, typename BitsT, typename ParamT>
ParamT BitSetT<N, BitsT, ParamT>::Iterator::operator*() const
{ … }

template <size_t N, typename BitsT, typename ParamT>
std::size_t BitSetT<N, BitsT, ParamT>::Iterator::getNextBit()
{ … }

BitSet8;

BitSet16;

BitSet32;
static_assert …;

BitSet64;

template <std::size_t N>
class BitSetArray;

namespace priv
{

EnableIfBitsFit;

template <size_t N, typename Enable = void>
struct GetBitSet
{ … };

// Prefer 64-bit bitsets on 64-bit CPUs. They seem faster than 32-bit.
#if defined(ANGLE_IS_64_BIT_CPU)
GetBitSet<N, EnableIfBitsFit<N, uint64_t>>;
constexpr std::size_t kDefaultBitSetSize = …;
BaseBitSetType;
#else
template <size_t N>
struct GetBitSet<N, EnableIfBitsFit<N, uint32_t>>
{
    using Type = BitSet32<N>;
};
constexpr std::size_t kDefaultBitSetSize = 32;
using BaseBitSetType                     = BitSet32<kDefaultBitSetSize>;
#endif  // defined(ANGLE_IS_64_BIT_CPU)

}  // namespace priv

BitSet;

template <std::size_t N>
class BitSetArray final
{ … };
static_assert …;

template <std::size_t N>
constexpr BitSetArray<N>::BitSetArray()
{ … }

template <std::size_t N>
constexpr BitSetArray<N>::BitSetArray(uint64_t value)
{ … }

template <std::size_t N>
constexpr BitSetArray<N>::BitSetArray(std::initializer_list<param_type> init)
{ … }

template <size_t N>
BitSetArray<N>::Iterator::Iterator(const BitSetArray<N> &bitSetArray, std::size_t index)
    : … { … }

template <std::size_t N>
typename BitSetArray<N>::Iterator &BitSetArray<N>::Iterator::operator++()
{ … }

template <std::size_t N>
bool BitSetArray<N>::Iterator::operator==(const BitSetArray<N>::Iterator &other) const
{ … }

template <std::size_t N>
bool BitSetArray<N>::Iterator::operator!=(const BitSetArray<N>::Iterator &other) const
{ … }

template <std::size_t N>
std::size_t BitSetArray<N>::Iterator::operator*() const
{ … }

template <std::size_t N>
constexpr BitSetArray<N> &BitSetArray<N>::operator&=(const BitSetArray<N> &other)
{ … }

template <std::size_t N>
constexpr BitSetArray<N> &BitSetArray<N>::operator|=(const BitSetArray<N> &other)
{ … }

template <std::size_t N>
constexpr BitSetArray<N> &BitSetArray<N>::operator^=(const BitSetArray<N> &other)
{ … }

template <std::size_t N>
constexpr BitSetArray<N> BitSetArray<N>::operator&(const angle::BitSetArray<N> &other) const
{ … }

template <std::size_t N>
constexpr BitSetArray<N> BitSetArray<N>::operator|(const angle::BitSetArray<N> &other) const
{ … }

template <std::size_t N>
constexpr BitSetArray<N> BitSetArray<N>::operator^(const angle::BitSetArray<N> &other) const
{ … }

template <std::size_t N>
constexpr bool BitSetArray<N>::operator==(const angle::BitSetArray<N> &other) const
{ … }

template <std::size_t N>
constexpr bool BitSetArray<N>::operator!=(const angle::BitSetArray<N> &other) const
{ … }

template <std::size_t N>
constexpr BitSetArray<N> BitSetArray<N>::operator~() const
{ … }

template <std::size_t N>
constexpr bool BitSetArray<N>::operator[](std::size_t pos) const
{ … }

template <std::size_t N>
constexpr BitSetArray<N> &BitSetArray<N>::set()
{ … }

template <std::size_t N>
constexpr BitSetArray<N> &BitSetArray<N>::set(std::size_t pos, bool value)
{ … }

template <std::size_t N>
constexpr BitSetArray<N> &BitSetArray<N>::reset()
{ … }

template <std::size_t N>
constexpr BitSetArray<N> &BitSetArray<N>::reset(std::size_t pos)
{ … }

template <std::size_t N>
constexpr bool BitSetArray<N>::test(std::size_t pos) const
{ … }

template <std::size_t N>
constexpr bool BitSetArray<N>::all() const
{ … }

template <std::size_t N>
constexpr bool BitSetArray<N>::any() const
{ … }

template <std::size_t N>
constexpr bool BitSetArray<N>::none() const
{ … }

template <std::size_t N>
constexpr std::size_t BitSetArray<N>::count() const
{ … }

template <std::size_t N>
constexpr bool BitSetArray<N>::intersects(const BitSetArray<N> &other) const
{ … }

template <std::size_t N>
constexpr BitSetArray<N> &BitSetArray<N>::flip()
{ … }

template <std::size_t N>
constexpr typename BitSetArray<N>::param_type BitSetArray<N>::first() const
{ … }

template <std::size_t N>
constexpr typename BitSetArray<N>::param_type BitSetArray<N>::last() const
{ … }

template <std::size_t N>
constexpr typename BitSetArray<N>::value_type BitSetArray<N>::bits(size_t index) const
{ … }

template <std::size_t N>
constexpr BitSetArray<N> BitSetArray<N>::Mask(std::size_t x)
{ … }
}  // namespace angle

template <size_t N, typename BitsT, typename ParamT>
inline constexpr angle::BitSetT<N, BitsT, ParamT> operator&(
    const angle::BitSetT<N, BitsT, ParamT> &lhs,
    const angle::BitSetT<N, BitsT, ParamT> &rhs)
{ … }

template <size_t N, typename BitsT, typename ParamT>
inline constexpr angle::BitSetT<N, BitsT, ParamT> operator|(
    const angle::BitSetT<N, BitsT, ParamT> &lhs,
    const angle::BitSetT<N, BitsT, ParamT> &rhs)
{ … }

template <size_t N, typename BitsT, typename ParamT>
inline constexpr angle::BitSetT<N, BitsT, ParamT> operator^(
    const angle::BitSetT<N, BitsT, ParamT> &lhs,
    const angle::BitSetT<N, BitsT, ParamT> &rhs)
{ … }

template <size_t N, typename BitsT, typename ParamT>
inline bool operator==(angle::BitSetT<N, BitsT, ParamT> &lhs, angle::BitSetT<N, BitsT, ParamT> &rhs)
{ … }

template <size_t N, typename BitsT, typename ParamT>
inline bool operator!=(angle::BitSetT<N, BitsT, ParamT> &lhs, angle::BitSetT<N, BitsT, ParamT> &rhs)
{ … }

#endif  // COMMON_BITSETITERATOR_H_