Skip to content

Instantly share code, notes, and snippets.

@hutorny
Last active January 2, 2020 07:40
Show Gist options
  • Save hutorny/c189289bb5687217ec32f408156ff8f6 to your computer and use it in GitHub Desktop.
Save hutorny/c189289bb5687217ec32f408156ff8f6 to your computer and use it in GitHub Desktop.
#include <type_traits>
#if __cplusplus > 201709L
#include <bit>
template<typename T>
constexpr int countr_zero(T val) noexcept { return std::countr_zero(val); }
template<typename T>
constexpr int popcount(T val) noexcept { return std::popcount(val); }
#else
template<typename T, typename = std::enable_if_t<std::is_integral<T>::value,T>>
constexpr int countr_zero(T val) noexcept { return __builtin_ctz(val); }
template<typename T, typename = std::enable_if_t<std::is_integral<T>::value,T>>
constexpr int popcount(T val) noexcept { return __builtin_popcount(val); }
#endif
template<typename T, typename = std::enable_if_t<std::is_integral<T>::value,T>>
constexpr int bitwidth(const T&) noexcept { return sizeof(T) * 8; }
template<template<std::size_t> class T, std::size_t N, typename = decltype(&T<N>::_Find_first)>
constexpr int countr_zero(const T<N>& val) noexcept {
return val._Find_first(); /* _Find_first is not in standard, its GCC extension */
}
template<template<std::size_t> class T, std::size_t N>
constexpr int popcount(const T<N>& val) noexcept {
return val.count();
}
template<template<std::size_t> class T, std::size_t N>
constexpr int bitwidth(const T<N>& val) noexcept {
return val.size();
}
/**
* setof - set of "named" bits, e.g. bit made from an enum
* params:
* Enum - enum type
* Storage - storage type, integral or bitset<N>
*/
template<typename Enum, typename Storage = unsigned>
class setof {
public:
static constexpr Storage lsh(Enum value) noexcept { return static_cast<Storage>(1) << static_cast<unsigned>(value); }
static constexpr Storage bit_or() noexcept { return {}; }
template<typename ... Enums>
static constexpr Storage bit_or(Enum value, Enums ... values) noexcept {
if constexpr (sizeof...(values) == 0 ) return lsh(value);
else return lsh(value) | bit_or(values...);
}
template<typename ... Enums>
constexpr setof(Enums ... values) noexcept : bits { bit_or(values...) } {
static_assert(std::conjunction<std::is_same<Enum,Enums>...>::value, "Value type mismatch");
}
constexpr setof(const setof& that) noexcept : bits { that.bits } {}
constexpr setof operator&(const setof& that) const noexcept { return setof(bits & that.bits); }
constexpr setof operator|(const setof& that) const noexcept { return setof(bits | that.bits); }
constexpr setof& operator|=(const setof& that) noexcept { bits |= that.bits; return *this; }
constexpr setof& operator&=(const setof& that) noexcept { bits &= that.bits; return *this; }
constexpr setof& operator=(const setof& that) noexcept { bits = that.bits; return *this; }
constexpr bool operator[](Enum val) const noexcept { return (bits & static_cast<unsigned>(val)) != Storage{}; }
constexpr bool operator==(const setof& that) const noexcept { return bits == that.bits; }
explicit constexpr operator Storage () const noexcept { return bits; }
constexpr int capacity() const noexcept { return bitwidth(bits); }
template<typename ... Enums>
constexpr bool any(Enums ... values) const noexcept {
static_assert(std::conjunction<std::is_same<Enum,Enums>...>::value, "Value type mismatch");
return Storage {} != (bits & setof(values...).bits);
}
template<typename ... Enums>
constexpr bool all(Enums ... values) const noexcept {
static_assert(std::conjunction<std::is_same<Enum,Enums>...>::value, "Value type mismatch");
return setof(values...).bits == (bits & setof(values...).bits);
}
template<typename ... Enums>
constexpr bool none(Enums ... values) const noexcept {
static_assert(std::conjunction<std::is_same<Enum,Enums>...>::value, "Value type mismatch");
return Storage {} == (bits & setof(values...).bits);
}
constexpr bool all(const setof& value) const noexcept { return value.bits == (bits & value.bits); }
constexpr bool any(const setof& value) const noexcept { return Storage {} != (bits & value.bits); }
constexpr bool none(const setof& value) const noexcept { return Storage {} == (bits & value.bits); }
constexpr bool empty() const noexcept { return bits == Storage {}; }
constexpr auto count() const noexcept { return popcount(bits); }
setof& set(Enum val) noexcept { bits |= lsh(val); return *this; }
setof& reset(Enum val) noexcept { bits &= ~lsh(val); return *this; }
class iterator {
public:
constexpr iterator(const iterator&) = default;
constexpr iterator& operator=(const iterator&) = default;
constexpr Enum operator*() const noexcept { return static_cast<Enum>(pos); }
constexpr iterator& operator++() {
const auto rem = container.bits >> ++pos;
if( rem == Storage{} ) pos = container.capacity();
else pos += countr_zero(rem);
return *this;
}
constexpr bool operator==(const iterator& that) const noexcept { return &container == &that.container && pos == that.pos; }
constexpr bool operator!=(const iterator& that) const noexcept { return not (that == *this); }
private:
friend class setof;
constexpr iterator(const setof& cont) noexcept : container(cont), pos {cont.empty() ? cont.capacity() : countr_zero(cont.bits)} {}
constexpr iterator(const setof& cont, unsigned) noexcept : container(cont), pos {cont.capacity()} {}
const setof& container;
int pos;
};
constexpr iterator begin() const noexcept { return iterator(*this); }
constexpr iterator end() const noexcept { return iterator(*this,0); }
private:
constexpr setof(Storage val) : bits { val } {}
Storage bits;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment