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
27namespace 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.
33template <typename EnumType>
34class 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.
204using CapabilitySet = EnumSet<SpvCapability>;
205
206} // namespace spvtools
207
208#endif // SOURCE_ENUM_SET_H_
209