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 LIBSPIRV_ENUM_SET_H 16 #define LIBSPIRV_ENUM_SET_H 17 18 #include <cstdint> 19 #include <functional> 20 #include <memory> 21 #include <set> 22 #include <utility> 23 24 #include "spirv/1.2/spirv.h" 25 26 namespace libspirv { 27 28 // A set of values of a 32-bit enum type. 29 // It is fast and compact for the common case, where enum values 30 // are at most 63. But it can represent enums with larger values, 31 // as may appear in extensions. 32 template <typename EnumType> 33 class EnumSet { 34 private: 35 // The ForEach method will call the functor on enum values in 36 // enum value order (lowest to highest). To make that easier, use 37 // an ordered set for the overflow values. 38 using OverflowSetType = std::set<uint32_t>; 39 40 public: 41 // Construct an empty set. EnumSet()42 EnumSet() {} 43 // Construct an set with just the given enum value. EnumSet(EnumType c)44 explicit EnumSet(EnumType c) { Add(c); } 45 // Construct an set from an initializer list of enum values. EnumSet(std::initializer_list<EnumType> cs)46 EnumSet(std::initializer_list<EnumType> cs) { 47 for (auto c : cs) Add(c); 48 } 49 // Copy constructor. EnumSet(const EnumSet & other)50 EnumSet(const EnumSet& other) { *this = other; } 51 // Move constructor. The moved-from set is emptied. EnumSet(EnumSet && other)52 EnumSet(EnumSet&& other) { 53 mask_ = other.mask_; 54 overflow_ = std::move(other.overflow_); 55 other.mask_ = 0; 56 other.overflow_.reset(nullptr); 57 } 58 // Assignment operator. 59 EnumSet& operator=(const EnumSet& other) { 60 if (&other != this) { 61 mask_ = other.mask_; 62 overflow_.reset(other.overflow_ ? new OverflowSetType(*other.overflow_) 63 : nullptr); 64 } 65 return *this; 66 } 67 68 // Adds the given enum value to the set. This has no effect if the 69 // enum value is already in the set. Add(EnumType c)70 void Add(EnumType c) { AddWord(ToWord(c)); } 71 72 // Returns true if this enum value is in the set. Contains(EnumType c)73 bool Contains(EnumType c) const { return ContainsWord(ToWord(c)); } 74 75 // Applies f to each enum in the set, in order from smallest enum 76 // value to largest. ForEach(std::function<void (EnumType)> f)77 void ForEach(std::function<void(EnumType)> f) const { 78 for (uint32_t i = 0; i < 64; ++i) { 79 if (mask_ & AsMask(i)) f(static_cast<EnumType>(i)); 80 } 81 if (overflow_) { 82 for (uint32_t c : *overflow_) f(static_cast<EnumType>(c)); 83 } 84 } 85 86 // Returns true if the set is empty. IsEmpty()87 bool IsEmpty() const { 88 if (mask_) return false; 89 if (overflow_ && !overflow_->empty()) return false; 90 return true; 91 } 92 93 // Returns true if the set contains ANY of the elements of |in_set|, 94 // or if |in_set| is empty. HasAnyOf(const EnumSet<EnumType> & in_set)95 bool HasAnyOf(const EnumSet<EnumType>& in_set) const { 96 if (in_set.IsEmpty()) return true; 97 98 if (mask_ & in_set.mask_) 99 return true; 100 101 if (!overflow_ || !in_set.overflow_) 102 return false; 103 104 for (uint32_t item : *in_set.overflow_) { 105 if (overflow_->find(item) != overflow_->end()) 106 return true; 107 } 108 109 return false; 110 } 111 112 private: 113 // Adds the given enum value (as a 32-bit word) to the set. This has no 114 // effect if the enum value is already in the set. AddWord(uint32_t word)115 void AddWord(uint32_t word) { 116 if (auto new_bits = AsMask(word)) { 117 mask_ |= new_bits; 118 } else { 119 Overflow().insert(word); 120 } 121 } 122 123 // Returns true if the enum represented as a 32-bit word is in the set. ContainsWord(uint32_t word)124 bool ContainsWord(uint32_t word) const { 125 // We shouldn't call Overflow() since this is a const method. 126 if (auto bits = AsMask(word)) { 127 return (mask_ & bits) != 0; 128 } else if (auto overflow = overflow_.get()) { 129 return overflow->find(word) != overflow->end(); 130 } 131 // The word is large, but the set doesn't have large members, so 132 // it doesn't have an overflow set. 133 return false; 134 } 135 136 // Returns the enum value as a uint32_t. ToWord(EnumType value)137 uint32_t ToWord(EnumType value) const { 138 static_assert(sizeof(EnumType) <= sizeof(uint32_t), 139 "EnumType must statically castable to uint32_t"); 140 return static_cast<uint32_t>(value); 141 } 142 143 // Determines whether the given enum value can be represented 144 // as a bit in a uint64_t mask. If so, then returns that mask bit. 145 // Otherwise, returns 0. AsMask(uint32_t word)146 uint64_t AsMask(uint32_t word) const { 147 if (word > 63) return 0; 148 return uint64_t(1) << word; 149 } 150 151 // Ensures that overflow_set_ references a set. A new empty set is 152 // allocated if one doesn't exist yet. Returns overflow_set_. Overflow()153 OverflowSetType& Overflow() { 154 if (overflow_.get() == nullptr) { 155 overflow_.reset(new OverflowSetType); 156 } 157 return *overflow_; 158 } 159 160 // Enums with values up to 63 are stored as bits in this mask. 161 uint64_t mask_ = 0; 162 // Enums with values larger than 63 are stored in this set. 163 // This set should normally be empty or very small. 164 std::unique_ptr<OverflowSetType> overflow_ = {}; 165 }; 166 167 // A set of SpvCapability, optimized for small capability values. 168 using CapabilitySet = EnumSet<SpvCapability>; 169 170 } // namespace libspirv 171 172 #endif // LIBSPIRV_ENUM_SET_H 173