1 //===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This file defines the SmallSet class. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_SMALLSET_H 15 #define LLVM_ADT_SMALLSET_H 16 17 #include "llvm/ADT/SmallPtrSet.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/STLExtras.h" 20 #include "llvm/ADT/iterator.h" 21 #include "llvm/Support/Compiler.h" 22 #include "llvm/Support/type_traits.h" 23 #include <cstddef> 24 #include <functional> 25 #include <set> 26 #include <type_traits> 27 #include <utility> 28 29 namespace llvm { 30 31 /// SmallSetIterator - This class implements a const_iterator for SmallSet by 32 /// delegating to the underlying SmallVector or Set iterators. 33 template <typename T, unsigned N, typename C> 34 class SmallSetIterator 35 : public iterator_facade_base<SmallSetIterator<T, N, C>, 36 std::forward_iterator_tag, T> { 37 private: 38 using SetIterTy = typename std::set<T, C>::const_iterator; 39 using VecIterTy = typename SmallVector<T, N>::const_iterator; 40 using SelfTy = SmallSetIterator<T, N, C>; 41 42 /// Iterators to the parts of the SmallSet containing the data. They are set 43 /// depending on isSmall. 44 union { 45 SetIterTy SetIter; 46 VecIterTy VecIter; 47 }; 48 49 bool isSmall; 50 51 public: SmallSetIterator(SetIterTy SetIter)52 SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {} 53 SmallSetIterator(VecIterTy VecIter)54 SmallSetIterator(VecIterTy VecIter) : VecIter(VecIter), isSmall(true) {} 55 56 // Spell out destructor, copy/move constructor and assignment operators for 57 // MSVC STL, where set<T>::const_iterator is not trivially copy constructible. ~SmallSetIterator()58 ~SmallSetIterator() { 59 if (isSmall) 60 VecIter.~VecIterTy(); 61 else 62 SetIter.~SetIterTy(); 63 } 64 SmallSetIterator(const SmallSetIterator & Other)65 SmallSetIterator(const SmallSetIterator &Other) : isSmall(Other.isSmall) { 66 if (isSmall) 67 VecIter = Other.VecIter; 68 else 69 // Use placement new, to make sure SetIter is properly constructed, even 70 // if it is not trivially copy-able (e.g. in MSVC). 71 new (&SetIter) SetIterTy(Other.SetIter); 72 } 73 SmallSetIterator(SmallSetIterator && Other)74 SmallSetIterator(SmallSetIterator &&Other) : isSmall(Other.isSmall) { 75 if (isSmall) 76 VecIter = std::move(Other.VecIter); 77 else 78 // Use placement new, to make sure SetIter is properly constructed, even 79 // if it is not trivially copy-able (e.g. in MSVC). 80 new (&SetIter) SetIterTy(std::move(Other.SetIter)); 81 } 82 83 SmallSetIterator& operator=(const SmallSetIterator& Other) { 84 // Call destructor for SetIter, so it gets properly destroyed if it is 85 // not trivially destructible in case we are setting VecIter. 86 if (!isSmall) 87 SetIter.~SetIterTy(); 88 89 isSmall = Other.isSmall; 90 if (isSmall) 91 VecIter = Other.VecIter; 92 else 93 new (&SetIter) SetIterTy(Other.SetIter); 94 return *this; 95 } 96 97 SmallSetIterator& operator=(SmallSetIterator&& Other) { 98 // Call destructor for SetIter, so it gets properly destroyed if it is 99 // not trivially destructible in case we are setting VecIter. 100 if (!isSmall) 101 SetIter.~SetIterTy(); 102 103 isSmall = Other.isSmall; 104 if (isSmall) 105 VecIter = std::move(Other.VecIter); 106 else 107 new (&SetIter) SetIterTy(std::move(Other.SetIter)); 108 return *this; 109 } 110 111 bool operator==(const SmallSetIterator &RHS) const { 112 if (isSmall != RHS.isSmall) 113 return false; 114 if (isSmall) 115 return VecIter == RHS.VecIter; 116 return SetIter == RHS.SetIter; 117 } 118 119 SmallSetIterator &operator++() { // Preincrement 120 if (isSmall) 121 VecIter++; 122 else 123 SetIter++; 124 return *this; 125 } 126 127 const T &operator*() const { return isSmall ? *VecIter : *SetIter; } 128 }; 129 130 /// SmallSet - This maintains a set of unique values, optimizing for the case 131 /// when the set is small (less than N). In this case, the set can be 132 /// maintained with no mallocs. If the set gets large, we expand to using an 133 /// std::set to maintain reasonable lookup times. 134 template <typename T, unsigned N, typename C = std::less<T>> 135 class SmallSet { 136 /// Use a SmallVector to hold the elements here (even though it will never 137 /// reach its 'large' stage) to avoid calling the default ctors of elements 138 /// we will never use. 139 SmallVector<T, N> Vector; 140 std::set<T, C> Set; 141 142 using VIterator = typename SmallVector<T, N>::const_iterator; 143 using SIterator = typename std::set<T, C>::const_iterator; 144 using mutable_iterator = typename SmallVector<T, N>::iterator; 145 146 // In small mode SmallPtrSet uses linear search for the elements, so it is 147 // not a good idea to choose this value too high. You may consider using a 148 // DenseSet<> instead if you expect many elements in the set. 149 static_assert(N <= 32, "N should be small"); 150 151 public: 152 using key_type = T; 153 using size_type = size_t; 154 using value_type = T; 155 using const_iterator = SmallSetIterator<T, N, C>; 156 157 SmallSet() = default; 158 empty()159 [[nodiscard]] bool empty() const { return Vector.empty() && Set.empty(); } 160 size()161 size_type size() const { 162 return isSmall() ? Vector.size() : Set.size(); 163 } 164 165 /// count - Return 1 if the element is in the set, 0 otherwise. count(const T & V)166 size_type count(const T &V) const { 167 if (isSmall()) { 168 // Since the collection is small, just do a linear search. 169 return vfind(V) == Vector.end() ? 0 : 1; 170 } else { 171 return Set.count(V); 172 } 173 } 174 175 /// insert - Insert an element into the set if it isn't already there. 176 /// Returns a pair. The first value of it is an iterator to the inserted 177 /// element or the existing element in the set. The second value is true 178 /// if the element is inserted (it was not in the set before). insert(const T & V)179 std::pair<const_iterator, bool> insert(const T &V) { 180 if (!isSmall()) { 181 auto [I, Inserted] = Set.insert(V); 182 return std::make_pair(const_iterator(I), Inserted); 183 } 184 185 VIterator I = vfind(V); 186 if (I != Vector.end()) // Don't reinsert if it already exists. 187 return std::make_pair(const_iterator(I), false); 188 if (Vector.size() < N) { 189 Vector.push_back(V); 190 return std::make_pair(const_iterator(std::prev(Vector.end())), true); 191 } 192 193 // Otherwise, grow from vector to set. 194 while (!Vector.empty()) { 195 Set.insert(Vector.back()); 196 Vector.pop_back(); 197 } 198 return std::make_pair(const_iterator(Set.insert(V).first), true); 199 } 200 201 template <typename IterT> insert(IterT I,IterT E)202 void insert(IterT I, IterT E) { 203 for (; I != E; ++I) 204 insert(*I); 205 } 206 erase(const T & V)207 bool erase(const T &V) { 208 if (!isSmall()) 209 return Set.erase(V); 210 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 211 if (*I == V) { 212 Vector.erase(I); 213 return true; 214 } 215 return false; 216 } 217 clear()218 void clear() { 219 Vector.clear(); 220 Set.clear(); 221 } 222 begin()223 const_iterator begin() const { 224 if (isSmall()) 225 return {Vector.begin()}; 226 return {Set.begin()}; 227 } 228 end()229 const_iterator end() const { 230 if (isSmall()) 231 return {Vector.end()}; 232 return {Set.end()}; 233 } 234 235 /// Check if the SmallSet contains the given element. contains(const T & V)236 bool contains(const T &V) const { 237 if (isSmall()) 238 return vfind(V) != Vector.end(); 239 return Set.find(V) != Set.end(); 240 } 241 242 private: isSmall()243 bool isSmall() const { return Set.empty(); } 244 vfind(const T & V)245 VIterator vfind(const T &V) const { 246 for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 247 if (*I == V) 248 return I; 249 return Vector.end(); 250 } 251 }; 252 253 /// If this set is of pointer values, transparently switch over to using 254 /// SmallPtrSet for performance. 255 template <typename PointeeType, unsigned N> 256 class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; 257 258 /// Equality comparison for SmallSet. 259 /// 260 /// Iterates over elements of LHS confirming that each element is also a member 261 /// of RHS, and that RHS contains no additional values. 262 /// Equivalent to N calls to RHS.count. 263 /// For small-set mode amortized complexity is O(N^2) 264 /// For large-set mode amortized complexity is linear, worst case is O(N^2) (if 265 /// every hash collides). 266 template <typename T, unsigned LN, unsigned RN, typename C> 267 bool operator==(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) { 268 if (LHS.size() != RHS.size()) 269 return false; 270 271 // All elements in LHS must also be in RHS 272 return all_of(LHS, [&RHS](const T &E) { return RHS.count(E); }); 273 } 274 275 /// Inequality comparison for SmallSet. 276 /// 277 /// Equivalent to !(LHS == RHS). See operator== for performance notes. 278 template <typename T, unsigned LN, unsigned RN, typename C> 279 bool operator!=(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) { 280 return !(LHS == RHS); 281 } 282 283 } // end namespace llvm 284 285 #endif // LLVM_ADT_SMALLSET_H 286