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: 52 SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {} 53 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. 58 ~SmallSetIterator() { 59 if (isSmall) 60 VecIter.~VecIterTy(); 61 else 62 SetIter.~SetIterTy(); 63 } 64 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 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 size_type = size_t; 153 using const_iterator = SmallSetIterator<T, N, C>; 154 155 SmallSet() = default; 156 157 [[nodiscard]] bool empty() const { return Vector.empty() && Set.empty(); } 158 159 size_type size() const { 160 return isSmall() ? Vector.size() : Set.size(); 161 } 162 163 /// count - Return 1 if the element is in the set, 0 otherwise. 164 size_type count(const T &V) const { 165 if (isSmall()) { 166 // Since the collection is small, just do a linear search. 167 return vfind(V) == Vector.end() ? 0 : 1; 168 } else { 169 return Set.count(V); 170 } 171 } 172 173 /// insert - Insert an element into the set if it isn't already there. 174 /// Returns a pair. The first value of it is an iterator to the inserted 175 /// element or the existing element in the set. The second value is true 176 /// if the element is inserted (it was not in the set before). 177 std::pair<const_iterator, bool> insert(const T &V) { 178 if (!isSmall()) { 179 auto [I, Inserted] = Set.insert(V); 180 return std::make_pair(const_iterator(I), Inserted); 181 } 182 183 VIterator I = vfind(V); 184 if (I != Vector.end()) // Don't reinsert if it already exists. 185 return std::make_pair(const_iterator(I), false); 186 if (Vector.size() < N) { 187 Vector.push_back(V); 188 return std::make_pair(const_iterator(std::prev(Vector.end())), true); 189 } 190 191 // Otherwise, grow from vector to set. 192 while (!Vector.empty()) { 193 Set.insert(Vector.back()); 194 Vector.pop_back(); 195 } 196 return std::make_pair(const_iterator(Set.insert(V).first), true); 197 } 198 199 template <typename IterT> 200 void insert(IterT I, IterT E) { 201 for (; I != E; ++I) 202 insert(*I); 203 } 204 205 bool erase(const T &V) { 206 if (!isSmall()) 207 return Set.erase(V); 208 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 209 if (*I == V) { 210 Vector.erase(I); 211 return true; 212 } 213 return false; 214 } 215 216 void clear() { 217 Vector.clear(); 218 Set.clear(); 219 } 220 221 const_iterator begin() const { 222 if (isSmall()) 223 return {Vector.begin()}; 224 return {Set.begin()}; 225 } 226 227 const_iterator end() const { 228 if (isSmall()) 229 return {Vector.end()}; 230 return {Set.end()}; 231 } 232 233 /// Check if the SmallSet contains the given element. 234 bool contains(const T &V) const { 235 if (isSmall()) 236 return vfind(V) != Vector.end(); 237 return Set.find(V) != Set.end(); 238 } 239 240 private: 241 bool isSmall() const { return Set.empty(); } 242 243 VIterator vfind(const T &V) const { 244 for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 245 if (*I == V) 246 return I; 247 return Vector.end(); 248 } 249 }; 250 251 /// If this set is of pointer values, transparently switch over to using 252 /// SmallPtrSet for performance. 253 template <typename PointeeType, unsigned N> 254 class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; 255 256 /// Equality comparison for SmallSet. 257 /// 258 /// Iterates over elements of LHS confirming that each element is also a member 259 /// of RHS, and that RHS contains no additional values. 260 /// Equivalent to N calls to RHS.count. 261 /// For small-set mode amortized complexity is O(N^2) 262 /// For large-set mode amortized complexity is linear, worst case is O(N^2) (if 263 /// every hash collides). 264 template <typename T, unsigned LN, unsigned RN, typename C> 265 bool operator==(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) { 266 if (LHS.size() != RHS.size()) 267 return false; 268 269 // All elements in LHS must also be in RHS 270 return all_of(LHS, [&RHS](const T &E) { return RHS.count(E); }); 271 } 272 273 /// Inequality comparison for SmallSet. 274 /// 275 /// Equivalent to !(LHS == RHS). See operator== for performance notes. 276 template <typename T, unsigned LN, unsigned RN, typename C> 277 bool operator!=(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) { 278 return !(LHS == RHS); 279 } 280 281 } // end namespace llvm 282 283 #endif // LLVM_ADT_SMALLSET_H 284