| 1 |
// Copyright (c) 2016 Google Inc. |
| 2 |
// |
| 3 |
// Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 |
// you may not use this file except in compliance with the License. |
| 5 |
// You may obtain a copy of the License at |
| 6 |
// |
| 7 |
// http://www.apache.org/licenses/LICENSE-2.0 |
| 8 |
// |
| 9 |
// Unless required by applicable law or agreed to in writing, software |
| 10 |
// distributed under the License is distributed on an "AS IS" BASIS, |
| 11 |
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 |
// See the License for the specific language governing permissions and |
| 13 |
// limitations under the License. |
| 14 |
|
| 15 |
#ifndef SOURCE_ENUM_SET_H_ |
| 16 |
#define SOURCE_ENUM_SET_H_ |
| 17 |
|
| 18 |
#include <cstdint> |
| 19 |
#include <functional> |
| 20 |
#include <memory> |
| 21 |
#include <set> |
| 22 |
#include <utility> |
| 23 |
|
| 24 |
#include "source/latest_version_spirv_header.h" |
| 25 |
#include "source/util/make_unique.h" |
| 26 |
|
| 27 |
namespace spvtools { |
| 28 |
|
| 29 |
// A set of values of a 32-bit enum type. |
| 30 |
// It is fast and compact for the common case, where enum values |
| 31 |
// are at most 63. But it can represent enums with larger values, |
| 32 |
// as may appear in extensions. |
| 33 |
template <typename EnumType> |
| 34 |
class EnumSet { |
| 35 |
private: |
| 36 |
// The ForEach method will call the functor on enum values in |
| 37 |
// enum value order (lowest to highest). To make that easier, use |
| 38 |
// an ordered set for the overflow values. |
| 39 |
using OverflowSetType = std::set<uint32_t>; |
| 40 |
|
| 41 |
public: |
| 42 |
// Construct an empty set. |
| 43 |
EnumSet() {} |
| 44 |
// Construct an set with just the given enum value. |
| 45 |
explicit EnumSet(EnumType c) { Add(c); } |
| 46 |
// Construct an set from an initializer list of enum values. |
| 47 |
EnumSet(std::initializer_list<EnumType> cs) { |
| 48 |
for (auto c : cs) Add(c); |
| 49 |
} |
| 50 |
EnumSet(uint32_t count, const EnumType* ptr) { |
| 51 |
for (uint32_t i = 0; i < count; ++i) Add(ptr[i]); |
| 52 |
} |
| 53 |
// Copy constructor. |
| 54 |
EnumSet(const EnumSet& other) { *this = other; } |
| 55 |
// Move constructor. The moved-from set is emptied. |
| 56 |
EnumSet(EnumSet&& other) { |
| 57 |
mask_ = other.mask_; |
| 58 |
overflow_ = std::move(other.overflow_); |
| 59 |
other.mask_ = 0; |
| 60 |
other.overflow_.reset(nullptr); |
| 61 |
} |
| 62 |
// Assignment operator. |
| 63 |
EnumSet& operator=(const EnumSet& other) { |
| 64 |
if (&other != this) { |
| 65 |
mask_ = other.mask_; |
| 66 |
overflow_.reset(other.overflow_ ? new OverflowSetType(*other.overflow_) |
| 67 |
: nullptr); |
| 68 |
} |
| 69 |
return *this; |
| 70 |
} |
| 71 |
|
| 72 |
friend bool operator==(const EnumSet& a, const EnumSet& b) { |
| 73 |
if (a.mask_ != b.mask_) { |
| 74 |
return false; |
| 75 |
} |
| 76 |
|
| 77 |
if (a.overflow_ == nullptr && b.overflow_ == nullptr) { |
| 78 |
return true; |
| 79 |
} |
| 80 |
|
| 81 |
if (a.overflow_ == nullptr || b.overflow_ == nullptr) { |
| 82 |
return false; |
| 83 |
} |
| 84 |
|
| 85 |
return *a.overflow_ == *b.overflow_; |
| 86 |
} |
| 87 |
|
| 88 |
friend bool operator!=(const EnumSet& a, const EnumSet& b) { |
| 89 |
return !(a == b); |
| 90 |
} |
| 91 |
|
| 92 |
// Adds the given enum value to the set. This has no effect if the |
| 93 |
// enum value is already in the set. |
| 94 |
void Add(EnumType c) { AddWord(ToWord(c)); } |
| 95 |
|
| 96 |
// Removes the given enum value from the set. This has no effect if the |
| 97 |
// enum value is not in the set. |
| 98 |
void Remove(EnumType c) { RemoveWord(ToWord(c)); } |
| 99 |
|
| 100 |
// Returns true if this enum value is in the set. |
| 101 |
bool Contains(EnumType c) const { return ContainsWord(ToWord(c)); } |
| 102 |
|
| 103 |
// Applies f to each enum in the set, in order from smallest enum |
| 104 |
// value to largest. |
| 105 |
void ForEach(std::function<void(EnumType)> f) const { |
| 106 |
for (uint32_t i = 0; i < 64; ++i) { |
| 107 |
if (mask_ & AsMask(i)) f(static_cast<EnumType>(i)); |
| 108 |
} |
| 109 |
if (overflow_) { |
| 110 |
for (uint32_t c : *overflow_) f(static_cast<EnumType>(c)); |
| 111 |
} |
| 112 |
} |
| 113 |
|
| 114 |
// Returns true if the set is empty. |
| 115 |
bool IsEmpty() const { |
| 116 |
if (mask_) return false; |
| 117 |
if (overflow_ && !overflow_->empty()) return false; |
| 118 |
return true; |
| 119 |
} |
| 120 |
|
| 121 |
// Returns true if the set contains ANY of the elements of |in_set|, |
| 122 |
// or if |in_set| is empty. |
| 123 |
bool HasAnyOf(const EnumSet<EnumType>& in_set) const { |
| 124 |
if (in_set.IsEmpty()) return true; |
| 125 |
|
| 126 |
if (mask_ & in_set.mask_) return true; |
| 127 |
|
| 128 |
if (!overflow_ || !in_set.overflow_) return false; |
| 129 |
|
| 130 |
for (uint32_t item : *in_set.overflow_) { |
| 131 |
if (overflow_->find(item) != overflow_->end()) return true; |
| 132 |
} |
| 133 |
|
| 134 |
return false; |
| 135 |
} |
| 136 |
|
| 137 |
private: |
| 138 |
// Adds the given enum value (as a 32-bit word) to the set. This has no |
| 139 |
// effect if the enum value is already in the set. |
| 140 |
void AddWord(uint32_t word) { |
| 141 |
if (auto new_bits = AsMask(word)) { |
| 142 |
mask_ |= new_bits; |
| 143 |
} else { |
| 144 |
Overflow().insert(word); |
| 145 |
} |
| 146 |
} |
| 147 |
|
| 148 |
// Removes the given enum value (as a 32-bit word) from the set. This has no |
| 149 |
// effect if the enum value is not in the set. |
| 150 |
void RemoveWord(uint32_t word) { |
| 151 |
if (auto new_bits = AsMask(word)) { |
| 152 |
mask_ &= ~new_bits; |
| 153 |
} else { |
| 154 |
auto itr = Overflow().find(word); |
| 155 |
if (itr != Overflow().end()) Overflow().erase(itr); |
| 156 |
} |
| 157 |
} |
| 158 |
|
| 159 |
// Returns true if the enum represented as a 32-bit word is in the set. |
| 160 |
bool ContainsWord(uint32_t word) const { |
| 161 |
// We shouldn't call Overflow() since this is a const method. |
| 162 |
if (auto bits = AsMask(word)) { |
| 163 |
return (mask_ & bits) != 0; |
| 164 |
} else if (auto overflow = overflow_.get()) { |
| 165 |
return overflow->find(word) != overflow->end(); |
| 166 |
} |
| 167 |
// The word is large, but the set doesn't have large members, so |
| 168 |
// it doesn't have an overflow set. |
| 169 |
return false; |
| 170 |
} |
| 171 |
|
| 172 |
// Returns the enum value as a uint32_t. |
| 173 |
uint32_t ToWord(EnumType value) const { |
| 174 |
static_assert(sizeof(EnumType) <= sizeof(uint32_t), |
| 175 |
"EnumType must statically castable to uint32_t"); |
| 176 |
return static_cast<uint32_t>(value); |
| 177 |
} |
| 178 |
|
| 179 |
// Determines whether the given enum value can be represented |
| 180 |
// as a bit in a uint64_t mask. If so, then returns that mask bit. |
| 181 |
// Otherwise, returns 0. |
| 182 |
uint64_t AsMask(uint32_t word) const { |
| 183 |
if (word > 63) return 0; |
| 184 |
return uint64_t(1) << word; |
| 185 |
} |
| 186 |
|
| 187 |
// Ensures that overflow_set_ references a set. A new empty set is |
| 188 |
// allocated if one doesn't exist yet. Returns overflow_set_. |
| 189 |
OverflowSetType& Overflow() { |
| 190 |
if (overflow_.get() == nullptr) { |
| 191 |
overflow_ = MakeUnique<OverflowSetType>(); |
| 192 |
} |
| 193 |
return *overflow_; |
| 194 |
} |
| 195 |
|
| 196 |
// Enums with values up to 63 are stored as bits in this mask. |
| 197 |
uint64_t mask_ = 0; |
| 198 |
// Enums with values larger than 63 are stored in this set. |
| 199 |
// This set should normally be empty or very small. |
| 200 |
std::unique_ptr<OverflowSetType> overflow_ = {}; |
| 201 |
}; |
| 202 |
|
| 203 |
// A set of SpvCapability, optimized for small capability values. |
| 204 |
using CapabilitySet = EnumSet<SpvCapability>; |
| 205 |
|
| 206 |
} // namespace spvtools |
| 207 |
|
| 208 |
#endif // SOURCE_ENUM_SET_H_ |