1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef SYNC_INTERNAL_API_PUBLIC_BASE_ENUM_SET_H_ 6 #define SYNC_INTERNAL_API_PUBLIC_BASE_ENUM_SET_H_ 7 8 #include <bitset> 9 #include <cstddef> 10 #include <string> 11 12 #include "base/basictypes.h" 13 #include "base/logging.h" 14 15 namespace syncer { 16 17 // Forward declarations needed for friend declarations. 18 template <typename E, E MinEnumValue, E MaxEnumValue> 19 class EnumSet; 20 21 template <typename E, E Min, E Max> 22 EnumSet<E, Min, Max> Union(EnumSet<E, Min, Max> set1, 23 EnumSet<E, Min, Max> set2); 24 25 template <typename E, E Min, E Max> 26 EnumSet<E, Min, Max> Intersection(EnumSet<E, Min, Max> set1, 27 EnumSet<E, Min, Max> set2); 28 29 template <typename E, E Min, E Max> 30 EnumSet<E, Min, Max> Difference(EnumSet<E, Min, Max> set1, 31 EnumSet<E, Min, Max> set2); 32 33 // An EnumSet is a set that can hold enum values between a min and a 34 // max value (inclusive of both). It's essentially a wrapper around 35 // std::bitset<> with stronger type enforcement, more descriptive 36 // member function names, and an iterator interface. 37 // 38 // If you're working with enums with a small number of possible values 39 // (say, fewer than 64), you can efficiently pass around an EnumSet 40 // for that enum around by value. 41 42 template <typename E, E MinEnumValue, E MaxEnumValue> 43 class EnumSet { 44 public: 45 typedef E EnumType; 46 static const E kMinValue = MinEnumValue; 47 static const E kMaxValue = MaxEnumValue; 48 static const size_t kValueCount = kMaxValue - kMinValue + 1; 49 COMPILE_ASSERT(kMinValue < kMaxValue, 50 min_value_must_be_less_than_max_value); 51 52 private: 53 // Declaration needed by Iterator. 54 typedef std::bitset<kValueCount> EnumBitSet; 55 56 public: 57 // Iterator is a forward-only read-only iterator for EnumSet. Its 58 // interface is deliberately distinct from an STL iterator as its 59 // semantics are substantially different. 60 // 61 // Example usage: 62 // 63 // for (EnumSet<...>::Iterator it = enums.First(); it.Good(); it.Inc()) { 64 // Process(it.Get()); 65 // } 66 // 67 // The iterator must not be outlived by the set. In particular, the 68 // following is an error: 69 // 70 // EnumSet<...> SomeFn() { ... } 71 // 72 // /* ERROR */ 73 // for (EnumSet<...>::Iterator it = SomeFun().First(); ... 74 // 75 // Also, there are no guarantees as to what will happen if you 76 // modify an EnumSet while traversing it with an iterator. 77 class Iterator { 78 public: 79 // A default-constructed iterator can't do anything except check 80 // Good(). You need to call First() on an EnumSet to get a usable 81 // iterator. 82 Iterator() : enums_(NULL), i_(kValueCount) {} 83 ~Iterator() {} 84 85 // Copy constructor and assignment welcome. 86 87 // Returns true iff the iterator points to an EnumSet and it 88 // hasn't yet traversed the EnumSet entirely. 89 bool Good() const { 90 return enums_ && i_ < kValueCount && enums_->test(i_); 91 } 92 93 // Returns the value the iterator currently points to. Good() 94 // must hold. 95 E Get() const { 96 CHECK(Good()); 97 return FromIndex(i_); 98 } 99 100 // Moves the iterator to the next value in the EnumSet. Good() 101 // must hold. Takes linear time. 102 void Inc() { 103 CHECK(Good()); 104 i_ = FindNext(i_ + 1); 105 } 106 107 private: 108 friend Iterator EnumSet::First() const; 109 110 explicit Iterator(const EnumBitSet& enums) 111 : enums_(&enums), i_(FindNext(0)) {} 112 113 size_t FindNext(size_t i) { 114 while ((i < kValueCount) && !enums_->test(i)) { 115 ++i; 116 } 117 return i; 118 } 119 120 const EnumBitSet* enums_; 121 size_t i_; 122 }; 123 124 // You can construct an EnumSet with 0, 1, 2, or 3 initial values. 125 126 EnumSet() {} 127 128 explicit EnumSet(E value) { 129 Put(value); 130 } 131 132 EnumSet(E value1, E value2) { 133 Put(value1); 134 Put(value2); 135 } 136 137 EnumSet(E value1, E value2, E value3) { 138 Put(value1); 139 Put(value2); 140 Put(value3); 141 } 142 143 // Returns an EnumSet with all possible values. 144 static EnumSet All() { 145 EnumBitSet enums; 146 enums.set(); 147 return EnumSet(enums); 148 } 149 150 ~EnumSet() {} 151 152 // Copy constructor and assignment welcome. 153 154 // Set operations. Put, Retain, and Remove are basically 155 // self-mutating versions of Union, Intersection, and Difference 156 // (defined below). 157 158 // Adds the given value (which must be in range) to our set. 159 void Put(E value) { 160 enums_.set(ToIndex(value)); 161 } 162 163 // Adds all values in the given set to our set. 164 void PutAll(EnumSet other) { 165 enums_ |= other.enums_; 166 } 167 168 // There's no real need for a Retain(E) member function. 169 170 // Removes all values not in the given set from our set. 171 void RetainAll(EnumSet other) { 172 enums_ &= other.enums_; 173 } 174 175 // If the given value is in range, removes it from our set. 176 void Remove(E value) { 177 if (InRange(value)) { 178 enums_.reset(ToIndex(value)); 179 } 180 } 181 182 // Removes all values in the given set from our set. 183 void RemoveAll(EnumSet other) { 184 enums_ &= ~other.enums_; 185 } 186 187 // Removes all values from our set. 188 void Clear() { 189 enums_.reset(); 190 } 191 192 // Returns true iff the given value is in range and a member of our 193 // set. 194 bool Has(E value) const { 195 return InRange(value) && enums_.test(ToIndex(value)); 196 } 197 198 // Returns true iff the given set is a subset of our set. 199 bool HasAll(EnumSet other) const { 200 return (enums_ & other.enums_) == other.enums_; 201 } 202 203 // Returns true iff our set and the given set contain exactly the 204 // same values. 205 bool Equals(const EnumSet& other) const { 206 return enums_ == other.enums_; 207 } 208 209 // Returns true iff our set is empty. 210 bool Empty() const { 211 return !enums_.any(); 212 } 213 214 // Returns how many values our set has. 215 size_t Size() const { 216 return enums_.count(); 217 } 218 219 // Returns an iterator pointing to the first element (if any). 220 Iterator First() const { 221 return Iterator(enums_); 222 } 223 224 private: 225 friend EnumSet Union<E, MinEnumValue, MaxEnumValue>( 226 EnumSet set1, EnumSet set2); 227 friend EnumSet Intersection<E, MinEnumValue, MaxEnumValue>( 228 EnumSet set1, EnumSet set2); 229 friend EnumSet Difference<E, MinEnumValue, MaxEnumValue>( 230 EnumSet set1, EnumSet set2); 231 232 explicit EnumSet(EnumBitSet enums) : enums_(enums) {} 233 234 static bool InRange(E value) { 235 return (value >= MinEnumValue) && (value <= MaxEnumValue); 236 } 237 238 // Converts a value to/from an index into |enums_|. 239 240 static size_t ToIndex(E value) { 241 DCHECK_GE(value, MinEnumValue); 242 DCHECK_LE(value, MaxEnumValue); 243 return value - MinEnumValue; 244 } 245 246 static E FromIndex(size_t i) { 247 DCHECK_LT(i, kValueCount); 248 return static_cast<E>(MinEnumValue + i); 249 } 250 251 EnumBitSet enums_; 252 }; 253 254 template <typename E, E MinEnumValue, E MaxEnumValue> 255 const E EnumSet<E, MinEnumValue, MaxEnumValue>::kMinValue; 256 257 template <typename E, E MinEnumValue, E MaxEnumValue> 258 const E EnumSet<E, MinEnumValue, MaxEnumValue>::kMaxValue; 259 260 template <typename E, E MinEnumValue, E MaxEnumValue> 261 const size_t EnumSet<E, MinEnumValue, MaxEnumValue>::kValueCount; 262 263 // The usual set operations. 264 265 template <typename E, E Min, E Max> 266 EnumSet<E, Min, Max> Union(EnumSet<E, Min, Max> set1, 267 EnumSet<E, Min, Max> set2) { 268 return EnumSet<E, Min, Max>(set1.enums_ | set2.enums_); 269 } 270 271 template <typename E, E Min, E Max> 272 EnumSet<E, Min, Max> Intersection(EnumSet<E, Min, Max> set1, 273 EnumSet<E, Min, Max> set2) { 274 return EnumSet<E, Min, Max>(set1.enums_ & set2.enums_); 275 } 276 277 template <typename E, E Min, E Max> 278 EnumSet<E, Min, Max> Difference(EnumSet<E, Min, Max> set1, 279 EnumSet<E, Min, Max> set2) { 280 return EnumSet<E, Min, Max>(set1.enums_ & ~set2.enums_); 281 } 282 283 } // namespace syncer 284 285 #endif // SYNC_INTERNAL_API_PUBLIC_BASE_ENUM_SET_H_ 286